2.3 对偶单纯形法
一, 什麽是对偶单纯形法？
对偶单纯形法 是应用 对偶原理 求解原始
线性规划的一种方法 —— 在原始问题的单
纯形表格上进行 对偶处理 。
注意,不是解对偶问题的单纯形法 ！
二, 对偶单纯形法的基本思想
1,对, 单纯形法, 求解过程认识的提
升 ——
从更高的角度理解单纯形法
初始可行基 （ 对应一个初始基本可行解 ）
→ 迭代 → 另一个可行基 （ 对应另一个基
本可行解 ）, 直至 所有检验数 ≤0为止 。
所有检验数 ≤0意味着
,CANBCC
BN ????
? ?01
说明 原始问题的最优基也是对偶问题的可行
基 。 换言之, 当原始问题的基 B既是原始可
行基又是对偶可行基时, B成为最优基 。
定理 2-5 B是线性规划的最优基 的 充要条件
是, B是可行基, 同时也是对偶可行基 。
单纯形法的求解过程就是：
在保持 原始可行 的前提下 （ b列保持 ≥0）,
通过逐步迭代 实现对偶可行 （ 检验数行 ≤0） 。
2,对偶单纯形法思想：
换个角度考虑 LP求解过程, 保持 对偶可行
的前提下 （ 检验数行保持 ≤0）, 通过逐步迭
代 实现原始可行 （ b列 ≥0,从非可行解变成
可行解 ） 。
三, 对偶单纯形法的实施
1,使用条件,① 检验数全部 ≤0；
② 解答列至少一个元素 < 0；
2,实施对偶单纯形法的基本原则：
在保持对偶可行的前提下进行基变换 —— 每一
次迭代过程中取出 基变量中的一个负分量 作为
换出变量 去 替换 某个 非基变量 （作为 换入变
量 ），使原始问题的非可行解向可行解靠近。
3,计算步骤,
① 建立初始单纯形表, 计算检验数行 。
解答列 ≥ 0—— 已得最优解；
至少一个元素 <0,转下步 ;
解答列 ≥ 0—— 原始单纯形法；
至少一个元素 <0,另外处理；
检验数全部 ≤ 0
（ 非基变量检验数 <0）
至少一个检验数 >0
?基变换：
先确定换出变量 —— 解答列中的负元素
（ 一般选最小的负元素 ） 对应的基变量 出基 ；
即
? ? 出基，则选 llii
i
xbBbBbB,)(0)()(m in 111 ??? ??
相应的行 为主元行 。
然后 确定换入变量 —— 原则 是：在 保持对偶
可行的前提 下, 减少原始问题的不可行性 。
如果
'
'
'
0m in
lk
kk
lj
lj
jj
j a
zc
a
a
zc ?
?
??
?
?
?
??
?
?
?
?
?
（最小比值原则）,则选 为换入变量，相
应的列为 主元列,主元行和主元列交叉处的
元素 为主元素 。
kx
'lka
?按主元素进行换基迭代 （ 旋转运算, 枢
运算 ）, 将主元素变成 1,主元列变成单位向
量, 得到新的单纯形表 。
继续以上步骤, 直至求出最优解 。
课后小组讨论 4 讨论对偶单纯形法中确定换入
变量的最小比值原则的依据, 给出详细的证明
过程 （ 附上必要的说明, 可以采用必要的文字
说明加上证明思路图, 主线框图等 ） 。 写出研
究报告和工作报告 。 （ 两周后交 ）
4、举例 —— 用对偶单纯形法求解 LP：
?
?
?
?
?
?
?
??
??
??
??
??
0,0
37
34
2
..
93
21
21
21
21
21
yy
yy
yy
yy
ts
yyM in W
化为
标准型 →
?
?
?
?
?
?
?
?
???
???
???
???
0,,
37
34
2
..
93
51
521
421
321
21
yy
yyy
yyy
yyy
ts
yyM a x Z
?
将三个等式约束两边分别乘以 -1，然后
列表求解如下：
-3/-1 -9/-1 --- --- ---比 值
-3 -9 0 0 00-Z
-1 -1 1 0 0
-1 -4 0 1 0
-1 -7 0 0 1
-2
-3
-3
y3
y4
y5
0
0
0
-3 -9 0 0 0
y1 y2 y3 y4 y5
cj
yj
b XBCB
--- -6/-3 -3/-1 --- ---比 值
0 -6 -3 0 06-Z
1 1 -1 0 0
0 -3 -1 1 0
0 -6 -1 0 1
2
-1
-1
y1
y4
y5
-3
0
0
-3 -9 0 0 0
y1 y2 y3 y4 y5
cj
yj
b XBCB
0 0 -1 -2 08-Z
1 0 -4/3 1/3 0
0 1 1/3 -1/3 0
0 0 1 -2 1
5/3
1/3
1
y1
y2
y5
-3
-9
0
-3 -9 0 0 0
y1 y2 y3 y4 y5
cj
yj
b XBCB
最优解是 Y*=（ 5/3,1/3,0,0,1） T，
目标函数最优值为 Wmin=-Zmax=8
思考题：
能否不要化为标准型, 直接按
极小化问题用单纯形表格迭代求解？
（ 结合课后小组讨论 4一并思考研究 ）
一, 什麽是对偶单纯形法？
对偶单纯形法 是应用 对偶原理 求解原始
线性规划的一种方法 —— 在原始问题的单
纯形表格上进行 对偶处理 。
注意,不是解对偶问题的单纯形法 ！
二, 对偶单纯形法的基本思想
1,对, 单纯形法, 求解过程认识的提
升 ——
从更高的角度理解单纯形法
初始可行基 （ 对应一个初始基本可行解 ）
→ 迭代 → 另一个可行基 （ 对应另一个基
本可行解 ）, 直至 所有检验数 ≤0为止 。
所有检验数 ≤0意味着
,CANBCC
BN ????
? ?01
说明 原始问题的最优基也是对偶问题的可行
基 。 换言之, 当原始问题的基 B既是原始可
行基又是对偶可行基时, B成为最优基 。
定理 2-5 B是线性规划的最优基 的 充要条件
是, B是可行基, 同时也是对偶可行基 。
单纯形法的求解过程就是：
在保持 原始可行 的前提下 （ b列保持 ≥0）,
通过逐步迭代 实现对偶可行 （ 检验数行 ≤0） 。
2,对偶单纯形法思想：
换个角度考虑 LP求解过程, 保持 对偶可行
的前提下 （ 检验数行保持 ≤0）, 通过逐步迭
代 实现原始可行 （ b列 ≥0,从非可行解变成
可行解 ） 。
三, 对偶单纯形法的实施
1,使用条件,① 检验数全部 ≤0；
② 解答列至少一个元素 < 0；
2,实施对偶单纯形法的基本原则：
在保持对偶可行的前提下进行基变换 —— 每一
次迭代过程中取出 基变量中的一个负分量 作为
换出变量 去 替换 某个 非基变量 （作为 换入变
量 ），使原始问题的非可行解向可行解靠近。
3,计算步骤,
① 建立初始单纯形表, 计算检验数行 。
解答列 ≥ 0—— 已得最优解；
至少一个元素 <0,转下步 ;
解答列 ≥ 0—— 原始单纯形法；
至少一个元素 <0,另外处理；
检验数全部 ≤ 0
（ 非基变量检验数 <0）
至少一个检验数 >0
?基变换：
先确定换出变量 —— 解答列中的负元素
（ 一般选最小的负元素 ） 对应的基变量 出基 ；
即
? ? 出基，则选 llii
i
xbBbBbB,)(0)()(m in 111 ??? ??
相应的行 为主元行 。
然后 确定换入变量 —— 原则 是：在 保持对偶
可行的前提 下, 减少原始问题的不可行性 。
如果
'
'
'
0m in
lk
kk
lj
lj
jj
j a
zc
a
a
zc ?
?
??
?
?
?
??
?
?
?
?
?
（最小比值原则）,则选 为换入变量，相
应的列为 主元列,主元行和主元列交叉处的
元素 为主元素 。
kx
'lka
?按主元素进行换基迭代 （ 旋转运算, 枢
运算 ）, 将主元素变成 1,主元列变成单位向
量, 得到新的单纯形表 。
继续以上步骤, 直至求出最优解 。
课后小组讨论 4 讨论对偶单纯形法中确定换入
变量的最小比值原则的依据, 给出详细的证明
过程 （ 附上必要的说明, 可以采用必要的文字
说明加上证明思路图, 主线框图等 ） 。 写出研
究报告和工作报告 。 （ 两周后交 ）
4、举例 —— 用对偶单纯形法求解 LP：
?
?
?
?
?
?
?
??
??
??
??
??
0,0
37
34
2
..
93
21
21
21
21
21
yy
yy
yy
yy
ts
yyM in W
化为
标准型 →
?
?
?
?
?
?
?
?
???
???
???
???
0,,
37
34
2
..
93
51
521
421
321
21
yy
yyy
yyy
yyy
ts
yyM a x Z
?
将三个等式约束两边分别乘以 -1，然后
列表求解如下：
-3/-1 -9/-1 --- --- ---比 值
-3 -9 0 0 00-Z
-1 -1 1 0 0
-1 -4 0 1 0
-1 -7 0 0 1
-2
-3
-3
y3
y4
y5
0
0
0
-3 -9 0 0 0
y1 y2 y3 y4 y5
cj
yj
b XBCB
--- -6/-3 -3/-1 --- ---比 值
0 -6 -3 0 06-Z
1 1 -1 0 0
0 -3 -1 1 0
0 -6 -1 0 1
2
-1
-1
y1
y4
y5
-3
0
0
-3 -9 0 0 0
y1 y2 y3 y4 y5
cj
yj
b XBCB
0 0 -1 -2 08-Z
1 0 -4/3 1/3 0
0 1 1/3 -1/3 0
0 0 1 -2 1
5/3
1/3
1
y1
y2
y5
-3
-9
0
-3 -9 0 0 0
y1 y2 y3 y4 y5
cj
yj
b XBCB
最优解是 Y*=（ 5/3,1/3,0,0,1） T，
目标函数最优值为 Wmin=-Zmax=8
思考题：
能否不要化为标准型, 直接按
极小化问题用单纯形表格迭代求解？
（ 结合课后小组讨论 4一并思考研究 ）
