1、第二章 對(duì)偶理論與靈敏度分析講授：郝海日期：2006-10目 錄1線性規(guī)劃的對(duì)偶問(wèn)題2對(duì)偶問(wèn)題的基本性質(zhì)3影子價(jià)格4對(duì)偶單純形法5靈敏度分析6對(duì)偶的經(jīng)濟(jì)解釋線性規(guī)劃的對(duì)偶問(wèn)題一、相關(guān)概念二、對(duì)偶問(wèn)題的提出三、對(duì)偶問(wèn)題的定義四、對(duì)偶關(guān)系對(duì)應(yīng)表相 關(guān) 概 念轉(zhuǎn)置矩陣： 將一個(gè)mn矩陣A的行換成同序數(shù)的列而得到的新矩陣，稱(chēng)為矩陣A的轉(zhuǎn)置矩陣，記為AT。逆矩陣：設(shè)有n階方陣A，如果存在n階方陣B，滿足AB=BA=E，則稱(chēng)A陣是可逆的，B是A的逆矩陣，記做B=A-1。相 關(guān) 概 念相 關(guān) 概 念矩陣的運(yùn)算：矩陣的加法，矩陣的減法， 矩陣的乘法對(duì)偶問(wèn)題的提出美佳公司利用該公司資源生產(chǎn)兩種家電產(chǎn)品。III每

2、天可用 能力設(shè)備A（h）設(shè)備B（h）調(diào)試工序（h）06152115245利潤(rùn)（元）21設(shè)：y1表示單位時(shí)間（h）設(shè)備A的出讓代價(jià)； y2表示單位時(shí)間（h）設(shè)備B的出讓代價(jià); y3表示調(diào)試工序的出讓代價(jià)。已知：美佳公司用6小時(shí)設(shè)備A和l小時(shí)調(diào)試可生 產(chǎn)一件家電I，盈利2元；用5小時(shí)設(shè)備A，2小時(shí)設(shè)備B及14小時(shí)調(diào)試可生產(chǎn)一件家電II，盈利1元。由此y1，y2，y3的取值應(yīng)滿足:該公司希望用最小代價(jià)把美佳公司的全部資源收買(mǎi)過(guò)來(lái)。因此，線性規(guī)劃模型為：LP2原問(wèn)題對(duì)偶問(wèn)題LP2(2 1) x1x20 5 21 115245x1x20 6 15 2 121y1y2y3(15 24 5) y1y2y3L

3、P2對(duì)偶問(wèn)題的定義原始問(wèn)題max z=CXs.t.AX bX 0對(duì)偶問(wèn)題min W=bTYs.t. ATY CTY 0CTATbTminmnmaxbACmn對(duì)偶理論的基本思想 每一個(gè)線性規(guī)劃問(wèn)題都存在一個(gè)與其對(duì)偶的問(wèn)題，在求出一個(gè)問(wèn)題的解的時(shí)候，也同時(shí)給出了另一個(gè)問(wèn)題的解。對(duì)偶單純形法基本原理決策變量的檢驗(yàn)數(shù)可寫(xiě)成：CBB-1稱(chēng)為單純形乘子非基變量基變量XB XNXS0 XS bB N IcjzjCB CN0基變量非基變量XBXN XSCB XB B -1 bIB -1N B -1 Cjzj0CN -CB B -1N -CB B -1C -CB B 1A0-CB B 10A yC y 0若令

4、y= CBB-1則顯然y= CBB-1是其對(duì)偶問(wèn)題的可行解，即原問(wèn)題檢驗(yàn)數(shù)的相反數(shù)恰好是其對(duì)偶問(wèn)題的一個(gè)可行解！代入對(duì)偶問(wèn)題min W=bT ys.t. A y C y 0得：C -CB B 1A0-CB B 10y AC y 0也就是說(shuō)：當(dāng)原問(wèn)題為最優(yōu)解時(shí)，這時(shí)對(duì)偶問(wèn)題為可行解，且兩者具有相同的目標(biāo)函數(shù)值，對(duì)偶問(wèn)題的解也為最優(yōu)解.將這個(gè)解代入對(duì)偶問(wèn)題的目標(biāo)函數(shù)值，有： 原問(wèn)題的松弛變量對(duì)應(yīng)著其對(duì)偶問(wèn)題的決策變量！基變量非基變量XBXN XSCB XB B -1 bIB -1N B -1 cjzj0CN -CB B -1N -CB B -1互為對(duì)偶問(wèn)題變量的對(duì)應(yīng)關(guān)系原問(wèn)題變量松弛變量 x1 x

