[理學(xué)]Chapter02線性規(guī)劃的對(duì)偶理論ppt課件

1、 2020年3月2022-5-52+設(shè)備租賃問題假定有四海機(jī)器廠想擴(kuò)大消費(fèi)規(guī)模想租賃常山機(jī)器廠的三種設(shè)備，常山方面應(yīng)如何決定出租價(jià)格呢？+設(shè)常山機(jī)器廠對(duì)三種設(shè)備的出租定價(jià)分別為y1,y2,y3元/小時(shí)。+常山機(jī)器廠的考慮：不能比自己組織消費(fèi)獲利少約束條件；+四海機(jī)器廠的考慮：租金盡可能少目的函數(shù)加工設(shè)備ABC單件利潤產(chǎn)品 I2402元產(chǎn)品 II2053元設(shè)備時(shí)限12h16h15h0,155 16 41222. .32max21212121xxxxxxtsxxz兩種產(chǎn)品的件數(shù)。在計(jì)劃期內(nèi)應(yīng)該生產(chǎn)為常山機(jī)器廠和21xx2022-5-53+寫出原問題和新問題的約束矩陣，右端項(xiàng)和目的函數(shù)系數(shù)0,155

2、 16 41222. . 32 max )(21212121xxxxxxtsxxz原問題0,35 22 42. . 151612 min )(3213121321yyyyyyytsyyyw對(duì)偶問題)3 ,2( 151612,500422 )(cbA原問題)15,16,12( 32,502042 )(cbA對(duì)偶問題問題：原問題的約束矩陣等和對(duì)偶問題的之間有什么關(guān)系？2022-5-54+原問題和對(duì)偶問題A, b 和 c 的對(duì)應(yīng)關(guān)系： A AT, bT c , cT b ;+原問題是極大化問題，對(duì)偶問題是極小化問題；+原問題 vs. 對(duì)偶問題：約束條件個(gè)數(shù) = 決策變量個(gè)數(shù)，反之仍然；+原問題的約束

3、為“號(hào)，對(duì)偶問題的約束為“號(hào)。0,155 16 41222. . 32 max )(21212121xxxxxxtsxxz原問題0,35 22 42. . 151612 min )(3213121321yyyyyyytsyyyw對(duì)偶問題2022-5-55+定義2.1 原問題 LP 的對(duì)偶問題為DP其中 y = y1,y2,ymT 為對(duì)偶問題的決策變量，稱LP為標(biāo)準(zhǔn)形式原問題。注：在對(duì)偶理論中，一般不再要求x和 b 非負(fù)。+例2.1 求下述問題的對(duì)偶問題。0s.t. max xbAxcxzTT0s.t. min ycyAybTw0, 0121 s.t.5 max21212121xxxxxxxxz

4、標(biāo)準(zhǔn)原問題0, 0121 s.t.5 max21212121xxxxxxxxz問題：請(qǐng)某位同學(xué)上黑板寫下對(duì)偶問題 4？2022-5-56+定理2.1 對(duì)偶問題 DP 的對(duì)偶問題為LP+證明思路：將對(duì)偶問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式原問題，即 “max + 約束 形式，再用定義求解。0s.t. max xbAxcxzTT0s.t. min ycyAybTw2022-5-57).12(.s.t. s.t. 1 . 2min max TTT，也可用定義證明可以利用定理的對(duì)偶問題為原問題推論0ycyA0 xbAxybcxwz難點(diǎn)記住：對(duì)偶問題約束的符號(hào)取決于原問題的變量符號(hào)； 對(duì)偶問題的變量符號(hào)取決于原問題的約束

5、符號(hào)。)(.s.t. s.t. 2 . 2max min TTT當(dāng)做課堂練習(xí)的對(duì)偶問題為原問題推論0ycyA0 xbAxybcxwz2022-5-58)(.s.t. s.t. 2 . 2min max TTT證明過程：見黑板的取值無限制的對(duì)偶問題為原問題定理ycyA0 xbAxybcxwz2022-5-59+設(shè)對(duì)偶問題的決策變量為 y = y1,y2,y3T， 對(duì)偶問題目的函數(shù)，約束矩陣，右端項(xiàng)容易寫出；關(guān)鍵是約束符號(hào)和變量符號(hào)問題。+第1約束：min + x1 0, 假如x10, 對(duì)偶問題約束該取“，此處相反取 “；+第2約束取“=；第3約束為 min + x3 0，約束取“；+對(duì)偶問題第1

6、變量y1: 由 min+第1約束“ 決定，y1 0 ;變量y2: 由 min+第2約束“ 決定，y2 0 ; 原問題第3個(gè)等式?jīng)Q定了變量y3取值無限制。0, 0303 5 5146324624 s.t.347min 32132321321321xxxxxxxxxxxxxxz取值無約束0s.t. max xbAxcxzTT0s.t. min ycyAybTw2022-5-510+始終規(guī)定 原問題 LP 對(duì)偶問題為DP其中 A為m n 階約束矩陣，x和y 分別為原問題和對(duì)偶問題的決策變量。0s.t. max xbAxcxzTT0s.t. min ycyAybTw)(. )DP( )LP( .32T

7、系即可證明，見黑板利用兩個(gè)問題的約束關(guān)的可行解，則恒有和分別是和若（弱對(duì)偶定理）定理ybxcyx).32( )DP( )LP( .32T反證法，見黑板證明和最優(yōu)解定義，或者用利用定理解。分別為兩個(gè)問題的最優(yōu)和則，的可行解，且有和分別是和若推論yxybxcyx2022-5-511+ 原問題 LP 對(duì)偶問題為DP其中 A為m n 階約束矩陣，x和y 分別為原問題和對(duì)偶問題的決策變量。0s.t. max xbAxcxzTT0s.t. min ycyAybTw，具體見黑板。證明理利用反證法和弱對(duì)偶定證明最優(yōu)性條件，和推論如利用其中一個(gè)問題，比行解。，則另外一個(gè)問題無可若其中一個(gè)問題解無界）（且目標(biāo)函數(shù)

8、值相同；解另外一個(gè)一定也有最優(yōu)之中一個(gè)有最優(yōu)解，則和若（強(qiáng)對(duì)偶定理）定理)2() 3 . 2() 1 (.32)LP( 2 , )DP( )LP( ) 1 ( .422022-5-512+ 原問題 LP 對(duì)偶問題為DP其中 A為m n 階約束矩陣，x和y 分別為原問題和對(duì)偶問題的決策變量。0s.t. max xbAxcxzTT0s.t. min ycyAybTw. 0 , )4(. , 0 )3(. 0, )2(. , 0 ) 1 ()DP()LP()( .52TT列的第為行，的第為其中就有如果就有如果就有如果就有如果，下列條件成立：和是，對(duì)所有的都是最優(yōu)解的充要條件和的可行解，那么和分別為和

9、設(shè)松緊定理定理jiybbyxccxjijiiiiiiijjjjjjApAAxAxAypypyxyx2022-5-513求原問題的最優(yōu)解。解為已知其對(duì)偶問題的最優(yōu)給定線性規(guī)劃問題),711,71(,0,23213. . 32 min 21321321321321yyxxxxxxxxxtsxxxTy.)0 ,75,74(,) 3)(2(Tx最終結(jié)果為求解劃，利用松緊定理解題思路：寫出對(duì)偶規(guī)2022-5-514+ 原問題 LP 對(duì)偶問題為DP其中 A為m n 階約束矩陣，x和y 分別為原問題和對(duì)偶問題的決策變量。+推論2.4 LP和DP存在一對(duì)互補(bǔ)的最優(yōu)基解：原問題的剩余變量對(duì)應(yīng)對(duì)偶問題的變量，對(duì)偶

10、問題的松弛變量對(duì)應(yīng)原問題的變量原問題解的基變量非基變量對(duì)應(yīng)對(duì)偶問題的非基變量基變量互補(bǔ)的基解對(duì)應(yīng)原問題和對(duì)偶問題的目的函數(shù)值一樣+推論2.4的應(yīng)用 假如原問題不方便求解，求其對(duì)偶問題最優(yōu)解，利用對(duì)偶問題最終單純形表的檢驗(yàn)數(shù)行獲得原問題最優(yōu)解。0s.t. max xbAxcxzTT0s.t. min ycyAybTw2022-5-515+問題1：原問題和對(duì)偶問題哪個(gè)更容易求解？為什么？+問題2：不容易求解的問題用什么方法求解？0,155 16 41222. . 32 max )(21212121xxxxxxtsxxz原問題0,35 22 42. . 151612 min )(3213121321

11、yyyyyyytsyyyw對(duì)偶問題2022-5-516原maxbx1x2x3x4x52x13101/20-1/50 x4400-214/53x2301001/5cj zj00-10-1/5對(duì)偶minby1y2y3y4y512y11120-1/2015y31/50-4/511/5-1/5cj zj04033就是對(duì)偶問題最優(yōu)解。由定理1T 4 . 2BcyB問題3：這個(gè)最優(yōu)解在原最終單純形表中的什么位置？是原問題最優(yōu)解。1T BcxB問題4：這里的B和B1分別是什么？2022-5-517bi : 第i種資源的擁有量；yi : 第i種資源的單位估價(jià)，不是市場(chǎng)價(jià)格，是消費(fèi)奉獻(xiàn)估價(jià)，稱為影子價(jià)格shad

12、ow price；影子價(jià)格是邊際價(jià)格。0,155 16 41222. .32max21212121xxxxxxtsxxznjmiiijjybxcz11 根據(jù)基解互補(bǔ)原理2022-5-518+影子價(jià)格和資源利用的關(guān)系1 假設(shè)Ai x 0, 那么Ai x = bi ;+結(jié)論：資源消耗完畢，影子價(jià)格大于零；未充分利用，影子價(jià)格為0+單純法中檢驗(yàn)數(shù)的含義：miiijjjjjyaccc11pBBn各個(gè)變量的含義cj : 第j種產(chǎn)品的產(chǎn)值；aijyi : 消費(fèi)單位產(chǎn)品消耗各種該資源的影子價(jià)格的總和，即產(chǎn)品的隱含本錢；n檢驗(yàn)數(shù)的含義三種情況n影子價(jià)格的應(yīng)用書P632022-5-519+單純形法的思想：保持原

13、問題是可行解，在目的函數(shù)值不減的條件下迭代求解，直至檢驗(yàn)數(shù)滿足最優(yōu)性標(biāo)準(zhǔn)。+原問題 vs. 對(duì)偶問題:根據(jù)基解互補(bǔ)原理，原問題檢驗(yàn)數(shù)非正時(shí)，其對(duì)偶問題到達(dá)可行解，此時(shí)相應(yīng)解為兩個(gè)問題的最優(yōu)解。+對(duì)偶單純形法的根本思想：保持對(duì)偶問題為可行解檢驗(yàn)數(shù)非正，此時(shí)原問題解未必可行的根底上，迭代求解目的函數(shù)值不增，當(dāng)原問題解變?yōu)榭尚薪鈺r(shí)，即到達(dá)最優(yōu)。2022-5-520+化標(biāo)準(zhǔn)形式：1 目的函數(shù)最大化？2 約束的處理？要求獲得初始單位陣基0,35 22 42. . 151612 min 3213121321yyyyyyytsyyywn對(duì)偶單純形算法的要求：保持對(duì)偶問題可行min + cj 0。cj-12-

14、16-1500CBBby1y2y3y4y50y4-2-2-40100y5-3-20-501cj zj-12-16-15000y4-2-2-4010-15y33/52/5010-1/5cj zj-6-1600-3-12y11120-1/20-15y31/50-4/511/5-1/5cj zj0-40-3-32022-5-521+先確定離基變量 br = minbi | bi 0, 那么對(duì)應(yīng)xr離基。+再確定進(jìn)基變量 = mincjzj/arj | arj 0,那么xj進(jìn)基繼續(xù)迭代。+假如某個(gè)基變量xi系數(shù)ci發(fā)生變化, cici ：所有檢驗(yàn)數(shù)都發(fā)生變化，目的函數(shù)值也會(huì)改變；此時(shí)需重新計(jì)算所有檢驗(yàn)

15、數(shù)，依情況考慮是否繼續(xù)迭代。n 檢驗(yàn)數(shù) j =cj cBB1pj ci aij目的函數(shù)值 z = z + ci bi+對(duì)和的分析見黑板。2022-5-524+考慮如下問題：1 把c1= 1改為 c1 = 4，求新問題最優(yōu)解；2 c2在什么范圍內(nèi)變化時(shí)，原問題最優(yōu)解仍是新問題的最優(yōu)解？0,4 26. . 2z max 32121321321xxxxxxxxtsxxx最優(yōu)單純形表為cj-12100CBBbx1x2x3x4x52x26111100 x51030111cj zj-30-1-202022-5-525+1x1是非基變量，只有1發(fā)生變化， c1 =1, c1 =4, c1=5， 1 = 1+

16、5 = 2 0 ,需要繼續(xù)迭代求解+2 x2是基變量，系數(shù)由2變?yōu)閏2 ， c2=c2-2,據(jù)6.12 = 2= 01 = 1 c2 1 = 1c23 = 3 c2 1 = 1c24 = 4 c2 1 = c2所有j 0，得c21最優(yōu)解不變，最優(yōu)值呢？cj42100CBBbx1x2x3x4x52x26111100 x51030111cj zj20-1-202x28/3012/32/3-1/34x110/3101/31/31/3cj zj00-5/3-8/3-2/3問題：新問題的最優(yōu)解和最優(yōu)值什么？2022-5-526+假設(shè)右端項(xiàng)b變?yōu)閎,此時(shí)xB= B1b和 z=cBB1b都有改變： 假如B1

