第2章 對偶理論與靈敏度分析.ppt

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

2、公司利用該公司資源生產(chǎn)兩種家電產(chǎn)品。,設：y1表示單位時間（h）設備A的出讓代價； y2表示單位時間（h）設備B的出讓代價; y3表示調(diào)試工序的出讓代價。 已知：美佳公司用6小時設備A和l小時調(diào)試可生 產(chǎn)一件家電I，盈利2元；用5小時設備A，2小時設備B及14小時調(diào)試可生產(chǎn)一件家電II，盈利1元。,由此y1，y2，y3的取值應滿足:,該公司希望用最小代價把美佳公司的全部資源收買過來。,因此，線性規(guī)劃模型為：,LP2,原問題,對偶問題,LP2,LP2,對偶問題的定義,原始問題 max z=CX s.t.AX b X 0,對偶問題 min W=bTY s.t. ATY CT Y 0,對偶理論的基本

3、思想,每一個線性規(guī)劃問題都存在一個與其對偶的問題，在求出一個問題的解的時候，也同時給出了另一個問題的解。,對偶單純形法基本原理,決策變量的檢驗數(shù)可寫成：,CBB-1稱為單純形乘子,C -CB B 1A0,-CB B 10,若令 y= CBB-1,則,顯然y= CBB-1是其對偶問題的可行解，即 原問題檢驗數(shù)的相反數(shù)恰好是其對偶問題的一個可行解！,代入,對偶問題 min W=bT y s.t. A y C y 0,得：,也就是說：當原問題為最優(yōu)解時，這時對偶問題為可行解，且兩者具有相同的目標函數(shù)值，對偶問題的解也為最優(yōu)解.,將這個解代入對偶問題的目標函數(shù)值，有：,原問題的松弛變量對應著其對偶問題

