《4对偶理论》由会员分享，可在线阅读，更多相关《4对偶理论（89页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章对偶原理对偶原理 窗含西岭千秋雪，门泊东吴万里船窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象对偶是一种普遍现象 2 x1 x2 x3 y1y2y3y4 甲甲乙乙丙丙丁丁材料材料 产品产品 A B C 每台每台 收益收益 2000 4000 3000 限额限额 600 400 200 300 123 123 123 123 123 123 200040003000 342600 22400 :33300 24200 ,0 MaxZxxx xxx xxx STxxx xxx x x x 假设工厂考虑不进行生产而把假设工厂考虑不进行生产而把 全部可利用的资源都让给其他全部可利用的资
2、源都让给其他 企业，工厂希望给这些资源定企业，工厂希望给这些资源定 出一个合理的价格，即使别的出一个合理的价格，即使别的 单位愿意购买，又使本工厂能单位愿意购买，又使本工厂能 得到生产这些产品所能获得的得到生产这些产品所能获得的 最大收益。最大收益。 1234 1234 1234 1234 1234 600400300200 322000 4324000 : 22343000 ,0 Minwyyyy yyyy yyyy ST yyyy y yyy 3 二、对偶问题的表达二、对偶问题的表达 （1 1）对称）对称LPLP问题的定义问题的定义 max . . 0 wb s twAc w min .
3、. 0 cx s tAxb x （2）对称对称LPLP问题的对偶问题问题的对偶问题 min . . 0 cx s tAxb x max . . 0 wb s twAc w 第一类对称形式第一类对称形式第二类对称形式第二类对称形式 (L) (D) max . . 0 TTT wb stA wc w 4 例例1 1：写出下列：写出下列LPLP问题的对偶问题问题的对偶问题 12 12 1 2 12 max23 28 416 : 412 ,0 ww ww w ST w w w 123 12 13 123 min81612 42 . .: 243 ,0 xxx xx stxx x x x 对偶 5 （3
4、 3）对偶问题的对偶）对偶问题的对偶 推导过程推导过程 变形 max . . 0 wb stwAc w min . . 0 TT TTT T b w stA wc w (D) 6 对偶 max . .() 0 TT TT x c stAxb x min . . 0 cx stAxb x 变形 min . . 0 TT TTT T b w s tA wc w 结论：对偶问题的对偶为原问题。结论：对偶问题的对偶为原问题。 (DD) 7 123 123 123 123 123 max 78 343 34 : 40 ,0 yyy yyy yyy ST yyy yyy 写出下列写出下列LPLP问题的对偶
5、问题：问题的对偶问题：例例2 2： 8 写出对称形式的对偶规划的要点：写出对称形式的对偶规划的要点： (1) min变成变成max (2) 价值系数与右端向量互换价值系数与右端向量互换 (3) 系数矩阵转置系数矩阵转置 (4) 变变 原问题中约束条件的个数原问题中约束条件的个数=对偶问题中变量的对偶问题中变量的 个数个数 原问题中变量的个数原问题中变量的个数=对偶问题中约束条件的对偶问题中约束条件的 个数个数 9 非对称形式的对偶非对称形式的对偶 min . . 0 cx stAxb x 写成对称形式写成对称形式 min . . 0 cx stAxb Axb x 对偶问题为：对偶问题为： ma
6、x . . ,0 ubvb stuAvAc u v max . . wb stwAc w 无限制 wuv令 10 例例 min 5x1+4x2+3x3 s.t. x1+x2+x3=4 3x1+2x2+x3=5 x1 0, x2 0, x3 0 对偶问题为对偶问题为 max 4w1+5w2 s.t. w1+3w25 w1+2w2 4 w1+w2 3 11 一般情形一般情形LP问题的对偶问题问题的对偶问题 min cx s.t. A1x b1A1为为m1n , b1为为m11 A2x =b2 A2为为m2n , b2为为m21 A3x b3A3为为m3n , b3为为m31 x 0 引入松弛变量引
7、入松弛变量 min cx s.t. A1x xs=b1xs为为m11 A2x=b2 A3x+xt= b3xt为为m31 x, xs, xt0 12 min cx s.t. A1x xs=b1xs为为m11 A2x=b2 A3x+xt= b3 xt为为m31 x, xs , xt0 对偶问题为对偶问题为 max w1b1+ w2b2 + w3b3 s.t. w1A1+ w2A2 + w3A3 c w1Is0 w3It0 max w1b1+ w2b2 + w3b3 s.t. w1A1+ w2A2 + w3A3 c w1 0, w3 0 11 22 33 min . . 0 cx stA xb A
8、xb A xb x 13 min max 变变0 约约 量量0 束束 无限制无限制= 方方 程程 约约 0 束束 0 变变 方方= 无限制无限制量量 程程 14 123 123 123 123 123 min 22 2 1 2 : 1 0, 0 xxx xxx xxx ST xxx xxx 无约束 123 max2www :ST 123 www 123 www 123 2www 2 1 2 1 0w 2 0w 3 w 无约束 15 直接写出直接写出LPLP问题的对偶问题问题的对偶问题 123 123 123 123 123 max2 2 1 : 2 2 0,0, xxx xxx xxx ST
9、xxx xxx 无约束 例3 123 min 22www 123 www 123 2www 123 www 1 2 1 0w 2 w 无约束 3 0w 1 :ST 16 123 123 123 123 132 min 22 21 2 : 1 0,0, xxx xxx xxx ST xxx xxx 无约束 ( )L 17 第二节第二节 对偶问题的基本性质对偶问题的基本性质 原问题原问题(L) 对偶问题对偶问题(D) min cxmax wb s.t. Ax bs.t. wA c x 0 w 0 18 (0) ( )xL由于是的可行解 定理定理1 1：弱对偶定理：弱对偶定理 (0)(0) (0)(
10、0) ,( ),()xwLD cxwb 若分别为的可行解，则 证明： (0)(0) ,0Axb x所以 (0) (D)w由于是的可行解 (0) 0w所以 (0) w 左乘不等式组的两边得 (0)(0)(0) wAxw b (0)(0) ,0wAc x又 (0)(0)(0) w Axcx所以 (0)(0) cxw b因此有 19 例： 1234 1234 1234 max234 . 22320 23220 (DLP) 0,1,2,3,4 j wwww stwwww wwww wj 12 12 min2020 . 21 xx stxx 12 22xx 12 12 12 233 324 ,0 xx
11、xx x x 1）原问题任一可行解）原问题任一可行解x=(1, 1)T （LP） 目标值目标值=40 40是是DLP问题最优目标值的上界问题最优目标值的上界. 2）对偶问题任一可行解）对偶问题任一可行解w=（1 1 1 1） 目标值目标值=10 10是是LP问题最优目标值的下界问题最优目标值的下界. * * 61 28 55 0 0 4 4 28 T x w 最优值 最优值 20 推论推论1： 若若LP(LP(或或DLP)DLP)问题有无界解，则其对偶问题问题有无界解，则其对偶问题( (或原问或原问 题题) )无可行解；无可行解； 若若LP (LP (或或DLP)DLP)问题无可行解，则对偶问
12、题问题无可行解，则对偶问题( (或原问题或原问题) ) 或者无可行解或者无可行解, ,或者目标函数值趋于无穷。或者目标函数值趋于无穷。 推论推论2 2： 极大化问题的任何一个可行解所对应的目标极大化问题的任何一个可行解所对应的目标 函数值都是其对偶问题的目标函数值的下界。函数值都是其对偶问题的目标函数值的下界。 极小化问题的任何一个可行解所对应的目标极小化问题的任何一个可行解所对应的目标 函数值都是其对偶问题的目标函数值的上界。函数值都是其对偶问题的目标函数值的上界。 推论推论3 3： 21 定理定理2 2：最优性准则：最优性准则 (0)(0) (0)(0) 00 ,( ),() (L) (D
13、) xwLD cxwb xw （ ）（ ） 若分别为的可行解且 ，则 ，分别为、问题的最优解 (0)(0)(0) 1, x cxwbcxwb 对原问题的任意可行解 由定理 可知而 证明：证明： (0) ( )xL则为的最优解 (0) ,()wD同理为的最优解 22 1234 1234 1234 1234 234 22320 : 23220 ,0 MaxZxxxx xxxx STxxxx x xx x 12 12 12 12 12 12 2020 21 22 : 233 324 ,0 MinWyy yy yy STyy yy yy ( )L ()D 例例5 5 (0) (0) (0)(0) (0,0,4,4) , 6 1 ,( ),() 5 5 28 T x yLD cxyb 由于 是的可行解 且 (0)(0) ,( ),( )xyLD所以，分别是的最优解 23 定理定理3 3：强对偶：强对偶定理定理 若若(L),(D)(L),(D)均有可行解均有可行解, ,则则(L),(D)(L),(D)均有最均有最 优解优解, ,且且(L),(D)(L),(D)的最优目标函数值相等的最优目标函数值相等. . 证明证明： (0)(0) ( ),( ),LDxw设问题的可行解