5、2x3 x4 x5 x3 15/2x1 7/2x2 3/20 01 00 11 5/4 -15/2 0 1/4 -1/2 0 -1/4 3/2cj-zj0 0 0 -1/4 -1/2 對(duì)偶問(wèn)題變量對(duì)偶問(wèn)題剩余變量 y1 y2 y3 y4 y5 y2 1/4y3 1/2 5/4 1 0 15/2 0 1-1/4 1/41 /2 -3/2cj-zj-15/2 0 0-7/2 -3/2對(duì)偶問(wèn)題的剩余變量y4 y5對(duì)偶問(wèn)題變量y1 y2 y3原問(wèn)題的松弛變量x3 x4 x5原問(wèn)題變量x1 x2原問(wèn)題最終表對(duì)偶問(wèn)題最終表 若存在對(duì)偶問(wèn)題的一個(gè)可行基B，只要令XB B-1b 0 ,則原問(wèn)題也有可行解,且同

6、為最優(yōu)解。互為對(duì)偶問(wèn)題變量的對(duì)應(yīng)關(guān)系可以看出：只需要求出原問(wèn)題（對(duì)偶問(wèn)題）的最優(yōu)解，從最優(yōu)解的單純形表中就可以同時(shí)得到其對(duì)偶問(wèn)題（原問(wèn)題）的最優(yōu)解。對(duì)偶單純形法的基本原理例1 1 2 加工能力(小時(shí)/天) A 2 2 12 B 1 2 8 C 4 0 16 D 0 4 12 2 3銷(xiāo)售收入產(chǎn)品設(shè)備寫(xiě)出原問(wèn)題與對(duì)偶問(wèn)題設(shè)x1 ， x2 為產(chǎn)品1，2的產(chǎn)量 2x1 +2x2 12 x1 +2x2 84x1 16 4x2 12x1 x2 0maxZ= 2x1 +3x2 (2 3) Cx1x2X2 2 1 2 4 0 0 4 Ax1x2X1281612b設(shè) ：y1 , y2 , y3 , y4分別為單

7、位時(shí)間內(nèi)出讓A, B, C, D設(shè)備的單價(jià)y1 y2y3 y4 2y1 +y2 +4y3 22y1 +2y2 +y4 3y1 y4 0minW=12y1+8y2 +16y3+12y4minW=bTyy1 y2 y3 y4(12 8 16 12 )bTATy CT2 1 4 02 2 0 4AT23CTmaxZ= 2x1 +3x2 2x1 +2x2 12 x1 +2x2 84x1 16 4x2 12x1 x2 0 2x1 +2x2 12 x1 +2x2 84x1 16 4x2 12x1 x2 0maxZ= 2x1 +3x2 2y1 +y2 +4y3 22y1 +2y2 +y4 3y1 y4 0m

8、inW=12y1+8y2 +16y3+12y4原問(wèn)題 對(duì)偶問(wèn)題 寫(xiě)出下面問(wèn)題的對(duì)偶規(guī)劃例2maxZ= 5x1 +6x2 3x1 2x2 =74x1 +x2 9x1 , x2 03x1 2x2 =73x1 2x2 73x1 2x2 7-3x1 +2x2 -73x1 2x2 7-3x1 +2x2 -74x1 +x2 9x1 , x2 0y1y1 y2對(duì)偶問(wèn)題令 y1 = y1 -y1 minW=7y1 -7y1 +9y23y1 -3y1 +4y2 5 -2y1 +2y1 +y2 6y1 , y1 , y2 0minW=7y1 +9y23y1+4y2 5 -2y1 +y2 6y1自由 , y2 03

9、y1-2y17y1對(duì)偶關(guān)系對(duì)應(yīng)表 原(對(duì)偶)問(wèn)題 對(duì)偶(原)問(wèn)題目標(biāo)函數(shù)類(lèi)型 max min目標(biāo)函數(shù)系數(shù) 目標(biāo)函數(shù)系數(shù) 右邊項(xiàng)系數(shù)與右邊項(xiàng)的對(duì)應(yīng)關(guān)系 右邊項(xiàng)系數(shù) 目標(biāo)函數(shù)系數(shù)變量數(shù)與約束數(shù) 變量數(shù)n 約束數(shù) n的對(duì)應(yīng)關(guān)系 約束數(shù)m 變量數(shù)m原問(wèn)題變量類(lèi)型與 變量 0 約束 對(duì)偶問(wèn)題約束類(lèi)型 變量 0 約束 的對(duì)應(yīng)關(guān)系 變量無(wú)限制 約束原問(wèn)題約束類(lèi)型與 約束 變量 0 對(duì)偶問(wèn)題變量類(lèi)型 約束 變量 0 的對(duì)應(yīng)關(guān)系 約束 變量無(wú)限制minW=7y1 +9y23y1+4y2 5 -2y1 +y2 6y1無(wú)限制 , y2 0maxZ= 5x1 +6x2 3x1 2x2 =74x1 +x2 9x1 ,

