用单纯形方法解线性规划问题

§12.1线性规划问题的标准型§12.2单纯形解的基本概念§12.3单纯形方法引例§12.4单纯形方法返回第十二章线性规划问题的单纯形法图解法对于两个变量的线性规划问题，是一个简单易行、形象直观的求解方法，但是当决策变量多于两个时，图解法就失效了．因此有必要研究线性规划问题更一般的解法，这种方法就是单纯形法．本章我们首先介绍线性规划问题的标准型，然后介绍有关单纯形法的重要概念，最后对单纯形法进行讨论．§12.1线性规划问题的标准型一、线性规划模型的标准型线性规划模型的标准型规定如下：nnxcxcxcS2211mins.t.njxxxbxaxaxabxaxaxabxaxaxanmnmnmmnnnn,,2,1,0,,,2122112222212111212111),,2,1(,0mibi其中其紧缩形式为：njjjxcS1min),,2,1(0),,2,1(..1njxmibxatsjnjijij),,2,1(,0mibi其中其矩阵形式为：CXSminOXbAXts..TnnxxxXcccC),,,(;),,,(2121mnmmnnaaaaaaaaaA212222111211mbbbb21000O其中),,2,1(),,,(21njaaaPTmjjjj若令njjjnnxPxxxPPPA12121),,,(则于是CXSminOXbxPtsnjjj1..线性规划问题的标准型具有如下特点：（1）目标函数为最小：CXSmin（2）决策变量为非负：OX（3）约束条件为等式：bAX（4）约束常数为非负：0b二、线性规划问题的标准化1．目标函数最小化2．决策变量非负化3．约束条件等式化4．约束常数非负化即目标函数统一为最小；决策变量统一为非负；约束条件统一为等式；约束常数统一为非负．如果给出的问题中，目标函数是最大化的类型，则可令S′=-S，这样就将目标函数即最小化．在求出S′的值以后，乘以（-1）就是原问题的最大值．如果某个变量没有非负限制，即xj≤0或xj符号不限．对于xj≤0，可令xj′=-xj，xj′≥0；若符号不限，则可令xj=xj′-xj″,其中xj′≥0,xj″≥0，当约束条件为“≤”式时，可在不等号的左边加上一个非负的变量，一般称为松弛变量，使不等式成为等式．当约束条件为“≥”式时，可在不等号的左边减去一个非负的变量，一般称为剩余变量，使不等式成为等式．若某个约束方程的右端常数为负数时，则可在这个约束等式两端同乘以（-1），从而使得右端常数为非负．例12.1.1将下面的线性规划问题化为标准型没有非负限制231321321321321,0,6423723..23maxxxxxxxxxxxxxtsxxxS解（1）令S=S′，则32123maxminxxxSS（2）由于x2没有非负限制，因此可令222xxx其中,02x02x（3）引入剩余变量04x松弛变量05x可将第一、二个约束条件化为等式，即3)(43221xxxxx7)(253221xxxxx（4）以（-1）乘以第三个约束方程两边，使其右端常数非负．于是，可得上述线性规划模型的标准型543221002)(3minxxxxxxS0,,,,,64)(237)(23)(..54322132214322153221xxxxxxxxxxxxxxxxxxxxts注1：所求的SSminmax由于引入的剩余变量在经济问题中表示应付需求的剩余，而松弛变量表示没有被利用的闲置资源，它们都不会产生利润，所以在目标函数中，其系数必为零．注2：§12.2单纯形解的基本概念对于一个线性规划问题CXSminOXbAXts..其约束矩阵为),,,(21212222111211nmnmmnnPPPaaaaaaaaaA一、基、基变量和非基变量设约束方程系数矩阵A的前m个列向量线性无关则有mnmmmmmmnmmnmmaaaaaaaaaaaaaaaA1212122222111111211=（P1P2…Pm|Pm+1…Pn）=（B|N）一般总是假r(A)=mn．因为只有mn时，约束方程组才有无穷多解，才谈得上是优化问题．称B为线性规划问题的一个基阵，简称0B其中为基，并称构成基阵的列向量),,2,1(mjPj为基向量，其余的列向量Pm+1，Pm+2，…，Pn称为非基jP相对应的),,2,1(mjxj称为关于基B的基变量，除此均称为关于基B的非基变量.向量；与基向量二、基本解、基本可行解和最优基本可行解对变量X也做相应的分块，即TnmmxxxxxX),,,,,,(121NBXX其中，XB表示关于基B的基变量，XN表示关于基B的非基变量．bXXNBNB)(即bNXBXNB因为0B所以存在B-1，用B-1左乘上式后得NBNXBbBX11可知，每给非基变量XN一组值，就能得到基变量XB的一组相应的值，从而得线性规划问题的一个解．TNBXXX)(特别当OXN时，得这样，约束方程组AX=b可以改写为TTNBObBXXX)()(1称之为线性规划问题的一个基本解．如果在基本解中ObBXB1则称X为线性规划问题的一个基本可行解，相应的基B称为线性规划问题的一个可行基．使目标函数达到最优的基本可行解，称为最优基本可行解，相应的基称为最优基．三、基本可行解的性质（1）线性规划问题如果有可行解，则必有基本可行解．（2）线性规划问题的可行域中，点X是顶点的充要条件是：X为基本可行解．（3）线性规划问题如有最优解，其最优解必可在它的基本可行解中找到．§12.3单纯形方法引例例1某厂用A、B两种原料生产甲、乙两种产品，已知一吨产品分别需要各种原料的数量、可得利润及工厂现存原料的数量如下表所示．甲乙现有原料A1328B4142利润（千元/吨）75试问甲、乙产品各生产多少，可获得最大利润？解设甲、乙产品分别生产,1x2x吨，则0,424282..57max21212121xxxxxxtsxxS引入松弛变量,3x4x将模型化为标准型：)4,3,2,1(,0424282..57min42132121jxxxxxxxtsxxSj显然，),(430PPB是一个现成的初始可行基，对应的基变量和非基变量分别为TBxxX),(430TNxxX),(210令非基变量0),(210TNxxX可得0)42,28,0,0()0(TX它是对应基B0的一个基本可行解，此时的目标函数值为零，这表明甲、乙产品都没有安排生产，各种资源都没有动用。解,因而也不是最优基．目标函数值便会减少，所以，从目标函数2157xxS中可以看出，只要0jx)0(X不是最优0B于是就需要“换基”．怎样换基？即让哪个非基变量“进基”呢？原则上讲，应该先让使目标函数减少得多的那个非基变量进基．的，的系数大2157xxSS由于利润函数中，1x2x因此选x1进基．于因为该问题的约束系数矩阵的秩r(A)=2，因此在x1进基的同时，原基变量必须有一个被换出基，那么又让谁“出基”呢？换基后必须保证新基仍然是可行基．因为当x1进基后，x2仍是新基B1的非基变量，所以在新基B1中仍取x2=0．并保持x3，x4的非负性，即04420281413xxxx因此，x1必须满足442}442,128min{01x为使x3，x4中有一个“出基”,x1的取值还必须能使x3，x4中有一个为零，注意到当x1=42/4时，x4=0，于是便确定x4出基．从而得到新基4011),(131PPB对应基B1的基本可行解为TX)0,235,0,221()1(相应的目标函数值为2147)()1(XS是不是最优解呢？但是)1(X我们将约束方程组变形为44722544221423421xxxxxx代入原目标函数，得42474132147xxS从此式可看出，)1(X仍不是最优解，还需继续换基．把上述换基程序归纳如下：（1）确定“进基”（换入）变量．需将目标函数改写为方程式05721xxS按“最大正系数原则”确定“进基”变量．（2）确定“出基”（换出）变量．即用约束常数项分别除以确定换入的新基变量所在列的正系数（负数或零除外），按“最小比值原则”确定“出基”变量．（3）确定了“进基”和“出基”变量之后的换基迭代过程．实际上是通过加减消元或代入消元，使新基变量所在的列成为初始单位列向量．这样，例1可通过以下方式求解：首先从标准型中选定一个初始可行基1001),(430PPB将目标函数表达式改写为与之等价的方程式，即000574321xxxxS于是标准型可视为如下线性方程组0005742042802432143214321xxxxSxxxxxxxx对其增广矩阵)(0BT按上述原则施以行初等变换00057142101402801210)(0BT21474704130122141041102354114700原问题的最优解为TX)10,8(最优值为106minS即当甲、乙产品分别生产8吨和10吨时，该厂可获得最大利润106千元．1067971300187271010107174100§12.4单纯形方法一、单纯形法和单纯形表单纯形方法是表格化的换基迭代法，因此，用单纯形方法解线性规划问题，需要将增广矩阵换基迭代法的过程用表格形式表示出来，这样的表格称为单纯形表。单纯形表的一般格式如下表所示．P决策变量（包括松弛变量等）B基变量约束方程系数约束常数S非基化目标（函数）方程系数把上节例1中的问题标准化后，即)4,3,2,1(,0424282..57min42132121jxxxxxxxtsxxSj按照上述表格所示填入各栏，得1x2x3x4xPb121028[4]10142S753x4x该表称为线性规划问题的初始单纯形表4x3x1x2x，显然，对应的基阵是初始可行基，相应的基变量是，．需要注意的是，此时目标函数方程中基变量的系数为零，即目标函数中仅含非基变量和．),(430PPB3x4x2157xxS1x2x称其为非基化的目标函数.由上一节的讨论知道，非基化了的目标函数可用来判断解的优劣．因此，目标函数系数所在的行称为检验行，各系数称为检验数，用（j=1，2，…，n）表示．j对应于基的单纯形表取非基变量，),(430PPB得基本可行解,相应的目标函数值为021xxTX)42,28,0,0()0(0S因为在检验行中有正检验数，表明该基本可行解不是最优解．按照“最大正系数原则”确定“进基”变量．确定换入新基的方法，就是在表上检验行中找到最大的正检验数7，在数7旁标上“”，表示箭头所指的变量就是换入的新基变量，注：如果有两个最大的正检验数相等，就取下标小的，即此时按照“最小下标原则”选取．再按照“最小比值原则”确定“出基”变量．确定换出的基变量的方法，就是在表中用约束常数列分别除以换入新基变量（“”）所在列的正系数（负数和零除外），选出最小比