线性规划单纯形法小结课件

线线 性性 规规 划划(Linear Programming)单纯形法小结单纯形法小结 一、无穷多最优解一、无穷多最优解例例1、用单纯形法表求解下面的线性规划问题。、用单纯形法表求解下面的线性规划问题。几种特殊情况 解：用单纯形表来求解。解：用单纯形表来求解。填入单纯形表计算得：填入单纯形表计算得：迭迭代代次次数数基变基变量量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 0 15015025050/1150/2j50 0 0 0 0125002x1s2x2500501 0 1 0 -10 0 -2 1 10 1 0 0 1505025050/1250/1j0 0 -50 0 015000 非基变量非基变量s3的检验数等于零，这样我们可以断定此线性规划问题有无穷多的检验数等于零，这样我们可以断定此线性规划问题有无穷多最优解。求得另一个基本可行解，如下表所示：最优解。求得另一个基本可行解，如下表所示：迭代迭代次数次数基基变变量量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，0）t，Z2=（100，200，0，0，50）t，则无穷多最优解可表示为，则无穷多最优解可表示为Z1+（1-）Z2，其中，其中01。二、无界解二、无界解 例例2 2、用单纯形表求解下面线性、用单纯形表求解下面线性规划问题。规划问题。几种特殊情况几种特殊情况 迭迭代代次次数数基基变变量量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填入单纯形表计算得：填入单纯形表计算得：解：在上述问题的约束条件中加入松驰变量，得标准型如下：解：在上述问题的约束条件中加入松驰变量，得标准型如下：三、无可行解三、无可行解 例例3、用单纯形表求解下列线性规划问题、用单纯形表求解下列线性规划问题解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：填入单纯形表计算得：填入单纯形表计算得：几种特殊情况迭迭代代次次数数基变基变量量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/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=-xj不不处处理理约束约束条件条件两端两端同乘同乘以以-1加加松松弛弛变变量量xs加加入入人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=-ZminZ=max z0-M标准化后列出初始单纯形表标准化后列出初始单纯形表 A线性规划问题单纯型方法求解的第一步是标准化线性规划问题单纯型方法求解的第一步是标准化A 四、退化问题四、退化问题 如果一个基本可行解的基变量中至少有一个为如果一个基本可行解的基变量中至少有一个为0，则称此基本可行解，则称此基本可行解为退化的基本可行解。为退化的基本可行解。例例4.用单纯形表，求解下列线性规划问题。用单纯形表，求解下列线性规划问题。几种特殊情况几种特殊情况解：加上松驰变量解：加上松驰变量s1,s2,s3化为标准形式，填入单纯形表计算：化为标准形式，填入单纯形表计算：迭迭代代次次数数基基变变量量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 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次迭代中次迭代中出现了退化，基变量出现了退化，基变量s2=0。又由于在第。又由于在第1次迭代出现次迭代出现了退化，导致第了退化，导致第2次迭代所取得的次迭代所取得的目标函数值目标函数值并没有并没有得到改善，仍然与第得到改善，仍然与第1次迭代的一样都等于次迭代的一样都等于4。像这。像这样继续迭代而得不到目标函数的改善，当然样继续迭代而得不到目标函数的改善，当然减低了减低了单纯形算法的效率单纯形算法的效率，但一般来说还是可以得到最优，但一般来说还是可以得到最优解的。当本题继续计算下去最后得到了最优解（解的。当本题继续计算下去最后得到了最优解（1，0，2，1，0，0）T，其最优值为，其最优值为5。但有些特殊情况下当出现退化时，即使存在最优但有些特殊情况下当出现退化时，即使存在最优解，而迭代过程总是重复解的某一部分迭代过程，解，而迭代过程总是重复解的某一部分迭代过程，出现了计算过程的循环，目标函数值总是不变，永出现了计算过程的循环，目标函数值总是不变，永远达不到最优解远达不到最优解 为了避免这种现象，我们介绍勃兰特法则。为了避免这种现象，我们介绍勃兰特法则。首先我们把松弛变量（剩余变量）、人工变量首先我们把松弛变量（剩余变量）、人工变量都用都用x xj j表示，一般松弛变量（剩余变量）的下标号列表示，一般松弛变量（剩余变量）的下标号列在决策变量之后，人工变量的下标号列在松弛变量在决策变量之后，人工变量的下标号列在松弛变量（剩余变量）之后，在计算中，遵守以下两个规则：（剩余变量）之后，在计算中，遵守以下两个规则：（1 1）在所有检验数大于零的非基变量中，选一个下）在所有检验数大于零的非基变量中，选一个下标最小的作为进基变量。标最小的作为进基变量。（2 2）在存在两个和两个以上最小比值时，选一个下）在存在两个和两个以上最小比值时，选一个下标最小的基变量为出基变量。标最小的基变量为出基变量。这样就一定能避免出现循环。这样就一定能避免出现循环。