對偶理論與靈敏度分析上課

1、對偶理論與靈敏度分析對偶理論與靈敏度分析 1線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題 2對偶問題的基本性質(zhì)對偶問題的基本性質(zhì) 3影子價格影子價格 4對偶單純形法對偶單純形法 5靈敏度分析靈敏度分析 6對偶的經(jīng)濟解釋對偶的經(jīng)濟解釋 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題 一、相關(guān)概念一、相關(guān)概念 二、對偶問題的提出二、對偶問題的提出 三、對偶問題的定義三、對偶問題的定義 四、對偶關(guān)系對應(yīng)表四、對偶關(guān)系對應(yīng)表 相相 關(guān)關(guān) 概概 念念 轉(zhuǎn)置矩陣：轉(zhuǎn)置矩陣： 將一個將一個mn矩陣矩陣A的行換成同序數(shù)的列而的行換成同序數(shù)的列而 得到的新矩陣，稱為矩陣得到的新矩陣，稱為矩陣A的轉(zhuǎn)置矩陣，記為的轉(zhuǎn)置矩陣，記為AT

2、。 逆矩陣：逆矩陣：設(shè)有設(shè)有n階方陣階方陣A，如果存在，如果存在n階方陣階方陣B，滿足，滿足 AB=BA=E，則稱，則稱A陣是可逆的，陣是可逆的，B是是A的逆矩陣，記做的逆矩陣，記做 B=A-1。 矩陣的運算：矩陣的運算：矩陣的加法，矩陣的減法，矩陣的乘法矩陣的加法，矩陣的減法，矩陣的乘法 對偶問題的提出對偶問題的提出 美佳公司利用該公司資源生產(chǎn)兩種家電產(chǎn)品。美佳公司利用該公司資源生產(chǎn)兩種家電產(chǎn)品。 I IIIII每天可用每天可用 能力能力 設(shè)備設(shè)備A A（h h） 設(shè)備設(shè)備B B（h h） 調(diào)試工序（調(diào)試工序（h h） 0 0 6 6 1 1 5 5 2 2 1 1 1515 2424 5

3、5 利潤（元）利潤（元）2 21 1 0, 5 2426 155 2max1 21 21 21 2 21 xx xx xx x xxzLP 設(shè)：設(shè)：y1表示單位時間（表示單位時間（h）設(shè)備）設(shè)備A的出讓代價；的出讓代價； y2表示單位時間（表示單位時間（h）設(shè)備）設(shè)備B的出讓代價的出讓代價; y3表示調(diào)試工序的出讓代價。表示調(diào)試工序的出讓代價。 已知：美佳公司用已知：美佳公司用6小時設(shè)備小時設(shè)備A和和l小時調(diào)試可生小時調(diào)試可生 產(chǎn)一件產(chǎn)一件 家電家電I，盈利，盈利2元；用元；用5小時設(shè)備小時設(shè)備A，2小時設(shè)備小時設(shè)備B及及14小時小時 調(diào)試可生產(chǎn)一件家電調(diào)試可生產(chǎn)一件家電II，盈利，盈利1元。

4、元。 由此由此y1，y2，y3的取值應(yīng)滿足的取值應(yīng)滿足: 該公司希望用最小代價把美佳公司的全部資源收買過該公司希望用最小代價把美佳公司的全部資源收買過 來。來。 因此，線性規(guī)劃模型為：因此，線性規(guī)劃模型為： 125 26 321 32 yyy yy 321 52415minyyyz 321 52415minyyyz 0, 125 26 321 321 32 yyy yyy yy LP2 原問題原問題 對偶問題對偶問題 0, 5 2426 155 2max1 21 21 21 2 21 xx xx xx x xxzLP 321 52415minyyyz 0, 125 26 321 321 32

