1、最優(yōu)化方法最優(yōu)化方法 OptimizationOptimization第七講第七講第四章第四章 對偶理論對偶理論 窗含西嶺千秋雪，門泊東吳萬里船。 -(唐)杜甫 對偶是一種普遍現(xiàn)象主要內(nèi)容主要內(nèi)容 對偶問題的形式對偶問題的形式普遍存在普遍存在 L P 對偶形式及定理對偶形式及定理 對偶問題經(jīng)濟解釋對偶問題經(jīng)濟解釋 對偶單純形法對偶單純形法 原原-對偶算法對偶算法對偶及鞍點問題對偶及鞍點問題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函數(shù)函數(shù)( , , ),( , )xDLagrangrL x w vw vw v對于任意的，函數(shù)是的線性函數(shù)，于是對偶函數(shù)作為線性函數(shù)的逐點下確界，必然是一個凹函數(shù)，所以，對偶問題是一個凸規(guī)劃問題。例：考慮線性規(guī)劃問題例：考慮線性規(guī)劃問題1122min. .0cxstAxbA xbx若取集合約束若取集合約束D=x|x0，則該，則該線性規(guī)劃問題的線性規(guī)劃問題的Lagrange函數(shù)為函數(shù)為1122

3、1212121212( , )inf()()|inf()|00.TTTTTTTTTTTTw vcxwAxbvA xbxDcw Av A xw bv bxDw bv bcw Av Acw Av A若若線性規(guī)劃的對偶問題為：線性規(guī)劃的對偶問題為：1212max. .0TTTTw bv bstw Av Acw0,04. .min21212221xxxxtsxx求下列非線性規(guī)劃問題的對偶問題求下列非線性規(guī)劃問題的對偶問題: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(弱對偶定理弱對偶定理)。題的可行解，則分別是原問題和對偶問和設(shè)),()

5、(),(vwxfvwx).()()()(| )()()(inf),(0, 0)(, 0)(),(xfxhvxgwxfDxxhvxgwxfvwwxhxgvwxTTTT是可行解，和證明： 推論推論1:.0| ),(sup, 0)(, 0)(| )(infwvwDxxhxgxf，必有對于原問題和對偶問題推論推論2:題的最優(yōu)解。分別是原問題和對偶問和，則為原問題的可行解，其中若),(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變形結(jié)論結(jié)論：對偶問題：對偶問題(D)的對偶的對偶 為原問題為原問題(P) 。(DD)minmin變成變成max max 價值系數(shù)與右端向量互換價值系數(shù)與右端向量互換系數(shù)矩陣轉(zhuǎn)置系數(shù)矩陣轉(zhuǎn)置 變變 原問題中約束條件的個數(shù)原問題中約束條件的個數(shù)= =對偶問題中變量的個數(shù)對偶問題中變量的個數(shù)原問題中變量的個數(shù)原問題中變量的個數(shù)= =對偶問題中約束條件的個數(shù)對偶問題中約束條件的個數(shù)寫出對稱形式

8、的對偶規(guī)劃的要點寫出對稱形式的對偶規(guī)劃的要點非對稱形式的對偶非對稱形式的對偶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對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)原問題原問題(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)最優(yōu)目標值的上界最優(yōu)目標值的上界.2）對偶問題）對偶問題(D1)一可行解一可行解 w=（1 1 1 1） 目標值目標值 =10 10是是(P1)最優(yōu)目標值的下界最優(yōu)目標值的下界. *61 28550 0 4 4 28Txw最優(yōu)值最優(yōu)值推論推論1推論推論2 2極大化問題的任何一個可行解所對應(yīng)的目標極大化問題的任何一個可行解所對應(yīng)的目標函數(shù)值都是其對偶問題的目標函數(shù)值的下界。函數(shù)值都是其對偶問題的目標函數(shù)值的下界。極小化問題的任何一個可行解所對應(yīng)的目標極小化問題的任何一個可行解所對應(yīng)的目標函數(shù)值都是其對偶問題的目標函數(shù)值的上界。函數(shù)值都是其對偶問題的目標函數(shù)值的上界。推論推論3