4、的決策變量！,互為對偶問題變量的對應關(guān)系,對偶問題的剩余變量 y4 y5,對偶問題變量 y1 y2 y3,原問題的松弛變量 x3 x4 x5,原問題變量 x1 x2,原問題最終表,對偶問題最終表,若存在對偶問題的一個可行基B，只要令XB B-1b 0 ,則原問題也有可行解,且同為最優(yōu)解。,互為對偶問題變量的對應關(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,寫出原問題與對偶問題,設x1

5、， x2 為產(chǎn)品1，2的產(chǎn)量,maxZ= 2x1 +3x2,設 ：y1 , y2 , y3 , y4分別為單位時間內(nèi)出讓A, B, C, D設備的單價,minW=bTy,ATy CT,maxZ= 2x1 +3x2,原問題,對偶問題,寫出下面問題的對偶規(guī)劃,例2,3x1 2x2 =7,-3x1 +2x2 -7,對偶問題,令 y1 = y1 -y1 ,7y1,對偶關(guān)系對應表,原(對偶)問題 對偶(原)問題 目標函數(shù)類型 max min 目標函數(shù)系數(shù) 目標函數(shù)系數(shù) 右邊項系數(shù) 與右邊項的對應關(guān)系 右邊項系數(shù) 目標函數(shù)系數(shù) 變量數(shù)與約束數(shù) 變量數(shù)n 約束數(shù) n 的對應關(guān)系 約束數(shù)m 變量數(shù)m 原問題變

6、量類型與 變量 0 約束 對偶問題約束類型 變量 0 約束 的對應關(guān)系 變量無限制 約束 原問題約束類型與 約束 變量 0 對偶問題變量類型 約束 變量 0 的對應關(guān)系 約束 變量無限制,minW=7y1 +9y2,原問題,對偶問題,請寫出以下問題的對偶問題,maxZ=180y1+60y2+240y3,S.t. y1+2y2+5y3 3 2y1-3y2+3y3 9 3y1+y2=4 y1無約束,y2 0,y3 0,若x是原問題的可行解，y是對偶問題的可行解。則有 cxyb,二. 弱對偶性：,對偶問題的基本性質(zhì),一 . 對稱性 ：,對偶問題的對偶是原問題,推論(1)： 原問題任一可行解的目標函數(shù)

7、值是其對偶問題目標函數(shù)值的下界，反之對偶問題任一可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界。,推論(2)： 若原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行解。注 ： 其逆不成立。,推論(3)：若原問題有可行解而其對偶問題無可行解，則原問題目標函數(shù)值無界，反之對偶問題有可行解而其原問題無可行解，則對偶問題的目標函數(shù)值無界。,弱對偶性的三個推論,AZ=W B,設x是原問題的可行解，y是對偶問題的可行解。 當 cx= yb 時 x, y 是最優(yōu)解。,三 . 最優(yōu)性,若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解且它們最優(yōu)解的目標函數(shù)值相等。,四 . 強對偶性（對偶定理）,五.互補

8、松弛性（松緊定理）,在線性規(guī)劃問題的最優(yōu)解中，如果對應某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；反之如果約束條件取嚴格不等式，則其對應的對偶變量一定為零。也即：,五.互補松弛性（松緊定理）,在線性規(guī)劃問題的最優(yōu)解中，如果對應某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；反之如果約束條件取嚴格不等式，則其對應的對偶變量一定為零。也即：,推論(3)：若原問題有可行解而其對偶問題無可行解，則原問題目標函數(shù)值無界，反之對偶問題有可行解而其原問題無可行解，則對偶問題的目標函數(shù)值無界。,證明：,1.證明原問題有可行解,2.寫出其對偶問題：,1 ）說明原問題和對偶問題都有最優(yōu)解. 2

9、 ）求原問題和對偶問題的最優(yōu)目標函數(shù)值的一個上界和下界.,四 . 強對偶性（對偶定理）若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解且它們最優(yōu)解的目標函數(shù)值相等。,推論(1)： 原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界，反之對偶問題任一可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界。,1.證明原問題有可行解,解：,1 ）說明原問題和對偶問題都有最優(yōu)解.,2. 對偶問題有可行解：,2）求原問題和對偶問題的最優(yōu)目標函數(shù)值的一個上界和下界.,用互補松弛定理計算對偶問題的最優(yōu)解,互補松弛定理:在線性規(guī)劃問題的最優(yōu)解中，,已知原問題,影子價格,式中bi是線性規(guī)劃原問題約束條件的右端項

10、，它代表第i種資源的擁有量；對偶變量yi*的意義代表在資源最優(yōu)利用條件下對單位第i種資源的估價。這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻而作的估價，為區(qū)別起見，稱為影子價格(shadow price)。,幾點說明：,1資源的影子價格是未知數(shù)，有賴于企業(yè)資源狀況。,2影子價格是一種邊際價格, 相當于在資源得到最優(yōu)利用的生產(chǎn)條件下，每增加一個單位時目標函數(shù)z的增量。,3資源的影子價格實際上又是一種機會成本。,4生產(chǎn)過程中如果某種資源未得到充分利用時，該種資源的影子價格為零；又當資源的影子價格不為零時，表明該種資源在生產(chǎn)中已耗費完畢。,5對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案

11、，而對于對偶問題的求解則是確定資源的恰當估價。,對偶單純形法,基本思路：在迭代過程中保持原問題的檢驗數(shù)為非正，逐步替換負基變量，從而得到最優(yōu)解。,即保持對偶問題有可行解,使原問題具有可行解,檢驗數(shù)為非正,替換負基變量,對偶單純形法計算步驟,1. 列出初始單純形表，且檢驗數(shù)非正。,2. b值有否為負，無，計算結(jié)束。有，轉(zhuǎn)3,5.以ars為主元素，進行迭代變換。,6 . 返 3，直到b 0為止。,用對偶單純形法求解下述線性規(guī)劃問題,例,化標準型：,整理得：,解：,在得到原始可行解時同時得到對偶可行解，已獲得最優(yōu)解： （y1, y2, y3, y4, y5）=（0,1/4, 1/2,0,0） max

12、 w=17/2 對偶問題的最優(yōu)解為： （x1, x2, x3 ）=（ 7/2, 3/2, 15/2） min z=17/2,例:(初始解原始、對偶都不可行的問題),先解決對偶可行性,已得到對偶可行解，再用對偶單純形法求解,在得到原始可行解時同時得到對偶可行解，已獲得最優(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.對于對偶問題有

13、可行解，而原問題無可行解的判斷。,對偶單純形法的優(yōu)點：,用對偶單純形法求解線性規(guī)劃問題時，當約束條件為“”時，不必引進人工變量，使計算簡化。,對偶單純形法的應用范圍：,在初始單純形表中其對偶問題應是基可行解這點，對多數(shù)線性規(guī)劃問題很難實現(xiàn)。因此對偶單純形法一般不單獨使用，多用于靈敏度分析等用途。,靈敏度分析,當這些參數(shù)中的一個或幾個發(fā)生變化時，問題的最優(yōu)解會有什么變化，或者這些參數(shù)在一個多大范圍內(nèi)變化時，問題的最優(yōu)解不變。,靈敏度分析的定義,靈敏度分析所要研究解決的問題,是指對系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。,條件變化,aij，bi，cj,最優(yōu)解,多大范圍內(nèi)變化,靈敏度分析原

14、理,單純形法的迭代計算是從一組基向量變換為另一組基向量，表中每步迭代得到的數(shù)字只隨基向量的不同選擇而改變，因此有可能把個別參數(shù)的變化直接在計算得到最優(yōu)解的最終單純形表上反映出來。,數(shù)字只隨基向量的不同選擇而改變,最終單純形表,1將參數(shù)的改變計算反映到最終單純形表上來：,靈敏度分析的步驟,最終單純形表,B-1B,3檢查對偶問題是否仍為可行解； 4按下表所列情況得以結(jié)論和決定繼續(xù)計算的步驟。,2檢查原問題是否仍為可行解；,靈敏度分析的任務,(1)、參數(shù)A，b，C在什么范圍內(nèi)變動，對當前方案無影響？,(2)、參數(shù)A，b，C中的一個(幾個)變動，對當前方案的影響？,(3)、如果最優(yōu)方案改變，如何用簡便

15、方法求新方案？,一、分析Cj的變化,Cj的變化僅僅影響到檢驗數(shù)(Cj-Zj)的變化。所以將Cj的變化直接反映到最終單純形表中，只可能出現(xiàn)前兩種情況。,Cj的變化僅僅影響到檢驗數(shù)(Cj-Zj)的變化,最終單純形表,例:,(1)若家電I的利潤降至1. 5元件，而家電的利潤增至2元件時，美佳公司最優(yōu)生產(chǎn)計劃有何變化； (2)若家電I的利潤不變，則家電II的利潤在什么范圍內(nèi)變化時，則該公司的最優(yōu)生產(chǎn)計劃將不發(fā)生變化？,在第一章例1的美佳公司例子中:,(1) 若家電I的利潤降至1. 5元件，而家電的利潤增至2元件時，美佳公司最優(yōu)生產(chǎn)計劃有何變化；,最終單純形表如下：,原問題可行，對偶問題不可行,用單純形

16、法繼續(xù)迭代求解。,將家電I，II的利潤變化cj直接反映到最終單純形表中。,-2 0 -1 1/8 -9/4,為使表中的解仍為最優(yōu)解，應有,即家電II的利潤C2的變化范圍應滿足：,2) 若家電I的利潤不變，則家電II的利潤在什么范圍內(nèi)變化時，則該公司的最優(yōu)生產(chǎn)計劃將不發(fā)生變化？,0 0 0 -1/4+1/4 -1/2-3/2 ,設家電II的利潤為(1+)元，反映到最終單純形表中為：,二、分析bi的變化,bj的變化在實際問題中反映為可用資源數(shù)量的變化。,可能出現(xiàn)的解的情況：,例：,若：(1)若設備A和調(diào)試工序的每天能力不變，而設備B每天的能力增加到32小時，分析公司最優(yōu)計劃的變化； (2)若設備A

17、和B每天可用能力不變，則調(diào)試工序能力在什么范圍內(nèi)變化時，問題的最優(yōu)基不變。,在上述美佳公司的例子中，,解：,1.求bj的變化量。,2.列出最終單純表。,1/2,原問題不可行，對偶問題可行，用對偶單純形法繼續(xù)迭代求：,3.在最終單純表中直接表現(xiàn)bj的變化量：bbb,35/2 11/2 -1/2,單純形表中b列數(shù)字為：,（2）調(diào)試工序能力在什么范圍內(nèi)變化時，問題的最優(yōu)基不變,解：,三、增加一個變量xj的分析,增加一個變量在實際問題中反映為增加一種新的產(chǎn)品。,可能出現(xiàn)的解的情況：,其分析步驟為：,例：,在美佳公司例子中，設該公司又計劃推出新型號的家電III，生產(chǎn)一件所需設備A、B及調(diào)試工序的時間分別

18、為3小時、4小時、2小時，該產(chǎn)品的預期盈利為3元件。試分析該種產(chǎn)品是否值得投產(chǎn)，如投產(chǎn)，對該公司的最優(yōu)生產(chǎn)計劃有何變化。,解：,1.計算由于增加新產(chǎn)品導致的參數(shù)改變量6，p6：,6,2.在最終單純表中直接表現(xiàn)c6，6，p6的變化量：,3 x6 -7 0 2 1,原問題可行，對偶問題不可行，用原始單純形法繼續(xù)迭代求解,四、分析參數(shù)aij的變化,1.變量xj在最終單純形表中為非基變量； 分析步驟與增加變量的情況雷同。 可能出現(xiàn)的解的情況：,aij的變化使線性規(guī)劃的約束系數(shù)矩陣A發(fā)生變化。,出現(xiàn)的兩種情況：,2.變量xj在最終單純形表中為基變量。,用對偶單純形法繼續(xù)解迭代求最優(yōu)解,在美佳公司的例子中

19、，若家電II每件需設備A，B和調(diào)試工時變?yōu)?小時、4小時、1小時，該產(chǎn)品的利潤變?yōu)?元/件，試重新確定該公司最優(yōu)生產(chǎn)計劃。,：將生產(chǎn)工時變化后的新家電II看作是一種新產(chǎn)品，生產(chǎn)量為x2。,例:,解,因x2已變換為x2 ，故用單純形算法將x2替換出基變量中的x2 ，并在單純形表中不再保留x2。,在最終單純表中直接表現(xiàn)aij的變化量：,原問題不可行，對偶問題也不可行，采用對偶單純形法繼續(xù)迭代求解。,五、增加一個約束條件的分析,先將原問題最優(yōu)解的變量值代入新增的約束條件。如滿足，說明新增的約束未起到限制作用，原最優(yōu)解不變。 否則，將新增的約束直接反映到最終單純形表中再進步分析。,增加一個約束條件在實

20、際問題中相當增添一道工序。 分析的方法：,例：,仍以美佳公司為例，設家電I，II經(jīng)調(diào)試后，還需經(jīng)過道環(huán)境試驗工序。家電I每件須環(huán)境試驗3小時，家電II每件2小時，又知環(huán)境試驗工序每天生產(chǎn)能力為12小時。試分析增加該工序后的美佳公司最優(yōu)生產(chǎn)計劃。,0 x6 12 3 2 0 0 0 1,原問題不可行，對偶問題可行， 用對偶單純形法繼續(xù)迭代求解,參數(shù)線性規(guī)劃,定義：,靈敏度分析中研究cj、bi等參數(shù)在保持最優(yōu)解或最優(yōu)基不變時的允許變化范圍或改變到某一值時對問題最優(yōu)解的影響，若C按(C+ C*)或b按(b+ b*)連續(xù)變化，而目標函數(shù)值z() 是參數(shù)的線性函數(shù)，稱這樣的規(guī)劃問題為參數(shù)線性規(guī)劃問題。,參數(shù)規(guī)劃的形式：,max z（ ）= (C+ C*) X s.t.AX b X 0,max z（ ）= (b+ b*) X s.t.AX b+ b* X 0,其中，b為原問題的資源向量， b*為變動