用对偶单纯形法求解线性规划问题.docx

用对偶单纯形法求解线性规划问题.docx例4-7
用对偶单纯形法求解线性规划问题.
Min z =5x
1 +3x2
. -2 x
1 + 3x 2 ≥ 6
-3
X4
2
-2/3
1
-1/3
0
0
X
-16
1
0
2
1
3
z
cj
z j
6
-7
0
-1
0
在表 4-17
中 ,b=-16<0,
而 y≥0, 故该问题无可行解 .
注意 :
对偶单纯形法仍是求解原问题
, 它是适用于当原问题无可行基
, 且所有检验数均为负
的情况 .
若原问题既无可行基
, 而检验数中又有小于
0 的情况 . 只能用人工变量法求解 .
在计算机求解时 , 只有人工变量法 , 没有对偶单纯形法 .
3. 对偶问题的最优解
由对偶理论可知 , 在原问题和对偶问题的最优解之间存在着密切的关系
, 可以根据这些关系 ,
从求解原问题的最优单纯形表中
, 得到对偶问题的最优解 .
(1) 设原问题 (p) 为
Min z=
CX
AX b
.
X 0
则标准型 (LP) 为
Max z= CX
AX b
.
X 0
其对偶线性规划（ D）为
Max z= bTY
AX
b
.
0
X
用对偶单纯形法求解（
LP），得最优基 B 和最优单纯形表
T（B）。对于（ LP）来说，当 j=n+i
时，有 Pj=-e i ， cj =0
从而，在最优单纯形表
T（ B）中，对于检验数，有
（σ n+1，σ n+2 σ n+m）=（ cn+1， cn+2 ， cn+m） -CBB-1 （ Pn
B -1
(-I)
+1,Pn+2 ,Pn+m） =- C B
于是， 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
. x
1 + 2x 2 ≥ 20
3 x
1
+ 2x
2 ≥50