表2-63500S-Mb0C.X1X2X3X4X5XB[1]0100044X320001012X4-M32001618X50005+2MZ=-18M3+3Mc3101004Xi000210126X4001-M[2]-363X000Z=12-6M5+2M-3-3Mc表2-650830bCO-Mci+X1X2X3X4X5XB13100044X1[3]60001-12X45031-3/201/2X2009/20-5/2Z=27c1M231001/31/3X1020011/31/3X350101/206X2000-3/2-1M7*=36C.31
31
（二）单纯形法求解线性规划问题的几种特殊情况1．无可行解将上述问题的约束条件中加入松弛变量、例如，使用大M法求解如下剩余变量和人工变量线性规划问题：后得到：maxZ = 20x +30x2maxZ=20x,+30x2-Mx3x,+10x,≤1503x, +10x, +x,=150≤30X+x,=30st.s.t.x+x,≥40x + x2 -x +x = 40,x≥0[, ≥0, j-1,2...,6（二）单纯形法求解线性规划问题的几种特殊情况一无可行解在第二次迭代时出现了如表2-7所示的情况表2-7C0C203000MbX4XX2XX6XsXS3001/10-3/100061Xi001030201000-1/10-7/10-14X1MM7MZ=780--3C,1100-M10104M32
32
（二）单纯形法求解线性规划问题的几种特殊情况一无可行解·表2-7最优解的值中x=4≠0，其最大的目标函数值是一个负无穷大的值。把最优解的值代入到约束方程，会发现第三个约束方程X+x2-36<40，这与约束条件x+x,≥40相矛盾，由此可知该线性规划问题无可行解。·结论：在用大M法求解线性规划问题时，如果在最优解中人工变量不为零，则此线性规划问题无可行解。（二）单纯形法求解线性规划问题的几种特殊情况一无界解例如：使用单纯形法求解下列线解：在引入松弛变量X3，X4性规划问题：max Z = x +x2max Z=x +x2[x -x2 +x, =1x -x, ≤1st3-3x +2x2 +x4 =6s1.3-3x +2x, ≤6[X1,X2,X3,X,≥0[, ≥033
33
（二）单纯形法求解线性规划问题的几种特殊情况一无界解在单纯形表的第1次迭代后，遇到如表2-8情况1100C:Sbxix2X3X4XBxi1-10111900-131X402-10Z-1C（二）单纯形法求解线性规划问题的几种特殊情况一无界解此时由检验数我们可以判断x2入基，但是2的系数列中不存在大于零的系数，这样就无法确定出基变量。现在我们来看一下此时问题的约束方程和解。[n-x, +x =1[-x2 +3x, +x, =9移项后可得(x =1+x, -x3[x =9+x -3x34
34
（二）单纯形法求解线性规划问题的几种特殊情况一无界解此时X2入基即X2从一个零值增加到一个更大的值故不妨设x=M可得如下的一组解：X=(M+1M0M+9)目标函数值为：Z=2M+1由于M是一个任意大的正数，这时的目标函数会趋向于无穷大，即此线性规划问题无有限最优解。结论：在单纯形表的某次迭代中，如果入基变量的系数向量的每个元素都小于或等于零，说明所有约束条件对进基变量的增加都无约束作用，因此目标函数可以无限地增加，此线性规划问题有无界解。（二）单纯形法求解线性规划问题的几种特殊情况一多重最优解例如，用单纯形法求解如下线性规划问题：maxZ=50x,+50x2x +x≤3002x, +x, ≤400st.sX,≤250[,x≥035
35