2024年5月7日发(作者：隆采春)
单纯形法课件3——大M法
条件：非单位矩阵
加人工变量的约束条件：>=或=的
MAX Z=-2X1-3X2+0S1+0S2+0S3-MA1-MA2
ST
X1+X2-S1 +A1 =350
X1 -S2 +A2=125
2X1+X2 +S3 =600
X1, X2, S1, S2, S3, A1, A2>=0
迭
代
次
数
基
变
量
A1
A2
X1
C
B
X2 S1 S2 S3 A1
-M
A2
-M
-2
-M
-M
0
zj
-3
1
0
1
-M
0
-1
0
0
M
0
0
-1
0
M
-M
0
0
0
1
0
0
b
350
125
600
Z=
-475M
225
125
350
比值
b
i
a
ij
1
1
2
-2M
1
0
0
-M
0
0
1
0
-M
0
350/1
125/1
600/2
0
S3
j
c
j
z
j
-2+2M -3+M -M
A1
X1
1
S3
zj
-M
-2
0
0
1
0
-2
1
0
1
-M
-1
0
0
1
-1
2
0
0
1
0
1
0
0
-1
1
-2
225/1
----
350/2
M -M+2 -M M-2 -225M
j
c
j
z
j
A1
X1
2
S2
zj
-M
-2
0
0 -3+M -M M-2 0 0 2-2M
-250
50
300
175
100
600
350
0
1
0
-2
0
1/2 -1
1/2
1/2
0
0
0
0
1
0
0
-1/2 1
1/2
1/2
0
0
0
0
-1
0
-M
j
c
j
z
j
X2
X1
3
S2
zj
-3
-2
0
-1/2M
M
-1
1/2M
-M
-2
1/2M
-M
-1
-1/2M
0
+1
-50M-600
0
1
0
-2
0
1
0
0
-3
0
-2
1
1
4
-4
0
0
1
0
0
-1
1
1
1
-1
2
-1
-1
-4
-M
+4
0
0
-1
0
-M
100
250
125
-800
j
c
j
z
j
第三次所有的检验数都小于等于0，找到最优解，最优解为
（250，100，0，125，0，0，0），Z=800，原问题最优值F=-Z=800
可不可以这样？
MAX Z=-2X1-3X2+0S1+0S2+0S3
ST
-X1-X2+S1 =-350
-X1 +S2 =-125
2X1+X2 +S3 =600
X1, X2, S1, S2, S3, >=0
迭基C
B
X1 X2 S1 S2 S3
比值
代
次
数
变
量
S1
S2
0
0
0
zj
-2 -3 0 0 0
b
-350
-125
600
Z=
0
b
i
a
i2
-1
-1
2
0
-1
0
1
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
S3
j
c
j
z
j
-2 -3 0 0
基变量X1、X2的检验数全部为负，得到最优解为（0，0，
-350，-125，600），不是可行解。因此，用负的单位向量作
基向量求得的基本解一般不满足非负条件，不是可行解，通
过加上人工变量构造初始单位矩阵的方法，可以克服这一问
题。当然，如果不通过使用单纯型法表，不从将单位矩阵作
为初始基变量开始迭代，而是用等式移项的方法，也可能可
以不加人工变量而求得最优解。如：
MAX Z=-2X1-3X2+0S1+0S2+0S3
ST
X1+X2-S1 =350
X1 -S2 =125
2X1+X2 +S3 =600
移项：
X1=350-X2+S1
S2= X1-125
X2=600-2X1-S3
用S1，S3表示X1 、X2 、S2，
X1=250-S3-S1
S2= 125-S3-S1
X2=100+2S1+S3
令非基变量S1，S3等于零，得一个基本解：（250，100，0，
125，0）是不是最优解？Z=-2（250-S3-S1）-3（100+2S1+S3）
=-800-4S1-S3，得到最优解，最优值为-800。
2024年5月7日发(作者：隆采春)
单纯形法课件3——大M法
条件：非单位矩阵
加人工变量的约束条件：>=或=的
MAX Z=-2X1-3X2+0S1+0S2+0S3-MA1-MA2
ST
X1+X2-S1 +A1 =350
X1 -S2 +A2=125
2X1+X2 +S3 =600
X1, X2, S1, S2, S3, A1, A2>=0
迭
代
次
数
基
变
量
A1
A2
X1
C
B
X2 S1 S2 S3 A1
-M
A2
-M
-2
-M
-M
0
zj
-3
1
0
1
-M
0
-1
0
0
M
0
0
-1
0
M
-M
0
0
0
1
0
0
b
350
125
600
Z=
-475M
225
125
350
比值
b
i
a
ij
1
1
2
-2M
1
0
0
-M
0
0
1
0
-M
0
350/1
125/1
600/2
0
S3
j
c
j
z
j
-2+2M -3+M -M
A1
X1
1
S3
zj
-M
-2
0
0
1
0
-2
1
0
1
-M
-1
0
0
1
-1
2
0
0
1
0
1
0
0
-1
1
-2
225/1
----
350/2
M -M+2 -M M-2 -225M
j
c
j
z
j
A1
X1
2
S2
zj
-M
-2
0
0 -3+M -M M-2 0 0 2-2M
-250
50
300
175
100
600
350
0
1
0
-2
0
1/2 -1
1/2
1/2
0
0
0
0
1
0
0
-1/2 1
1/2
1/2
0
0
0
0
-1
0
-M
j
c
j
z
j
X2
X1
3
S2
zj
-3
-2
0
-1/2M
M
-1
1/2M
-M
-2
1/2M
-M
-1
-1/2M
0
+1
-50M-600
0
1
0
-2
0
1
0
0
-3
0
-2
1
1
4
-4
0
0
1
0
0
-1
1
1
1
-1
2
-1
-1
-4
-M
+4
0
0
-1
0
-M
100
250
125
-800
j
c
j
z
j
第三次所有的检验数都小于等于0，找到最优解，最优解为
（250，100，0，125，0，0，0），Z=800，原问题最优值F=-Z=800
可不可以这样？
MAX Z=-2X1-3X2+0S1+0S2+0S3
ST
-X1-X2+S1 =-350
-X1 +S2 =-125
2X1+X2 +S3 =600
X1, X2, S1, S2, S3, >=0
迭基C
B
X1 X2 S1 S2 S3
比值
代
次
数
变
量
S1
S2
0
0
0
zj
-2 -3 0 0 0
b
-350
-125
600
Z=
0
b
i
a
i2
-1
-1
2
0
-1
0
1
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
S3
j
c
j
z
j
-2 -3 0 0
基变量X1、X2的检验数全部为负，得到最优解为（0，0，
-350，-125，600），不是可行解。因此，用负的单位向量作
基向量求得的基本解一般不满足非负条件，不是可行解，通
过加上人工变量构造初始单位矩阵的方法，可以克服这一问
题。当然，如果不通过使用单纯型法表，不从将单位矩阵作
为初始基变量开始迭代，而是用等式移项的方法，也可能可
以不加人工变量而求得最优解。如：
MAX Z=-2X1-3X2+0S1+0S2+0S3
ST
X1+X2-S1 =350
X1 -S2 =125
2X1+X2 +S3 =600
移项：
X1=350-X2+S1
S2= X1-125
X2=600-2X1-S3
用S1，S3表示X1 、X2 、S2，
X1=250-S3-S1
S2= 125-S3-S1
X2=100+2S1+S3
令非基变量S1，S3等于零，得一个基本解：（250，100，0，
125，0）是不是最优解？Z=-2（250-S3-S1）-3（100+2S1+S3）
=-800-4S1-S3，得到最优解，最优值为-800。