5、yyy yyy yy LP2 (2 1) x1 x2 0 5 6 2 1 1 15 24 5 x1 x2 0 6 1 5 2 1 2 1 y1 y2 y3 (15 24 5) y1 y2 y3 0, 5 2426 155 2max1 21 21 21 2 21 xx xx xx x xxzLP 321 52415minyyyz 0, 125 26 321 321 32 yyy yyy yy LP2 對偶問題的定義對偶問題的定義 原始問題原始問題 max z=CX s.t.AX b X 0 對偶問題對偶問題 min W=bTY s.t. ATY CT Y 0 CTAT bT min m n ma

6、x bA C m n 例例1 1 2 加工能力加工能力(小時小時/天天) A 2 2 12 B 1 2 8 C 4 0 16 D 0 4 12 2 3 銷售收入銷售收入 產(chǎn)品產(chǎn)品 設(shè)備設(shè)備 寫出原問題與對偶問題寫出原問題與對偶問題 設(shè)設(shè)x1 ， x2 為產(chǎn)品為產(chǎn)品1，2的產(chǎn)量的產(chǎn)量 2x1 +2x2 12 x1 +2x2 8 4x1 16 4x2 12 x1 x2 0 maxZ= 2x1 +3x2 (2 3) C x1 x2 X 2 2 1 2 4 0 0 4 A x1 x2 X 12 8 16 12 b 設(shè)設(shè) ：y1 , y2 , y3 , y4分別為單位時間內(nèi)出讓分別為單位時間內(nèi)出讓A,

7、B, C, D設(shè)備設(shè)備 的單價的單價 y1 y2 y3 y4 2y1 +y2 +4y3 2 2y1 +2y2 +y4 3 y1 y4 0 minW=12y1+8y2 +16y3+12y4 minW=bTy y1 y2 y3 y4 (12 8 16 12 ) bT ATy CT 2 1 4 0 2 2 0 4 AT 2 3 CT maxZ= 2x1 +3x2 2x1 +2x2 12 x1 +2x2 8 4x1 16 4x2 12 x1 x2 0 2x1 +2x2 12 x1 +2x2 8 4x1 16 4x2 12 x1 x2 0 maxZ= 2x1 +3x2 2y1 +y2 +4y3 2 2y

8、1 +2y2 +y4 3 y1 y4 0 minW=12y1+8y2 +16y3+12y4 原問題原問題 對偶問題對偶問題 寫出下面問題的對偶規(guī)劃寫出下面問題的對偶規(guī)劃 例例2 maxZ= 5x1 +6x2 3x1 2x2 =7 4x1 +x2 9 x1 , x2 0 3x1 2x2 =7 3x1 2x2 7 3x1 2x2 7 -3x1 +2x2 -7 3x1 2x2 7 -3x1 +2x2 -7 4x1 +x2 9 x1 , x2 0 y1 y1 y2 對偶問題對偶問題 令令 y1 = y1 -y1 minW=7y1 -7y1 +9y2 3y1 -3y1 +4y2 5 -2y1 +2y1

9、+y2 6 y1 , y1 , y2 0 minW=7y1 +9y2 3y1+4y2 5 -2y1 +y2 6 y1自由自由 , y2 0 3y1 -2y1 7y1 對偶關(guān)系對應(yīng)表對偶關(guān)系對應(yīng)表 原原( (對偶對偶) )問題問題 對偶對偶( (原原) )問題問題 目標函數(shù)類型目標函數(shù)類型 max minmax min 目標函數(shù)系數(shù)目標函數(shù)系數(shù) 目標函數(shù)系數(shù)目標函數(shù)系數(shù) 右邊項系數(shù)右邊項系數(shù) 與右邊項的對應(yīng)關(guān)系與右邊項的對應(yīng)關(guān)系 右邊項系數(shù)右邊項系數(shù) 目標函數(shù)系數(shù)目標函數(shù)系數(shù) 變量數(shù)與約束數(shù)變量數(shù)與約束數(shù) 變量數(shù)變量數(shù)n n 約束數(shù)約束數(shù) n n 的對應(yīng)關(guān)系的對應(yīng)關(guān)系 約束數(shù)約束數(shù)m m 變量數(shù)

