Lecture3 對(duì)偶理論-凸函數(shù)

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

3、221212121212( , )inf()()|inf()|00.TTTTTTTTTTTTw vcxwAxbvA xbxDcw Av A xw bv bxDw bv bcw Av Acw Av A若若線性規(guī)劃的對(duì)偶問(wèn)題為：線性規(guī)劃的對(duì)偶問(wèn)題為：1212max. .0TTTTw bv bstw Av Acw0,04. .min21212221xxxxtsxx求下列非線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題求下列非線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題:11222212120,0 ,( )inf(4)|.xxDxxxwxxw xxxD解：把變量的非負(fù)限制作為集約束，即則.42444)(.4220|inf.4220|inf,040

4、|inf0|inf0, 0|4inf| )4(inf)(2222222222211212222112121222121212221wwwwwwwwwwxwxxwwwwxwxxwwxwxxxwxxxxwwxxwxxDxxxwxxw時(shí)當(dāng)對(duì)偶問(wèn)題為對(duì)偶問(wèn)題為:0. .42max2wtsww對(duì)偶定理對(duì)偶定理TlTmxhxhxhxgxgxgDxxhxgtsxf)(,),()()(,),()(0)(0)(. .)(min110. .),(maxwtsvw( , )inf( )( )( )|TTw vf xw g xv h xxD定理定理1(弱對(duì)偶定理弱對(duì)偶定理)。題的可行解，則分別是原問(wèn)題和對(duì)偶問(wèn)和設(shè)),