10、x2 0原問(wèn)題 對(duì)偶問(wèn)題 請(qǐng)寫(xiě)出以下問(wèn)題的對(duì)偶問(wèn)題maxZ=180y1+60y2+240y3S.t. y1+2y2+5y3 3 2y1-3y2+3y3 9 3y1+y2=4 y1無(wú)約束,y2 0,y3 0 若x是原問(wèn)題的可行解，y是對(duì)偶問(wèn)題的可行解。則有 cxyb 二. 弱對(duì)偶性：對(duì)偶問(wèn)題的基本性質(zhì)一 . 對(duì)稱(chēng)性 ：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題 推論(1)： 原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界，反之對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界。 推論(2)： 若原問(wèn)題（對(duì)偶問(wèn)題）為無(wú)界解，則其對(duì)偶問(wèn)題（原問(wèn)題）無(wú)可行解。注 ： 其逆不成立。 推論(3)：若原問(wèn)題有可

11、行解而其對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題目標(biāo)函數(shù)值無(wú)界，反之對(duì)偶問(wèn)題有可行解而其原問(wèn)題無(wú)可行解，則對(duì)偶問(wèn)題的目標(biāo)函數(shù)值無(wú)界。弱對(duì)偶性的三個(gè)推論AZ=W B 設(shè)x是原問(wèn)題的可行解，y是對(duì)偶問(wèn)題的可行解。 當(dāng) cx= yb 時(shí) x, y 是最優(yōu)解。三 . 最優(yōu)性 若原問(wèn)題及其對(duì)偶問(wèn)題均具有可行解，則兩者均具有最優(yōu)解且它們最優(yōu)解的目標(biāo)函數(shù)值相等。四 . 強(qiáng)對(duì)偶性（對(duì)偶定理）五.互補(bǔ)松弛性（松緊定理） 在線性規(guī)劃問(wèn)題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。也即：五.互補(bǔ)松弛性（松緊定理） 在線性規(guī)劃問(wèn)題的最優(yōu)解中，

12、如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。也即：推論(3)：若原問(wèn)題有可行解而其對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題目標(biāo)函數(shù)值無(wú)界，反之對(duì)偶問(wèn)題有可行解而其原問(wèn)題無(wú)可行解，則對(duì)偶問(wèn)題的目標(biāo)函數(shù)值無(wú)界。證明：1.證明原問(wèn)題有可行解2.寫(xiě)出其對(duì)偶問(wèn)題：-1y1-1y201 ）說(shuō)明原問(wèn)題和對(duì)偶問(wèn)題都有最優(yōu)解. 2 ）求原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)目標(biāo)函數(shù)值的一個(gè)上界和下界.四 . 強(qiáng)對(duì)偶性（對(duì)偶定理）若原問(wèn)題及其對(duì)偶問(wèn)題均具有可行解，則兩者均具有最優(yōu)解且它們最優(yōu)解的目標(biāo)函數(shù)值相等。 推論(1)： 原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題

13、目標(biāo)函數(shù)值的下界，反之對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界。1.證明原問(wèn)題有可行解解：1 ）說(shuō)明原問(wèn)題和對(duì)偶問(wèn)題都有最優(yōu)解.2. 對(duì)偶問(wèn)題有可行解：2）求原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)目標(biāo)函數(shù)值的一個(gè)上界和下界.用互補(bǔ)松弛定理計(jì)算對(duì)偶問(wèn)題的最優(yōu)解互補(bǔ)松弛定理:在線性規(guī)劃問(wèn)題的最優(yōu)解中，已知原問(wèn)題影子價(jià)格 式中bi是線性規(guī)劃原問(wèn)題約束條件的右端項(xiàng)，它代表第i種資源的擁有量；對(duì)偶變量yi*的意義代表在資源最優(yōu)利用條件下對(duì)單位第i種資源的估價(jià)。這種估價(jià)不是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而作的估價(jià)，為區(qū)別起見(jiàn)，稱(chēng)為影子價(jià)格(shadow price)。幾點(diǎn)說(shuō)明：1資源的影子

