文档介绍：38修正39对偶
（4） 计算：
（5） 形成变换矩阵：
Ers
（6） 计算：
以 代 ，以 … + amn ym ≥ cn
y1 ， y2 ，… ，ym ≥ 0
一对对称形式的对偶规划之间具有下面的对应关系。原问题记为LP,对偶问题记为DP
LP问题为目标最大化，DP问题为最小化;
LP问题的约束为“≤”,DP问题的约束为“≥”;
LP的价值系数ci ,在DP问题中恰好为约束右端项;
LP的约束右端项bi ,在DP问题中恰好为价值系数;
LP中的每个约束条件对应着DP问题中的一个变量,而LP中的每个决策变量对应着DP问题中的一个约束;
Max z = c1 x1 + c2 x2 + … + cn xn
. a11 x1 + a12 x 2 + … + a1n xn ≤ b1
a21 x1 + a22 x2 + … + a2n xn ≤ b2
…… ……
am1 x1+ am2 x2 + … + amn xn ≤ bm
x1 ，x2 ，… ，xn ≥ 0
Min f = b1y1 + b2 y2 + … + bn ym
. a11 y1 + a21 y2 + … + am1 ym ≥ c1
a12 y1 + a22 y2 + … + am2 ym ≥c2
…… ……
a1n y1 + a2n y2 + … + amn ym ≥ cn
y1 ， y2 ，… ，ym ≥ 0
1)
2)
3)
4)
5)
(LP) Max z = CTX
. AX ≤ b
X ≥ 0
Max z = c1 x1 + c2 x2 + … + cn xn
. a11 x1 + a12 x 2 + … + a1n xn ≤ b1
a21 x1 + a22 x2 + … + a2n xn ≤ b2
…… ……
am1 x1+ am2 x2 + … + amn xn ≤ bm
x1 ，x2 ，… ，xn ≥ 0
Max f = b1y1 + b2 y2 + … + bm ym
. a11 y1 + a21 y2 + … + am1 ym ≥ c1
a12 y1 + a22 y2 + … + am2 ym ≥c2
…… ……
a1n y1 + a2n y2 + … + amn ym ≥ cm
y1 ， y2 ，… ，ym ≥ 0
LP与DP的矩阵的形式
(DP) Min f = bT y
. AT y ≥ C
y ≥ 0
(2)非对称形式的对偶关系
Max z = 2x1 + 4 x2
. x1 + x 2 = 1
-3x1 + 2 x2 ≤ 3
x1 , x 2 ≥0
Max z = 2x1 + 4 x2
. x1 + x 2 ≤ 1
-x1 - x2 ≤ 1
-3x1 + 2 x2 ≤ 3
Min y1 - y2 +3y3
. y1 - y2 - 3y3 ≥ 2
y1 - y2 +2y3 ≥ 4
y1 , y2 ,y3, ≥ 0
令 y1 - y2 = y4
Min y4 +3y3
. y4 - 3y3 ≥ 2
y4 +2y3 ≥ 4
y3 ≥ 0
若LP问题的某个约束条件为等式约束，则在对偶DP问题中与此约束对应着一个变量且那个变量取值无非负限制；