第1章4线性规划单纯形法小结ppt课件

1、线线 性性 规规 划划(Linear Programming)单纯形法小结单纯形法小结 一、无穷多最优解一、无穷多最优解例例1、用单纯形法表求解下面的线性规划问题。、用单纯形法表求解下面的线性规划问题。121212212max5050300,2400,250,0.zxxxxxxxxx目标函数约束条件几种特殊情况 解：用单纯形表来求解。解：用单纯形表来求解。123121211222312123,m ax5050300,2400,250,0.ssszxxxxsxxsxsxxsss加 入 松 弛 变 量， 我 们 得 到 标 准 形 ：目 标 函 数约 束 条 件填入单纯形表计算得：填入单纯形表计算

2、得：迭迭代代次次数数基变基变量量CBx1 x2 s1 s2 s3b比值比值50 50 0 0 00s1s2s30001 1 1 0 02 1 0 1 00 1 0 0 1300400250300/1400/1250/1j50 50 0 0 001s1s2x200501 0 1 0 -12 0 0 1 -10 1 0 01150/2j50 0 0 0 0125002x1s2x2500501 0 1 0 -10 0 -2 1 10 1 0 0 1505025050/1250/1j0 0 -50 0 015000 非基变量非基变量s3的检验数等于零，这样我们可以断定此线性规

3、划问题有无穷多的检验数等于零，这样我们可以断定此线性规划问题有无穷多最优解。求得另一个基本可行解，如下表所示：最优解。求得另一个基本可行解，如下表所示：迭代迭代次数次数基基变变量量CBx1 x2 s1 s2 s3b50 50 0 0 03x1s3x2500501 0 -1 1 00 0 -2 1 10 1 2 -1 010050200j0 0 -50 0 015000不妨用向量不妨用向量Z1，Z2表示上述两个最优解即表示上述两个最优解即Z1 =（50，250，0，50，0t， Z2 =（100，200，0，0，50t，则无穷多最优解可表示为，则无穷多最优解可表示为Z1+（1- ）Z2，其中，其

4、中01。 二、无界解二、无界解 例例2 2、用单纯形表求解下面线性、用单纯形表求解下面线性规划问题。规划问题。 12121212max1,326,0.zxxxxxxxx目标函数约束条件几种特殊情况几种特殊情况 迭迭代代次次数数基基变变量量CBx1 x2 s1 s2b比比值值1 1 0 00s1s2001 -1 1 0-3 2 0 1161j 1 1 0 01x1s2101 -1 1 0 0 -1 3 119j 0 2 -1 0填入单纯形表计算得：填入单纯形表计算得：解：在上述问题的约束条件中加入松驰变量，得标准型如下：解：在上述问题的约束条件中加入松驰变量，得标准型如下：12121122121

5、2max1,326,0.zxxxxsxxsxxss目 标 函 数约 束 条 件 .0,40,30,1501033020max212112121xxxxxxxxxz约束条件目标函数三、无可行解三、无可行解 例例3、用单纯形表求解下列线性规划问题、用单纯形表求解下列线性规划问题解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到： 121121121231121231max2030310150,30,40,0.zxxMaxxsxsxxsaxxsssa目 标 函 数约 束 条 件 填入单纯形表计算得：填入单纯形表计算得：几种特

6、殊情况迭迭代代次次数数基变基变量量CBx1 x2 s1 s2 s3 a1b比值比值20 30 0 0 0 -M0s1s2a100-M3 10 1 0 0 01 0 0 1 0 01 1 0 0 -1 11503040150/1040/1j20+M 30+M 0 0 -M 01x2s2a1300-M3/10 1 1/10 0 0 0 1 0 0 1 0 07/10 0 -1/10 0 -1 115302515/(3/10)30/125/(7/10)j11+7/10M 0 -3-M/10 0 -M 0 2x2x1a13020-M0 1 1/10 -3/10 0 01 0 0 1 0 00 0 -1

7、/10 -7/10 -1 1 6304j0 0 -3-M/10 -11-7M/10 -M 0780-4M只要最优解有人工变量大于零，则原线性规划无可行解。只要最优解有人工变量大于零，则原线性规划无可行解。 有初始可行基的情况下：唯一最优解、无穷多最优解、无界解； 无初始可行基的情况下会怎样？决策变量决策变量右端常数项右端常数项约束方程约束方程是等式或是等式或不等式不等式目标函数是极大目标函数是极大或极小或极小新加变新加变量价值量价值系数系数xj0 xj无无约束约束xj 0 bi 0bi 0=maxZminZxs xa不不处处理理令令xj = xj - xj xj 0 xj 0令令 xj =-