10、變量數(shù)m m 原問題原問題變量變量類型與類型與 變量變量 0 0 約束約束 對偶問題對偶問題約束約束類型類型 變量變量 0 0 約束約束 的對應(yīng)關(guān)系的對應(yīng)關(guān)系 變量無限制變量無限制 約束約束 原問題原問題約束約束類型與類型與 約束約束 變量變量 0 0 對偶問題對偶問題變量變量類型類型 約束約束 變量 變量 0 0 的對應(yīng)關(guān)系的對應(yīng)關(guān)系 約束約束 變量變量無限制無限制 minW=7y1 +9y2 3y1+4y2 5 -2y1 +y2 6 y1無限制無限制 , y2 0 maxZ= 5x1 +6x2 3x1 2x2 =7 4x1 +x2 9 x1 , x2 0 原問題原問題 對偶問題對偶問題 請

11、寫出以下問題的對偶問題請寫出以下問題的對偶問題 maxZ=180y1+60y2+240y3 S.t. y1+2y2+5y3 3 2y1-3y2+3y3 9 3y1+y2=4 y1無約束無約束,y2 0,y3 0 對偶理論的基本思想對偶理論的基本思想 每一個線性規(guī)劃問題都存在一個與其對偶的每一個線性規(guī)劃問題都存在一個與其對偶的 問題，在求出一個問題的解的時候，也同時給出問題，在求出一個問題的解的時候，也同時給出 了另一個問題的解。了另一個問題的解。 對偶單純形法基本原理 決策變量的檢驗數(shù)可寫成：決策變量的檢驗數(shù)可寫成： CBB-1稱為單純形乘子稱為單純形乘子 非基變量非基變量基變量基變量 XB

12、XNXS 0 XS bB N I cjzjCB CN0 基變量基變量非基變量非基變量 XBXN XS CB XB B -1 bIB -1N B -1 Cjzj0= CN -CB B -1B CN -CB B -1N -CB B -1 C -CB B 1A0 -CB B 10 A y C y 0 若令若令 y= CBB-1 則則 顯然顯然y= CBB-1是其對偶問題的可行解是其對偶問題的可行解，即，即 原問題檢驗數(shù)的相反數(shù)恰好是其對偶問題的一個可行解！原問題檢驗數(shù)的相反數(shù)恰好是其對偶問題的一個可行解！ 代入代入 對偶問題對偶問題 min W=bT y s.t. A y C y 0 得：得： C

13、-CB B 1A0 -CB B 10 y AC y 0 也就是說也就是說：當原問題為最優(yōu)解時，這時對偶問題為可行：當原問題為最優(yōu)解時，這時對偶問題為可行 解，且兩者具有相同的目標函數(shù)值，對偶問題的解也為解，且兩者具有相同的目標函數(shù)值，對偶問題的解也為 最優(yōu)解最優(yōu)解. 將這個解代入對偶問題的目標函數(shù)值，有：將這個解代入對偶問題的目標函數(shù)值，有： 原問題的松弛變量對應(yīng)著其對偶問題的決策變量！原問題的松弛變量對應(yīng)著其對偶問題的決策變量！ 基變量基變量非基變量非基變量 XBXN XS CB XB B -1 bIB -1N B -1 cjzj0CN -CB B -1N -CB B -1 zXCbBCby

14、w BBB 1 互為對偶問題變量的對應(yīng)關(guān)系互為對偶問題變量的對應(yīng)關(guān)系 原問題變量原問題變量松弛變量松弛變量 x1 x2x3 x4 x5 x3 15/2 x1 7/2 x2 3/2 0 0 1 0 0 1 1 5/4 -15/2 0 1/4 -1/2 0 -1/4 3/2 cj-zj0 0 0 -1/4 -1/2 對偶問題變量對偶問題變量對偶問題剩余變量對偶問題剩余變量 y1 y2 y3 y4 y5 y2 1/4 y3 1/2 5/4 1 0 15/2 0 1 -1/4 1/4 1 /2 -3/2 cj-zj-15/2 0 0-7/2 -3/2 對偶問題的剩余變量對偶問題的剩余變量 y4 y5