14、價(jià)格是未知數(shù)，有賴(lài)于企業(yè)資源狀況。2影子價(jià)格是一種邊際價(jià)格, 相當(dāng)于在資源得到最優(yōu)利用的生產(chǎn)條件下，每增加一個(gè)單位時(shí)目標(biāo)函數(shù)z的增量。3資源的影子價(jià)格實(shí)際上又是一種機(jī)會(huì)成本。4生產(chǎn)過(guò)程中如果某種資源未得到充分利用時(shí)，該種資源的影子價(jià)格為零；又當(dāng)資源的影子價(jià)格不為零時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完畢。 5對(duì)線性規(guī)劃問(wèn)題的求解是確定資源的最優(yōu)分配方案，而對(duì)于對(duì)偶問(wèn)題的求解則是確定資源的恰當(dāng)估價(jià)。對(duì)偶單純形法 基本思路：在迭代過(guò)程中保持原問(wèn)題的檢驗(yàn)數(shù)為非正，逐步替換負(fù)基變量，從而得到最優(yōu)解。即保持對(duì)偶問(wèn)題有可行解使原問(wèn)題具有可行解檢驗(yàn)數(shù)為非正替換負(fù)基變量對(duì)偶單純形法計(jì)算步驟 1. 列出初始單純形表，

15、且檢驗(yàn)數(shù)非正。 2. b值有否為負(fù)，無(wú)，計(jì)算結(jié)束。有，轉(zhuǎn)35.以ars為主元素，進(jìn)行迭代變換。6 . 返 3，直到b 0為止。用對(duì)偶單純形法求解下述線性規(guī)劃問(wèn)題例化標(biāo)準(zhǔn)型：整理得：解：Cj1524500CByBby1y2y3y4y50y420-6-1100y51-5-2-101 j=cj-zj24y21/3011/6-1/600y5-1/3-50-2/3-1/31 j=cj-zj-15-24-500-150-1-4024y21/4-5/410-1/41/4-5y31/215/2011/2-3/2 j=cj-zj-15/200-7/2-3/2在得到原始可行解時(shí)同時(shí)得到對(duì)偶可行解，已獲得最優(yōu)解：（

16、y1, y2, y3, y4, y5）=（0,1/4, 1/2,0,0） max w=17/2對(duì)偶問(wèn)題的最優(yōu)解為：（x1, x2, x3 ）=（ 7/2, 3/2, 15/2） min z=17/2例:(初始解原始、對(duì)偶都不可行的問(wèn)題)Cj322000CBXBbx1x2x3x4x5x60 x441111000 x552310100 x62221001 j=cj-zj322000先解決對(duì)偶可行性0 x341111000 x59120-1100 x62110101 j=cj-zj500-200已得到對(duì)偶可行解，再用對(duì)偶單純形法求解Cj322000CBXBbx1x2x3x4x5x62x317/21/

17、2013/2-1/20-2x29/2-1/2101/2-1/200 x65/21/2001/21/21 j=cj-zj500-2000 x360012010 x270100110 x15010011 j=cj-zj000-7510在得到原始可行解時(shí)同時(shí)得到對(duì)偶可行解，已獲得最優(yōu)解：（x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） minz=17對(duì)偶問(wèn)題的最優(yōu)解為： （y1, y2, y3）=（7,5, 10） 即（y1, y2, y3）=（7,5, 10） maxw=17對(duì)偶單純形法中出現(xiàn)的一些情況2.對(duì)偶單純形法與原始單純形法的比較：1.對(duì)于對(duì)偶問(wèn)題有可行解，而原問(wèn)題無(wú)可行解的判斷。項(xiàng)目原始單純形法對(duì)偶單純形法選主元素按列選主元按行選主元確定主元素arj 0arj 1時(shí)，表中為-1/4+1/4 0，x4入基，x3出基。b.當(dāng) 0，x5入基，x2出基。 2+ 1+2 0 0 002+1+2 0 0 0 -1/4+1/4 -1/2-5/2x46234/5-1/51/5100-6100 0 1/5-1/5 0 -2-顯然，當(dāng) 1時(shí)，當(dāng)前表檢驗(yàn)數(shù)均取負(fù)值，即當(dāng)前解為最優(yōu)解，且z78 。 2+ 1+2 0 0 002+0 0 0 0 -1/4+1/4 -1/2-5/21541x551/32/301/61/6001 0 1/35/3 0 -1/3-