第2章-對偶理論與靈敏度分析課件

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

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

3、P2對偶問題的定義原始問題max z=CXs.t.AX bX 0對偶問題min W=bTYs.t. ATY CTY 0CTATbTminmnmaxbACmn對偶理論的基本思想 每一個線性規(guī)劃問題都存在一個與其對偶的問題，在求出一個問題的解的時候，也同時給出了另一個問題的解。對偶單純形法基本原理決策變量的檢驗數(shù)可寫成：CBB-1稱為單純形乘子非基變量基變量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是其對偶問題的可行解，即原問題檢驗數(shù)的相反數(shù)恰好是其對偶問題的一個可行解！代入對偶問題min W=bT ys.t. A y C y 0得：C -CB B 1A0-CB B 10y AC y 0也就是說：當原問題為最優(yōu)解時，這時對偶問題為可行解，且兩者具有相同的目標函數(shù)值，對偶問題的解也為最優(yōu)解.將這個解代入對偶問題的目標函數(shù)值，有： 原問題的松弛變量對應(yīng)著其對偶問題的決策變量！基變量非基變量XBXN XSCB XB B -1 bIB -1N B -1 cjzj0CN -CB B -1N -CB B -1互為對偶問題變量的對應(yīng)關(guā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 對偶問題變量對偶問題剩余變量 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對偶問題的剩余變量y4 y5對偶問題變量y1 y2 y3原問題的松弛變量x3 x4 x5原問題變量x1 x2原問題最終表對偶問題最終表 若存在對偶問題的一個可行基B，只要令XB B-1b 0 ,則原問題也有可行解,且同

6、為最優(yōu)解?；閷ε紗栴}變量的對應(yīng)關(guān)系可以看出：只需要求出原問題（對偶問題）的最優(yōu)解，從最優(yōu)解的單純形表中就可以同時得到其對偶問題（原問題）的最優(yōu)解。對偶單純形法的基本原理例1 1 2 加工能力(小時/天) A 2 2 12 B 1 2 8 C 4 0 16 D 0 4 12 2 3銷售收入產(chǎn)品設(shè)備寫出原問題與對偶問題設(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、位時間內(nèi)出讓A, B, C, D設(shè)備的單價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原問題 對偶問題 寫出下面問題的對偶規(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對偶問題令 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對偶關(guān)系對應(yīng)表 原(對偶)問題 對偶(原)問題目標函數(shù)類型 max min目標函數(shù)系數(shù) 目標函數(shù)系數(shù) 右邊項系數(shù)與右邊項的對應(yīng)關(guān)系 右邊項系數(shù) 目標函數(shù)系數(shù)變量數(shù)與約束數(shù) 變量數(shù)n 約束數(shù) n的對應(yīng)關(guān)系 約束數(shù)m 變量數(shù)m原問題變量類型與 變量 0 約束 對偶問題約束類型 變量 0 約束 的對應(yīng)關(guān)系 變量無限制 約束原問題約束類型與 約束 變量 0 對偶問題變量類型 約束 變量 0 的對應(yīng)關(guān)系 約束 變量無限制minW=7y1 +9y23y1+4y2 5 -2y1 +y2 6y1無限制 , y2 0maxZ= 5x1 +6x2 3x1 2x2 =74x1 +x2 9x1 ,

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

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

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

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

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

15、且檢驗數(shù)非正。 2. b值有否為負，無，計算結(jié)束。有，轉(zhuǎn)35.以ars為主元素，進行迭代變換。6 . 返 3，直到b 0為止。用對偶單純形法求解下述線性規(guī)劃問題例化標準型：整理得：解：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在得到原始可行解時同時得到對偶可行解，已獲得最優(yōu)解：（

16、y1, y2, y3, y4, y5）=（0,1/4, 1/2,0,0） max w=17/2對偶問題的最優(yōu)解為：（x1, x2, x3 ）=（ 7/2, 3/2, 15/2） min z=17/2例:(初始解原始、對偶都不可行的問題)Cj322000CBXBbx1x2x3x4x5x60 x441111000 x552310100 x62221001 j=cj-zj322000先解決對偶可行性0 x341111000 x59120-1100 x62110101 j=cj-zj500-200已得到對偶可行解，再用對偶單純形法求解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在得到原始可行解時同時得到對偶可行解，已獲得最優(yōu)解：（x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） minz=17對偶問題的最優(yōu)解為： （y1, y2, y3）=（7,5, 10） 即（y1, y2, y3）=（7,5, 10） maxw=17對偶單純形法中出現(xiàn)的一些情況2.對偶單純形法與原始單純形法的比較：1.對于對偶問題有可行解，而原問題無可行解的判斷。項目原始單純形法對偶單純形法選主元素按列選主元按行選主元確定主元素arj 0arj 1時，表中為-1/4+1/4 0，x4入基，x3出基。b.當 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-顯然，當 1時，當前表檢驗數(shù)均取負值，即當前解為最優(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-