15、對偶問題變量對偶問題變量 y1 y2 y3 原問題的松弛變量原問題的松弛變量 x3 x4 x5 原問題變量原問題變量 x1 x2 原問題最終表原問題最終表對偶問題最終表對偶問題最終表 若存在對偶問題的一個可行基若存在對偶問題的一個可行基B B，只要令，只要令X XB B B B- - 1 1b b 0 0 , ,則原問題也有可行解則原問題也有可行解, ,且且同為最優(yōu)解同為最優(yōu)解。 互為對偶問題變量的對應(yīng)關(guān)系可以看出：互為對偶問題變量的對應(yīng)關(guān)系可以看出： 只需要求出原問題（對偶問題）的只需要求出原問題（對偶問題）的 最優(yōu)解，從最優(yōu)解的單純形表中就最優(yōu)解，從最優(yōu)解的單純形表中就 可以同時得到其對偶

16、問題（原問題）可以同時得到其對偶問題（原問題） 的最優(yōu)解。的最優(yōu)解。 對偶單純形法的基本原理對偶單純形法的基本原理 若若x是原問題的可行解，是原問題的可行解，y是對偶問題的可行解，是對偶問題的可行解， 則有則有 cxyb 二二. 弱對偶性：弱對偶性： 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì) 一一 . 對稱性對稱性 ： 對偶問題的對偶是原問題對偶問題的對偶是原問題 設(shè)設(shè)x是原問題的可行解，是原問題的可行解，y是對偶問題的可行解。是對偶問題的可行解。 當當 cx= yb 時時 x, y 是最優(yōu)解。是最優(yōu)解。 三三 . 最優(yōu)性最優(yōu)性 若原問題及其對偶問題均具有可行解，則兩者若原問題及其對偶問題均具有可

17、行解，則兩者 均具有最優(yōu)解且它們最優(yōu)解的目標函數(shù)值相等。均具有最優(yōu)解且它們最優(yōu)解的目標函數(shù)值相等。 四四 . 強對偶性（對偶定理）強對偶性（對偶定理） 五五.互補松弛性（松緊定理）互補松弛性（松緊定理） 在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件 的對偶變量值為非零，則該約束條件取嚴格等式；反之如的對偶變量值為非零，則該約束條件取嚴格等式；反之如 果約束條件取嚴格不等式，則其對應(yīng)的對偶變量一定為零。果約束條件取嚴格不等式，則其對應(yīng)的對偶變量一定為零。 也即：也即： n j siijiji xbxay 1 0,0即則有若 0,0, 1 i n j

