最优化方法之对偶理论讲解PPT演示课件

1、最优化方法最优化方法 optimizationoptimization第七讲第七讲第四章第四章 对偶理论对偶理论 窗含西岭千秋雪，门泊东吴万里船。 -(唐)杜甫 对偶是一种普遍现象主要内容主要内容 对偶问题的形式对偶问题的形式普遍存在普遍存在 l p 对偶形式及定理对偶形式及定理 对偶问题经济解释对偶问题经济解释 对偶单纯形法对偶单纯形法 原原-对偶算法对偶算法对偶及鞍点问题对偶及鞍点问题lagrange 对偶问题对偶问题dxljxhmixgtsxfji, 1, 0)(, 1, 0)(. .)(min(1)定义定义(1)的对偶问题的对偶问题:0. .),(maxwtsvw(2)集约束集约束dx

2、xhvxgwxfvwljjjmiii11)()()(inf),(其中0. .),(maxwtsvw11( , ):( )( )( )mliijjijl x w vf xw g xv h xlagrange函数函数( , , ),( , )xdlagrangrl x w vw vw v对于任意的，函数是的线性函数，于是对偶函数作为线性函数的逐点下确界，必然是一个凹函数，所以，对偶问题是一个凸规划问题。例：考虑线性规划问题例：考虑线性规划问题1122min. .0cxstaxba xbx若取集合约束若取集合约束d=x|x0，则该，则该线性规划问题的线性规划问题的lagrange函数为函数为1122

3、1212121212( , )inf()()|inf()|00.ttttttttttttw vcxwaxbva xbxdcw av a xw bv bxdw bv bcw av acw av a若若线性规划的对偶问题为：线性规划的对偶问题为：1212max. .0ttttw bv bstw av acw0,04. .min21212221xxxxtsxx求下列非线性规划问题的对偶问题求下列非线性规划问题的对偶问题:11222212120,0 ,( )inf(4)|.xxdxxxwxxw xxxd解：把变量的非负限制作为集约束，即则.42444)(.4220|inf.4220|inf,040|i

4、nf0|inf0, 0|4inf| )4(inf)(2222222222211212222112121222121212221wwwwwwwwwwxwxxwwwwxwxxwwxwxxxwxxxxwwxxwxxdxxxwxxw时当对偶问题为对偶问题为:0. .42max2wtsww对偶定理对偶定理tltmxhxhxhxgxgxgdxxhxgtsxf)(,),()()(,),()(0)(0)(. .)(min110. .),(maxwtsvw( , )inf( )( )( )|ttw vf xw g xv h xxd定理定理1(弱对偶定理弱对偶定理)。题的可行解，则分别是原问题和对偶问和设),()

