minZ= 10x1 +8x2 +7 x3 2x1 + x2 ≥ 6 S.t. x1 + x2 + x3 ≥ 4 x1 , x2 , x3≥0
化线性规划模型为标准型
maxZ’= －10x1－ 8x2 － 7x3 +0x4－Mx5 +0x6－Mx7 2x1 + x2 － x4 + x5 = 6 x 1 + x 2 + x 3 － x 6 + x 7= 4 x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥0
Cj CB 0 0 XB
标准化
Max z=2x1+4x2+ 0x3+ 0x4+ 0x5+ 0x6 2x1+2x2 + x3 =12 x1+2x2+ x4 =8 4x1 +x5 =16 4x2 +x6=12 x1, …, x6≥0
2 4 x2 0 x3 0 x4 0 x5 0 x6 x1
b
12 8 16 12 0
线性规划
～
0 0 -Z -Z’
1 0 0 -10
1/2 1/2 0 -8
0 1 0 -7
-1/2 1/2 0 0
1/2 -1/2 -1
0 -1 0
0 1 -1
3 1
0
σj<0
第一阶段规划最优
0 1 -1
～
0
0 -Z’
1
0 0 1 0 0
1/2 1/2 1/2
0 1 0
0
1 0 -1 2 -1
-1/2
9
线性规划
接上表
0
0
3
0 -2 1 1 0 0 0
0
1 0 0 0 1 0 0
0
0 1 0 0 0 1 0
1
0 0 0 1/3 0 2/3 -1/3
-2
-1 0 -1 -2/3 -1 -4/3 -1/3
0
1 0 0 0 1 0 0
-1
-2 1 -3 -1 -2 1 -3
12
1 1 2 4 1 9 -2
0
x6 0.5 -0.5 2
b
2
2
x1 0 1 0
比 值
4 4 32
8
8
0
0
1
0
0
0
0
-2
0
0
0.25
0
检验数j
-36
j<0
令 x4=0，x6=0，得x1=2，x2=8，x3=2， x5=8 即 X0=(2, 8, 2 ,0 , 8, 0) T 此时Z＝ 2×2+4×8=36 是最优解
16
线性规划
11
线性规划 第一阶段规划求解
Min Z x5 x7 MaxZ ' x5 x7 2 x1 x2 x4 x5 6 x1 x2 x3 x6 x7 4 x ,, x 0 7 1
-1 0 1 0 0 -1 0 1 -1 0 1 0 6 4 0