18、 siijij yxbxa則有即若 0 isi yx因此，一定有 五五.互補松弛性（松緊定理）互補松弛性（松緊定理） 在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件 的對偶變量值為非零，則該約束條件取嚴格等式；反之如的對偶變量值為非零，則該約束條件取嚴格等式；反之如 果約束條件取嚴格不等式，則其對應(yīng)的對偶變量一定為零。果約束條件取嚴格不等式，則其對應(yīng)的對偶變量一定為零。 也即：也即： m i jiijj cyax 1 ,0則有如果有 0, 1 n j jjjij xcya則有如果有 28)4 , 4 , 0 , 0( 0 20232 20322 4

19、32max 3 * 4321 4321 4321 zx x xxxx xxxx xxxxz LP i 最優(yōu)解為 問題：已知例 用互補松弛定理計算對偶問題的最優(yōu)解用互補松弛定理計算對偶問題的最優(yōu)解 互補松弛定理互補松弛定理: 在線性規(guī)劃問題在線性規(guī)劃問題 的最優(yōu)解中，的最優(yōu)解中， m i jiijj cyax 1 ,0則有如果有 0, 1 n j jjjij xcya則有如果有 0, 423 332 22 12 2020min 21 21 21 21 21 21 yy yy yy yy yy yy 解：對偶問題為： 42304 214 yyx有 根據(jù)互補松弛定理， 5/1,5/6 21 yy解得

20、 33204 213 yyx有由 )4 , 4 , 0 , 0( * x最優(yōu)解為 已知原問題 最優(yōu)值。為對偶問題的最優(yōu)解和 ； 28 5/1, 5/6 21 yy * 21 28 5/1,5/6 z yy 對應(yīng)目標函數(shù)值 為對偶問題的可行解，經(jīng)檢驗 0, 423 332 22 12 2020min 21 21 21 21 21 21 yy yy yy yy yy yy 5/1, 5/6 21 yy 影子價格影子價格 式中式中b bi i是線性規(guī)劃原問題約束條件的右端項，它代是線性規(guī)劃原問題約束條件的右端項，它代 表第表第i i種資源的擁有量；對偶變量種資源的擁有量；對偶變量y yi i* *的

21、意義代表在資源的意義代表在資源 最優(yōu)利用條件下對單位第最優(yōu)利用條件下對單位第i i種種資源的估價。這種估價不資源的估價。這種估價不 是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻 而作的估價，為區(qū)別起見，稱為影子價格而作的估價，為區(qū)別起見，稱為影子價格(shadow (shadow price)price)。 幾點說明：幾點說明： 1資源的影子價格是未知數(shù)，有賴于企業(yè)資源狀況。資源的影子價格是未知數(shù)，有賴于企業(yè)資源狀況。 2影子價格是一種邊際價格影子價格是一種邊際價格, 相當于在資源得到最優(yōu)利用的生產(chǎn)相當于在資源得到最優(yōu)利用的生產(chǎn) 條件下，每增

22、加一個單位時目標函數(shù)條件下，每增加一個單位時目標函數(shù)z的增量。的增量。 3資源的影子價格實際上又是一種機會成本。資源的影子價格實際上又是一種機會成本。 4生產(chǎn)過程中如果某種資源未得到充分利用時，該種資源的影子價生產(chǎn)過程中如果某種資源未得到充分利用時，該種資源的影子價 格為零；又當資源的影子價格不為零時，表明該種資源在生產(chǎn)中已格為零；又當資源的影子價格不為零時，表明該種資源在生產(chǎn)中已 耗費完畢。耗費完畢。 5對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對 偶問題的求解則是確定資源的恰當估價。偶問題的求解則是確定資源的恰當估價。 對偶單

23、純形法 v 基本思路：在迭代過程中保持原問題的檢驗 數(shù)為非正，逐步替換負基變量，從而得到最優(yōu) 解。 即保持對偶問題有可行解即保持對偶問題有可行解 使原問題具有可行解使原問題具有可行解 檢驗數(shù)為非正替換負基變量 對偶單純形法計算步驟對偶單純形法計算步驟 1. 1. 列出初始單純形表，且列出初始單純形表，且檢驗數(shù)非正檢驗數(shù)非正。 為換出變量。對應(yīng)的基變量 按 r rii i x bBbBbB 111 0min.3 為換入變量確定 按 s rs ss rj rj jj x a zc a a zc 0min.4 2. b 2. b值有否為負，無，計算結(jié)束。有，轉(zhuǎn)值有否為負，無，計算結(jié)束。有，轉(zhuǎn)3 3

24、5.以以ars為主元素，進行迭代變換。為主元素，進行迭代變換。 6 . 返返 3，直到，直到b 0為止。為止。 用對偶單純形法求解下述線性規(guī)劃問題用對偶單純形法求解下述線性規(guī)劃問題 例例 化標準型：化標準型： 整理得：整理得： 解：解： Cj1524500 CByBby1y2y3y4y5 0y420-6-110 0y51-5-2-101 j=cj-zj 24y21/3011/6-1/60 0y5-1/3-50-2/3-1/31 j=cj-zj -15-24-500 -150-1-40 24y21/4-5/410-1/41/4 -5y31/215/2011/2-3/2 j=cj-zj -15/2

25、00-7/2-3/2 在得到原始可行解時同時得到對偶可行解，已獲得最優(yōu)在得到原始可行解時同時得到對偶可行解，已獲得最優(yōu) 解：解： （y1, y2, y3, y4, y5）= =（0,1/4, 1/2,0,00,1/4, 1/2,0,0） max w=17/2max w=17/2 對偶問題的最優(yōu)解為：對偶問題的最優(yōu)解為： （x1, x2, x3 ）= =（ 7/2, 3/2, 15/27/2, 3/2, 15/2） min z=17/2min z=17/2 對偶單純形法的優(yōu)點：對偶單純形法的優(yōu)點： 用對偶單純形法求解線性規(guī)劃問題時，當約束條用對偶單純形法求解線性規(guī)劃問題時，當約束條 件為件為“”

26、時，不必引進人工變量，使計算簡化。時，不必引進人工變量，使計算簡化。 對偶單純形法的應(yīng)用范圍：對偶單純形法的應(yīng)用范圍： 在初始單純形表中其對偶問題應(yīng)是基可行解這點，對在初始單純形表中其對偶問題應(yīng)是基可行解這點，對 多數(shù)線性規(guī)劃問題很難實現(xiàn)。因此對偶單純形法一般不單多數(shù)線性規(guī)劃問題很難實現(xiàn)。因此對偶單純形法一般不單 獨使用，多用于靈敏度分析等用途。獨使用，多用于靈敏度分析等用途。 靈敏度靈敏度分析 當這些參數(shù)中的一個或幾個發(fā)生變化時，問題當這些參數(shù)中的一個或幾個發(fā)生變化時，問題 的最優(yōu)解會有什么變化，或者這些參數(shù)在一個多大的最優(yōu)解會有什么變化，或者這些參數(shù)在一個多大 范圍內(nèi)變化時，問題的最優(yōu)解不

27、變。范圍內(nèi)變化時，問題的最優(yōu)解不變。 靈敏度分析的定義靈敏度分析的定義 靈敏度分析所要研究解決的問題靈敏度分析所要研究解決的問題 是指對系統(tǒng)或事物因周圍條件變化顯是指對系統(tǒng)或事物因周圍條件變化顯 示出來的敏感程度的分析。示出來的敏感程度的分析。 條件變化條件變化 aij，bi，cj 最優(yōu)解最優(yōu)解 多大范圍內(nèi)變化多大范圍內(nèi)變化 1將參數(shù)的改變計算反映到最終單純形表上來：將參數(shù)的改變計算反映到最終單純形表上來： 靈敏度分析的步驟靈敏度分析的步驟 最終單純形表最終單純形表 B-1B 3檢查對偶問題是否仍為可行解；檢查對偶問題是否仍為可行解； 4按下表所列情況得以結(jié)論和決定繼續(xù)計算的步驟。按下表所列情

28、況得以結(jié)論和決定繼續(xù)計算的步驟。 2檢查原問題是否仍為可行解；檢查原問題是否仍為可行解； 靈敏度分析的任務(wù)靈敏度分析的任務(wù) (1)、參數(shù)、參數(shù)A，b，C在什么范圍內(nèi)變動，對當前方在什么范圍內(nèi)變動，對當前方 案無影響？案無影響？ (2)、參數(shù)、參數(shù)A，b，C中的一個中的一個(幾個幾個)變動，對當前方變動，對當前方 案的影響？案的影響？ (3)、如果最優(yōu)方案改變，如何用簡便方法求新方、如果最優(yōu)方案改變，如何用簡便方法求新方 案？案？ 一、分析一、分析Cj的變化的變化 Cj的變化僅僅影響到檢驗數(shù)的變化僅僅影響到檢驗數(shù)(Cj-Zj)的變化。所以將的變化。所以將Cj 的變化直接反映到最終單純形表中，只可

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

30、中: (1) 若家電若家電I的利潤降至的利潤降至1. 5元件，而家電的利潤增至元件，而家電的利潤增至2元件時，美佳公司最優(yōu)元件時，美佳公司最優(yōu) 生產(chǎn)計劃有何變化；生產(chǎn)計劃有何變化； 最終單純形表如下：最終單純形表如下： 原問題可行，對偶問題不可行原問題可行，對偶問題不可行,用單純形法繼續(xù)迭代求解。用單純形法繼續(xù)迭代求解。 將家電將家電I，II的利潤變化的利潤變化cj直接反映到最終單純形表中。直接反映到最終單純形表中。 -2 0 -1 1/8 -9/4 為使表中的解仍為最優(yōu)解，應(yīng)有為使表中的解仍為最優(yōu)解，應(yīng)有 即家電即家電II的利潤的利潤C2的變化范圍應(yīng)滿足：的變化范圍應(yīng)滿足： 2) 若家電若家

