文档介绍：第八节 单纯形法的进一步讨论 ——人工变量
1
人工变量法
考虑标准型 (M)：
分别给每个约束方程硬性加入一个非负变量
a11x1 +a12x2+…+a1nxn +xn+1 = b1 (≥0)
a12x1 +a22x2+…+a2nxn +xn+2 = b2 (≥0)
… … … … …
am1x1+am2x2+…+amnxn +xn+m = bm(≥0)
n个
xn+1, xn+2, … , xn+m 称为人工变量。
初始基本可行解：( 人造基本解 )
X0 = ( 0, 0, … , 0, b1, b2, …, bm )T
()
2
基本思想：
人造解 X0 不是原LP问题的基本可行解。
但若能通过单纯形法的迭代步骤，将虚拟
的人工变量都替换出去，都变为非基变量（即
人工变量xn+1 = xn+2 = … = xn+m = 0），则X0的
前n个分量就构成原LP问题的一个基本可行解。
反之，若经过迭代，不能把人工变量都变
为非基变量，则表明原LP问题无可行解。
人工变量法
大M法或两阶段法
3
一、大M法
若迭代最终得到最优解X* ，而且基变量中不含有人工变量，则X*的
前n个分量就构成原问题的一个最优基本解；否则，原问题无可行解。
若迭代结果是解无界，而且基变量中不含有人工变量， 则原问题也
解无界；否则，原问题无可行解。
4
一、大M法
例： 用大M法解下列线性规划
解：首先将数学模型化为标准形式
系数矩阵中不存在单位矩阵，无法建立初始单纯形表。
5
一、大M法
故人为添加两个单位向量，得到人工变量单纯形法数学模型：
其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。
6
一、大M法
cj
3
2
-1
0
0
-M
-M
CB
XB
b
x1
x2
x3
x4
x5
x6
x7
θi
-M
x6
4
-4
3
1
-1
0
1
0
4
0
x5
10
1
-1
2
0
1
0
0
5
-M
x7
1
2
-2
1
0
0
0
1
1
3-2M
2+M
-1+2M↑
-M
-M
x6
3
-6
5
0
-1
0
1
3/5
0
x5
8
-3
3
0
0
1
0
8/3
-1
x3
1
2
-2
1
0
0
0
——
5-6M
5M↑
0
-M
0
0
2
x2
3/5
－6/5
1
0
－1/5
0
——
0
x5
31/5
3/5
0
0
3/5
1
31/3
-1
x3
11/5
－2/5
0
1
－2/5
0
——
5 ↑
0
0
0
0
2
x2
13
0
1
0
1
2
3
x1
31/3
1
0
0
1
5/3
-1
x3
19/3
0
0
1
0
2/3
0
0
0
-5
-25/3
→
→
→
7
一、大M法
例 用大M法求解下述LP问题
max z = 3x1 – x2 – 2x3
3x1+ 2x2 – 3x3 = 6
x1 – 2x2 + x3 = 4
x1， x2， x3 ≥ 0
max z = 3x1 – x2 – 2x3
3x1+ 2x2 – 3x3 +x4