第2章 對(duì)偶理論與靈敏度分析.ppt

1、第二章 對(duì)偶理論與靈敏度分析,講授：郝海 日期：2006-10,目 錄,1線性規(guī)劃的對(duì)偶問題 2對(duì)偶問題的基本性質(zhì) 3影子價(jià)格 4對(duì)偶單純形法 5靈敏度分析 6對(duì)偶的經(jīng)濟(jì)解釋,線性規(guī)劃的對(duì)偶問題,一、相關(guān)概念 二、對(duì)偶問題的提出 三、對(duì)偶問題的定義 四、對(duì)偶關(guān)系對(duì)應(yīng)表,相 關(guān) 概 念,轉(zhuǎn)置矩陣： 將一個(gè)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) 概 念,矩陣的運(yùn)算：矩陣的加法，矩陣的減法， 矩陣的乘法,對(duì)偶問題的提出,美佳

2、公司利用該公司資源生產(chǎn)兩種家電產(chǎn)品。,設(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à)把美佳公司的全部資源收買過來。,因此，線性規(guī)劃模型為：,LP2,原問題,對(duì)偶問題,LP2,LP2,對(duì)偶問題的定義,原始問題 max z=CX s.t.AX b X 0,對(duì)偶問題 min W=bTY s.t. ATY CT Y 0,對(duì)偶理論的基本

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

4、的決策變量！,互為對(duì)偶問題變量的對(duì)應(yīng)關(guān)系,對(duì)偶問題的剩余變量 y4 y5,對(duì)偶問題變量 y1 y2 y3,原問題的松弛變量 x3 x4 x5,原問題變量 x1 x2,原問題最終表,對(duì)偶問題最終表,若存在對(duì)偶問題的一個(gè)可行基B，只要令XB B-1b 0 ,則原問題也有可行解,且同為最優(yōu)解。,互為對(duì)偶問題變量的對(duì)應(yīng)關(guān)系可以看出：,只需要求出原問題（對(duì)偶問題）的最優(yōu)解，從最優(yōu)解的單純形表中就可以同時(shí)得到其對(duì)偶問題（原問題）的最優(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,寫出原問題與對(duì)偶問題,設(shè)x1

5、， x2 為產(chǎn)品1，2的產(chǎn)量,maxZ= 2x1 +3x2,設(shè) ：y1 , y2 , y3 , y4分別為單位時(shí)間內(nèi)出讓A, B, C, D設(shè)備的單價(jià),minW=bTy,ATy CT,maxZ= 2x1 +3x2,原問題,對(duì)偶問題,寫出下面問題的對(duì)偶規(guī)劃,例2,3x1 2x2 =7,-3x1 +2x2 -7,對(duì)偶問題,令 y1 = y1 -y1 ,7y1,對(duì)偶關(guān)系對(duì)應(yīng)表,原(對(duì)偶)問題 對(duì)偶(原)問題 目標(biāo)函數(shù)類型 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 原問題變

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

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

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

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

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

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

12、 w=17/2 對(duì)偶問題的最優(yōu)解為： （x1, x2, x3 ）=（ 7/2, 3/2, 15/2） min z=17/2,例:(初始解原始、對(duì)偶都不可行的問題),先解決對(duì)偶可行性,已得到對(duì)偶可行解，再用對(duì)偶單純形法求解,在得到原始可行解時(shí)同時(shí)得到對(duì)偶可行解，已獲得最優(yōu)解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） minz=17 對(duì)偶問題的最優(yōu)解為： （y1, y2, y3）=（7,5, 10） 即（y1, y2, y3）=（7,5, 10） maxw=17,對(duì)偶單純形法中出現(xiàn)的一些情況,2.對(duì)偶單純形法與原始單純形法的比較：,1.對(duì)于對(duì)偶問題有

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

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

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

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

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

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

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

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