31、電I的利潤不變，則家電的利潤不變，則家電II的利潤在什么范圍內(nèi)變化時，則該公司的最優(yōu)的利潤在什么范圍內(nèi)變化時，則該公司的最優(yōu) 生產(chǎn)計劃將不發(fā)生變化？生產(chǎn)計劃將不發(fā)生變化？ 0 0 0 -1/4+1/4 -1/2-3/2 設(shè)家電設(shè)家電II的利潤為的利潤為(1+)元，反映到最終單純形表中為：元，反映到最終單純形表中為： 二、分析二、分析b bi i的變化的變化 bj的變化在實際問題中反映為可用資源數(shù)量的變化。的變化在實際問題中反映為可用資源數(shù)量的變化。 可能出現(xiàn)的解的情況：可能出現(xiàn)的解的情況： 例：例： 若：若：(1)若設(shè)備若設(shè)備A和調(diào)試工序的每天能力不變，而設(shè)備和調(diào)試工序的每天能力不變，而設(shè)備B

32、每天的能力增每天的能力增 加到加到32小時，分析公司最優(yōu)計劃的變化；小時，分析公司最優(yōu)計劃的變化； (2)若設(shè)備若設(shè)備A和和B每天可用能力不變，則調(diào)試工序能力在什么范圍每天可用能力不變，則調(diào)試工序能力在什么范圍 內(nèi)變化時，問題的最優(yōu)基不變。內(nèi)變化時，問題的最優(yōu)基不變。 在上述美佳公司的例子中，在上述美佳公司的例子中， 解：解： 1.求求bj的變化量。的變化量。 2.列出最終單純表。列出最終單純表。 1/2 原問題不可行，對偶問題可行，用對偶單純形法繼續(xù)迭代求原問題不可行，對偶問題可行，用對偶單純形法繼續(xù)迭代求： 3.在最終單純表中直接表現(xiàn)在最終單純表中直接表現(xiàn)bj的變化量：的變化量：bbb 3

