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

线 性 规 划(Linear Programming)单纯形法小结一、无穷多最优解例 1、用单纯形法表求解下面的线性规划问题。几种特殊情况解：用单纯形表来求解。填入单纯形表计算得：迭代次数基 变量CB x1 x2 s1 s2 s3 b 比 值50 50 0 0 00s1s2s30001 1 1 0 02 1 0 1 00 1 0 0 1300400250300/1400/1250/1j 50 50 0 0 001s1s2x200501 0 1 0 -12 0 0 1 -10 1 0 01150/2j 50 0 0 0 0125002x1s2x2500501 0 1 0 -10 0 -2 1 10 1 0 0 1505025050/1250/1j 0 0 -50 0 015000非基变量 s3的检验数等于零，这样我们可以断定此线性规划问题有无穷多最优解。求得另一个基本可行解，如下表所示：迭代次数基变量CB x1 x2 s1 s2 s3 b50 50 0 0 03x1s3x2500501 0 -1 1 00 0 -2 1 10 1 2 -1 010050200j 0 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、用单纯形表求解下面线性规划问题。几种特殊情况迭代次数基变量CB x1 x2 s1 s2 b 比值1 1 0 00s1s2001 -1 1 0-3 2 0 1161j1 1 0 01x1s2101 -1 1 0 0 -1 3 119j0 2 -1 0填入单纯形表计算得：解：在上述问题的约束条件中加入松驰变量，得标准型如下：三、无可行解例 3、用单纯形表求解下列线性规划问题解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到： 填入单纯形表计算得：几种特殊情况迭代次数基 变量CB x1 x2 s1 s2 s3 a1 b 比 值20 30 0 0 0 -M0s1s2a100-M3 10 1 0 0 01 0 0 1 0 01 1 0 0 -1 11503040150/1040/1j 20+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)j 11+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 6304j 0 0 -3-M/10 -11-7M/10 -M 0780-4M只要最优解有人工变量大于零，则原线性规划无可行解。有初始可行基的情况下：唯一最优解、无穷多最优解、无界解；无初始可行基的情况下会怎样？决策变量 右端常数项 约束方程是等式或不等式目标函数是极大或极小新加变量价值系数xj0 xj无约束xj 0 bi 0 bi 0 = maxZ minZ xs xa不处理令 xj = xj - xj xj 0xj 0令 xj =- xj不处理约束条件两端同乘以 -1加松弛变量xs加入人工变量xa减去xs加入xa不处理令z=- ZminZ=max z0 -M标准化后列出初始单纯形表 A线性规划问题单纯型方法求解的第一步是标准化A四、退化问题如果一个基本可行解的基变量中至少有一个为 0，则称此基本可行解为退化的基本可行解。例 4.用单纯形表，求解下列线性规划问题。几种特殊情况几种特殊情况解：加上松驰变量 s1,s2,s3化为标准形式，填入单纯形表计算：迭代次数基变量CB x1 x2 x3 s1 s2 s3 b 比 值2 0 3/2 0 0 00s1s2s30001 -1 0 1 0 02 0 1 0 1 01 1 1 0 0 12432/14/23/1j 2 0 3/2 0 0 0Z=01x1s2s32001 -1 0 1 0 0 0 2 1 -2 1 00 2 1 -1 0 12010/21/2j 0 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)j 0 0 1/2 0 -1 0Z=4迭代次数基变量CB x1 x2 x3 s1 s2 s3 b 比 值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/1j 0 -1 0 1 -3/2 0Z=44x1x3s123/201 -1 0 0 1 -10 2 1 0 -1 20 0 0 1 -1 1 221j 0 -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。但有些特殊情况下当出现退化时，即使存在最优解，而迭代过程总是重复解的某一部分迭代过程，出现了计算过程的循环，目标函数值总是不变，永远达不到最优解为了避免这种现象，我们介绍勃兰特法则。 首先我们把松弛变量（剩余变量）、人工变量都用 xj表示，一般松弛变量（剩余变量）的下标号列在