第三章对偶理论 §1对偶问题的提出 回顾对第一章§1例3营养问题 食物 各种营养的最 营养成分 n 低要求 bi 单价 的分析,得到如下形式的线性规划问题 AX≥b > 现在从另一个角度提出问题: 设有一个制造商,要生产m种不同的药丸来代替上述n种不同的食物,试问每种药丸 的价格如何确定,才能获利最大 仍可利用上面的表格,设第i种药丸的价格是w;,并记W=(w1,…,m)为了达到畅 销的目的,药丸的价格当然不宜超过与之相当的食物的价格,即应有WA≤C,于是问题变 成 MA≤C (DW≥0 I max wb 据此我们得到如下定义 1°、称(L)和(D所规定的线性规划问题是互为对偶问题。若其一叫原问题,则另一叫对 偶问题,也称它们构成一组对称的对偶规划 20、对于标准形的线性规划问题 AX= b (LX≥b CX 考虑 MA≤C (L)和(D)叫作一组非对称的对偶规划 以下证明,对称对偶规划与非对称对偶规划是可以互相推出的 由对称情形推出非对称情形
91 第三章 对偶理论 §1 对偶问题的提出 回顾对第一章§1 例 3 营养问题 食物 营养成分 x1 x2 xn 1 2 n 各种营养的最 低要求 w1 1 w2 2 ┇ wm m a11 a12 … a1n a21 a22 … a2n … … am1 am2 … amn b1 b2 ┇ bm 单价 C1 C2 … Cn 的分析，得到如下形式的线性规划问题： CX X AX b L min ( ) 0 现在从另一个角度提出问题： 设有一个制造商，要生产 m 种不同的药丸来代替上述 n 种不同的食物，试问每种药丸 的价格如何确定，才能获利最大。 仍可利用上面的表格，设第 i 种药丸的价格是 wi ，并记 ( , , ) W = w1 wm 为了达到畅 销的目的，药丸的价格当然不宜超过与之相当的食物的价格，即应有 WA C ，于是问题变 成 Wb W WA C D max ( ) 0 据此我们得到如下定义： 1 0、称(L)和(D)所规定的线性规划问题是互为对偶问题。若其一叫原问题，则另一叫对 偶问题，也称它们构成一组对称的对偶规划。 2 0、对于标准形的线性规划问题 = CX X b AX b L min ( ) 考虑 Wb WA C D max ( ) (L) 和 (D) 叫作一组非对称的对偶规划。 以下证明，对称对偶规划与非对称对偶规划是可以互相推出的。 由对称情形推出非对称情形
AX≤b 因AX=b AX≥b 故(L’)可变成 X≥0 min CX 此为(L)型按定义其对偶规划应为 (W1, C H,W2)20 max(WI, W2 W-W)A≤C (W1,W2)≥0 max(W1-W2)b 令W”=1-2,则W已无非负限制,从而上式变成 WA≤C max w b 这便是(D)的形式,说明(L)的对偶规划确为(D)。 反之,设(L)的对偶是(D),可证(L)的对偶是(D) 对(L)引入剩余变量y=(y,…,yn)≥0,将其化成标准形式: X≥0,y≥0 X min( C,0 从而其对偶问题具形式:
92 因 = AX b AX b AX b 故 (L) 可变成: − − CX X b b X A A min 0 此为(L)型,按定义其对偶规划应为 − − b b W W W W C A A W W max( , ) ( , ) 0 ( , ) 1 2 1 2 1 2 即 − − W W b W W W W A C max( ) ( , ) 0 ( ) 1 2 1 2 1 2 令 1 2 * W = w − w ，则 * W 已无非负限制，从而上式变成 W b W A C * * max 这便是 (D) 的形式，说明 (L) 的对偶规划确为 (D) 。 反之，设 (L) 的对偶是 (D) ，可证(L)的对偶是(D)。 对(L)引入剩余变量 ( , , ) 0, = 1 T m Y y y 将其化成标准形式： = − Y X C X Y b Y X A I min( ,0) 0, 0 ( , ) 从而其对偶问题具形式：
W(A,-D)≤(C,0) max wb 此即 W≥0 max Wb 它恰为D) 除此之外,还有将两种情形结合起来的混合型对偶规划,例如设 A A12 A21A2 其中A为mxn阶矩阵i=12。m+m2=mm1+n2=n,x,X2分别为n,n2维向量 若原问题为 A,X1+A,、X2≥b Ax+Ax2=b X≥0,X2无限制 min(C X+C x) 则它的对偶规划为 A2+W22=C2 1≥0,W2无限制 max(wb+wb) 综上,我们可以总结出构成一般对偶规划的规则如下: (i)把原问题的约束条件统一成≥及=(或≤及=),目标函数改写成求极小(或极大)。 (i)原问题的一个行约束对应一个变量w;,若行约束是不等式,则v1≥0,否则v无符 号限制。 (ⅲi)原问题每个变量x,对应一个行约束:若x,≥0, 则对应∑wn≤c(或∑wa≥c)若x无限制,则对应∑wan=c1(c,是原问 题目标函数x,的系数)。 (ⅳv)原目标函数CX若为求极小(极大),则对应目标函数Wb求极大(极小)(这里 b是原问题约束中的常数项列) 例1原问题
93 − Wb W A I C max ( , ) ( ,0) 此即 Wb W WA C max 0 它恰为(D)。 除此之外，还有将两种情形结合起来的混合型对偶规划，例如设 = = 2 1 21 22 11 12 , x x X A A A A A 其中 Aij 为 mi n j 阶矩阵 i,j=1,2。m1 + m2 = m,n1 + n2 = n， 1 2 X , X 分别为 1 2 n ,n 维向量。 若原问题为 + + = + min( ) 0, 1 1 2 2 1 2 2 2 22 1 21 2 1 12 1 11 C X C X X X A X A X b A X A X b 无限制 则它的对偶规划为 + + = + max( ) 0, 1 1 2 2 1 2 2 22 2 12 1 1 21 2 11 1 W b W b W W W A W A C W A W A C 无限制 综上，我们可以总结出构成一般对偶规划的规则如下： （ⅰ）把原问题的约束条件统一成 及=（或 及=），目标函数改写成求极小（或极大）。 （ⅱ）原问题的一个行约束对应一个变量 wi ，若行约束是不等式，则 wi 0 ，否则 wi 无符 号限制。 （ⅲ）原问题每个变量 j x 对应一个行约束：若 x j 0 ， 则对应 ij j m i i w a c =1 （或 ij j m i i w a c =1 ），若 j x 无限制，则对应 ij j m i i w a = c =1 （ j c 是原问 题目标函数 j x 的系数）。 （ⅳ）原目标函数 CX 若为求极小（极大），则对应目标函数 Wb 求极大（极小）（这里 b 是原问题约束中的常数项列）。 例 1 原问题
6x1-3x2 x4 28x1-17x,+4x3+2x4≤-3 x1≥0, 0 无限制 mn5x1-6x2+7x3+4x4 把不等式统一成≥,再列成下表: 4=fmin x1≥0,x,≥0,x2,x4无限制 据此可直接写出对偶规划 1+6,+283≤5 2w1-32+17v3≤-6 7 W1无限制,w2,w3≥0 max-7w1+14w2+3 §2对偶定理 对于原问题和它的对偶问题的关系有以下几个定理,它们在理论和应用中都是很重要 定理1(L)和(D),(L)和(D)同时有最优解的充要条件是同时有可行解 证明只需证充分性,设(L)和(D)分别有可行解X和W°,既有 AX0≥b,X°≥0,W°A≤C,W0≥0。于是对(L)的任一可行解X,有 CX≥W0AX≥W"b 即CX在可行解集合有下界W%b,从而在基可行解的集合上有下界,由于基可行解是有限 的故必于某点X·达到其下界,再根据X的典式。其检验数λ,或者全小于等于0,或者经 过若干次迭代后,变得小于等于0,但目标函数值仍为CX”,从而由单纯法的理论,知X 即为最优解,这便证明了(L)有最优解 同样对D的任一可行解集W,有
94 − + + − − + + − − + − + − − = − 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 min 5 6 7 4 0, 0, , 28 17 4 2 3 6 3 7 14 2 7 x x x x x x x x x x x x x x x x x x x x 无限制 把不等式统一成 ，再列成下表： x1 x2 x3 x4 w1 w2 w3 1 2 -1 -1=-7 6 -3 1 -7 14 28 17 -4 -2 3 5 -6 7 4 = f min 1 2 3 4 x 0, x 0, x , x 无限制 据此可直接写出对偶规划： − + + − − − = − + − = − + − + + 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 max 7 14 3 , , 0 7 2 4 4 7 2 3 17 6 6 28 5 w w w w w w w w w w w w w w w w w w 无限制 §2 对偶定理 对于原问题和它的对偶问题的关系有以下几个定理，它们在理论和应用中都是很重要 的。 定理 1 （L）和（D）， (L) 和 (D) 同时有最优解的充要条件是同时有可行解。 证 明 只 需 证 充 分 性 ， 设 （ L ）和（ D ） 分 别 有 可 行 解 0 0 X 和W ，既有 , 0; , 0 0 0 0 0 AX b X W A C W 。于是对（L）的任一可行解 X，有 CX W AX W b 0 0 即 CX 在可行解集合有下界 W b 0 ，从而在基可行解的集合上有下界，由于基可行解是有限 的故必于某点 * X 达到其下界，再根据 * X 的典式。其检验数 j 或者全小于等于 0，或者经 过若干次迭代后，变得小于等于 0，但目标函数值仍为 CX ，从而由单纯法的理论，知 X 即为最优解，这便证明了（L）有最优解。 同样对 D 的任一可行解集 W，有
Wb≤WAX0≤CX0 故Wb在可行解集合有上界CX°,从而类似可证(D)有最优解。 推论若X0和W0分别是(L)和(D)的可行解,且CX0=W°b,则它们分别是(L) 和(D)的最优解 同理可证结论对(L)和(D)成立 CF≥W0AX=W%b Wb=WAX0≤CX0 定理2设(L)和(D)(或(L)和(D))中一个有最优解,则另一个也一定有最优解, 且目标函数值相同。 证明设(L)有最优解,引入剩余变量Y则(L)可化为标准形式 (A,-1 X≥0,y≥0 X min( C,o) 运用单纯形法可求得最优解X°,X0是基可行解,对应于某一基B,据最优判别准则有 CB-(A-1)≤(C0) 令W0=CB-,上式可变成 WA≤C W0≥0 故W0是(D)的可行解,又因 Wb=CB-b=C XD=C 故由定理1的推论知W是(D)的最优解,且 min CX=w b= max wb 反之,设(D)有最优解,将(D)化成标准形式:
95 0 0 Wb WAX CX 故 Wb 在可行解集合有上界 0 CX ，从而类似可证（D）有最优解。 推论 若 0 X 和 0 W 分别是（L）和（D）的可行解，且 CX W b 0 0 = ，则它们分别是（L） 和（D）的最优解。 同理可证结论对 (L) 和 (D) 成立： 0 0 0 0 Wb WAX CX CX W AX W b = = 定理 2 设（L）和（D）（或 (L) 和 (D) ）中一个有最优解，则另一个也一定有最优解， 且目标函数值相同。 证明 设（L）有最优解，引入剩余变量 Y 则（L）可化为标准形式： = − Y X C X Y b Y X A I min( ,0) 0, 0 ( , ) 运用单纯形法可求得最优解 0 X ， 0 X 是基可行解，对应于某一基 B，据最优判别准则有 ( , ) ( ,0) 1 CB B A −I C − 令 0 −1 W = CB B ，上式可变成 0 0 0 W W A C 故 0 W 是（D）的可行解，又因 0 1 0 0 W b = CB B b = CB XB = CX − 故由定理 1 的推论知 0 W 是（D）的最优解,且 min CX W b max Wb 0 = = 反之，设（D）有最优解，将（D）化成标准形式：