用对偶单纯形法求解线性规划问题.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