17、b 0，最優(yōu)基不變，重新計(jì)算最優(yōu)解和最優(yōu)值即可。 假如B1b 0，說明B1b中有負(fù)的分量，當(dāng)前解不是不行的，但是對(duì)偶可行的為什么？，修改右端列，代以B1b，利用對(duì)偶單純形法繼續(xù)求解。2022-5-527n問題：請(qǐng)問最優(yōu)基B B是什么？ B B1是什么？ 5 求新問題的最優(yōu)解。），（），（變?yōu)椋?，（先將已知問題的最優(yōu)表如右給定線性規(guī)劃問題例TTT321321321321321323 )2(319 ) 1 (429,0,42 92. . 4z max 6.2 bbbxxxxxxxxxxxxtsxxxcj-1-14000CBBbx1x2x3x4x5x6-1x11/31-1/301/30-2/30 x

18、560200114x313/302/311/301/3cj zj0-40-10-22022-5-528+1 B1，重新計(jì)算xB= B1b即可：+ B1b = 1,4,4T 0, 現(xiàn)行解仍是可行解，又對(duì)偶可行的，故當(dāng)前基解為最優(yōu)解，x*=1,0,4, z* = 15.問題：最優(yōu)解和最優(yōu)值分別是什么？+2 計(jì)算 B1b = -1,5,2T ，b1 0,那么xj進(jìn)基繼續(xù)迭代。基列pi發(fā)生變化，變?yōu)閜i 1 假設(shè)pi 和原基中其余各列線性無關(guān)不易判斷，此時(shí)可在原最優(yōu)表中增加一列pn+1 = B1pi ,令cn+1= ci, 原ci = M充分小，在原最優(yōu)表根底上繼續(xù)迭代計(jì)算不作為大綱要求。2 假設(shè)pi