5、(),(vwxfvwx).()()()(| )()()(inf),(0, 0)(, 0)(),(xfxhvxgwxfdxxhvxgwxfvwwxhxgvwxtttt是可行解，和证明： 推论推论1:.0| ),(sup, 0)(, 0)(| )(infwvwdxxhxgxf，必有对于原问题和对偶问题推论推论2:题的最优解。分别是原问题和对偶问和，则为原问题的可行解，其中若),(0),()(vwxwxvwxf推论推论3:。，有则对若),(0, 0)(, 0)(| )(infvwwdxxhxgxf推论推论4:sup( , )|0w vw 如果，则原问题没有可行解。对偶间隙：对偶间隙：minmaxin

6、f( )| ( )0, ( )0,=sup( , )|0f xg xh xxdfw vw记记minmax0f问题问题：0. 成立的条件lp 对偶问题的表达对偶问题的表达（1 1）对称）对称lplp问题的定义问题的定义m in. .0tcxs ta xbx（2）对称对称lplp问题的对偶问题问题的对偶问题(p)(d)max. .0ttb ws ta wcw例：写出下列例：写出下列lplp问题的对偶问题问题的对偶问题12121212max2328416. . 412,0wwwwws twww1231213123min8161242. 243,0 xxxxxstxxx x x对偶例：写出对偶问题例：

7、写出对偶问题(d)的对偶的对偶变形(d)min. .0ttb ws ta wcw max. .0ttb ws ta wcw对偶max. .()0tttc xs taxbx m in. .0tc xs taxbx变形结论结论：对偶问题：对偶问题(d)的对偶的对偶 为原问题为原问题(p) 。(dd)minmin变成变成max max 价值系数与右端向量互换价值系数与右端向量互换系数矩阵转置系数矩阵转置 变变 原问题中约束条件的个数原问题中约束条件的个数= =对偶问题中变量的个数对偶问题中变量的个数原问题中变量的个数原问题中变量的个数= =对偶问题中约束条件的个数对偶问题中约束条件的个数写出对称形式

8、的对偶规划的要点写出对称形式的对偶规划的要点非对称形式的对偶非对称形式的对偶min. .0tc xs taxbx对称形式对称形式m in. . 0tcxs ta xba xbx 对偶对偶max.,0ttttb u b vsta ua vcu vmax. .ttb ws ta wcw无 限 制wuv令(p)(d)例例 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 3112233min.0where ,1,2,3.ii

9、tmm nniic xstax bax bax bxc r brari31112233min. . ,0where , are slack variables.tststmmstc xsta xxba xba xxbx x xxrxr一般情形一般情形lplp问题的对偶问题问题的对偶问题标准形标准形对偶对偶112233112233123max . . , 0, free, 0. ttttttb wb wb wsta wa wa wcwww变量变量约束约束约束约束变量变量123123123123123min 22 2 1 2. . 1 0, 0 xxxxxxxxxs txxxxxx无约束123ma

10、x2www. st123www123www1232www21210w 20w 3w 无约束123123123123123max2 2 1:2 20,0,xxxxxxxxxstxxxxxx无约束123min 22www123www1232www123www1210w 2w 无约束30w 1. st123123123123132min 22212. . 10,0,xxxxxxxxxstxxxxxx无约束练习题练习题lp对偶问题的基本性质对偶问题的基本性质原问题原问题(p)对偶问题对偶问题(d)m in. .0tcxs ta xbxm a x. . 0ttbws tawcw定理定理1(1(弱对偶定理

11、弱对偶定理) )(0)(0)(0)(0),( ),( ).ttxwpdc xb w若分别为的可行解，则(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(),0.(),0,().ttttpabdcab证明：因x是的可行解，故xx因w是的可行解，故a ww从而c xxww例：123412341234max 234 . 22320 ( 1)23220 0,1,2,3,4 jwwwwstwwwwwwwwwjd1212min2020. 21xxstxx1222xx121212233324,0 xxxxx x1）原问题）原问题(p1)一可行解一可行解 x=(1, 1)t(p1)目标值目标值 =

12、4040是是(d1)最优目标值的上界最优目标值的上界.2）对偶问题）对偶问题(d1)一可行解一可行解 w=（1 1 1 1） 目标值目标值 =10 10是是(p1)最优目标值的下界最优目标值的下界. *61 28550 0 4 4 28txw最优值最优值推论推论1推论推论2 2极大化问题的任何一个可行解所对应的目标极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的下界。函数值都是其对偶问题的目标函数值的下界。极小化问题的任何一个可行解所对应的目标极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的上界。函数值都是其对偶问题的目标函数值的上界。推论推论3

13、 3若问题若问题(p)或或(d)有无界解，则其对偶问题有无界解，则其对偶问题(d)或或(p)无可行解；无可行解； 若问题若问题(p)或或(d)无可行解，则其对偶问题无可行解，则其对偶问题(d)或或(p)或者无可行解或者无可行解, ,或者目标函数值趋于无穷。或者目标函数值趋于无穷。定理定理2(2(最优性准则最优性准则) )(0 )(0 )(0 )(0 )00,(), ()(p) (d)xwpdcxwbxw（ ）（ ）若分 别 为的 可 行 解 且，则，分 别 为,问 题 的 最 优 解 .(0)(0)(0)(0),1,(),ttttxc xbpwc xb wx对原问题(p)的任意可行解由定理 可

14、则为的知而最优解.证明：证明：(0),()wd同理为的最优解1234123412341234max 23422320. . 23220,0zxxxxxxxxs txxxxx xxx121212121212min 20202122. . 233324,0wyyyyyys tyyyyyy( )p()d例例(0)(0)(0)(0)(0,0,4,4) ,6 1,(),()5 528ttttxypdc xb y由于是的可行解且(0)(0),( ),( )xypd所以，分别是的最优解定理定理3(3(强对偶强对偶定理定理)若若(p),(d)(p),(d)均有可行解均有可行解, ,则则(p),(d)(p),(

15、d)均有最优解均有最优解, ,且且(p),(d)(p),(d)的最优的最优目标函数值相等目标函数值相等. .证明：因为证明：因为(p),(d)(p),(d)均有可行解均有可行解, ,由推论由推论2,2,推论推论3 3知知,(p),(p)的目标的目标函数值在其可行域内有下界函数值在其可行域内有下界, (d), (d)的目标函数值在其可行域内的目标函数值在其可行域内有上界有上界, , 故则故则(p),(d)(p),(d)均有最优解均有最优解. .引入剩余变量，把引入剩余变量，把(p)(p)化为标准形化为标准形: :m in (, 0 ). .(,)0 ,0tsssxcxxs taibxxx(0)(

16、).pxb设的最优解为，所对应的最优基为(0)1(0)(0)(0)0bnxbbxxx可以表示为1(,)()( ,0)0ttbaibcc则(0)1),(tbwbc令由上式得(0)(0)(0),0,()ta wc wwd故是的可行解.(0)(0)(01)()btttttbbb wbcc xcbx又因为(0 )(0 )(0 )()m inm ax.ttttwdcxcxb wb w故是的 最 优 解 ， 且推论推论在用单纯形法求解在用单纯形法求解lplp问题（问题（p p）的最优单纯）的最优单纯形表中松弛变量的检验数的相反数形表中松弛变量的检验数的相反数( (单纯形单纯形乘子乘子w= =(b-1)tc

17、b) )就是其对偶问题（就是其对偶问题（d d）的最优解）的最优解. .由于由于(p)(p)化成标准形式时化成标准形式时, ,松弛变量松弛变量x xn n+ +j j 对应的列为对应的列为- -e ej j，它在目标函数中的价格系数，它在目标函数中的价格系数，所以，判别数为所以，判别数为 (b(b-1-1) )t tc cb b(-(-e ej j)-0=-)-0=-w wj j则松弛变量对应的判别数均乘以则松弛变量对应的判别数均乘以(-1)(-1)，便得到单纯，便得到单纯形乘子形乘子w w=(=(w w1 1,w wm m).). 当原问题达最优时当原问题达最优时, ,单纯形乘子即为对偶问题

18、的最优解单纯形乘子即为对偶问题的最优解. .解：化为标准形：化为标准形121231425max 23284164120,1,2,3,4,5jxxxxxxxxxxj例例: : 求下列问题之对偶问题的最优解求下列问题之对偶问题的最优解12121212max2328416. .412,0 xxxxxs txx xx1 x2 x3 x4 x5 1 2 1 0 04 0 0 1 00 4 0 0 1-2 -3 0 0 0 x3x4x58161201 0 1 0 -1/24 0 0 1 00 1 0 0 1/4-2 0 0 0 3/4x3x4x22163941x1 x2 x3 x4 x5 1 0 1 0

19、-1/20 0 -4 1 20 1 0 0 1/40 0 2 0 -1/4x1x4x22831321 0 0 1/4 00 0 -2 1/2 10 1 1/2 -1/8 00 0 3/2 1/8 0 x1x5x244214此时达到最优解。此时达到最优解。x* *=(4,2), maxz=14=(4,2), maxz=14。12121212max2328416. .412,0 xxxxxs txxx1231213123min81612. .42243,0wwws twwwww ww(p)(d)31, 0 ,14.28w(d)最优解为：最优值小结小结原问题原问题(min) 对应关系对应关系 对偶问

20、题对偶问题(max) 有最优解有最优解无界解不可行不可行无界解1212112212 max . . 1 (d) -1 ,0ywwstwwlwwlw w （无可行解）（无可行解）1212112212min . . 1 (p) -1 ,0zxxstxxlxxlx x 例1:（无可行解）（无可行解）w1w2l2l1x1x2l1l21212112212 max . . 1 (p) 1 ,02zxxstxxlxxlx x例 ： （无界解）（无界解）1212112212 min . . 1 (d) 1 ,0wyystyylyyly y （无可行解）（无可行解）l2x1x2l1zy1y2l1l2定理定理4

21、4（互补松驰定理）（互补松驰定理）0000 xwpdxwpd（ ）（ ）（ ）（ ）设，分别为（ ），（）问题的可行解则，分别为（ ），（）的最优解的充要条件是(0)(0)0,jjjxwpc若则(1)(2)(0)(0),0jjjwpcx若则(3)()(0)0,iiiwaxb若则(4)(0)(0),0iiiaxbw若则, (1,1),i jimjn 有.jipajaai其中 是 的第 列， 是 的第 行(0)(0)()0cwa x(0)(0)()0waxb11( )*,*,* 0;(1)0,0,0;(2)(*) 0,*ker()0.(3)mnttttlxwraxbxca w rwrw akaru

22、sh kuhn tuckktxbr x （）对于线性规划来说， 是其最优解，当且仅当存在向最优性条件定理量条件，使得证明：（必要性）证明：（必要性）(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)( )()0,0,()0,() 0.xwpdaxbxwa cwwaxwbwaxcxcxwaxwbxwcxwb cxwaxwbc wa xwaxb 设和分别是和的最优解，则且故有即因为是最有解 所以有所以，即，且 证明：（充分性）证明：（充分性）(0)(0)(0)(0)(0)(0)(0

23、)(0)(0)(0)(0)(0)(0)(0)()0,() 02,( )().c wa xcxwaxwaxbwaxwbcxwbxwpd 由得由， 得因此有由定理 知，为和的最优解定理定理44：互补松驰定理：互补松驰定理( (非对称形式）非对称形式）(0)(0)tt(0)(0)(0)(0)(0)(0)minmax. . .0(1)0,(2)0.tjjjjjjxwc xb wstaxbsta wcxxwjxwpcwpcx设和分别是和的可行解，则和是最优解的充要条件时，对任意的 ，下列关系成立：若则；若，则12341234123412342342232 0. .2322 0,0m a xzxxxxxx

24、xxs txxxxxxxx12121212121220202122. .233324,0m inwyyyyyys tyyyyyy( )p()d例例: : 考虑下面问题考虑下面问题*6 1(),5 5( )dyp已知的最优解为用互补松弛定理求出的最优解解解:*120 ,0yy由 于4由 定 理知*123422320(1)xxxx*12342322 0(2 )xxxx*11yy*12yy*342320 xx*343220 xx*344xx则( )p所以问题的最优解为*(0, 0, 4, 4)x*1201xx ，代入（），（2）12121212121220

25、202122: 233324,0minwyyyyyystyyyyyy1 1、定义、定义对偶问题的经济学解释：影子价格对偶问题的经济学解释：影子价格(自学自学)影 子 价 格 是 最 优 配 置 下 资 源 的 理 想 价 格*1122mmfcxw bw bw bw b由 于12,mb bb假设是变化的，则2 2、含义、含义*1212,mmfffwwwbbb*1( )iiwbp可以理解成当资源 变化 单位时，极小化问题的目标函数值的变化量考虑在最优解处考虑在最优解处,右端项右端项bi的微小变动对目标函数值的影响的微小变动对目标函数值的影响. 若把原问题的约束条件看成是广义的资源约束若把原问题的约

26、束条件看成是广义的资源约束, ,则右端则右端项的值表示每种资源的可用量项的值表示每种资源的可用量. . 对偶解的经济含义对偶解的经济含义: :资源的单位改变量引起目标函数值资源的单位改变量引起目标函数值的增加量的增加量. . 通常称对偶解为影子价格通常称对偶解为影子价格. . 影子价格的大小客观地反映了资源在系统内的稀缺程度影子价格的大小客观地反映了资源在系统内的稀缺程度. .资源的影子价格越高资源的影子价格越高, ,说明资源在系统内越稀缺说明资源在系统内越稀缺, ,而增加而增加该资源的供应量对系统目标函数值贡献越大该资源的供应量对系统目标函数值贡献越大. . 木门木门 木窗木窗木工木工 4小

27、时小时 3小时小时 120小时小时/日日油漆工油漆工 2小时小时 1小时小时 50小时小时/日日收入收入 56 30解：设该车间每日安排解：设该车间每日安排 x1 x2 x3 x4生产木门生产木门x1扇，木窗扇，木窗x2 x3 4 3 1 0 120max z=56 x1 +30 x2 x4 2 1 0 1 50 s.t. 4 x1 +3 x2120 -56 -30 0 0 0 2 x1 + x2 50 x3 0 1 1 -2 20 x1 x2 0 x1 1 1/2 0 1/2 25 0 -2 0 28 1400 x2 0 1 1 -2 20 x1 0 0 -1/2 -1/2 15 0 0 2

28、 24 1440对偶问题的解为对偶问题的解为:w*=(2, 24) （2 2）告诉管理者花多大代价购买进资源或卖出资源是合适的）告诉管理者花多大代价购买进资源或卖出资源是合适的 3 3、影子价格的作用、影子价格的作用（1 1）告诉管理者增加何种资源对企业更有利）告诉管理者增加何种资源对企业更有利 （3）为新产品定价提供依据）为新产品定价提供依据对偶单纯形法对偶单纯形法 定义：设定义：设x(0)是是(p)的一个的一个基本解基本解（不一定是可行（不一定是可行解），它对应的矩阵为解），它对应的矩阵为b，记，记w=cbb-1，若，若w是是(p)的对偶问题的可行解，即对任意的的对偶问题的可行解，即对任意

29、的j, wpj-cj 0，则，则称称x(0)为原问题的为原问题的对偶可行的基解对偶可行的基解。 结论：当对偶可行的基解是原问题的可行解时，结论：当对偶可行的基解是原问题的可行解时，由于判别数由于判别数0，因此，它就是原问题的最优解。，因此，它就是原问题的最优解。1231234123512345min. .3142,0 xxxs txxxxxxxxxxxxx1212121212m ax2. .3141111wws twwwwwwww 000012tx1111000bc bac 所以，所以，x(0)为对偶可行的基解。为对偶可行的基解。基本思想：基本思想： 从原问题的一个对偶可行的基解出发；从原问题

30、的一个对偶可行的基解出发； 求改进的对偶可行的基解：每个对偶可行的基解求改进的对偶可行的基解：每个对偶可行的基解x=(xbt,0)t对应一个对偶问题的可行解对应一个对偶问题的可行解w=cbb-1，相应的对偶问题的目标函数值为相应的对偶问题的目标函数值为wb=cbb-1b，所，所谓改进的对偶可行的基解，是指对于原问题的这谓改进的对偶可行的基解，是指对于原问题的这个基解，相应的对偶问题的目标函数值个基解，相应的对偶问题的目标函数值wb有改进有改进（选择离基变量和进基变量，进行（选择离基变量和进基变量，进行主元消去主元消去）；）； 当得到的对偶可行的基解是原问题的可行解时，当得到的对偶可行的基解是原

31、问题的可行解时，就达到最优解。就达到最优解。与原单纯形法的区别：与原单纯形法的区别： 原单纯形法保持原问题的可行性，对偶单纯形原单纯形法保持原问题的可行性，对偶单纯形法法保持所有检验数保持所有检验数wpj-cj 0，即保持对偶问题，即保持对偶问题的可行性。的可行性。 特点：先选择出基变量，再选择进基变特点：先选择出基变量，再选择进基变 量。量。120b b、判断，若，则已得到最优解3、换基迭代、换基迭代 1min0,riribbx）确定换出变量，为换出变量.1、 化标准型化标准型,建立初始单纯形表建立初始单纯形表2min0,jjkkrjkjrjrkzczcyxyy）确定换入变量，为换入变量.3rky）换基迭代