2024年5月20日发(作者：藤晶)
例4-7 用对偶单纯形法求解线性规划问题.
Min z =5x
1
+3x
2
s.t. -2 x
1 +
3x
2
≥6
3 x
1
- 6 x
2
≥4
Xj≥0（j=1,2）
解： 将问题转化为
Max z = -5 x
1
- 3 x
2
s.t. 2 x
1
- 3x
2
+ x
3
= -6
-3 x
1
+ 6 x
2
+ x
4
≥-4
Xj≥0（j=1,2，3,4）
其中，x
3
，x
4
为松弛变量，可以作为初始基变量，单纯形表见表4-17.
表4-17 例4-7单纯形表
C
j
C
B
迭代0
次
0
0
X
4
X
5
-6
-4
0
b
2
-16
6
2
-3
-5
X
1
-2/3
1
-7
[-3]
6
-3
X
2
1
0
0
X
3
-1/3
2
-1
1
0
0
X
4
0
1
0
0
1
0
X
B
b
-6
X
1
-3
X
2
-4
X
3
0
X
4
z
c
j
z
j
C
B
迭代1次
-3
0
X
4
X
3
X
B
z
c
j
z
j
在表4-17中,b=-16<0,而y≥0,故该问题无可行解.
注意: 对偶单纯形法仍是求解原问题,它是适用于当原问题无可行基,且所有检验数均为负
的情况.
若原问题既无可行基,而检验数中又有小于0的情况.只能用人工变量法求解.
在计算机求解时,只有人工变量法,没有对偶单纯形法.
3.对偶问题的最优解
由对偶理论可知,在原问题和对偶问题的最优解之间存在着密切的关系,可以根据这些关系,
从求解原问题的最优单纯形表中,得到对偶问题的最优解.
(1) 设原问题(p)为
Min z=CX
s.t.
AXb
X0
则标准型(LP)为
Max z=CX
AXb
s.t.
X0
其对偶线性规划（D）为
Max z=b
T
Y
s.t.
AXb
X0
用对偶单纯形法求解（LP），得最优基B和最优单纯形表T（B）。对于（LP）来说，当j=n+i
时，有Pj=-e
i
，c
j
=0
从而，在最优单纯形表T（B）中，对于检验数，有
（σn+1，σn+2…σn+m）=（c
n+1
，c
n+2
…，c
n+m
）-C
B
B
-1
（Pn
+1,Pn+2…,Pn+m）=- C
B
B
-1
(-I)
于是，Y*=（σn+1，σn+2…σn+m）
T
。可见，在（LP）的最优单纯形表中，剩余变
量对应的检验数就是对偶问题的最优解。
同时，在最优单纯形表T（B）中，由于剩余变量对应的系数
所以
B
-1
=（-y
n+1
，-y
n+2
…-y
n+m
）
例4-8 求下列线性规划问题的对偶问题的最优解。
Min z =6x
1
+8x
2
s.t. x
1 +
2x
2
≥20
3 x
1
+ 2x
2
≥50
Xj≥0（j=1,2）
解： 将问题转化为
Max z =-6x
1
-8x
2
s.t. -x
1
—
2x
2
+ x
3
=20
-3 x
1
- 2x
2
+ x
4
=50
Xj≥0（j=1,2，3,4）
用对偶单纯形法求解如表
表4-18 例4-8单纯形表
C
j
C
B
迭代0
次
-8
-6
X
4
X
5
5/2
15
-110
0
1
0
1
0
0
-3/4
1/2
3
1/4
-1/2
1
X
B
b
-6
X
1
-8
X
2
0
X
3
0
X
4
z
c
j
z
j
在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原
规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。
对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采
用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上
看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分
析中有时也要用到对偶单纯形方法，可以简化计算。
例
4-9
：
求解线性规划问题：
Min f = 2x1 + 3x2 + 4x3
S.t. x1 + 2x2 + x3 ≥ 3
2x1 - x2 + x3 ≥ 4
x1 , x2 , x3 ≥ 0
标准化：Max z = - 2x1 - 3x2 - 4x3
s.t. -x1-2x2-x3+x4= -3
-2x1+x2-3x3+x5= -4
x1,x2,x3,x4,x5 ≥ 0
表格对偶单纯形法
C
j
C
B
迭代0
次
-8
-6
X
4
X
5
5/2
15
-110
0
1
0
1
0
0
-3/4
1/2
3
1/4
-1/2
1
X
B
b
-6
X
1
-8
X
2
0
X
3
0
X
4
z
c
j
z
j
2024年5月20日发(作者：藤晶)
例4-7 用对偶单纯形法求解线性规划问题.
Min z =5x
1
+3x
2
s.t. -2 x
1 +
3x
2
≥6
3 x
1
- 6 x
2
≥4
Xj≥0（j=1,2）
解： 将问题转化为
Max z = -5 x
1
- 3 x
2
s.t. 2 x
1
- 3x
2
+ x
3
= -6
-3 x
1
+ 6 x
2
+ x
4
≥-4
Xj≥0（j=1,2，3,4）
其中，x
3
，x
4
为松弛变量，可以作为初始基变量，单纯形表见表4-17.
表4-17 例4-7单纯形表
C
j
C
B
迭代0
次
0
0
X
4
X
5
-6
-4
0
b
2
-16
6
2
-3
-5
X
1
-2/3
1
-7
[-3]
6
-3
X
2
1
0
0
X
3
-1/3
2
-1
1
0
0
X
4
0
1
0
0
1
0
X
B
b
-6
X
1
-3
X
2
-4
X
3
0
X
4
z
c
j
z
j
C
B
迭代1次
-3
0
X
4
X
3
X
B
z
c
j
z
j
在表4-17中,b=-16<0,而y≥0,故该问题无可行解.
注意: 对偶单纯形法仍是求解原问题,它是适用于当原问题无可行基,且所有检验数均为负
的情况.
若原问题既无可行基,而检验数中又有小于0的情况.只能用人工变量法求解.
在计算机求解时,只有人工变量法,没有对偶单纯形法.
3.对偶问题的最优解
由对偶理论可知,在原问题和对偶问题的最优解之间存在着密切的关系,可以根据这些关系,
从求解原问题的最优单纯形表中,得到对偶问题的最优解.
(1) 设原问题(p)为
Min z=CX
s.t.
AXb
X0
则标准型(LP)为
Max z=CX
AXb
s.t.
X0
其对偶线性规划（D）为
Max z=b
T
Y
s.t.
AXb
X0
用对偶单纯形法求解（LP），得最优基B和最优单纯形表T（B）。对于（LP）来说，当j=n+i
时，有Pj=-e
i
，c
j
=0
从而，在最优单纯形表T（B）中，对于检验数，有
（σn+1，σn+2…σn+m）=（c
n+1
，c
n+2
…，c
n+m
）-C
B
B
-1
（Pn
+1,Pn+2…,Pn+m）=- C
B
B
-1
(-I)
于是，Y*=（σn+1，σn+2…σn+m）
T
。可见，在（LP）的最优单纯形表中，剩余变
量对应的检验数就是对偶问题的最优解。
同时，在最优单纯形表T（B）中，由于剩余变量对应的系数
所以
B
-1
=（-y
n+1
，-y
n+2
…-y
n+m
）
例4-8 求下列线性规划问题的对偶问题的最优解。
Min z =6x
1
+8x
2
s.t. x
1 +
2x
2
≥20
3 x
1
+ 2x
2
≥50
Xj≥0（j=1,2）
解： 将问题转化为
Max z =-6x
1
-8x
2
s.t. -x
1
—
2x
2
+ x
3
=20
-3 x
1
- 2x
2
+ x
4
=50
Xj≥0（j=1,2，3,4）
用对偶单纯形法求解如表
表4-18 例4-8单纯形表
C
j
C
B
迭代0
次
-8
-6
X
4
X
5
5/2
15
-110
0
1
0
1
0
0
-3/4
1/2
3
1/4
-1/2
1
X
B
b
-6
X
1
-8
X
2
0
X
3
0
X
4
z
c
j
z
j
在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原
规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。
对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采
用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上
看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分
析中有时也要用到对偶单纯形方法，可以简化计算。
例
4-9
：
求解线性规划问题：
Min f = 2x1 + 3x2 + 4x3
S.t. x1 + 2x2 + x3 ≥ 3
2x1 - x2 + x3 ≥ 4
x1 , x2 , x3 ≥ 0
标准化：Max z = - 2x1 - 3x2 - 4x3
s.t. -x1-2x2-x3+x4= -3
-2x1+x2-3x3+x5= -4
x1,x2,x3,x4,x5 ≥ 0
表格对偶单纯形法
C
j
C
B
迭代0
次
-8
-6
X
4
X
5
5/2
15
-110
0
1
0
1
0
0
-3/4
1/2
3
1/4
-1/2
1
X
B
b
-6
X
1
-8
X
2
0
X
3
0
X
4
z
c
j
z
j