MaxZ=-3x1+x3
MaxZ=-3x1+x3-Mx6-Mx7
x1+ x2+ x3≤4
x1+ x2+ x3+x4
=4
-2x1+ x2- x3≥1 3x2+x3=9
标准化 及变形
xi ≥0,j=1,2,3
-2x1+ x2-x3 -x5+x6 =1
3x2+x3
+x7=9
xi ≥0,j=1,…,7
增加人工变量后，线性规划问题中就存在一个B为单位矩阵， 后面可以根据我们前面所讲的单纯形法来进行求解。
0
0 无解
B8 P1P2P5 4 2 0 0 4 14 √
Q2
A
B9 P1P2P4 2 3 0 8 0 13 √
Q3
4
B1 P1P2P3 4 3 -2 0 0 17 ╳
B
Q4
Q3
B
0
3
max z 2x1 3x2
2
Q2
1
2020/1/20
O
1
2
3 4 Q1
C x1
x1 2x 2 x3
第5节 单纯当形之处法，请的联系进本人一或网步站删讨除。论
一、人工变量法（大M法）
约束条件：
“≤” →加一个松弛变量 “≥” →减一个剩余变量后，再加一个人工变
量
“＝” →加一个人工变量
目标函数： 人工变量的系数为“－M”，即罚因子
2020/1/20
9
若线性规划问题有最优解则人工变量必为0。
本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不 当之处，请联系本人或网站删除。
本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不
回顾：单纯当形之法处，求请解联系步本人骤或：网站删除。
2020/1/20
7
本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不
第5节 单当纯之处形，请法联系的本进人或一网站步删除讨。论
2020/1/20
8
本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不
本St文e档p所1提供化的为信标息仅准当供型之参，处考找，之出请用联，初系不始能本可作人行为或基科网学站，依删并据除列，。出请初勿模始仿单。纯文形档表如有不
2020/1/20
1
• 上述初始单纯形表中，最后一行称为检验数σj
本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不 当之基处，基请向联量系本x1人x或2 网x站3 删x4除。x5 Z 可行解 图中点
8
4 x1
x4 16

4 x2
x5 12
x j 0, j 1,,5
2
本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不
• Step2：检查非基当变之量处所，对请应联系的本检人验或数网σ站j，删除若。所有的σj≤0，则当 前的基可行解就是最优解，当前的目标函数值就是最优值，停 止计算。
当之处，请联系本人或网站删除。
cj
-3 0 1 0 0 -M -M
CB XB bi x1 x2 x3 x4 x5 x6 x7 θ
0 x4 4
1
1
1
1
0 0 04
-M x6 1
-2 [ 1 ] -1 0 -1
1
01
-M x7 9
0
3
1
0
0
0
13
σj 0 x4
0 x2
-M x7
-3-2M [4M] 1 33 0 2 1 -2 1 -1 6 [ 6] 0 4
• 例7 用单当纯之形处，法请求联系解本人例或6网。站删除。
•
max z = 2x1 + 3x2
x1 + 2x2 +x3
=8
s.t.x2
+x5 =12
xj≥0，j=1,2,…,5
2020/1/20
4
本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不
练习： 当之处，请联系本人或网站删除。
• 分别用图解法和单纯形法求解下列线性规划问 题，并指出单纯形法迭代的每一步相当于图形 上哪一个顶点。
Max Z = 10x1+ 5x2
3x1+ 4x2≤9 5x1+ 2x2 ≤8 x1 ，x2≥0
2020/1/20
5
本文解档：所提供的信息仅当供之参处考，之请用联，系不能本作人为或科网学站依删据除，。请勿模仿。文档如有不
0 -M 0 0 x2入，x6出 1 1 -1 0 1 0 -1 1 0 0 3 -3 1 1
σj
0 x4
[6M-3] 0 4M+1 0 3M -4M 0 x1入，x7出 0 0 0 0 1 -1/2 1/2 -1/2 -
0 x2 -3 x1
σj
B1 P3P4P5 0 0 8 16 12 0 √
O
B2 P2P4P5 0 4 0 16 -4 12 ╳
A
B3 P2P3P5 0
0
无解
B4 P2P3P4 0 3 2 16 0 9 √
Q4
B5 P1P4P5 8 0 0 -16 12 16 ╳
C
x2
B6 P1P3P5 4 0 4 0 12 8 √
Q1
B7 P1P3P4
• 否则，转入下一步。
• SP算tke≤。p03(即：P若k中存每在一一个个分σk>量0a，ikσ≤k0所)，对则应该的L变P无量有xk限的最系优数解列，向停量止计 • 否则，转入下一步。
• Step4：进行可行基的迭代。
• 重复以上步骤
2020/1/20
3
本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不
2020/1/20
10
本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不 当之处，请联系本人或网站删除。
练习：列出初始单纯形表，并求解第2
小题的最优解 1. P55，2.2（1） 2.
2020/1/20
11
本文单档所纯提形供表的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不
cj
CB 0 0
XB x3 x4
对 应 0
bi 9 8
0 10
σσXxjj 31对应A
21/5 8/5
5 10
σXxj 21对 应B
3/2 1
10 5 0 0
x1 x2 x3 x4 θ
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出
0 1 5/14 -3/14
C: (0,9/4)
1 0 -1/7 2/7
0
0 -5/14 -25/14
B:(1,3/2)
所以：X*=(x1,x2)T=(1,3/2)T Z*=35/2
2020/1/20
0: (0,0)
x1 A: (86/5,0)