2020/4/3
12
单纯形表
cj CB XB 0 x4 -M x6 -M x7
σj 0 x4 0 x2 -M x7
σj
0 x4 0 x2 -3 x1
σj
0 x4 0 x2 1 x3
σj
-3 0 1 0
bi x1 x2 x3 x4
4
1
1
1
1
1 -2 [ 1 ] -1 0
9
03
1
0
-3-2M [4M] 1 0
6 [ 6 ] 0 4 0 3 -3 1 1
[ 6] 0
40
3
-4 0 x1入，x7出
0 0 0 0 1 -1/2 1/2 -1/2 3 0 1 1/3 0 0 0 1/3 1 1 0 2/3 0 1/2 -1/2 1/6
0
0
000
-1
-1
所以：已得最优解，且人工变量为非基变量，则可 去掉人工变量，得原问题的一个即可行基。
σj 0 x4 0 x2 -1 x7
σj
0 x4 0 x2 0 x1
σj
0 0 0 0 0 -1 -1
bi x1 x2 x3 x4 x5 x6 x7 θ
4
1
1
1
1
0 0 04
1
-2 [ 1 ] -1
0
-1
1
01
9
0
3
1
0
0
0
13
-2 [ 4 ] 0 0 -1
0 0 x2入，x6出
3 3 0 2 1 1 -1 0 1 1 -2 1 -1 0 -1 1 0 －
0
C x1
x2 x3 x4 x5 Z 可行解 图中点
0 8 16 12 0 √
O
4 0 16 -4 12 ╳
A
0
无解
3 2 16 0 9 √
Q4
0 0 -16 12 16 ╳
C
0 4 0 12 8 √
Q1
0
0 无解
2 0 0 4 14 √
Q2
3 0 8 0 13 √
Q3
3 -2 0 0 17 ╳
B
max z 2x1 3x2
量
“＝” →加一个人工变量
目标函数： 人工变量的系数为“－M”，即罚因子
2020/4/3
10
若线性规划问题有最优解则人工变量必为0。
MaxZ=-3x1+x3
MaxZ=-3x1+x3-Mx6-Mx7
x1+ x2+ x3≤4
x1+ x2+ x3+x4
=4
-2x1+ x2- x3≥1 3x2+x3=9
标准化 及变形
-9/2 0
0 0 -3/4 -M+3/4 -M-1/4
2020/所4/3以：X*=(x1,x2,x3)T=(0,5/2, 3/2)T Z*=3/2
13
二、两阶段法
• 第一阶段暂不考虑原问题是否存在基可行解，给原问题加 入人工变量，并构建一个仅含人工变量的目标函数（求极 小化），人工变量的价值系数一般为1，约束条件和原问 题的一样。
0
2 0 -1
θ -
50
x1入，x4出
因为σ2 = 2,且ai2 全≤0
所以：无界
2020/4/3
22
例3: 下表为一极大化问题对应的单纯形表
x1
x2
x3
x4
x5
bi
x1
1
0
a1
0
a2
a6
x2
0
1
1
0 -2 2
x4
0
0
-2
1
a3
3
σj
0
0
a4
0
a5
讨论在a1,a2,a3,a4,a5,a6取何值的情况下，该表中的解为：
40
σj
40 45 25
0
0 x2入，x4出
……
45 X2 80/3 1/3 1
0 2/3 -1/3
25 x3 20 1 0 1 -1 1
σj
0
0 0 -5 -10
因为全σj ≤ 0,且σ1=0,则有无穷多最优解。
所以：其中一个最优解为X*=(0,80/3,20,0,0) T,Z*=1700
2020思/4/3考：无穷多最优解的一般形式？ 21
B:(1,3/2)
2020/4/3
0: (0,0)
x1 A: (87/5,0)
回顾：单纯形法求解步骤：
2020/4/3
8
第5节 单纯形法的进一步讨论
2020/4/3
9
第5节 单纯形法的进一步讨论
一、人工变量法（大M法）
约束条件：
“≤” →加一个松弛变量 “≥” →减一个剩余变量后，再加一个人工变
x1 2x 2 x3
8
4x1
x4 16
4 x2
x5 12
x j 0, j 1, ,5
3
• Step2：检查非基变量所对应的检验数σj，若所有的σj≤0，则当 前的基可行解就是最优解，当前的目标函数值就是最优值，停 止计算。
• 否则，转入下一步。
• SP算tke≤。p03(即：P若k中存每在一一个个分σk>量0a，ikσ≤k0所)，对则应该的L变P无量有xk限的最系优数解列，向停量止计 • 否则，转入下一步。
2020/4/3
16
（第二阶段）单纯形表2
cj
-3 0 1 0 0
CB XB bi x1 x2 x3 x4 x5 θ
0 x4 0
0
0
0
1 -1/2 -
0 x2 3 0 1 1/3 0 0 9
-3 x1 1
1
0 [2/3] 0 1/2 3/2
σj
0
0 [3]
0 3/2 x3入，x1出
0 X4 0
0
0
新加变量系数
xs
xa
0
-M
2020/4/3
18
第5节 单纯形法的进一步讨论
人工变量法（大M法）和两阶段法
约束条件：
“≤” →加一个松弛变量 “≥” →减一个剩余变量后，再加一个人工变
量
“＝” →加一个人工变量
若线性2020规/4/划3 问题有最优解则人工变量必为0。
19
三、单纯形法计算中的几个问题
• ⑴.要求解问题的目标函数能用数值指 标来反映，且为线性函数；
• ⑵.存在着多种方案； • ⑶.要求达到的目标是在一定条件下实
现的，这些约束可用线性等式或不等式描 述。
2020/4/3
25
建模步骤：
第一步：设置要求解的决策变量。决策变量选取得 当，不仅能顺利地建立模型而且能方便地求解，否则 很可能事倍功半。
• 目标函数极小化时解的最 当所有非基变量的σj≥0时为最优解；
优性判别；
• 无可行解的判别；
最优解中人工变量为非0的基变量时；
• 无界的判别； • 无穷多最优解的判别； • 唯一最优解的判别.
存在某个σk>0，且所有的aik≤0时；
得最优解时，有检验数为0的非基变量； 得最优解时，所有非基变量检验数为负；
第4节 单纯形法计算步骤
2020/4/3
1
Step 1 化为标准型，找出初始可行基，并列出初始单纯形表
2020/4/3
2
• 上述初始单纯形表中，最后一行称为检验数σj
x2
A 4
Q4
Q3
B
3
2
Q2
1
2020/4/3
O
1
2
3 4 Q1
基 基向量 x1 B1 P3P4P5 0 B2 P2P4P5 0 B3 P2P3P5 0 B4 P2P3P4 0 B5 P1P4P5 8 B6 P1P3P5 4 B7 P1P3P4 B8 P1P2P5 4 B9 P1P2P4 2 B1 P1P2P3 4
✓唯一最优解；
• a4<0,a5<0, a6≥0
✓无穷多最优解；
• a6≥0,a4≤0, a5≤0, a4=0或a5=0
✓无界； ✓无可行解；
✓非最优，继续换基：
• a6≥0,a5>0,a2≤0, a3≤0 • a4≤0,a5≤0, x4或x2为人工变量，a6≥0 ； x1为人工变量，a6>0 • a4>0,a4>a5;a6/a1>2→a1>0
33 0 2 1 1 -2 1 -1 0
6 [ 6] 0 4 0
[6M-3] 0 4M+1 0 00 0 0 1
3 0 1 1/3 0 1 1 0 [2/3] 0
0 0 [ 3] 0 00 0 0 1 5/2 -1/2 1 0 0
0 -M -M
x5 x6 x7 θ
0 0 04 -1 1 0 1
0 0 13
xi ≥0,j=1,2,3
-2x1+ x2-x3 -x5+x6 =1
3x2+x3
+x7=9
xi ≥0,j=1,…,7
增加人工变量后，线性规划问题中就存在一个B为单位矩阵， 后面可以根据我们前面所讲的单纯形法来进行求解。
2020/4/3
11
练习：列出初始单纯形表，并求解第2
小题的最优解
1. P55，2.2（1） 2.
3 4 1 03 [ 5 ] 2 0 1 8/5
[10] 5
0
0 x1入,x4出
0 [14/5] 1 -3/5 3/2
1 2/5 0 [1]
0 0
1/5 4
x2
-2 x2入,x3出