5、()(),(vwxfvwx).()()()(| )()()(inf),(0, 0)(, 0)(),(xfxhvxgwxfDxxhvxgwxfvwwxhxgvwxTTTT是可行解，和證明： 推論推論1:.0| ),(sup, 0)(, 0)(| )(infwvwDxxhxgxf，必有對(duì)于原問(wèn)題和對(duì)偶問(wèn)題推論推論2:題的最優(yōu)解。分別是原問(wèn)題和對(duì)偶問(wèn)和，則為原問(wèn)題的可行解，其中若),(0),()(vwxwxvwxf推論推論3:。，有則對(duì)若),(0, 0)(, 0)(| )(infvwwDxxhxgxf推論推論4:sup( , )|0w vw 如果，則原問(wèn)題沒(méi)有可行解。對(duì)偶間隙：對(duì)偶間隙：minmax

6、inf( )| ( )0, ( )0,=sup( , )|0f xg xh xxDfw vw記記minmax0f問(wèn)題問(wèn)題：0. 成立的條件LP 對(duì)偶問(wèn)題的表達(dá)對(duì)偶問(wèn)題的表達(dá)（1 1）對(duì)稱）對(duì)稱LPLP問(wèn)題的定義問(wèn)題的定義m in. .0Tcxs tA xbx（2）對(duì)稱對(duì)稱LPLP問(wèn)題的對(duì)偶問(wèn)題問(wèn)題的對(duì)偶問(wèn)題(P)(D)max. .0TTb ws tA wcw例：寫(xiě)出下列例：寫(xiě)出下列LPLP問(wèn)題的對(duì)偶問(wèn)題問(wèn)題的對(duì)偶問(wèn)題12121212max2328416. . 412,0wwwwws twww1231213123min8161242. 243,0 xxxxxstxxx x x對(duì)偶例：寫(xiě)出對(duì)偶問(wèn)題

7、例：寫(xiě)出對(duì)偶問(wèn)題(D)的對(duì)偶的對(duì)偶變形(D)min. .0TTb ws tA wcw max. .0TTb ws tA wcw對(duì)偶max. .()0TTTc xs tAxbx m in. .0Tcxs tAxbx變形結(jié)論結(jié)論：對(duì)偶問(wèn)題：對(duì)偶問(wèn)題(D)的對(duì)偶的對(duì)偶 為原問(wèn)題為原問(wèn)題(P) 。(DD)minmin變成變成max max 價(jià)值系數(shù)與右端向量互換價(jià)值系數(shù)與右端向量互換系數(shù)矩陣轉(zhuǎn)置系數(shù)矩陣轉(zhuǎn)置 變變 原問(wèn)題中約束條件的個(gè)數(shù)原問(wèn)題中約束條件的個(gè)數(shù)= =對(duì)偶問(wèn)題中變量的個(gè)數(shù)對(duì)偶問(wèn)題中變量的個(gè)數(shù)原問(wèn)題中變量的個(gè)數(shù)原問(wèn)題中變量的個(gè)數(shù)= =對(duì)偶問(wèn)題中約束條件的個(gè)數(shù)對(duì)偶問(wèn)題中約束條件的個(gè)數(shù)寫(xiě)出對(duì)稱形

8、式的對(duì)偶規(guī)劃的要點(diǎn)寫(xiě)出對(duì)稱形式的對(duì)偶規(guī)劃的要點(diǎn)非對(duì)稱形式的對(duì)偶非對(duì)稱形式的對(duì)偶min. .0Tc xs tAxbx對(duì)稱形式對(duì)稱形式m in. . 0Tcxs tA xbA xbx 對(duì)偶對(duì)偶max.,0TTTTb u b vstA uA vcu vmax. .TTb ws tA wcw無(wú) 限 制wuv令(P)(D)例例 min 5x1+4x2+3x3 s.t. x1+x2+x3=4 3x1+2x2+x3 =5 x1 0, x2 0, x3 0 對(duì)偶問(wèn)題為對(duì)偶問(wèn)題為 max 4w1+5w2 s.t. w1+3w25 w1+2w2 4 w1+w2 3112233min.0where ,1,2,3.i

9、iTmm nniic xstAx bAx bAx bxc R bRARi31112233min. . ,0where , are slack variables.Tststmmstc xstA xxbA xbA xxbx x xxRxR一般情形一般情形LPLP問(wèn)題的對(duì)偶問(wèn)題問(wèn)題的對(duì)偶問(wèn)題標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形對(duì)偶對(duì)偶112233112233123max . . , 0, free, 0. TTTTTTb wb wb wstA wA wA wcwww變量變量約束約束約束約束變量變量123123123123123min 22 2 1 2. . 1 0, 0 xxxxxxxxxs txxxxxx無(wú)約束123m

10、ax2www. st123www123www1232www21210w 20w 3w 無(wú)約束123123123123123max2 2 1:2 20,0,xxxxxxxxxSTxxxxxx無(wú)約束123min 22www123www1232www123www1210w 2w 無(wú)約束30w 1. st123123123123132min 22212. . 10,0,xxxxxxxxxstxxxxxx無(wú)約束練習(xí)題練習(xí)題LP對(duì)偶問(wèn)題的基本性質(zhì)對(duì)偶問(wèn)題的基本性質(zhì)原問(wèn)題原問(wèn)題(P)對(duì)偶問(wèn)題對(duì)偶問(wèn)題(D)m in. .0Tcxs tA xbxm a x. . 0TTbws tAwcw定理定理1(1(弱對(duì)偶定

11、理弱對(duì)偶定理) )(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）原問(wèn)題）原問(wèn)題(P1)一可行解一可行解 x=(1, 1)T(P1)目標(biāo)值目標(biāo)值

12、=4040是是(D1)最優(yōu)目標(biāo)值的上界最優(yōu)目標(biāo)值的上界.2）對(duì)偶問(wèn)題）對(duì)偶問(wèn)題(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極大化問(wèn)題的任何一個(gè)可行解所對(duì)應(yīng)的目標(biāo)極大化問(wèn)題的任何一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值都是其對(duì)偶問(wèn)題的目標(biāo)函數(shù)值的下界。函數(shù)值都是其對(duì)偶問(wèn)題的目標(biāo)函數(shù)值的下界。極小化問(wèn)題的任何一個(gè)可行解所對(duì)應(yīng)的目標(biāo)極小化問(wèn)題的任何一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值都是其對(duì)偶問(wèn)題的目標(biāo)函數(shù)值的上界。函數(shù)值都是其對(duì)偶問(wèn)題的目標(biāo)函數(shù)值的上界。推論推論

13、3 3若問(wèn)題若問(wèn)題(P)或或(D)有無(wú)界解，則其對(duì)偶問(wèn)題有無(wú)界解，則其對(duì)偶問(wèn)題(D)或或(P)無(wú)可行解；無(wú)可行解； 若問(wèn)題若問(wèn)題(P)或或(D)無(wú)可行解，則其對(duì)偶問(wèn)題無(wú)可行解，則其對(duì)偶問(wèn)題(D)或或(P)或者無(wú)可行解或者無(wú)可行解, ,或者目標(biāo)函數(shù)值趨于無(wú)窮。或者目標(biāo)函數(shù)值趨于無(wú)窮。定理定理2(2(最優(yōu)性準(zhǔn)則最優(yōu)性準(zhǔn)則) )(0 )(0 )(0 )(0 )00,(), ()(P) (D)xwPDcxwbxw（ ）（ ）若分 別 為的 可 行 解 且，則，分 別 為,問(wèn) 題 的 最 優(yōu) 解 .(0)(0)(0)(0),1,(),TTTTxc xbPwc xb wx對(duì)原問(wèn)題(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)對(duì)偶強(qiáng)對(duì)偶定理定理)若若(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)解為，所對(duì)應(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問(wèn)題（問(wèn)題（P P）的最優(yōu)單純）的最優(yōu)單純形表中松弛變量的檢驗(yàn)數(shù)的相反數(shù)形表中松弛變量的檢驗(yàn)數(shù)的相反數(shù)( (單純形單純形乘子乘子w= =(B-1)Tc

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

18、對(duì)偶問(wèn)題的最優(yōu)解單純形乘子即為對(duì)偶問(wèn)題的最優(yōu)解. .解：化為標(biāo)準(zhǔn)形：化為標(biāo)準(zhǔn)形121231425max 23284164120,1,2,3,4,5jxxxxxxxxxxj例例: : 求下列問(wèn)題之對(duì)偶問(wèn)題的最優(yōu)解求下列問(wèn)題之對(duì)偶問(wèn)題的最優(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此時(shí)達(dá)到最優(yōu)解。此時(shí)達(dá)到最優(yōu)解。x* *=(4,2), =(4,2), MaxZMaxZ=14=14。12121212max2328416. .412,0 xxxxxs txxx1231213123min81612. .42243,0wwws twwwww ww(P)(D)31, 0 ,14.28w(D)最優(yōu)解為：最優(yōu)值小結(jié)小結(jié)原問(wèn)題原問(wèn)題(min) 對(duì)應(yīng)關(guān)系對(duì)應(yīng)關(guān)系

20、 對(duì)偶問(wèn)題對(duì)偶問(wèn)題(max) 有最優(yōu)解有最優(yōu)解無(wú)界解不可行不可行無(wú)界解1212112212 max . . 1 (D) -1 ,0ywwstwwlwwlw w （無(wú)可行解）（無(wú)可行解）1212112212min . . 1 (P) -1 ,0zxxstxxlxxlx x 例1:（無(wú)可行解）（無(wú)可行解）w1w2l2l1x1x2l1l21212112212 max . . 1 (P) 1 ,02zxxstxxlxxlx x例 ： （無(wú)界解）（無(wú)界解）1212112212 min . . 1 (D) 1 ,0wyystyylyyly y （無(wú)可行解）（無(wú)可行解）l2x1x2l1zy1y2l1l2定理

21、定理4 4（互補(bǔ)松馳定理）（互補(bǔ)松馳定理）0000 xwPDxwPD（ ）（ ）（ ）（ ）設(shè)，分別為（ ），（ ）問(wèn)題的可行解則，分別為（ ），（ ）的最優(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

22、 AKarush Kuhn TucKKTxbr x （）對(duì)于線性規(guī)劃來(lái)說(shuō)， 是其最優(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

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

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

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

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

27、木工 4小時(shí)小時(shí) 3小時(shí)小時(shí) 120小時(shí)小時(shí)/日日油漆工油漆工 2小時(shí)小時(shí) 1小時(shí)小時(shí) 50小時(shí)小時(shí)/日日收入收入 56 30解：設(shè)該車間每日安排解：設(shè)該車間每日安排 x1 x2 x3 x4生產(chǎn)木門(mén)生產(chǎn)木門(mé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對(duì)偶問(wèn)題的解為對(duì)偶問(wèn)題的解為:w*=(2, 24) （2 2）告訴管理者花多大代價(jià)購(gòu)買(mǎi)進(jìn)資源或賣(mài)出資源是合適的）告訴管理者花多大代價(jià)購(gòu)買(mǎi)進(jìn)資源或賣(mài)出資源是合適的 3 3、影子價(jià)格的作用、影子價(jià)格的作用（1 1）告訴管理者增加何種資源對(duì)企業(yè)更有利）告訴管理者增加何種資源對(duì)企業(yè)更有利 （3）為新產(chǎn)品定價(jià)提供依據(jù)為新產(chǎn)品定價(jià)提供依據(jù)對(duì)偶單純形法對(duì)偶單純形法 定義：設(shè)定義：設(shè)x(0)是是(P)的一個(gè)的一個(gè)基本解基本解（不一定是可行（不一定是可行解），它對(duì)應(yīng)的矩陣為解），它對(duì)應(yīng)的矩陣為B，記，記w=cBB-1，若，若w是是(P)的對(duì)偶問(wèn)題的可行解，即對(duì)任意的的對(duì)偶問(wèn)題的可行解，

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

30、從原問(wèn)題的一個(gè)對(duì)偶可行的基解出發(fā)； 求改進(jìn)的對(duì)偶可行的基解：每個(gè)對(duì)偶可行的基解求改進(jìn)的對(duì)偶可行的基解：每個(gè)對(duì)偶可行的基解x=(xBT,0)T對(duì)應(yīng)一個(gè)對(duì)偶問(wèn)題的可行解對(duì)應(yīng)一個(gè)對(duì)偶問(wèn)題的可行解w=cBB-1，相應(yīng)的對(duì)偶問(wèn)題的目標(biāo)函數(shù)值為相應(yīng)的對(duì)偶問(wèn)題的目標(biāo)函數(shù)值為wb=cBB-1b，所，所謂改進(jìn)的對(duì)偶可行的基解，是指對(duì)于原問(wèn)題的這謂改進(jìn)的對(duì)偶可行的基解，是指對(duì)于原問(wèn)題的這個(gè)基解，相應(yīng)的對(duì)偶問(wèn)題的目標(biāo)函數(shù)值個(gè)基解，相應(yīng)的對(duì)偶問(wèn)題的目標(biāo)函數(shù)值wb有改進(jìn)有改進(jìn)（選擇離基變量和進(jìn)基變量，進(jìn)行（選擇離基變量和進(jìn)基變量，進(jìn)行主元消去主元消去）；）； 當(dāng)?shù)玫降膶?duì)偶可行的基解是原問(wèn)題的可行解時(shí)，當(dāng)?shù)玫降膶?duì)偶可行的

31、基解是原問(wèn)題的可行解時(shí)，就達(dá)到最優(yōu)解。就達(dá)到最優(yōu)解。與原單純形法的區(qū)別：與原單純形法的區(qū)別： 原單純形法保持原問(wèn)題的可行性，對(duì)偶單純形原單純形法保持原問(wèn)題的可行性，對(duì)偶單純形法法保持所有檢驗(yàn)數(shù)保持所有檢驗(yàn)數(shù)wPj-cj 0，即保持對(duì)偶問(wèn)題，即保持對(duì)偶問(wèn)題的可行性。的可行性。 特點(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）確定換入變量，為換入

32、變量.3rky）換基迭代，為主元.4、回到第、回到第2步步(若所有若所有yrj0, ,則該則該LPLP無(wú)可行解）無(wú)可行解）步驟：步驟：min 0min|0rijjkkrjrkrjxxbbzczcyyy迭代到 時(shí)，0rrrrkbbby()0kkjjjjrjrkzczcyy檢驗(yàn)數(shù)1.BBc bc B b迭代前，對(duì)偶問(wèn)題的目標(biāo)函數(shù)值.kkBrBrkzcc bbc by迭代后，對(duì)偶問(wèn)題的目標(biāo)函數(shù)值123123123123 min 3 1 -42 ,0 xxxs.txxxxxxx xx例：1231234123512345min 3 1 -42 ,0 xxxs.txxxxxxxxx x x x x解：引入

33、松弛變量，化為標(biāo)準(zhǔn)型1231234123512345min 3 1 42 ,0 xxxs.txxxxxxxxx x x x x 1( 1, 1, 1,0,0)0Bc B Acc x1 x2 x3 x4 x5-3 -1 -1 1 01 -4 -1 0 1-1 -1 -1 0 0 x4x5-1-20-4-13/4 0 -3/4 1 -1/4-1/4 1 1/4 0 -1/4-5/4 0 -3/4 0 -1/4x4x2-1/21/21/2-13/41 0 3/13 -4/13 1/130 1 4/13 -1/13 -3/130 0 -6/13 -5/13 -2/13x1x22/137/139/13m

34、 in52,1 31 3*279x, 0 , 0 , 0f1 31 31 3為 最 優(yōu) 解 ，對(duì) 偶 問(wèn) 題 的 最 優(yōu) 解 為12312312323123m in23 4 28: 2,0 xxxxxxxxxSTxxxxx12312341235236123456min23 4 2 8: 2,0 xxxxxxxxxxxSTxxxx x x x x x 用對(duì)偶單純形法求解下列用對(duì)偶單純形法求解下列LPLP問(wèn)題問(wèn)題解：原問(wèn)題變形為解：原問(wèn)題變形為x1 x2 x3 x4 x5 x6-1 1 -1 1 0 01 1 2 0 1 00 -1 1 0 0 1x4x5x6-1 -2 -3 0 0 0-48-2

35、01 -1 1 -1 0 00 2 1 1 1 00 -1 1 0 0 1x1x5x60 -3 -2 -1 0 044-24-1-11 0 0 -1 0 -10 0 3 1 1 20 1 -1 0 0 -1x1x5x20 0 -5 -1 0 -36021010)0, 2, 6(*minfxT凸函數(shù)凸函數(shù)凸函數(shù)凸函數(shù)：設(shè)設(shè)S是是En中的非空凸集，中的非空凸集， f(x)是定義在是定義在S上的上的實(shí)函數(shù)，如果實(shí)函數(shù)，如果對(duì)于每一對(duì)對(duì)于每一對(duì)x1，x2 S及每一個(gè)及每一個(gè)a，0a1,都都有有f(ax1+(1a)x2)a f(x1)+(1a)f(x2)則稱函數(shù)則稱函數(shù)f(x)為為S上的上的凸函數(shù)上式中

36、，若凸函數(shù)上式中，若變?yōu)樽優(yōu)?，則，則稱為嚴(yán)格凸函數(shù)。稱為嚴(yán)格凸函數(shù)。 若若-f(x)為為S的凸函數(shù)，則稱的凸函數(shù)，則稱f(x)為為S上的上的凹函數(shù)凹函數(shù)(a)嚴(yán)格凸x凸x非凸x(b)(c)凸函數(shù)性質(zhì)凸函數(shù)性質(zhì) (1) 設(shè)設(shè)f1(x)，f2(x)是凸集是凸集S上的凸函數(shù)，則函數(shù)上的凸函數(shù)，則函數(shù)f1(x)+f2(x)在在S上也是凸函數(shù)。上也是凸函數(shù)。(2) 設(shè)設(shè)f(x)是凸集是凸集S上的凸函數(shù)，則對(duì)任意的上的凸函數(shù)，則對(duì)任意的a0，函數(shù)，函數(shù)af(x)是凸的。是凸的。推廣：推廣：設(shè)設(shè)f1(x)，f2(x), , fk(x)是凸集是凸集S上的凸函數(shù)，上的凸函數(shù)，ai0,則則a1f1(x)+a2f2

37、(x)+ + akfk(x)也是凸集也是凸集S S上的凸函上的凸函數(shù)數(shù). .(3) 設(shè)設(shè)f(x)是凸集是凸集S上的凸函數(shù)，對(duì)每一個(gè)實(shí)數(shù)上的凸函數(shù)，對(duì)每一個(gè)實(shí)數(shù)c，則集，則集合合(level set)Scx | x S，f(x) c是凸集。是凸集。(4)設(shè)設(shè)S是是En中的非空凸集，中的非空凸集，f是定義在是定義在S上的凸函數(shù)，上的凸函數(shù)， 則則f在在S上的局部極小點(diǎn)是整體極小點(diǎn)，且極小點(diǎn)上的局部極小點(diǎn)是整體極小點(diǎn)，且極小點(diǎn) 的集合是凸集的集合是凸集凸函數(shù)性質(zhì)凸函數(shù)性質(zhì)證明：證明：(0)(0)(0)(0)(0)(0)0( )( )( )( )( )()(0,1)(1)(1) )()(1) ( )(

38、 )(1) ( )( )xfSxNxxSNxf xf xxxSf xf xSxxSfSfxxf xf xf xf xf xx 設(shè) 是 在 中的局部極小點(diǎn)，既存在 的鄰域使得對(duì)，有。若 不是整體極小點(diǎn)，則使，是凸集，對(duì)有，是 上的凸函數(shù)，當(dāng) 取得充分小時(shí)，可使(1)( ) |,( )xSNxxxfSfSSx xS f x，這與 為局部極小點(diǎn)矛盾，是 在 上的整體極小點(diǎn)。在 上的極小值也是它在 上的最小值。極小點(diǎn)集合為，則由性質(zhì)（3），為凸集。凸函數(shù)的判別凸函數(shù)的判別梯度：梯度：Tnxxfxxfxf)(,)()(1Hesse矩陣：矩陣：221222122122122)()()()()()()(nn

39、nnxxfxxxfxxxfxxxfxxxfxxfxfAxfbAxxfcxbAxxxfTT)()(21)(2方向?qū)?shù)方向?qū)?shù)00000000,0( )()()()lim.(; )nntxEpEpf xxpf xf xtpf xptDf xpfxp 設(shè)，則函數(shù)在點(diǎn) 關(guān)于方向 的方向?qū)?shù)定義為：我們用表示 在點(diǎn) 關(guān)于方向 的方向?qū)?shù)。方向?qū)?shù)通常用下面的公式計(jì)算：方向?qū)?shù)通常用下面的公式計(jì)算：00(; )().TDf xpf xp 凸函數(shù)的充要條件凸函數(shù)的充要條件(1)(2)(2)(1)(1)(2)(1)(1)(2)(2)(1)(1)(2)(1)( )( ),()()() ()( ),()()()