33、5/2 11/2 -1/2 單純形表中單純形表中b列數(shù)字為：列數(shù)字為： （2）調(diào)試工序能力在什么范圍內(nèi)變化時，問題的最優(yōu)基不變）調(diào)試工序能力在什么范圍內(nèi)變化時，問題的最優(yōu)基不變 解：解： 6. 對偶的經(jīng)濟解釋對偶的經(jīng)濟解釋 (1)原始問題是利潤最大化的生產(chǎn)計劃問題原始問題是利潤最大化的生產(chǎn)計劃問題 0 . . max 2121 2211 222222121 111212111 2211 mnnnn mmnnmnmm nnn nnn nn xxxxxx bxxaxaxa bxxaxaxa bxxaxaxat s xcxcxcz 單位產(chǎn)品的利潤（單位產(chǎn)品的利潤（元元/件）件） 產(chǎn)品產(chǎn)量（件）產(chǎn)品產(chǎn)量（件） 總利潤（元）總利潤（元） 資源限量（噸）資源限量（噸） 單位產(chǎn)品消耗的資源（噸單位產(chǎn)品消耗的資源（噸/件）件）剩余的資源（剩余的資源（噸）噸） 消耗的資源（噸）消耗的資源（噸） (2)對偶問題對偶問題 0wwwwww cwwawawa cwwawawa cwwawawa. t . s wbwbwbymin nm2m1mm21 nnmmmn2n21n1 22mm2m222112 11mm1m221111 mm2211 資源限量（噸）資源限量（噸） 資源價格（元資源價格（元/噸）噸） 總利潤（元