最優(yōu)化方法之對偶理論講解PPT演示課件

1、最優(yōu)化方法最優(yōu)化方法 optimizationoptimization第七講第七講第四章第四章 對偶理論對偶理論 窗含西嶺千秋雪，門泊東吳萬里船。 -(唐)杜甫 對偶是一種普遍現(xiàn)象主要內(nèi)容主要內(nèi)容 對偶問題的形式對偶問題的形式普遍存在普遍存在 l p 對偶形式及定理對偶形式及定理 對偶問題經(jīng)濟(jì)解釋對偶問題經(jīng)濟(jì)解釋 對偶單純形法對偶單純形法 原原-對偶算法對偶算法對偶及鞍點(diǎn)問題對偶及鞍點(diǎn)問題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ù)的逐點(diǎn)下確界，必然是一個凹函數(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解：把變量的非負(fù)限制作為集約束，即則.42444)(.4220|inf.4220|inf,040|i

4、nf0|inf0, 0|4inf| )4(inf)(2222222222211212222112121222121212221wwwwwwwwwwxwxxwwwwxwxxwwxwxxxwxxxxwwxxwxxdxxxwxxw時當(dāng)對偶問題為對偶問題為: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 對偶問題的表達(dá)對偶問題的表達(dá)（1 1）對稱）對稱lplp問題的定義問題的定義m in. .0tcxs ta xbx（2）對稱對稱lplp問題的對偶問題問題的對偶問題(p)(d)max. .0ttb ws ta wcw例：寫出下列例：寫出下列l(wèi)plp問題的對偶問題問題的對偶問題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ī)劃的要點(diǎn)寫出對稱形式的對偶規(guī)劃的要點(diǎn)非對稱形式的對偶非對稱形式的對偶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問題的對偶問題問題的對偶問題標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形對偶對偶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無約束練習(xí)題練習(xí)題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)目標(biāo)值目標(biāo)值 =

12、4040是是(d1)最優(yōu)目標(biāo)值的上界最優(yōu)目標(biāo)值的上界.2）對偶問題）對偶問題(d1)一可行解一可行解 w=（1 1 1 1） 目標(biāo)值目標(biāo)值 =10 10是是(p1)最優(yōu)目標(biāo)值的下界最優(yōu)目標(biāo)值的下界. *61 28550 0 4 4 28txw最優(yōu)值最優(yōu)值推論推論1推論推論2 2極大化問題的任何一個可行解所對應(yīng)的目標(biāo)極大化問題的任何一個可行解所對應(yīng)的目標(biāo)函數(shù)值都是其對偶問題的目標(biāo)函數(shù)值的下界。函數(shù)值都是其對偶問題的目標(biāo)函數(shù)值的下界。極小化問題的任何一個可行解所對應(yīng)的目標(biāo)極小化問題的任何一個可行解所對應(yīng)的目標(biāo)函數(shù)值都是其對偶問題的目標(biāo)函數(shù)值的上界。函數(shù)值都是其對偶問題的目標(biāo)函數(shù)值的上界。推論推論3