19、 和原基中其余各列線性相關(guān)，一般需要重新計(jì)算不作為大綱要求。增加一個(gè)變量的分析書P69類似和的分析，最優(yōu)表中先增加一列pn+1 = B1pn+1,再重新計(jì)算檢驗(yàn)數(shù)，根據(jù)檢驗(yàn)數(shù)的符號(hào)決定是否繼續(xù)迭代。2022-5-530+在第一章的例子中本幻燈片第二頁，假設(shè)增加一個(gè)變量，比方x6, c6 =4, p6=2,4,5T,分析最優(yōu)解的變化最優(yōu)解如右所示。cj23000CBBbx1x2x3x4x52x13101/20-1/50 x4400-214/53x2301001/5cj zj00-10-1/5n分析和求解：1 B，計(jì)算B1p6 增加到最優(yōu)表中；2 計(jì)算檢驗(yàn)數(shù)c6-z6，決定是否繼續(xù)迭代。4x604

20、112x13101/20-1/504x6100-1/21/41/513x22011/2-1/400cj zj00-1/2-1/4-2/502022-5-531+設(shè)原問題約束為Ax=b，x0, A為mn矩陣，秩A=m .現(xiàn)增加一個(gè)約束條件 x bm+1, 為n維行向量，此時(shí)：+假設(shè)原問題最優(yōu)解x*滿足新的約束條件，那么x*也是新問題的最優(yōu)解證明略。+假設(shè)x* bm+1,說明x*不是新問題的可行解，需要重新構(gòu)造新基B見黑板,這種情況下， x*是對(duì)偶可行的，可利用對(duì)偶單純形法求解約束寫成BxB+ NxN+xn+1 = bm+1：n 結(jié)論1：新約束添加消元后，原變量檢驗(yàn)數(shù)j1jn不變， n+1=0n

