1、1.4 单纯形算法的进一步讨论(一 )、大 M法(二 )、两阶段法初始基本可行解的求法解 : 令 S= - S加入松弛变量 x4,剩余变量 x5x1 -2x2 + x3 +x4 =11-4x1 + x2 + 2x3 -x5 =3-2x1 +x3 =1 x1 , x2 , ,x5 , 0max S= 3x1 - x2 -x3例 1.11求解 L.P.的最优解 :x1 -2x2 + x3 11s.t . -4x1 + x2 + 2x3 3-2x1 +x3= 1 x1 , x2 , x3 0minZ= -3x1 + x2 + x3+x6+x7,x6 ,x7-M x6-M x7再加入 人工变量 x6
2、,x7(一 )、大 M法 例x4 11 1 -2 1 1 0 0 0x6 3 -4 1 2 0 -1 1 0x7 1 -2 0 1 0 0 0 1表 1.16 3-6M M-1 3M-1 0 -M 0 0表 1.15 3 -1 -1 0 0 -M -MXB b* x1 x2 x3 x4 x5 x6 x7x4 11 1 -2 1 1 0 0 0x6 3 -4 1 2 0 -1 1 0x7 1 -2 0 1 0 0 0 1-S 0 3 -1 -1 0 0 -M -Mcj 3 -1 -1 0 0 -M -MXB b* x1 x2 x3 x4 x5 x6 x7x4 11 1 -2 1 1 0 0 0x
3、6 3 -4 1 2 0 -1 1 0x7 1 -2 0 1 0 0 0 1表 1.16 3-6M M-1 3M-1 0 -M 0 0x4 10 3 -2 0 1 0 0 -1x6 1 0 1 0 0 -1 1 -2x3 1 -2 0 1 0 0 0 1表 1.17 1 M-1 0 0 -M 0 1-3Mcj 3 -1 -1 0 0 -M -MXB b* x1 x2 x3 x4 x5 x6 x7x4 12 3 0 0 1 -2 2 -5x2 1 0 1 0 0 -1 1 -2x3 1 -2 0 1 0 0 0 1表 1.18 1 0 0 0 -1 1-M -1-Mx1 4 1 0 0 1/3
4、-2/3 2/3 -5/3x2 1 0 1 0 0 -1 1 -2x3 9 0 0 1 2/3 -4/3 4/3 -7/3表 1.19 0 0 0 -1/3 -1/3 1/3-M 2/3-M所有 j 0， X* = ( 4, 1, 9, 0, 0, 0, 0 )T Z = 2 Z= -2判定 无解 条件：当进行到最优表时，仍有人工变量在基中，且 0， 则说明原问题无可行解。例 1.12用两阶段法求解 L.P的最优解 :解 :加入松弛变量、剩余变量、人工变量： x6 , x7第一阶段的 L.P问题min W= x6 +x7 = max W= - x6 -x7x1 -2x2 + x3 11s.t.
5、 -4x1 + x2 + 2x3 3-2x1 +x3=1 x1 , x2 , x3 0maxZ= 3x1 -x2 -x3x1 -2x2 + x3 +x4 =11s.t. -4x1 + x2 + 2x3 -x5 =3-2x1 +x3 =1 x1 , x2 , ,x5 0+x6+x7,x6 ,x7(二 )、两阶段法 -例表 1.20 0 0 0 0 0 -1 -1XB b* x1 x2 x3 x4 x5 x6 x7x4 11 1 -2 1 1 0 0 0x6 3 -4 1 2 0 -1 1 0x7 1 -2 0 1 0 0 0 1- W 0 0 0 0 0 0 -1 -1XB b* x1 x2 x
6、3 x4 x5 x6 x7x4 11 1 -2 1 1 0 0 0x6 3 -4 1 2 0 -1 1 0x7 1 -2 0 1 0 0 0 1表 1.21 4 -6 1 3 0 -1 0 0cj 0 0 0 0 0 -1 -1XB b* x1 x2 x3 x4 x5 x6 x7x4 11 1 -2 1 1 0 0 0x6 3 -4 1 2 0 -1 1 0x7 1 -2 0 1 0 0 0 1表 1.21 4 -6 1 3 0 -1 0 0x4 10 3 -2 0 1 0 0 -1x6 1 0 1 0 0 -1 1 -2x3 1 -2 0 1 0 0 0 1表 1.22 1 0 1 0 0 -1 0 -3x4 12 3 0 0 1 -2 2 -5x2 1 0 1 0 0 -1 1 -2x3 1 -2 0 1 0 0 0 1表 1.23 0 0 0 0 0 -1 -1开始第二阶段的计算x1 -2x2 + x3 +x4 =11s.t. -4x1 + x2 + 2x3 -x5 =3-2x1 +x3 =1 x1 , x2 , ,x5 0max S= 3x1 -x2 -x3cj 3 -1 -1 0 0XB b* x1 x2 x3 x4 x5x4 12 3 0 0 1 -2x2 1 0 1 0 0 -1x3 1 -2 0 1 0 0-S 0 3 -1 -1 0 0