Max W x6 x7
x1
1 -4 -2 0 1 -4 -2 -6
x2
-2 1 0 0 -2 1 0 1
x3
1 2 1 0 1 2 1 3
x1 2 x2 x3 x4 11 4 x x 2 x x x 3 1 2 3 5 6 2 x1 x3 x7 1 x1 , , x7 0
-1
0 1 0 0 2
1
-1 -2 1 -3 -5
-2
10 1 1 1 12
1
～
0 -W 0
～
0
0
-Z’ -W
-2
0
1
0
0 0 -1
0 -1
1 -1
1 0 2 1
3 0 1 3
-1 0 -1 -1 0 0 0 0
0 0 0
进行第二阶段的计算
此时求解不是最优，继续迭代
令x5= 将第一阶段的人工变量列取消, 并将目标函数系数换成原问题的 x6= x7=0，得最优解X= ( 0, 1, 1 ,12, 0 )T， minW= 0。因人工变 量目标函数系数, 重新计算检验数行, MinxZ = 0, x1 x 2 x 3 化为标准型 MaxZ ' 3x1 x2 x3 6=x7 3 所以是原问题的基可行解。于是可以开始第二阶段的计 可得如下第二阶段的初始单纯形 算。 表；应用单纯形算法求解得最终表。
目的达到：则所求解为 原问题的可行解 目的未达到：则原问题 无解
第二阶段利用已求出的初始基可行解来求原问题最优解。
第二阶段Max Z ' 3x1 x2 x3
5
线性规划 试用两阶段法求解如下线性规划问题
Min Z 3x1 x 2 x 3 Max Z 3x1 x 2 x3 0 x 4 0 x5 Mx 6 Mx 7 x1 2 x 2 x 3 11 4 x x 2 x 3 1 2 3 2 x 1 x 3 1 x1 , x 2 , x 3 0
x1 2 x2 x3 x4 11 4 x x 2 x x x 3 1 2 3 5 6 2 x1 x3 x7 1 x1 ,, x7 0
6
线性规划 初等变换 -Z ’
0 0 0 -W 0
Min Z x6 x7
1 1 -8 1 1
-8+2M
0 1 -7 0 1
-7+M
-1 0 0 -1 0
-M
1 0 -M 1 0
0
0 -1 0 0 -1
-M
0 1 -M 0
6 4 0 6 4
10M
～
1
-10+3M
1
0
～
1
0
0
1/2 1/2
-3+1/2M
0
-1/2
1/2
0
0 1
3
1
-7+M
1/2
1/2M-5
-1/2
5-3/2M
0 -1 0
0 0 0
进行第二阶段的计算
此时求解不是最优，继续迭代
令x5= 将第一阶段的人工变量列取消, 并将目标函数系数换成原问题的 x6= x7=0，得最优解X= ( 0, 1, 1 ,12, 0 )T， minW= 0。因人工变 量目标函数系数, 重新计算检验数行, MinxZ = 0, x1 x 2 x 3 化为标准型 MaxZ ' 3x1 x2 x3 6=x7 3 所以是原问题的基可行解。于是可以开始第二阶段的计 可得如下第二阶段的初始单纯形 算。 表；应用单纯形算法求解得最终表。
x1 2 x 2 x3 x 4 11 4 x x 2 x x x 3 1 2 3 5 6 2 x1 x3 x7 1 x1 ,, x7 0
第一阶段是先求以人工变量等于0为目标的线性规划问题
第一阶段 Min Z x6 x7
1/2 -3/2 -11 1 -2
1/2
-1/2 1/2 1/2 -1/2 1/2
0
-1 -7 1 -2 -6
3
1 37 2 2 36
13
～
0 0 -Z’
0
1
-1
σj<0
线性规划
四、单纯形法补遗
进基变量相持：
– 单纯形法运算过程中，同时出现多个相同的j最大。 – 在符合要求的j(目标为max：j＞0，min：j＜0)中，选取下标
0 0
2 1
1 1
0 1
-Z’ 0
0 2
1 3 1 0
0 1
1 2 1/2 1/2 1/2
0 0
1 1 0 1 1
0 -1
0 -1 -1/2 1/2
-1 1
0 0 1/2 -1/2
0 0
-1 -1 0 -1
6
4 10 3 1 1
12
～
0 -Z’ 0
0
1 0
～
0
-Z’
0
1/2
-3/2
-1
令 x3= x4=x6=0得 x1=2, x2=2, 此解最优 max-Z’=36 第二阶段规划求解 Min Z 10x1 8x 2 7x 3 Max Z' 10x1 8x 2 7x从而得 minZ=36 3
x4
x5
0 -1 0 0
x6
0 1 0 -1
x7
0 0 1
b
1 0 0 0 1 0 0 0
11 3 1 0 11 3 1 4
7
-1 0 0 1 0
0 -1 0 -1
0 1 0 0
～
0 0 -W
线性规划
0 0 3 0 -2 0 3
0
-2 1 0 1 0
1
0 0 1 0 0
0
1 0 0 0 1
0
0 -1 0 -1 -2
再次迭代结果
结论：非基变量检验数有为0的，此线性规划有无穷多个解
2
线性规划
试用大M法求解
maxZ’= －10x1－ 8x2 － 7x3 +0x4－Mx5 +0x6－Mx7 2x1 + x2 － x4 + x5 = 6 x1 + x2 + x3 － x6 + x7= 4 x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥0
2 1 -10 2
4
线性规划