21、結(jié)論2：消元后bm+1 位置變?yōu)椋?bm+1 BB 1b 0,故可以利用對(duì)偶單純形法處理。新基B確實(shí)定，結(jié)論1和結(jié)論2見黑板推導(dǎo)。2022-5-532+在第一章的例子中本幻燈片第二頁，假設(shè)增加一個(gè)約束條件3x1+2x214,分析最優(yōu)解的變化。cj230000CBBbx1x2x3x4x5x62x13101/20-1/500 x4400-214/503x2301001/500 x614320001cj zj00-10-1/50n分析和求解：1原最優(yōu)解x*=3,3T, 不滿足新約束；2新約束化為等式參加到最終單純形表中;3把新約束的B部分消元為0，檢驗(yàn)數(shù)部分不必重新計(jì)算。0 x6502-3/203/

22、510 x6-100-3/201/512022-5-533n新問題最優(yōu)解：x*=8/3,3T, z*=43/3cj230000CBBbx1x2x3x4x5x62x13101/20-1/500 x4400-214/503x2301001/500 x6-100-3/201/51cj zj00-10-1/500 x32/30010-2/15-2/30 x416/300018/15-4/32x18/31000-2/151/3cj zj0000-1/3-2/32022-5-534+靈敏度分析研究的內(nèi)容參數(shù)aij,bi,cj離散變化時(shí)，最優(yōu)解和最優(yōu)值的變化情況最優(yōu)解或最優(yōu)基不變的情況下，參數(shù)aij,bi,

23、cj的變化區(qū)間+參數(shù)線性規(guī)劃的研究內(nèi)容和要求 研究內(nèi)容：引進(jìn)新參數(shù)，把原參數(shù)寫成與的線性和的形式，即bibi+di 以及cjcj+dj ,研究當(dāng)連續(xù)變化時(shí), 問題的最優(yōu)解值z(mì)=z和之間的關(guān)系。 要求： z=z 是的線性函數(shù)，因此一般要求b和c不能同時(shí)含參數(shù)，一般也不研究A的變化問題：為什么這樣要求？。 z=z一般為 +的分段線性函數(shù)。+參數(shù)線性規(guī)劃和靈敏度分析之間的關(guān)系稍后將2022-5-535+求解方法：先令=0求得最終單純形表將參數(shù)的反映到最終單純表中，據(jù)參數(shù)變化范圍迭代。cj2+2 3+ 000CBBbx1x2x3x4x52+2 x13101/20-1/50 x4400-214/53+ x2301001/5cj zj0