13、 3若問題若問題(P)或或(D)有無界解，則其對偶問題有無界解，則其對偶問題(D)或或(P)無可行解；無可行解； 若問題若問題(P)或或(D)無可行解，則其對偶問題無可行解，則其對偶問題(D)或或(P)或者無可行解或者無可行解, ,或者目標函數(shù)值趨于無窮。或者目標函數(shù)值趨于無窮。定理定理2(2(最優(yōu)性準則最優(yōu)性準則) )(0 )(0 )(0 )(0 )00,(), ()(P) (D)xwPDcxwbxw（ ）（ ）若分 別 為的 可 行 解 且，則，分 別 為,問 題 的 最 優(yōu) 解 .(0)(0)(0)(0),1,(),TTTTxc xbPwc xb wx對原問題(P)的任意可行解由定理 可

14、則為的知而最優(yōu)解.證明：證明：(0),()wD同理為的最優(yōu)解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所以，分別是的最優(yōu)解定理定理3(3(強對偶強對偶定理定理)若若(P),(D)(P),(D)均有可行解均有可行解, ,則則(P),(D)(P),(

15、D)均有最優(yōu)解均有最優(yōu)解, ,且且(P),(D)(P),(D)的最優(yōu)的最優(yōu)目標函數(shù)值相等目標函數(shù)值相等. .證明：因為證明：因為(P),(D)(P),(D)均有可行解均有可行解, ,由推論由推論2,2,推論推論3 3知知,(P),(P)的目標的目標函數(shù)值在其可行域內(nèi)有下界函數(shù)值在其可行域內(nèi)有下界, (D), (D)的目標函數(shù)值在其可行域內(nèi)的目標函數(shù)值在其可行域內(nèi)有上界有上界, , 故則故則(P),(D)(P),(D)均有最優(yōu)解均有最優(yōu)解. .引入剩余變量，把引入剩余變量，把(P)(P)化為標準形化為標準形: :m in (, 0 ). .(,)0 ,0Tsssxcxxs tAIbxxx(0)(

16、).PxB設(shè)的最優(yōu)解為，所對應(yīng)的最優(yōu)基為(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故是的 最 優(yōu) 解 ， 且推論推論在用單純形法求解在用單純形法求解LPLP問題（問題（P P）的最優(yōu)單純）的最優(yōu)單純形表中松弛變量的檢驗數(shù)的相反數(shù)形表中松弛變量的檢驗數(shù)的相反數(shù)( (單純形單純形乘子乘子w= =(B-1)Tc

17、B) )就是其對偶問題（就是其對偶問題（D D）的最優(yōu)解）的最優(yōu)解. .由于由于(P)(P)化成標準形式時化成標準形式時, ,松弛變量松弛變量x xn n+ +j j 對應(yīng)的列為對應(yīng)的列為- -e ej j，它在目標函數(shù)中的價格系數(shù)，它在目標函數(shù)中的價格系數(shù)，所以，判別數(shù)為所以，判別數(shù)為 (B(B-1-1) )T Tc cB B(-(-e ej j)-0=-)-0=-w wj j則松弛變量對應(yīng)的判別數(shù)均乘以則松弛變量對應(yīng)的判別數(shù)均乘以(-1)(-1)，便得到單純，便得到單純形乘子形乘子w w=(=(w w1 1, , ,w wm m).). 當原問題達最優(yōu)時當原問題達最優(yōu)時, ,單純形乘子即為

18、對偶問題的最優(yōu)解單純形乘子即為對偶問題的最優(yōu)解. .解：化為標準形：化為標準形121231425max 23284164120,1,2,3,4,5jxxxxxxxxxxj例例: : 求下列問題之對偶問題的最優(yōu)解求下列問題之對偶問題的最優(yōu)解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

19、1 0 -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此時達到最優(yōu)解。此時達到最優(yōu)解。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)最優(yōu)解為：最優(yōu)值小結(jié)小結(jié)原問題原問題(min) 對應(yīng)關(guān)系對應(yīng)關(guān)系

20、 對偶問題對偶問題(max) 有最優(yōu)解有最優(yōu)解無界解不可行不可行無界解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定理

21、定理4 4（互補松馳定理）（互補松馳定理）0000 xwPDxwPD（ ）（ ）（ ）（ ）設(shè)，分別為（ ），（）問題的可行解則，分別為（ ），（）的最優(yōu)解的充要條件是(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 A

22、Karush Kuhn TucKKTxbr x （）對于線性規(guī)劃來說， 是其最優(yōu)解，當且僅當存在向最優(yōu)性條件定理量條件，使得證明：（必要性）證明：（必要性）(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 設(shè)和分別是和的最優(yōu)解，則且故有即因為是最有解 所以有所以，即，且 證明：（充分性）證明：（充分性）(0)(0)(0)(0)(0)(

23、0)(0)(0)(0)(0)(0)(0)(0)(0)()0,() 02,( )().c wA xcxwAxwAxbwAxwbcxwbxwPD 由得由， 得因此有由定理 知，為和的最優(yōu)解定理定理4 4：互補松馳定理：互補松馳定理( (非對稱形式）非對稱形式）(0)(0)TT(0)(0)(0)(0)(0)(0)minmax. . .0(1)0,(2)0.Tjjjjjjxwc xb wstAxbstA wcxxwjxwPcwPcx設(shè)和分別是和的可行解，則和是最優(yōu)解的充要條件時，對任意的 ，下列關(guān)系成立：若則；若，則12341234123412342342232 0. .2322 0,0M a xZx

24、xxxxxxxs txxxxxxxx12121212121220202122. .233324,0M inWyyyyyys tyyyyyy( )P()D例例: : 考慮下面問題考慮下面問題*6 1(),5 5( )DyP已知的最優(yōu)解為用互補松弛定理求出的最優(yōu)解解解:*120 ,0yy由 于4由 定 理知*123422320(1)xxxx*12342322 0(2 )xxxx*11yy*12yy*342320 xx*343220 xx*344xx則( )P所以問題的最優(yōu)解為*(0, 0, 4, 4)x*1201xx ，代入（），（2）121212121

25、21220202122: 233324,0MinWyyyyyySTyyyyyy1 1、定義、定義對偶問題的經(jīng)濟學解釋：影子價格對偶問題的經(jīng)濟學解釋：影子價格(自學自學)影 子 價 格 是 最 優(yōu) 配 置 下 資 源 的 理 想 價 格*1122mmfcxw bw bw bw b由 于12,mb bb假設(shè)是變化的，則2 2、含義、含義*1212,mmfffwwwbbb*1( )iiwbP可以理解成當資源 變化 單位時，極小化問題的目標函數(shù)值的變化量考慮在最優(yōu)解處考慮在最優(yōu)解處,右端項右端項bi的微小變動對目標函數(shù)值的影響的微小變動對目標函數(shù)值的影響. 若把原問題的約束條件看成是廣義的資源約束若把

26、原問題的約束條件看成是廣義的資源約束, ,則右端則右端項的值表示每種資源的可用量項的值表示每種資源的可用量. . 對偶解的經(jīng)濟含義對偶解的經(jīng)濟含義: :資源的單位改變量引起目標函數(shù)值資源的單位改變量引起目標函數(shù)值的增加量的增加量. . 通常稱對偶解為影子價格通常稱對偶解為影子價格. . 影子價格的大小客觀地反映了資源在系統(tǒng)內(nèi)的稀缺程度影子價格的大小客觀地反映了資源在系統(tǒng)內(nèi)的稀缺程度. .資源的影子價格越高資源的影子價格越高, ,說明資源在系統(tǒng)內(nèi)越稀缺說明資源在系統(tǒng)內(nèi)越稀缺, ,而增加而增加該資源的供應(yīng)量對系統(tǒng)目標函數(shù)值貢獻越大該資源的供應(yīng)量對系統(tǒng)目標函數(shù)值貢獻越大. . 木門木門 木窗木窗木工

27、木工 4小時小時 3小時小時 120小時小時/日日油漆工油漆工 2小時小時 1小時小時 50小時小時/日日收入收入 56 30解：設(shè)該車間每日安排解：設(shè)該車間每日安排 x1 x2 x3 x4生產(chǎn)木門生產(chǎn)木門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

28、0 0 2 24 1440對偶問題的解為對偶問題的解為:w*=(2, 24) （2 2）告訴管理者花多大代價購買進資源或賣出資源是合適的）告訴管理者花多大代價購買進資源或賣出資源是合適的 3 3、影子價格的作用、影子價格的作用（1 1）告訴管理者增加何種資源對企業(yè)更有利）告訴管理者增加何種資源對企業(yè)更有利 （3）為新產(chǎn)品定價提供依據(jù)為新產(chǎn)品定價提供依據(jù)對偶單純形法對偶單純形法 定義：設(shè)定義：設(shè)x(0)是是(P)的一個的一個基本解基本解（不一定是可行（不一定是可行解），它對應(yīng)的矩陣為解），它對應(yīng)的矩陣為B，記，記w=cBB-1，若，若w是是(P)的對偶問題的可行解，即對任意的的對偶問題的可行解，

29、即對任意的j, wPj-cj 0，則，則稱稱x(0)為原問題的為原問題的對偶可行的基解對偶可行的基解。 結(jié)論：當對偶可行的基解是原問題的可行解時，結(jié)論：當對偶可行的基解是原問題的可行解時，由于判別數(shù)由于判別數(shù)0，因此，它就是原問題的最優(yōu)解。，因此，它就是原問題的最優(yōu)解。1231234123512345min. .3142,0 xxxs txxxxxxxxxxxxx1212121212m ax2. .3141111wws twwwwwwww 000012Tx1111000Bc BAc 所以，所以，x(0)為對偶可行的基解。為對偶可行的基解。基本思想：基本思想： 從原問題的一個對偶可行的基解出發(fā)；

30、從原問題的一個對偶可行的基解出發(fā)； 求改進的對偶可行的基解：每個對偶可行的基解求改進的對偶可行的基解：每個對偶可行的基解x=(xBT,0)T對應(yīng)一個對偶問題的可行解對應(yīng)一個對偶問題的可行解w=cBB-1，相應(yīng)的對偶問題的目標函數(shù)值為相應(yīng)的對偶問題的目標函數(shù)值為wb=cBB-1b，所，所謂改進的對偶可行的基解，是指對于原問題的這謂改進的對偶可行的基解，是指對于原問題的這個基解，相應(yīng)的對偶問題的目標函數(shù)值個基解，相應(yīng)的對偶問題的目標函數(shù)值wb有改進有改進（選擇離基變量和進基變量，進行（選擇離基變量和進基變量，進行主元消去主元消去）；）； 當?shù)玫降膶ε伎尚械幕馐窃瓎栴}的可行解時，當?shù)玫降膶ε伎尚械?/p>

31、基解是原問題的可行解時，就達到最優(yōu)解。就達到最優(yōu)解。與原單純形法的區(qū)別：與原單純形法的區(qū)別： 原單純形法保持原問題的可行性，對偶單純形原單純形法保持原問題的可行性，對偶單純形法法保持所有檢驗數(shù)保持所有檢驗數(shù)wPj-cj 0，即保持對偶問題，即保持對偶問題的可行性。的可行性。 特點：先選擇出基變量，再選擇進基變特點：先選擇出基變量，再選擇進基變 量。量。120B b、判斷，若，則已得到最優(yōu)解3、換基迭代、換基迭代 1min0,riribbx）確定換出變量，為換出變量.1、 化標準型化標準型,建立初始單純形表建立初始單純形表2min0,jjkkrjkjrjrkzczcyxyy）確定換入變量，為換入變量.3rky）換基迭代