40、().nTTSEf xSf xxxSf xf xf xxxf xxxSf xf xf xxx設(shè) 是中非空開(kāi)凸集，是定義在 上的函數(shù)，則為凸函數(shù)的充要條件是對(duì)任意兩點(diǎn)，有；為嚴(yán)格凸函數(shù)的充要條件是對(duì)任意互不相同兩點(diǎn)有可，微定理（一階充要條件）定理（一階充要條件）凸性凸性(1)(2)(2)(1)(2)(1)(1)(2)(1)(1)(2)(1)(1)(2)(1)(1)(2)(1)(1)(2)(1),(0,1)(1)()(1) ()()()()()0(;)() (TfSxxSfxxf xf xf xxxf xf xf xffxxxDf xxxf xxx “”設(shè) 是 上的凸函數(shù)，則對(duì)及，有即令，由 的可

41、微性，得 在點(diǎn)關(guān)于方向的方向?qū)?shù)(2)(1)(2)(1)(1)(2)(1)()(),()()() ().Tf xf xf xf xf xxx證證 明明).()()()()()(21)()()()()(21)(21).()()()().(21)(212121)(212121,)1()2()1()1()2()1()2()1()1()1()1()1()2()1()1()1()1()2()1()2()1()2()1()2()1()2()1(xxxfxfxfxxxfxfxyxfxfxfxfxyxfxfyffxfxfxxfyfSxxyxxSxxSfTTTT是凸函數(shù)，且，則取，及上的嚴(yán)格凸函數(shù)時(shí)，對(duì)是”當(dāng)“是凸函數(shù)。有及由假設(shè)，對(duì)。，則，令。，有設(shè)對(duì)”“fxxfyfyxxyfyfxfxfyxyfyfxfyxyfyfxfSyxSyxSyxxyxxxfxfxfSxxTTT)1 ()(