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

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ù)是的線(xiàn)性函數(shù)，于是對(duì)偶函數(shù)作為線(xiàn)性函數(shù)的逐點(diǎn)下確界，必然是一個(gè)凹函數(shù)，所以，對(duì)偶問(wèn)題是一個(gè)凸規(guī)劃問(wèn)題。例：考慮線(xiàn)性規(guī)劃問(wèn)題例：考慮線(xiàn)性規(guī)劃問(wèn)題1122min. .0cxstaxba xbx若取集合約束若取集合約束d=x|x0，則該，則該線(xiàn)性規(guī)劃問(wèn)題的線(xiàn)性規(guī)劃問(wèn)題的lagrange函數(shù)為函數(shù)為1122

3、1212121212( , )inf()()|inf()|00.ttttttttttttw vcxwaxbva xbxdcw av a xw bv bxdw bv bcw av acw av a若若線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題為：線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題為：1212max. .0ttttw bv bstw av acw0,04. .min21212221xxxxtsxx求下列非線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題求下列非線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題:11222212120,0 ,( )inf(4)|.xxdxxxwxxw xxxd解：把變量的非負(fù)限制作為集約束，即則.42444)(.4220|inf.4220|inf,040|i

4、nf0|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ì)偶間隙：minmaxin

6、f( )| ( )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ì)稱(chēng)）對(duì)稱(chēng)lplp問(wèn)題的定義問(wèn)題的定義m in. .0tcxs ta xbx（2）對(duì)稱(chēng)對(duì)稱(chēng)lplp問(wèn)題的對(duì)偶問(wèn)題問(wèn)題的對(duì)偶問(wèn)題(p)(d)max. .0ttb ws ta wcw例：寫(xiě)出下列例：寫(xiě)出下列l(wèi)plp問(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. .0tc xs 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ì)稱(chēng)形式

8、的對(duì)偶規(guī)劃的要點(diǎn)寫(xiě)出對(duì)稱(chēng)形式的對(duì)偶規(guī)劃的要點(diǎn)非對(duì)稱(chēng)形式的對(duì)偶非對(duì)稱(chēng)形式的對(duì)偶min. .0tc xs taxbx對(duì)稱(chēng)形式對(duì)稱(chēng)形式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.ii

9、tmm 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ú)約束123ma

10、x2www. 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ù)值的上界。推論推論3

13、 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í), ,單純形乘子即為對(duì)偶問(wèn)題

18、的最優(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 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此時(shí)達(dá)到最優(yōu)解。此時(shí)達(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é)原問(wèn)題原問(wèn)題(min) 對(duì)應(yīng)關(guān)系對(duì)應(yīng)關(guān)系 對(duì)偶問(wèn)

20、題對(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定理定理4

21、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 akaru

22、sh kuhn tuckktxbr x （）對(duì)于線(xiàn)性規(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)(0)(0

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

24、xxs 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*12342322 0(2 )xxxx*11yy*12yy*342320 xx*343220 xx*344xx則( )p所以問(wèn)題的最優(yōu)解為*(0, 0, 4, 4)x*1201xx ，代入（），（2）12121212121220

25、202122: 233324,0minwyyyyyystyyyyyy1 1、定義、定義對(duì)偶問(wèn)題的經(jīng)濟(jì)學(xué)解釋?zhuān)河白觾r(jià)格對(duì)偶問(wèn)題的經(jīng)濟(jì)學(xué)解釋?zhuān)河白觾r(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)題的約束條件看成是廣義的資源約束若把原問(wèn)題的約

26、束條件看成是廣義的資源約束, ,則右端則右端項(xiàng)的值表示每種資源的可用量項(xiàng)的值表示每種資源的可用量. . 對(duì)偶解的經(jīng)濟(jì)含義對(duì)偶解的經(jīng)濟(jì)含義: :資源的單位改變量引起目標(biāo)函數(shù)值資源的單位改變量引起目標(biāo)函數(shù)值的增加量的增加量. . 通常稱(chēng)對(duì)偶解為影子價(jià)格通常稱(chēng)對(duì)偶解為影子價(jià)格. . 影子價(jià)格的大小客觀(guān)地反映了資源在系統(tǒng)內(nèi)的稀缺程度影子價(jià)格的大小客觀(guān)地反映了資源在系統(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) 木窗木窗木工木工 4小

27、時(shí)小時(shí) 3小時(shí)小時(shí) 120小時(shí)小時(shí)/日日油漆工油漆工 2小時(shí)小時(shí) 1小時(shí)小時(shí) 50小時(shí)小時(shí)/日日收入收入 56 30解：設(shè)該車(chē)間每日安排解：設(shè)該車(chē)間每日安排 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 0 0 2

28、 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)題的可行解，即對(duì)任意

29、的j, wpj-cj 0，則，則稱(chēng)稱(chēng)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ā)；從原問(wèn)題

30、的一個(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）確定換入變量，為換入變量.3rky）換基迭代