13、 3若問題若問題(p)或或(d)有無界解，則其對偶問題有無界解，則其對偶問題(d)或或(p)無可行解；無可行解； 若問題若問題(p)或或(d)無可行解，則其對偶問題無可行解，則其對偶問題(d)或或(p)或者無可行解或者無可行解, ,或者目標(biāo)函數(shù)值趨于無窮?；蛘吣繕?biāo)函數(shù)值趨于無窮。定理定理2(2(最優(yōu)性準(zhǔn)則最優(yōu)性準(zhǔn)則) )(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(強(qiáng)對偶強(qiáng)對偶定理定理)若若(p),(d)(p),(d)均有可行解均有可行解, ,則則(p),(d)(p),(

15、d)均有最優(yōu)解均有最優(yōu)解, ,且且(p),(d)(p),(d)的最優(yōu)的最優(yōu)目標(biāo)函數(shù)值相等目標(biāo)函數(shù)值相等. .證明：因?yàn)樽C明：因?yàn)?p),(d)(p),(d)均有可行解均有可行解, ,由推論由推論2,2,推論推論3 3知知,(p),(p)的目標(biāo)的目標(biāo)函數(shù)值在其可行域內(nèi)有下界函數(shù)值在其可行域內(nèi)有下界, (d), (d)的目標(biāo)函數(shù)值在其可行域內(nèi)的目標(biāo)函數(shù)值在其可行域內(nèi)有上界有上界, , 故則故則(p),(d)(p),(d)均有最優(yōu)解均有最優(yōu)解. .引入剩余變量，把引入剩余變量，把(p)(p)化為標(biāo)準(zhǔn)形化為標(biāo)準(zhǔn)形: :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又因?yàn)?0 )(0 )(0 )()m inm ax.ttttwdcxcxb wb w故是的 最 優(yōu) 解 ， 且推論推論在用單純形法求解在用單純形法求解lplp問題（問題（p p）的最優(yōu)單純）的最優(yōu)單純形表中松弛變量的檢驗(yàn)數(shù)的相反數(shù)形表中松弛變量的檢驗(yàn)數(shù)的相反數(shù)( (單純形單純形乘子乘子w= =(b-1)tc

17、b) )就是其對偶問題（就是其對偶問題（d d）的最優(yōu)解）的最優(yōu)解. .由于由于(p)(p)化成標(biāo)準(zhǔn)形式時化成標(biāo)準(zhǔn)形式時, ,松弛變量松弛變量x xn n+ +j j 對應(yīng)的列為對應(yīng)的列為- -e ej j，它在目標(biāo)函數(shù)中的價格系數(shù)，它在目標(biāo)函數(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).). 當(dāng)原問題達(dá)最優(yōu)時當(dāng)原問題達(dá)最優(yōu)時, ,單純形乘子即為對偶問題

18、的最優(yōu)解單純形乘子即為對偶問題的最優(yōu)解. .解：化為標(biāo)準(zhǔn)形：化為標(biāo)準(zhǔn)形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 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此時達(dá)到最優(yōu)解。此時達(dá)到最優(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定理定理4

21、4（互補(bǔ)松馳定理）（互補(bǔ)松馳定理）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 akaru

22、sh kuhn tuckktxbr x （）對于線性規(guī)劃來說， 是其最優(yōu)解，當(dāng)且僅當(dāng)存在向最優(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)解，則且故有即因?yàn)槭亲钣薪?所以有所以，即，且 證明：（充分性）證明：（充分性）(0)(0)(0)(0)(0)(0)(0

23、)(0)(0)(0)(0)(0)(0)(0)()0,() 02,( )().c wa xcxwaxwaxbwaxwbcxwbxwpd 由得由， 得因此有由定理 知，為和的最優(yōu)解定理定理44：互補(bǔ)松馳定理：互補(bǔ)松馳定理( (非對稱形式）非對稱形式）(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 xzxxxxxx

24、xxs txxxxxxxx12121212121220202122. .233324,0m inwyyyyyys tyyyyyy( )p()d例例: : 考慮下面問題考慮下面問題*6 1(),5 5( )dyp已知的最優(yōu)解為用互補(bǔ)松弛定理求出的最優(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）12121212121220

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

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

27、時小時 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 0 0 2

28、 24 1440對偶問題的解為對偶問題的解為:w*=(2, 24) （2 2）告訴管理者花多大代價購買進(jìn)資源或賣出資源是合適的）告訴管理者花多大代價購買進(jìn)資源或賣出資源是合適的 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é)論：當(dāng)對偶可行的基解是原問題的可行解時，結(jié)論：當(dāng)對偶可行的基解是原問題的可行解時，由于判別數(shù)由于判別數(shù)0，因此，它就是原問題的最優(yōu)解。，因此，它就是原問題的最優(yōu)解。1231234123512345min. .3142,0 xxxs txxxxxxxxxxxxx1212121212m ax2. .3141111wws twwwwwwww 000012tx1111000bc bac 所以，所以，x(0)為對偶可行的基解。為對偶可行的基解?；舅枷耄夯舅枷耄?從原問題的一個對偶可行的基解出發(fā)；從原問題

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

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