例4-7
用对偶单纯形法求解线性规划问题.
Min z =5x1+3x2 s.t. -2 x1 + 3x2≥6 3 x1 - 6 x2≥4 Xj≥0（j=1,2） 解： 将问题转化为
Max z = -5 x1 - 3 x2 s.t. 2 x1 - 3x2+ x3 = -6 -3 x1 + 6 x2+ x4≥-4
Xj≥0（j=1,2，3,4）
其中，x3 ，x4 为松弛变量，可以作为初始基变量，单纯形表见表4-17. 表4-17 例4-7单纯形表 Cj CB 迭代0次 0 0 X4 X5 -6 -4 0 b 2 -16 6 2 -3 -5 X1 -2/3 1 -7 [-3] 6 -3 X2 1 0 0 X3 -1/3 2 -1 1 0 0 X4 0 1 0 0 1 0 XB b -6 X1 -3 X2 -4 X3 0 X4 ?z??cj?zj? CB 迭代1次 -3 0 X4 X3 XB ?z??cj?zj? 在表4-17中,b=-16<0,而y≥0,故该问题无可行解. 注意: 对偶单纯形法仍是求解原问题,它是适用于当原问题无可行基,且所有检验数均为负的情况.
若原问题既无可行基,而检验数中又有小于0的情况.只能用人工变量法求解. 在计算机求解时,只有人工变量法,没有对偶单纯形法.
3.对偶问题的最优解
由对偶理论可知,在原问题和对偶问题的最优解之间存在着密切的关系,可以根据这些关系,从求解原问题的最优单纯形表中,得到对偶问题的最优解.
(1) 设原问题(p)为
Min z=CX s.t. ??AX?b
?X?0则标准型(LP)为
Max z=CX
?AX?b s.t. ?
X?0?其对偶线性规划（D）为
Max z=bTY s.t. ??AX?b
X?0?
用对偶单纯形法求解（LP），得最优基B和最优单纯形表T（B）。对于（LP）来说，当j=n+i时，有Pj=-ei，cj=0
从而，在最优单纯形表T（B）中，对于检验数，有
（σn+1，σn+2…σn+m）=（cn+1，cn+2…，cn+m）-CBB-1（Pn +1,Pn+2…,Pn+m）=- CBB-1 (-I)
于是，Y*=（σn+1，σn+2…σn+m）T 。可见，在（LP）的最优单纯形表中，剩余变量对应的检验数就是对偶问题的最优解。
同时，在最优单纯形表T（B）中，由于剩余变量对应的系数 所以
B-1 =（-y n+1，-y n+2…-yn+m）
例4-15 求下列线性规划问题的对偶问题的最优解。 Min z =6x1+8x2 s.t. x1 + 2x2≥20
3 x1 + 2x2≥50
Xj≥0（j=1,2）
解： 将问题转化为
Max z =-6x1-8x2
s.t. -x1 — 2x2 + x3=20
-3 x1 - 2x2+ x4 =50
Xj≥0（j=1,2，3,4）
用对偶单纯形法求解如表
表4-18 例4-8单纯形表 Cj CB 迭代0次 -8 -6 X4 X5 5/2 15 -110 0 1 0 1 0 0 -3/4 1/2 3 1/4 -1/2 1 XB b -6 X1 -8 X2 0 X3 0 X4 ?z??cj?zj?
在引入松弛变量化为标准型之后，约束等式两侧同乘-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 表格对偶单纯形法
Cj CB 迭代0次 -8 -6 X4 X5 5/2 15 -110 0 1 0 1 0 0 -3/4 1/2 3 1/4 -1/2 1 XB b -6 X1 -8 X2 0 X3 0 X4 ?z??cj?zj?