8、xj不不处处理理约束约束条件条件两端两端同乘同乘以以-1加加松松弛弛变变量量xs加加入入人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=- ZminZ=max z0-M标准化后列出初始单纯形表标准化后列出初始单纯形表 A线性规划问题单纯型方法求解的第一步是标准化线性规划问题单纯型方法求解的第一步是标准化停止停止Aj:求0 j所所有有kj即找出max)0(0 ika)0( lklkiiaab 计计算算lkxx替换基变量用非基变量到新单纯形表初等行变换得0是否为人工变量ax?0 j非基变量的有某个最最优优解解一一唯唯 无无可可行行解解最优解无穷多是是否否环环循循是否否否否否是是是是

9、循环循环无无界界解解 四、退化问题四、退化问题 如果一个基本可行解的基变量中至少有一个为如果一个基本可行解的基变量中至少有一个为0，则称此，则称此基本可行解为退化的基本可行解。基本可行解为退化的基本可行解。例例4.用单纯形表，求解下列线性规划问题。用单纯形表，求解下列线性规划问题。1312131231233max222,24,3,0.zxxxxxxxxxxxx目 标 函 数约 束 条 件几种特殊情况几种特殊情况解：加上松驰变量解：加上松驰变量s1,s2,s3化为标准形式，填入单纯形表计算：化为标准形式，填入单纯形表计算：0,342 2 232 max 321321332122112121sss

10、xxxsxxxsxxsxxxxZ迭迭代代次次数数基基变变量量CBx1 x2 x3 s1 s2 s3b比值比值2 0 3/2 0 0 00s1s2s30001 -1 0 1 0 02 0 1 0 1 01 1 1 0 0 12432/14/23/1j2 0 3/2 0 0 0Z=01x1s2s32001 -1 0 1 0 0 0 2 1 -2 1 00 2 1 -1 0 12010/21/2j0 2 3/2 -2 0 0Z=42x1x2s32001 0 1/2 0 1/2 00 1 1/2 - 1 1/2 00 0 0 1 -1 1 2012/(1/2)0/(1/2)j0 0 1/2 0 -1

11、0Z=4迭迭代代次次数数基基变变量量CBx1 x2 x3 s1 s2 s3b比值比值2 0 3/2 0 0 03x1x3s323/201 -1 0 1 0 00 2 1 - 2 1 00 0 0 1 -1 1 2012/11/1j0 -1 0 1 -3/2 0Z=44x1x3s123/201 -1 0 0 1 -10 2 1 0 -1 20 0 0 1 -1 1 221j0 -1 0 0 -1/2 -1Z=5 在以上的计算中可以看出在在以上的计算中可以看出在0次迭代中，由于比值次迭代中，由于比值b1/a11=b2/a21=2为最小比值，导致在第为最小比值，导致在第1次迭代中出现了退化，基变量次

12、迭代中出现了退化，基变量s2=0。又由于在第。又由于在第1次迭代出现了退化，导致第次迭代出现了退化，导致第2次迭代所取得的目标函数值并没有得到改善，次迭代所取得的目标函数值并没有得到改善，仍然与第仍然与第1次迭代的一样都等于次迭代的一样都等于4。像这样继续迭代而得不到目标函数的改。像这样继续迭代而得不到目标函数的改善，当然减低了单纯形算法的效率，但一般来说还是可以得到最优解的。善，当然减低了单纯形算法的效率，但一般来说还是可以得到最优解的。当本题继续计算下去最后得到了最优解当本题继续计算下去最后得到了最优解1，0，2，1，0，0T，其最优，其最优值为值为5。 但有些特殊情况下当出现退化时，即使存在最优解，而但有些特殊情况下当出现退化时，即使存在最优解，而迭代过程总是重复解的某一部分迭代过程，出现了计算过程迭代过程总是重复解的某一部分迭代过程，出现了计算过程的循环，目标函数值总是不变，永远达不到最优解的循环，目标函数值总是不变，永远达不到最优解 为了避免这种现象，我们介绍勃兰特法则。为了避免这种现象，我们介绍勃兰特法则。 首先我们把松弛变量剩余变量）、人工变量都用首先我们把松弛变量剩余变量）、人工变量都用xj表示，表示，一般松弛变量剩余变量的下标号列在决策变量之后，人一般松弛变量剩余变量的下标号列在决策变量之后，人工变量的下标号列在松弛变量剩余变量之后，在计算中