中國礦業(yè)大學(xué)管理運(yùn)籌學(xué)課件第二章對(duì)偶問題與靈敏度分析

1、第二章線性規(guī)劃的對(duì)偶問題與靈敏度分析2.1 線性規(guī)劃的對(duì)偶問題2.2 對(duì)偶單純形法2.3 靈敏度分析1.6 運(yùn)輸問題第二章線性規(guī)劃的對(duì)偶問題與靈敏度分析LP一個(gè)線性規(guī)劃另一個(gè)線性規(guī)劃極值問題存在同一個(gè)研究對(duì)象極值問題ABC458090121113 4 5 甲 乙 資源量 利 潤 y1y2y3 Max ZX=4x1+5x2 x1 + x2 45 2x1 + x2 80 x1 + 3x2 90 x1，x2 0 LP2.1.1問題的引入：資源價(jià)格問題生產(chǎn)計(jì)劃問題 資源價(jià)格問題W(y= 45y1+80y2+90y3 y1 +2y2+ y3ABC458090121113 4 5 甲 乙 資源量 利 潤

2、y1y2y3 賣方： 買方：Miny1 + y2+3y3y1，y2，y3 045LP 資源價(jià)格問題2112兩問題數(shù)學(xué)模型的對(duì)應(yīng)關(guān)系 (1)兩個(gè)問題的系數(shù)矩陣互為轉(zhuǎn)置。 (2)一個(gè)問題變量的個(gè)數(shù)，等于另一個(gè)問題的約束條件的個(gè)數(shù)。 Max ZX=4x1+5x2 x1 + x2 45 2x1 + x2 80 x1 +3x2 90 x1，x2 0 Min W(y= 45y1+80y2+90y3 y1 +2y2+ y34 y1 + y2+3y35 y1，y2，y3 0y1x1 x2y2 y3 (3)一個(gè)問題的右端常數(shù)，是另一個(gè)問題的目標(biāo)函數(shù)的系數(shù)。 (4)假設(shè)一個(gè)問題的目標(biāo)為“max，約束為“類型；那么

3、另一個(gè)問題的目標(biāo)為“min，約束為“類型。 這種關(guān)系稱為對(duì)稱型對(duì)偶關(guān)系。212對(duì)稱型對(duì)偶問題的一般形式生產(chǎn)計(jì)劃問題 原問題 Max ZX= c1x1+c2x2+cnxn a11x1 + a12x2+a1n xn b1 a21x1 + a22x2+a2n xn b2 . am1x1 + am2x2+amn xn bm x1，x2，xn 0 其對(duì)偶問題為： Min W(y= b1y1+b2y2+bmym a11y1 + a21y2+am1ymc1 a12y1 + a22y2+am2ymc2 a1ny1 + a2ny2+amnymcn y1，y2， ，ym 0這種模型的特點(diǎn)：所有決策變量均為非負(fù)變量

4、，所有約束條件均為“型，目標(biāo)函數(shù)為“Max。y1y2.ymx1x2xnLP213非對(duì)稱型對(duì)偶問題例：求以下線性規(guī)劃的對(duì)偶問題 MaxZX= 2x2-5x3 x1 + x3 2 2x1 + x2 +6x3 6 x1 - x2 +3x3 =0 x1，x2，x30 x1 - x2 +3x3 0 x1 - x2 +3x3 0 MaxZX= 2x2-5x3 -x1 -x3 - 2 2x1 + x2+6x3 6 x1 - x2+3x3 0 -x1 + x2-3x3 0 x1，x2，x30 其對(duì)偶問題為： Min W(y= -2y1+6y2 -y1 +2y2 +y3/ -y3/ 0y1y2y3/y3/ y2

5、 -y3/ +y3/ 2-y1 +6y2+3y3/-3y3/-5y1，y2，y3/，y3/ 0 x1x2x3LP MaxZX= 2x2-5x3 x1 + x3 2 2x1 + x2 +6x3 6 x1 - x2 +3x3 =0 x1，x2，x30 MaxZX= 2x2-5x3 -x1 -x3 - 2 2x1 + x2+6x3 6 x1 - x2+3x3 = 0 x1，x2，x30 其對(duì)偶問題為： Min W(y= -2y1+6y2 x1 -y1 +2y2 +y3/ -y3/ 0 x2 y2 -y3/ +y3/ 2 x3 -y1 +6y2+3y3/-3y3/-5 y1，y2，y3/，y3/ 0M

6、in W(y= -2y1+6y2 x1 -y1 +2y2 +y3 0 x2 y2 -y3 2 x3 -y1 +6y2+3y3 -5 y1，y2 0 以： y3 =y3 /-y3 /代入上對(duì)偶問題，觀察原問題與 對(duì)偶問題的關(guān)系LP Min W(y= -2y1+6y2 -y1 +2y2 +y3 0 y2 -y3 2 -y1 +6y2+3y3 -5 y1，y2 0 原問題： MaxZX= 2x2-5x3 x1 + x3 2 2x1 + x2 +6x3 6 x1 - x2 +3x3 =0 x1，x2，x30 其對(duì)偶問題為： Min W(y= 2y1+6y2 y1 +2y2 +y3 0 y2 -y3 2

7、 y1 +6y2+3y3 -5 y1 0，y2 0練習(xí)： MinZX= x1+2x2+x3 x1 +x2 + x3 2 x1 -x2 + x3 =12x1 +x2 + x3 1x10 MinZX= x1+2x2+x3 -x1 -x2 - x3 -2 x1 -x2 + x3 = 1 2x1 +x2 + x3 1 x10y1y2y3 其對(duì)偶問題為： Max W(y= -2y1+y2 +y3-y1 + y2 +2y3x2x1x3-y1 - y2 + y3=2 y1，y3 0-y1 + y2 + y3 1=1LP練習(xí)： MinZX= x1+2x2+x3 x1 +x2 + x3 2 x1 -x2 + x

8、3 =12x1 +x2 + x3 1x10 其對(duì)偶問題為： Max W(y= -2y1+y2 +y3-y1 + y2 +2y3x2x1x3-y1 - y2 + y3=2 y1，y3 0-y1 + y2 + y3 1=1LP 其對(duì)偶問題為： Max W(y= 2y1+y2 +y3y1 + y2 +2y3x2x1x3y1 - y2 + y3=2 y1 0，y3 0y1 + y2 + y3 1=1等價(jià)變換3個(gè)約束2個(gè)變量2個(gè)約束 3個(gè)變量原問題對(duì)偶問題一般規(guī)律對(duì)稱型：原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系對(duì)偶問題：原問題：3個(gè)約束4個(gè)變量4個(gè)約束3個(gè)變量對(duì)應(yīng)關(guān)系可歸納成下表：原對(duì)偶問題對(duì)偶原問題目標(biāo)函數(shù)目標(biāo)函數(shù)

9、第 i 個(gè)約束左端第 i 個(gè)約束左端第 i 個(gè)變 量第 i 個(gè)變 量自由變量自由變量= 右端= 右端右端MaxMin右端 0 0LP一般情形：混合型對(duì)偶問題的對(duì)應(yīng)關(guān)系P與(D)的關(guān)系對(duì)應(yīng)表： 原問題 對(duì)偶問題目標(biāo)函數(shù)max目標(biāo)函數(shù)min目標(biāo)函數(shù)系數(shù)約束方程常數(shù)列約束方程常數(shù)列目標(biāo)函數(shù)系數(shù)變量個(gè)數(shù)n約束方程個(gè)數(shù)n約束方程個(gè)數(shù)m變量個(gè)數(shù)m約束方程變量00=無符號(hào)約束變量0約束方程0無符號(hào)約束=系數(shù)矩陣A=-3對(duì)偶規(guī)劃問題D為：原問題P對(duì)偶問題D變量約束：方程約束：變量方程變量無限制方程=變量方程方程約束：變量約束：方程=變量無限制方程變量方程變量結(jié)構(gòu)與對(duì)稱型相似練習(xí)：P與(D)的關(guān)系對(duì)應(yīng)表： 原問

10、題 對(duì)偶問題目標(biāo)函數(shù)max目標(biāo)函數(shù)min目標(biāo)函數(shù)系數(shù)約束方程常數(shù)列約束方程常數(shù)列目標(biāo)函數(shù)系數(shù)變量個(gè)數(shù)n約束方程個(gè)數(shù)n約束方程個(gè)數(shù)m變量個(gè)數(shù)m約束方程變量00=無符號(hào)約束變量0約束方程0無符號(hào)約束=系數(shù)矩陣A214對(duì)偶問題的基本性質(zhì)以對(duì)稱型為例 設(shè)原問題P為 其對(duì)偶問題D為 max ZX=CX min W(Y)=Yb AX b YAC X 0 Y01對(duì)偶問題(D)的對(duì)偶問題，是原問題(P)。LP2假設(shè)X/是問題(P)的一可行解， Y/是問題(D)的一個(gè)可行解， 那么有:CX/Y/b。3假設(shè)X*,Y*分別為問題(P)和問題(D)的可行解，且CX*=Y*b ；那么，X*和Y*分別為問題(P)和問題(

11、D)的最優(yōu)解。 4假設(shè)問題(P)的目標(biāo)函數(shù)值Z無上界，那么問題(D)無可行解； 假設(shè)問題(D)的目標(biāo)函數(shù)值W無下界，那么問題(P) 無可行解。 5對(duì)偶定理：假設(shè)問題(P)和問題D之一有最優(yōu)解，那么 另一個(gè)問題也一定有最優(yōu)解，且目標(biāo)函數(shù)值相等。對(duì)偶問題為： Min W(y= b1y1+b2y2+bmym a11y1 + a21y2+am1ymc1 a12y1 + a22y2+am2ymc2 . a1ny1 + a2ny2+amnymcn y1，y2， ，ym 0 Max (-W= -b1y1-b2y2-bmym -a11y1 - a21y2-am1ym -c1 -a12y1 - a22y2-am

12、2ym -c2 . -a1ny1 - a2ny2-amnym -cn y1，y2， ，ym 0 -a11x1 - a12x2-a1n xn -b1 -a21x1 - a22x2-a2n xn -b2 . -am1x1 - am2x2-amn xn -bm x1，x2，xn 0 a11x1 + a12x2+a1n xn b1 a21x1 + a22x2+a2n xn b2 . am1x1 + am2x2+amn xn bm x1，x2，xn 0 原問題為：Min (-Z= -c1x1-c2x2-cnxn Max Z= c1x1+c2x2+cnxnx1x2xn根據(jù)條件有： 2假設(shè)X/是問題(P)的

13、一可行解， Y/是問題(D)的一個(gè)可行解，那么有:CX/Y/b Y/AX/ Y/bCX/ Y/bCX/ Y/AX/ Y/bY/AX/CX/Y/A CY/0AX/ b X/ 0原問題P為 其對(duì)偶問題D為 max ZX=CX min W(Y)=Yb AX b YAC X 0 Y0LP3假設(shè)X*,Y*分別為問題(P)和問題(D)的可行解，且CX*=Y*b；那么，X*和Y*分別為問題(P)和問題(D)的最優(yōu)解。 原問題P為 其對(duì)偶問題D為 max ZX=CX min W(Y)=Yb AX b YAC X 0 Y0CX/ Y/b根據(jù)2有：CX* Y/bCX/ CX*Y*b =Y*b Y/bCX/ Y/b

14、CX/ Y*b= CX*4假設(shè)問題(P)的目標(biāo)函數(shù)值Z無上界，那么問題(D)無可行解；假設(shè)問題(D)的目標(biāo)函數(shù)值W無下界，那么問題(P) 無可行解。CX* Y/bCX/ Y*b-+LP215對(duì)偶問題的解 由對(duì)偶定理可知，從原問題的最終單純表中可直接得到其對(duì)偶問題的最優(yōu)解。 X(0) =(0,0,45,80,90) Y(0) =(0,0,0,-4,-5)LP X* =(45/2，45/2，0，25/2，0) Y* =7/2，0，1/2，0，0 X(1) =(0,30,15,50,0) Y(1) = (0,0,5/3,-7/3,0)LP假設(shè)將資源價(jià)格問題作為原問題求解兩階段法， Min W(y=

15、45y1+80y2+90y3 y1 +2y2+ y34 y1 + y2+3y35 y1，y2，y3 0輔助問題：LPMin W = y6+y7 y1 +2y2+ y3- y4 + y6 =4 y1 + y2+3y3 - y5 +y7 =5 y1，,y7 0假設(shè)將資源價(jià)格問題作為原問題求解兩階段法， Y*=7/2，0，1/2，0，0 X*=45/2，45/2，0，25/2，0*在兩個(gè)互為對(duì)偶的線性規(guī)劃中，可任選一個(gè)進(jìn)行求解Min W(y= 45y1+80y2+90y3 y1 +2y2+ y34 y1 + y2+3y35 y1，y2，y3 0其最終單純形表如下：x1x2LP 例：求以下線性規(guī)劃的解

16、 Max ZX=4x1+3x2 x1 6 x2 8 x1 + x2 7 3x1 + x2 15 -x2 1 x1，x20 解：該問題的對(duì)偶問題僅有兩個(gè)變量:單純形表如下： MinWY= 6y1+8y2+7y3 +15y4 +y5 St y1 +y3 +3y4 4 y2 +y3 + y4 -y5 3 y1，y2，y3，y4，y5 0LP0X*=4，3；ZX*=25LP3假設(shè)X*,Y*分別為問題(P)和問題(D)的可行解，且CX*=Y*b ；那么，X*和Y*分別為問題(P)和問題(D)的最優(yōu)解。 用對(duì)偶性質(zhì)重新解釋單純形法。 單純形法：在整個(gè)迭代過程中，始終保持該問題解的可行性即滿足 ，而其對(duì)偶問

17、題的互補(bǔ)解初始時(shí)并不滿足可行性條件即檢驗(yàn)數(shù)不完全部小于等于0；當(dāng)不可行性完全消失即滿足 時(shí)，原問題和對(duì)偶問題同時(shí)達(dá)到最優(yōu)。0 對(duì)偶純形法：在整個(gè)迭代過程中，始終保持其對(duì)偶問題解的可行性即 ，而該問題的初始解并不滿足可行性條件即不完全部大于等于0；當(dāng)不可行性完全消失即滿足 時(shí)，原問題和對(duì)偶問題同時(shí)達(dá)到最優(yōu)。 022對(duì)偶單純形法221對(duì)偶單純形基本步驟原問題對(duì)偶問題原問題對(duì)偶問題單純形法對(duì)偶純形法可行可行可行可行非可行非可行最優(yōu)可行可行圖示LP221對(duì)偶單純形基本步驟 (1)列出初始單純形表，保證所有的 (3)基變換首先確定退出基變量，其次決定進(jìn)入基變量， 然后求新的基本可行解。返回到2。 (2)

18、檢驗(yàn)：假設(shè)滿足 ，那么獲得最優(yōu)解，否那么下一步LP例：用對(duì)偶單純形求解 Max ZX= -x2-2x3x1 + x2 + x3 =5 2x2 + x3 +x4 = 5 -4x2 - 6x3 +x5 =-9x1，x2，x3，x4，x50初始單純形表：LP X*=(11/4, 9/4,0,1/2,0) ZX*=-9/40 Max ZX= -x2-2x3 x1 + x2 + x3 =5 2x2 + x3 +x4 = 5 -4x2 - 6x3 +x5 =-9 x1，x2，x3，x4，x50 Max ZX= -x2-2x3 x2 + x3 5 2x2 + x3 5 -4x2 - 6x3 -9 x2，x3

19、，0LP思考：如何直接寫出對(duì)偶問題的解？ MinWY= 45y1+80y2+90y3 St y1+2y2 + y3 4 y1 +y2 +3y3 5 y1，y2，y3 0Max-WY= -45y1-80y2-90y3 y1+2y2 + y3 -y4 =4 y1 +y2 +3y3 -y5 =5 y1，y2，y3 , y4, y50標(biāo)準(zhǔn)形求解資源價(jià)格問題初始單純形表：Y(0) =(0,0,0,-4,-5)LP可用對(duì)偶單純形法求解資源價(jià)格問題 0 y5 -5 -1 -1 -3 0 1 0 y4 -4 -1 -2 -1 1 0 -45 -80 -90 0 0-90 y3 5/3 1/3 1/3 1 0

20、-1/3 0 y4 -7/3 -2/3 -5/3 0 1 -1/3 -15 -50 0 0 -30LP Y*=(7/2,0,1/2,0，0) X*=(45/2,45/2,0,25/2,0)T最終單純形表0-90 y5 5/3 1/3 1/3 1 0 -1/3 0 y4 -7/3 -2/3 -5/3 0 1 -1/3 -15 -50 0 0 -30LP222 影子價(jià)格對(duì)偶問題的經(jīng)濟(jì)解釋 資源價(jià)格問題 三種資源： A、 B、 C Y*=(7/2, 0, 1/2) 三種資源剩余量分別為0， 25/2， 0 目標(biāo)函數(shù)： W =7/245 +080 +1/290 = 405/2 經(jīng)濟(jì)意義：反映了資源與總

21、收益之間的關(guān)系，即當(dāng)?shù)趇種資源每增加一個(gè)單位時(shí)，在其他條件不變的情況下，該資源對(duì)目標(biāo)值的貢獻(xiàn)就是yi 圖示：LPADOCBX2X1例 1:Max ZX= 4x1+5x2 x1 + x2 451 2x1 + x2 802 x1 +3x2 903 x1，x2 0 C/x1 + x2 = 461/24，22 Z=206x1 +3x2 =903LPADOCBX2X1例 1:Max ZX= 4x1+5x2 x1 + x2 451 2x1 + x2 802 x1 +3x2 903 x1，x2 0 C/x1 +3x2 = 913/22，23Z=203x1 + x2 = 451LP2.3 靈敏度分析資源的合理

22、利用問題：資源單位消費(fèi)產(chǎn)品資源限制單位利潤 線性規(guī)劃問題中， 都是常數(shù)，但在建模時(shí)這些系數(shù)有可能采用的是估計(jì)值或預(yù)測(cè)值。 存在的問題：市場(chǎng)的變化工藝的變化資源的變化研究內(nèi)容：線性規(guī)劃中， 的變化對(duì)最優(yōu)解的影響。一、目標(biāo)函數(shù)系數(shù)C價(jià)格變化的靈敏度分析 XB XN常數(shù)項(xiàng)檢驗(yàn)行0 CN- CBB-1NZ- CBB-1bXBE B-1NB-1b：新問題還沒取到最優(yōu)在原最優(yōu)單純形表上用單純形法繼續(xù)迭代最優(yōu)單純形表：任務(wù)：找出C的變化范圍，原問題的最優(yōu)解還是新問題的最優(yōu)解使在該范圍內(nèi)，經(jīng)濟(jì)意義：即最優(yōu)生產(chǎn)方案是不生產(chǎn)第i種產(chǎn)品最優(yōu)生產(chǎn)方案不變，最優(yōu)解不變，第i種產(chǎn)品的價(jià)格上漲，仍然不生產(chǎn)該產(chǎn)品第i種產(chǎn)品的

23、價(jià)格下降但上漲金額不超過最優(yōu)生產(chǎn)方案不變，仍然不生產(chǎn)該產(chǎn)品例：某工廠準(zhǔn)備生產(chǎn) A、B、C三種產(chǎn)品， 他們都消耗勞動(dòng)力 和材料，有關(guān)數(shù)據(jù)如 右表： 原料 產(chǎn)品ABC擁有量勞動(dòng)力63545材料34530售價(jià)（元）314最優(yōu)單純形表：X1X2X3X4X50-20-1/5-3/5Z-27X11-1/301/3-1/35X3011-1/52/53最優(yōu)生產(chǎn)方案：5個(gè)A，0個(gè)B，3個(gè)C問題：假設(shè)市場(chǎng)對(duì)B產(chǎn)品有需求，問B的售價(jià)至少需 漲至多少才可考慮生產(chǎn)非基變量C22最優(yōu)解不變當(dāng)B產(chǎn)品的價(jià)格3元時(shí)，最優(yōu)生產(chǎn)方案不變即仍然不生產(chǎn)B產(chǎn)品因此，只有當(dāng)B產(chǎn)品的價(jià)格3元時(shí)，才可考慮生產(chǎn)B產(chǎn)品 原料 產(chǎn)品ABC擁有量勞動(dòng)

24、力63545材料34530售價(jià)（元）314X1X2X3X4X50-20-1/5-3/5Z-27X11-1/301/3-1/35X3011-1/52/53問題：假設(shè)市場(chǎng)對(duì)B產(chǎn)品有需求，問B的售價(jià)至少需 漲至多少才可考慮生產(chǎn)231 目標(biāo)系數(shù)的靈敏度分析(1)非基變量系數(shù)的靈敏度分析 Max ZX=8x1+20 x2+10 x3+20 x4+21x5 x1 +2x2+ x3 +x5 + x6 =10 x1 + x3+3x4 +2x5 + x7 =24 x1 +2x2+2x3+2x4+ 2x5 + x8 =21 x1，x2，x3，x4，x5，x6，x7，x80最終單純形表例：LP最終單純形表+ 檢驗(yàn)數(shù)

25、= 8 -CBP1/+如果：新檢驗(yàn)數(shù)=0那么原最優(yōu)解不變即：33如果：繼續(xù)迭代求新的最優(yōu)解。新+-3= -3=8 -CBP1/時(shí)LP+-一般當(dāng)那么原最優(yōu)解不變最終單純形表221LP(2)基變量系數(shù)的靈敏度分析最終單純形表+8 -CBP1/-020 -CBP2/-2 0-2 10 -CBP3/- 00 -CBP6/-0 -1= -3= -2= -11= -1LP欲最優(yōu)解不變 需滿足：將改變所有非基變量檢驗(yàn)數(shù)二、 增加一個(gè)新變量 的靈敏度分析資源的合理利用問題：資源單位消費(fèi)產(chǎn)品資源限制單位利潤新問題：工廠研制了一種新產(chǎn)品，估計(jì)單位利 潤為cn+1，問是否投入生產(chǎn)，假設(shè)投入生產(chǎn)，求最優(yōu)生產(chǎn)方案對(duì)問題

26、： XB XN常數(shù)項(xiàng)檢驗(yàn)行0 CN- CBB-1NZ- CBB-1bXBE B-1NB-1b最優(yōu)單純形表增加一個(gè)新變量xn+1對(duì)問題： XB XN常數(shù)項(xiàng)檢驗(yàn)行0 CN- CBB-1NZ- CBB-1bXBE B-1NB-1b最優(yōu)單純形表增加一個(gè)新變量xn+1對(duì)新問題： XB XN常數(shù)項(xiàng)檢驗(yàn)行0 CN- CBB-1NZ- CBB-1bXBE B-1NB-1b單純形表此表達(dá)到最優(yōu)此表未達(dá)到最優(yōu)用單純形法迭代至找到最優(yōu)解例：某工廠準(zhǔn)備生產(chǎn)A、B、C三種產(chǎn)品，他們都消耗勞動(dòng)力和材料，有關(guān)數(shù)據(jù)如下： 原料 產(chǎn)品ABC擁有量勞動(dòng)力63545材料34530售價(jià)（元）314最優(yōu)單純形表:X1X2X3X4X50

27、-20-1/5-3/5Z-27X11-1/301/3-1/35X3011-1/52/53最優(yōu)生產(chǎn)方案：5個(gè)A，0個(gè)B，3個(gè)C問題1、假設(shè)工廠開發(fā)出第四種產(chǎn)品D，預(yù)計(jì)售價(jià)2元， 生產(chǎn)每個(gè)D產(chǎn)品需要3個(gè)勞動(dòng)力和3個(gè)單位材 料，問是否生產(chǎn)該產(chǎn)品？2、假設(shè)產(chǎn)品D的售價(jià)為3元，問如何調(diào)整生產(chǎn)方案？問題1、假設(shè)工廠開發(fā)出第四種產(chǎn)品D，預(yù)計(jì)售價(jià)2元， 生產(chǎn)每個(gè)D產(chǎn)品需要3個(gè)勞動(dòng)力和3個(gè)單位材 料，問是否生產(chǎn)該產(chǎn)品？最優(yōu)基不變，X6是非基變量，在最優(yōu)解中取0即當(dāng)新產(chǎn)品D的售價(jià)為2元時(shí)，不生產(chǎn)該產(chǎn)品。X1X2X3X4X50-20-1/5-3/5Z-27X11-1/301/3-1/35X3011-1/52/53X

28、603/53/5最優(yōu)單純形表:X1X2X3X4X50-20-1/5-3/5Z-27X11-1/301/3-1/35X3011-1/52/532、假設(shè)產(chǎn)品D的售價(jià)為3元，問如何調(diào)整生產(chǎn)方案？X1X2X3X4X5X60-3-10-10Z-30X11-1/301/3-1/305X605/35/3-1/32/315最優(yōu)生產(chǎn)方案：5個(gè)A產(chǎn)品， 0個(gè)B產(chǎn)品， 0個(gè)C產(chǎn)品， 5個(gè)D產(chǎn)品Max ZX= 8x1+20 x2 +10 x3 +20 x4 +21 x5 x1 +2x2+ x3 + x5 + x6 = 10 x1 +x3 + 3x4 +2x5 + x7 = 24 x1 +2x2+2x3+ 2x4 +2

29、x5 + x8 = 21 x1，x2，x3，x4，x5，x6，x7，x8， 0233 增加新變量的靈敏度分析+ x9+ 2x9+ x9+12x9 x93/2-1/2 11LPP9/=11-10100-3/21/2121=13/2-1/2x912(a, b, 1)=(an , bn , 100)A ZX*=2212/3最終單純形表LP三、增加一個(gè)新約束 的靈敏度分析將最優(yōu)解代入新的約束中：1假設(shè)滿足新約束，那么原最優(yōu)解不變；2假設(shè)不滿足新約束，那么原最優(yōu)解改變， 將新增的約束條件添入最終的單純形 表中，并增加一個(gè)基變量，繼續(xù)迭代。例：某工廠準(zhǔn)備生產(chǎn)A、B、C三種產(chǎn)品，他們都消耗勞動(dòng)力和材料，有關(guān)數(shù)據(jù)如下： 原料 產(chǎn)品ABC擁有量勞動(dòng)力63545材料34530售價(jià)（元）314最優(yōu)生產(chǎn)方案：5個(gè)A，0個(gè)B，3個(gè)C新問題：由于特殊原因，要求至少生產(chǎn)6個(gè)C產(chǎn)品，求最優(yōu)生產(chǎn)方案最優(yōu)單純形表X1X2X3X4X50-20-1/5-3/5Z-27X11-1/301/3-1/35X3011-1/52/5300000-1001-6X6X6X1X2X3X4X50-20-1/5-3/5Z-27X11-1/301/3-1/35X3011-1/52/53X6X6000X1X2X3X4X5X60-20-1/5-3/50Z-27X11-1/301/3-1/305X30