對(duì)偶理論與靈敏度分析ppt課件

1、第二章第二章 對(duì)偶實(shí)際與靈敏度分析對(duì)偶實(shí)際與靈敏度分析1線性規(guī)劃的對(duì)偶問題2對(duì)偶問題的根本性質(zhì)3影子價(jià)錢4對(duì)偶單純形法5靈敏度分析第二章1線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題1.1 對(duì)偶問題的提出1.2 對(duì)稱方式下對(duì)偶問題的普通方式1.3 非對(duì)稱方式的原對(duì)偶問題關(guān)系1.4 對(duì)偶問題的定義1.5 對(duì)偶關(guān)系對(duì)應(yīng)表第二章例1：美佳公司利用該公司資源消費(fèi)兩種家電產(chǎn)品。項(xiàng)目項(xiàng)目I IIIII每天可用能力每天可用能力設(shè)備設(shè)備A A（h h）設(shè)備設(shè)備B B（h h）調(diào)試工序（調(diào)試工序（h h）0 06 61 15 52 21 1151524245 5利潤（元）利潤（元）2 21 1212max1xxzLP0

2、,52426155.2121212xxxxxxxst1.1 1.1 對(duì)偶問題的提出對(duì)偶問題的提出1線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題第二章現(xiàn)從另一角度提出問題。假定有另一公司想把美佳公司的資源收買過來，它至少應(yīng)付出多大代價(jià)，才干使美佳公司情愿放棄消費(fèi)活動(dòng)，出讓本人的資源？顯然美佳公司愿出讓本人資源的條件是，出讓代價(jià)應(yīng)不低于用同等數(shù)量資源由本人組織消費(fèi)活動(dòng)時(shí)獲取的盈利。設(shè)分別用yl，y2和y3代表單位時(shí)間h設(shè)備A、設(shè)備B和調(diào)試工序的出讓代價(jià)。因美佳公司用6小時(shí)設(shè)備A和l小時(shí)調(diào)試可消費(fèi)一件家電I，盈利2元；用5小時(shí)設(shè)備A，2小時(shí)設(shè)備B及1小時(shí)調(diào)試可消費(fèi)一件家電II，盈利1元。1線性規(guī)劃的對(duì)偶問題

3、線性規(guī)劃的對(duì)偶問題第二章由此y1，y2，y3的取值應(yīng)滿足:該公司希望用最小代價(jià)把美佳公司的全部資源收買過來。因此，線性規(guī)劃模型為：32152415minyyyz1252632132yyyyy32152415min)2(yyyzLP0,12526.32132132yyyyyyyyts1線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題第二章例2 寫出以下問題的原問題與對(duì)偶問題 1 2 加工才干(小時(shí)/天) A 2 2 12 B 1 2 8 C 4 0 16 D 0 4 12 2 3銷售收入產(chǎn)品設(shè)備1線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題第二章原問題：設(shè)x1 ， x2 為產(chǎn)品1，2的產(chǎn)量2x1 +2x2 12 x

4、1 +2x2 84x1 16 4x2 12x1 x2 0maxZ= 2X1 +3x2 2 2 12 1 2 x1 84 0 x2 160 4 12(2 3) x1x21線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題第二章對(duì)偶問題：設(shè) y1 , y2 , y3 , y4分別為A, B, C, D設(shè)備的單價(jià)2y1 +y2 +4y3 22y1 +2y2 +44 3y1 y4 02 1 4 02 2 0 4y1 y2 y3 y4 23(y1 y2 y3 y4)1281612minW=12y1+8y2 +16y3+12y4y1 y4 “影子價(jià)錢1線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題第二章對(duì)稱的含義：滿足以下條件的

5、線性規(guī)劃問題稱為具有對(duì)稱方式：其變量均具有非負(fù)約束，其約束條件當(dāng)目的函數(shù)求極大時(shí)均取“號(hào)，當(dāng)目的函數(shù)求極小時(shí)均取“號(hào)。對(duì)稱方式下線性規(guī)劃原問題的普通方式為：max Z=c1x1+ c2x2+cnxna11x1+ a12x2+ a1nxn b1a21x1+ a22x2+ a2nxn b2 am1x1+ am2x2+ amnxn bmxj 0(j=1,n)s.t.1.2 對(duì)稱方式下對(duì)偶問題的普通方式對(duì)稱方式下對(duì)偶問題的普通方式1線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題第二章用yi(i1，m)代表第i種資源的估價(jià)，那么其對(duì)偶問題的普通方式為：min w=b1y1+ b2y2+bmyma11y1+ a21

6、y2+ am1ym c1a12y1+ a22y2+ am2ym c2 a1ny1+ a2ny2+ amnym cnXj 0(j=1,m)s.t.1線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題第二章用矩陣方式表示，原問題為:其對(duì)偶問題為：CXz max0.XbAXstbYwmin0.YCYAst1線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題第二章原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系 原問題 對(duì)偶問題A 約束系數(shù)矩陣 其系數(shù)矩陣轉(zhuǎn)置B 約束條件右端項(xiàng)向量 目的函數(shù)價(jià)值系數(shù)C 目的函數(shù)價(jià)值系數(shù) 約束條件 右端項(xiàng)向量 目的函數(shù) maxz=CX min w =Yb 約束條件 AX b AY C 決策變量 X 0 Y0 1線性規(guī)劃

7、的對(duì)偶問題線性規(guī)劃的對(duì)偶問題第二章1.3 非對(duì)稱方式的原對(duì)偶問題關(guān)系非對(duì)稱方式的原對(duì)偶問題關(guān)系1線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題例例2 寫出下述線性規(guī)劃問題的對(duì)偶問題寫出下述線性規(guī)劃問題的對(duì)偶問題321321321321321, 0, 041632532. .34maxxxxxxxxxxxxxtsxxxz無約束第二章1.3 非對(duì)稱方式的原對(duì)偶問題關(guān)系非對(duì)稱方式的原對(duì)偶問題關(guān)系1線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題寫出其對(duì)偶問題為：寫出其對(duì)偶問題為：可變換成具有如下對(duì)稱可變換成具有如下對(duì)稱方式的線性規(guī)劃問題方式的線性規(guī)劃問題0,44166325532. .334max 3321 3321 3

8、321 3321 3321 3321xxxxxxxxxxxxxxxxxxxxtsxxxxz0,36536543132. .442min 3321 3321 3321 3321 3321 3321yyyyyyyyyyyyyyyyyyyytsxyyyw第二章1.3 非對(duì)稱方式的原對(duì)偶問題關(guān)系非對(duì)稱方式的原對(duì)偶問題關(guān)系1線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題進(jìn)展整理為：進(jìn)展整理為：321321321321321, 0, 036543132. .42minyyyyyyyyyyyytsyyyz無約束第二章例3 寫出下述線性規(guī)劃問題的對(duì)偶問題1.3 非對(duì)稱方式的原對(duì)偶問題關(guān)系非對(duì)稱方式的原對(duì)偶問題關(guān)系max

9、Z= 5X1 +6X2 3X1 -2X2 =74X1 +X2 9X1 , X2 01線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題第二章解：原問題可化為maxZ= 5X1 +6X2 3X1 -2X2 7-3X1 +2X2 -74X1 +X2 9X1 , X2 0y1y1 y2那么對(duì)偶問題：3y1 -3y1 +4y2 5 -2y1 +2y1 +y2 6y1 , y1 , y2 0minW=7y1 -7y1 +9y21線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題第二章令 y1 = y1 -y1 minW=7y1 +9y23y1+4y2 5 -2y1 +y2 6y1自在 , y2 01線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶

10、問題第二章1.4 1.4 對(duì)偶的關(guān)系對(duì)偶的關(guān)系原始問題max z=CTXs.t.AX bX 0對(duì)偶問題min y=bTWs.t. ATW CW 0CATbTminmnmaxbACTmn1線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題第二章 原問題 對(duì)偶問題目的函數(shù)類型 max min目的函數(shù)系數(shù) 目的函數(shù)系數(shù) 右邊項(xiàng)系數(shù)與右邊項(xiàng)的對(duì)應(yīng)關(guān)系 右邊項(xiàng)系數(shù) 目的函數(shù)系數(shù)變量數(shù)與約束數(shù) 變量數(shù)n 約束數(shù) n的對(duì)應(yīng)關(guān)系 約束數(shù)m 變量數(shù)m原問題變量類型與 0 對(duì)偶問題約束類型 變量 0 約束 的對(duì)應(yīng)關(guān)系 無限制 原問題約束類型與 0 對(duì)偶問題變量類型 約束 變量 0 的對(duì)應(yīng)關(guān)系 無限制1.5 1.5 對(duì)偶關(guān)系對(duì)應(yīng)

11、表對(duì)偶關(guān)系對(duì)應(yīng)表1線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題第二章第二章2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)單純形法計(jì)算的矩陣描畫單純形法計(jì)算的矩陣描畫一、對(duì)稱性一、對(duì)稱性 二、弱對(duì)偶性二、弱對(duì)偶性三、無界性三、無界性 四、可行解是最優(yōu)解的性質(zhì)四、可行解是最優(yōu)解的性質(zhì)五、對(duì)偶定理五、對(duì)偶定理六、松緊定理六、松緊定理 第二章用矩陣方式表示，原問題為:其對(duì)偶問題為：min y=bYs.t. AY CY 0max z=CXs.t.AX bX 02對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)滿足這兩個(gè)條件的Y是對(duì)偶問題的一個(gè)可行解。滿足這兩個(gè)條件的X是原問題的一個(gè)可行解。第二章單純形法計(jì)算的矩陣描畫單純形法計(jì)算的

12、矩陣描畫對(duì)稱方式線性規(guī)劃問題的矩陣表達(dá)式加上松弛變量后為：0, 00maxSSSXXbIXAXXCXZ上式中XS為松弛變量) ,(21mnnnSxxxX I 為mm單位矩陣經(jīng)過迭代后: X=XB + XN相應(yīng)地: C=CB + CN系數(shù)矩陣 : A= B + N2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)參1-105第二章迭代后新的單純形表為：初始單純形表：非基變量基變量XXS0 XS bcj-zj基變量非基變量XB XN XSCB XB B-1bcj-zj2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章迭代后新的單純形表為：初始單純形表：非基變量基變量XB XN XS0 XS bB NIcj-zjCB

13、 CN0基變量非基變量XB XN XSCB XB B-1bI B-1N B-1cj-zjCB- CBB-1BCN- CBB-1N -CBB-1C- CBB-1A2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章可以看出：(1)對(duì)應(yīng)初始單純形表中的單位矩陣I，迭代后的單純形表中為B-1 ；(2)初始單純形表中基變量Xsb，迭代后的表中 XB=B1b ；(3)初始單純形表中約束系數(shù)矩陣為A，I B，N，I ，迭代后的表中約束系數(shù)矩陣為B-1A，B-1IB-1B，B-1N，B-1I I，B-1N，B-1 ；(4)假設(shè)初始矩陣中變量Xi的系數(shù)向量為Pj，迭代后為Pj，那么有Pj=B-1Pj 。2對(duì)偶問題的根

14、本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章當(dāng)B為最優(yōu)基時(shí)因xB的檢驗(yàn)數(shù)可寫為 CB- CBI=0CBB-1稱為單純形乘子，假設(shè)令Y= CBB-1 ，那么所以0YCAY0YCYACN- CBB-1N 0 -CBB-1 0C- CBB-1A 0 -CBB-1 02對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章看出這時(shí)檢驗(yàn)數(shù)行，假設(shè)取其相反數(shù)恰好是其對(duì)偶問題的一個(gè)可行解。將這個(gè)解代入對(duì)偶問題的目的函數(shù)值，有：當(dāng)原問題為最優(yōu)解時(shí)，這時(shí)對(duì)偶問題為可行解，且兩者具有一樣的目的函數(shù)值，對(duì)偶問題的解也為最優(yōu)解。w=Yb= CBB-1b=z2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章例例4 5x2 +x3 =15 s.t. 6

15、x1 +2x2 +x4 =24 x1 + x2 +x5 =5 x1 , , x5 0 maxZ=2x1+ x2+0 x3 +0 x4+0 x5s.t. 6y2 + y3 -y4 =2 5y1 + 2y2 + y3 -y5 =1 y1 , , y5 0 min w=15y1+ 24y2+ 5y3 +0y4+0y52對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章最終單純形表：最終單純形表：原問題變量松弛變量XB bx1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2zj-cj0001/41/2對(duì)偶問題的剩余變量對(duì)偶問題變量y4y5y1y2y

16、3對(duì)偶問題變量對(duì)偶問題的剩余變量XB by1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2cj zj15/2007/23/2原問題的松馳變量原問題變量x3x4x5x1x22對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章 0maxxbAxLxczT0minYcYADYbw一一 . 對(duì)稱性對(duì)稱性 ： 對(duì)偶問題的對(duì)偶是原問題對(duì)偶問題的對(duì)偶是原問題2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章 0minYcYADYbw 0)()(maxYcAYDbYw 0minxbAxLxcwT 0maxxbAxLxczT對(duì)對(duì)偶偶2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章假設(shè)x是

17、原問題的可行解，y是對(duì)偶問題的可行解。那么有 cxyb byxAyxcoxcAybyxAyybxA又證明：0二二. 弱對(duì)偶性弱對(duì)偶性2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章推論(2)： 假設(shè)原問題對(duì)偶問題為無界解，那么其對(duì)偶問題原問題無可行解。推論(1)： 原問題任一可行解的目的函數(shù)值是其對(duì)偶問標(biāo)題的函數(shù)值的下界，反之對(duì)偶問題任一可行解的目的函數(shù)值是其原問標(biāo)題的函數(shù)值的上界。 注 ： 其逆不成立。推論(3)假設(shè)原問題有可行解而其對(duì)偶問題無可行解，那么原問標(biāo)題的函數(shù)值無界，反之對(duì)偶問題有可行解而其原問題無可行解，那么對(duì)偶問題的目的函數(shù)值無界。2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章設(shè)x是

18、原問題的可行解，y是對(duì)偶問題的可行解. 當(dāng) cx= yb 時(shí) x, y 是最優(yōu)解。三三 . 最優(yōu)性最優(yōu)性*CXCX證明：bYbY*bYCX又bYCX*CXCXbYbY*CXCXbYbY2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章四四 . 強(qiáng)對(duì)偶性對(duì)偶定理強(qiáng)對(duì)偶性對(duì)偶定理 假設(shè)原問題及其對(duì)偶問題均具有可行解，那么兩者均具有最優(yōu)解且它們最優(yōu)解的目的函數(shù)值相等。證明： 由弱對(duì)偶定理推論1，可知兩者都有最優(yōu)解。由前面公式可知，當(dāng)原問題有最優(yōu)解時(shí)，對(duì)偶問題有可行解，且目的函數(shù)值相等。由最優(yōu)性知，兩者均為最優(yōu)解。2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章五五. 互補(bǔ)松弛性松緊定理互補(bǔ)松弛性松緊定理在線性

19、規(guī)劃問題的最優(yōu)解中，假設(shè)對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，那么該約束條件取嚴(yán)厲等式；反之假設(shè)約束條件取嚴(yán)厲不等式，那么其對(duì)應(yīng)的對(duì)偶變量一定為零。y1y2y3212max1xxzLP0,52426155.2121212xxxxxxxst2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章即：0即,則有,0若1sinjijijixbxay0則有, 0即, ,若1isinjiijyxbxa0因此一定有isiyx2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì) miiiminjijijnjjjybyxaxc1111001njijijibxa，y必有時(shí)當(dāng)001injijijy，bxa必有時(shí)當(dāng)證明：011injijijm

20、iybxa01injijijybxa第二章無最優(yōu)解。：證明：0324min132131321ixxxxxxxxx幾個(gè)練習(xí)幾個(gè)練習(xí)2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章故無最優(yōu)解。原問題是無界的，對(duì)偶問題不可行，因而考慮其對(duì)偶問題為其一可行解。證明：0,121134max)0 , 0 , 4(212122121yyyyyyyyyzx2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章025357162954max2321321321ixxxxxxxxxxz：考慮問題1 闡明原問題和對(duì)偶問題都有最優(yōu)解.2 求原問題和對(duì)偶問題的最優(yōu)目的函數(shù)值的一個(gè)上界和下界.2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二

21、章兩者都有最優(yōu)解。對(duì)偶性質(zhì)可知，兩問題都有可行解，由有可行解：其對(duì)偶問題為：原問題有可行解）解：)0 , 5(0,93255472516min)8 ,0 ,0(12121212121yyyyyyyyyyyx2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章8072.80)0 , 5(;72)8 ,0 ,0(2*zzyzx下界。有上數(shù)值由弱對(duì)偶性最優(yōu)目標(biāo)函有對(duì)于對(duì)偶問題的可行解有）對(duì)于原問題的可行解2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章對(duì)偶問題的最優(yōu)解。用互補(bǔ)松弛定理計(jì)算的最優(yōu)解為問題：已知28)4 , 4 , 0 , 0(02023220322432max3*432143214321zxxxx

22、xxxxxxxxxxzLPi0,42333222122020min212121212121yyyyyyyyyyyy解：對(duì)偶問題為：2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章最優(yōu)值。為對(duì)偶問題的最優(yōu)解和；對(duì)應(yīng)目標(biāo)函數(shù)值為對(duì)偶問題的可行解，經(jīng)檢驗(yàn)解得有由有根據(jù)互補(bǔ)松弛定理，由285/1, 5/6285/1, 5/65/1, 5/6423043320421*2121214213yyzyyyyyyxyyx2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章最優(yōu)解。）是可行的，則一定有證明：若問題（）：?jiǎn)栴}（。得到改為有最優(yōu)解?，F(xiàn)將向量）：?jiǎn)栴}（：設(shè)20min20min14XdAXCXLPdbXbAXCXLP

23、2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章?？芍鋵?duì)偶問題必可行理，）有最優(yōu)解，由對(duì)偶定問題（ 1）的對(duì)偶問題亦可行，從而問題（ 2）一定有最優(yōu)解。由強(qiáng)對(duì)偶性，問題（2CYAYbzmax1）的對(duì)偶問題為：證明：?jiǎn)栴}（0YCYAYdzmax2）的對(duì)偶問題為：?jiǎn)栴}（0Y2對(duì)偶問題的根本性質(zhì)對(duì)偶問題的根本性質(zhì)第二章3影子價(jià)錢影子價(jià)錢式中bi是線性規(guī)劃原問題約束條件的右端項(xiàng)，它代表第i種資源的擁有量；對(duì)偶變量yi*的意義代表在資源最優(yōu)利用條件下對(duì)單位第i仲資源的估價(jià)。這種估價(jià)不是資源的市場(chǎng)價(jià)錢，而是根據(jù)資源在消費(fèi)中作出的奉獻(xiàn)而作的估價(jià)，為區(qū)別起見，稱為影子價(jià)錢(shadow price)。njmii

24、ijjwybxcz11*第二章關(guān)于影子價(jià)錢的幾點(diǎn)闡明1影子價(jià)錢是未知數(shù),有賴于資源的利用情況。2影子價(jià)錢是一種邊沿價(jià)錢。miiiybz1*iiybz求導(dǎo) 這闡明影子價(jià)錢的值相當(dāng)于在資源得到最優(yōu)利用的消費(fèi)條件下，b每添加一個(gè)單位時(shí)目的函數(shù)Z的增量。3影子價(jià)錢影子價(jià)錢第二章原問題變量松弛變量XB bx1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2zj-cj0001/41/2對(duì)偶問題的剩余變量對(duì)偶問題變量y4y5y1y2y3例1ABC15/200資源剩余01/41/2影子價(jià)錢543210002maxxxxxxz)5,.,1(05242

25、615552142132jxxxxxxxxxj3影子價(jià)錢影子價(jià)錢第二章15/4，5/4z=8.753，3z=9BAC7/2，3/2z=8.5所以第2種資源的影子價(jià)錢為0.25，第3種資源的影子價(jià)錢為0.5。3影子價(jià)錢影子價(jià)錢第二章3資源的影子價(jià)錢實(shí)踐上又是一種時(shí)機(jī)本錢。在純市場(chǎng)經(jīng)濟(jì)條件下，可以根據(jù)影子價(jià)錢與市場(chǎng)價(jià)錢的關(guān)系確定資源的買進(jìn)或賣出。4消費(fèi)過程中假設(shè)某種資源末得到充分利用時(shí)，該種資源的影子價(jià)錢為零；又當(dāng)資源的影子價(jià)錢不為零時(shí)，闡明該種資源在消費(fèi)中已耗費(fèi)終了。3影子價(jià)錢影子價(jià)錢第二章5單純形表中各個(gè)檢驗(yàn)數(shù)的經(jīng)濟(jì)意義 6對(duì)線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對(duì)于對(duì)偶問題的求解那么

26、是確定對(duì)資源的恰當(dāng)估價(jià)。當(dāng)產(chǎn)品產(chǎn)值大于隱含本錢時(shí)，闡明消費(fèi)該項(xiàng)產(chǎn)品有利，可在方案中安排，否那么這些資源來消費(fèi)別的產(chǎn)品更為有利，就不在方案中安排。這就是單純形表中各個(gè)檢驗(yàn)數(shù)的經(jīng)濟(jì)意義。miiijjjBjjyacPBCc113影子價(jià)錢影子價(jià)錢第二章4對(duì)偶單純形法對(duì)偶單純形法單純形法的思緒：找一個(gè)基可行解，在堅(jiān)持解可行的前單純形法的思緒：找一個(gè)基可行解，在堅(jiān)持解可行的前提下，讓檢驗(yàn)數(shù)全為非正。提下，讓檢驗(yàn)數(shù)全為非正。 原問題變量原問題變量松弛變量松弛變量XB bx1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2zj-cj0001/41/

27、2對(duì)偶問題的剩余變量對(duì)偶問題的剩余變量對(duì)偶問題變量對(duì)偶問題變量y4y5y1y2y3第二章對(duì)偶單純形法的根本思緒：先找出一個(gè)對(duì)偶問題對(duì)偶單純形法的根本思緒：先找出一個(gè)對(duì)偶問題的可行基，并堅(jiān)持對(duì)偶問題為可行解條件下，如不存的可行基，并堅(jiān)持對(duì)偶問題為可行解條件下，如不存在在XB o，經(jīng)過變換到一個(gè)相鄰的目的函數(shù)值較小的，經(jīng)過變換到一個(gè)相鄰的目的函數(shù)值較小的根本解根本解(因?qū)ε紗栴}是求目的函數(shù)極小化因?qū)ε紗栴}是求目的函數(shù)極小化)，并循環(huán)進(jìn)，并循環(huán)進(jìn)展，不斷到原問題也為可行解展，不斷到原問題也為可行解(即即XB o)，這時(shí)對(duì)偶，這時(shí)對(duì)偶問題與原問題均為可行解。問題與原問題均為可行解。在迭代過程中堅(jiān)持原問

28、題的檢驗(yàn)數(shù)為非正，逐漸在迭代過程中堅(jiān)持原問題的檢驗(yàn)數(shù)為非正，逐漸交換負(fù)基變量，從而得到最優(yōu)解。交換負(fù)基變量，從而得到最優(yōu)解。4對(duì)偶單純形法對(duì)偶單純形法第二章對(duì)偶單純形法的計(jì)算步驟：對(duì)偶單純形法的計(jì)算步驟： 1. 列出初始單純形表，且檢驗(yàn)數(shù)非正。 為換出變量。對(duì)應(yīng)的基變量按rriiixbBbBbB1110min.2為換入變量確定按srsssrjrjjjxazcaazc0min.34對(duì)偶單純形法對(duì)偶單純形法第二章4.以ars為主元素，進(jìn)展迭代變換?？梢宰C明，按照上述方法進(jìn)展迭代變換以后，檢驗(yàn)數(shù)仍堅(jiān)持為非正，即對(duì)偶問題仍可行。5 . 返 2，直到B 0為止。原始單純形法 按列選主元 對(duì)偶單純形法 按

29、行選主元對(duì)于對(duì)偶問題有可行解，而原問題無可行解的判別。判別準(zhǔn)那么是：對(duì) ，而對(duì)一切j=1,n，有 。0rja0rb4對(duì)偶單純形法對(duì)偶單純形法第二章例5：用對(duì)偶單純形法求解以下問題02225324. .23min321321321321321xxxxxxxxxxxxtsxxxz02225324. .23min654321632153214321321xxxxxxxxxxxxxxxxxxtsxxxz4對(duì)偶單純形法對(duì)偶單純形法第二章02225324. .23max654321632153214321321xxxxxxxxxxxxxxxxxxtsxxxzCj321000CBXBbx1x2x3x4x5x

30、60 x441111000 x552310100 x62221001 j=cj-zj4對(duì)偶單純形法對(duì)偶單純形法第二章Cj321000CBXBbx1x2x3x4x5X60 x417/31/302/31-1/30-2x25/3-2/31-1/30-1/300X6-16/3-2/30-1/302/31 j=cj-zjCj321000CBXBbx1x2x3x4x5X60 x417/31/302/31-1/30-2X25/3-2/31-1/30-1/300X6-16/3-2/30-1/302/31 j=cj-zj-13/30-5/30-2/304對(duì)偶單純形法對(duì)偶單純形法第二章Cj321000CBXBbx

31、1x2x3x4x5X60 x4-5-10011/32-2X270100-1-1-1X3162010-2-3 j=cj-zj-1000-7/3-5Cj321000CBXBbx1x2x3x4x5X6-3x15100-1-1/3-2-2X270100-1-1-1X360012-21 j=cj-zj000-1-5-74對(duì)偶單純形法對(duì)偶單純形法第二章已獲得最優(yōu)解：x1, x2, x3, x4, x5, x6=5, 7, 6, 0, 0, 0 min z=35對(duì)偶問題的最優(yōu)解為：w1, w2, w3, w4, w5, w6=-1, 5, 7, 0, 0, 0 max y=354對(duì)偶單純形法對(duì)偶單純形法第二

32、章 從以上計(jì)算可以看出，用對(duì)偶單純形法求解線性規(guī)劃問題時(shí)，當(dāng)約束條件為“時(shí)，不用引進(jìn)人工變量，使計(jì)算簡(jiǎn)化。但在初始單純形表中其對(duì)偶問題應(yīng)是基可行解這點(diǎn)，對(duì)多數(shù)線性規(guī)劃問題很難實(shí)現(xiàn)。因此對(duì)偶單純形法普通不單獨(dú)運(yùn)用，而主要運(yùn)用于靈敏度分析及整數(shù)規(guī)劃等有關(guān)章節(jié)中。4對(duì)偶單純形法對(duì)偶單純形法例:(初始解原始、對(duì)偶都不可行的問題)0 xxx2xx2x5xx3x24xxx. t . sx2x2x3zmin3213213213213210 xxxxxx2xxx2x5xxx3x24xxxx. t . sx2x2x3zmin65432163215321432132102225324. .223max654321

33、632153214321321xxxxxxxxxxxxxxxxxxtsxxxz解法1：先處理原始可行性Cj322000CBXBbx1x2x3x4x5x60 x441111000 x552310100 x62221001 j=cj-zjCj322000CBXBbx1x2x3x4x5x60 x417/31/302/31-1/30-2x25/3-2/31-1/30-1/300 x6-16/3-2/30-1/302/31 j=cj-zj-13/304/30-2/30Cj322000CBXBbx1x2x3x4x5x60 x43001/2101/2-2x270100-1-1-3x18101/20-1-3/

34、2 j=cj-zj0011/20-5-13/2Cj322000CBXBbx1x2x3x4x5x62x36001201-2x270100-1-1-3x15100-1-1-2 j=cj-zj000-7-5-10在得到原始可行解時(shí)同時(shí)得到對(duì)偶可行解，已獲得最優(yōu)解：x1, x2, x3, x4, x5, x6=5, 7, 6, 0, 0, 0 min z=17對(duì)偶問題的最優(yōu)解為：w1, w2, w3, w4, w5, w6=-7, 5, 10, 0, 0, 0 max y=17第二章Cj322000CBXBbx1x2x3x4x5x60 x441111000 x552310100 x62221001 j

35、=cj-zj322000解法2：先處理對(duì)偶可行性已得到對(duì)偶可行解，再用對(duì)偶單純形法求解Cj322000CBXBbx1x2x3x4x5x62x341111000 x59120-1100 x62110101 j=cj-zj500-200Cj322000CBXBbx1x2x3x4x5x62x317/21/2013/2-1/20-2x29/2-1/2101/2-1/200 x6-5/2-1/2001/21/21 j=cj-zj500-200Cj322000CBXBbx1x2x3x4x5x62x36001201-2x270100-1-1-3x15100-1-1-2 j=cj-zj000-7-5-10得到

36、原始可行解，已獲得最優(yōu)解：x1, x2, x3, x4, x5, x6=5, 7, 6, 0, 0, 0 min z=17對(duì)偶問題的最優(yōu)解為：w1, w2, w3, w4, w5, w6=-7, 5, 10, 0, 0, 0 max y=17第二章對(duì)偶單純形法的優(yōu)點(diǎn)：對(duì)偶單純形法的優(yōu)點(diǎn)： 1 簡(jiǎn)化計(jì)算簡(jiǎn)化計(jì)算 2 減少計(jì)算量減少計(jì)算量 3 靈敏度分析靈敏度分析缺陷：缺陷： 第一個(gè)正那么解很難找到第一個(gè)正那么解很難找到4對(duì)偶單純形法對(duì)偶單純形法第二章5靈敏度分析靈敏度分析靈敏度分析是指對(duì)系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。A，b，C當(dāng)這些參數(shù)中的一個(gè)或幾個(gè)發(fā)生變化時(shí)，問題的最優(yōu)解會(huì)

37、有什么變化，或者這些參數(shù)在一個(gè)多大范圍內(nèi)變化時(shí)，問題的最優(yōu)解不變。這就是靈敏度分析所要研討處理的問題。單純形法的迭代計(jì)算是從一組基向量變換為另一組基向量，表中每步迭代得到的數(shù)字只隨基向量的不同選擇而改動(dòng)，因此有能夠把個(gè)別參數(shù)的變化直接在計(jì)算得到最優(yōu)解的最終單純形表上反映出來。第二章 靈敏度分析的步驟靈敏度分析的步驟1將參數(shù)的改動(dòng)計(jì)算反映到最終單純形表上來：將參數(shù)的改動(dòng)計(jì)算反映到最終單純形表上來：5靈敏度分析靈敏度分析bBb1jjPBP1bBXB1jjPBP101ABCCBmiiijjjjyaczc1*)(第二章2檢查原問題能否仍為可行解；3檢查對(duì)偶問題能否仍為可行解；4按下表所列情況得以結(jié)論和

38、決議繼續(xù)計(jì)算的步驟。原問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解最優(yōu)解可行解非可行解用單純形法求解最優(yōu)解非可行解可行解用對(duì)偶單純形法求解最優(yōu)解非可行解非可行解引入人工變量求解最優(yōu)解5靈敏度分析靈敏度分析第二章靈敏度分析處理的主要問題：(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)、假設(shè)最優(yōu)方案改動(dòng)，如何用簡(jiǎn)便方法求新方案？5靈敏度分析靈敏度分析第二章一、分析一、分析Cj的變化的變化線性規(guī)劃目的函數(shù)中變量系數(shù)線性規(guī)劃目的函數(shù)中變量系數(shù)Cj的變化僅僅影的變化僅僅影響到檢驗(yàn)數(shù)響到檢驗(yàn)數(shù)(Cj-Zj)約變化。所以將約變

39、化。所以將Cj的變化直接反的變化直接反映到最終單純形表中，只能夠出現(xiàn)前兩種情況。映到最終單純形表中，只能夠出現(xiàn)前兩種情況。5靈敏度分析靈敏度分析原問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解最優(yōu)解可行解非可行解用單純形法求解最優(yōu)解非可行解可行解用對(duì)偶單純形法求解最優(yōu)解非可行解非可行解引入人工變量求解最優(yōu)解第二章5靈敏度分析靈敏度分析 例5 在第一章例1的美佳公司例子中:(1)假設(shè)家電I的利潤降至1. 5元件，而家電的利潤增至2元件時(shí)，美佳公司最優(yōu)消費(fèi)方案有何變化?Cj21000CBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010

40、-1/43/2 j=cj-zj000-1/4-1/2第二章5靈敏度分析靈敏度分析解 (1)將家電I，II的利潤變化直接反映到最終單純形表中。Cj1.52000CBXBbX1x2x3x4x50 x315/20015/4-15/21.5x17/21001/4-1/22x23/2010-1/43/2 j=cj-zj0001/8-9/4以x4為換入變量,x3為換出變量，列新單純形表。Cj1.52000CBXBbx1x2x3x4x50 x46004/51-61.5x1210-1/5012x23011/500 j=cj-zj00-1/10 0-3/2一切檢驗(yàn)數(shù)為非正，問題得到最優(yōu)解：X2，3，0，6，0第

41、二章5靈敏度分析靈敏度分析(2)假設(shè)家電I的利潤不變，那么家電II的利潤在什么范圍內(nèi)變化時(shí)，那么該公司的最優(yōu)消費(fèi)方案將不發(fā)生變化？設(shè)家電II的利潤為(1十)元，反映到最終單純形表中為：Cj21十000CBXBbx1x2x3x4x50 x460015/4-15/22x121001/4-1/21十x23010-1/43/2 j=cj-zj000-1/4+1/4 -1/2-3/2 為使表中的解仍為最優(yōu)解，應(yīng)有即家電II的利潤C(jī)2的變化范圍應(yīng)滿足：第二章例6 A B C 備用資源 甲 1 1 1 12 乙 1 2 2 20 利潤 5 8 6 產(chǎn)品原料問：如何安排產(chǎn)品產(chǎn)量，可獲最大利潤？5靈敏度分析靈敏

42、度分析第二章maxZ=5X1 +8X2 +6X3X1+ X2 + X3+X4 = 12X1+2X2+2X3 +X5 =20X1 X5 0解：Cj58600CBXBbx1x2x3x4x55x14100218x2801111 j=cj-zj00223最優(yōu)單純形表為：?jiǎn)? 價(jià)值系數(shù)變化時(shí)對(duì)最優(yōu)解的影響？5靈敏度分析靈敏度分析第二章(1)、非基變量系數(shù)Cj Cj 改動(dòng)，仍有j0 時(shí)對(duì)最優(yōu)方案無影響。12=C3 -(5 8) =C3 -80 2 -1-1 1即C3 8 例中C3在什么范圍內(nèi)變化時(shí)，對(duì)最優(yōu)方案無影響？ 3 = C3 -CBB-1 P35靈敏度分析靈敏度分析第二章 C3改為10， 最優(yōu)方案如

43、何變化？CB XB b 5 8 10 0 0 5 X1 4 1 0 0 2 -1 8 X2 8 0 1 (1) -1 1 0 0 (2) -2 -3 5 X1 4 1 0 0 2 -1 X3 8 0 1 1 -1 1 0 -2 0 0 -5 3 =205靈敏度分析靈敏度分析第二章(2)、基變量系數(shù)Cj Cj 改動(dòng)？ 全部 j0，最優(yōu)方案不變例中C1改動(dòng) A = C -CBB-1 A =(0,0,-2,-2C1+8, C1 -8) 0-2C1+8 0C1-8 04 C1 81 0 0 2 -10 1 1 -1 1=(C1 ,8,6,0,0 ) -(C1 8)5靈敏度分析靈敏度分析第二章 C1改動(dòng)

44、 C1=10？ XB 10 8 6 0 010 X1 4 1 0 0 2 -1 8 X2 8 0 1 1 -1 (1) 0 0 -2 -12 2 10 X1 12 1 1 1 1 0 0 X5 8 0 1 1 -1 1 0 -2 -4 -10 0 5 =20 ,換基5靈敏度分析靈敏度分析第二章二、分析二、分析bi的變化的變化右端項(xiàng)bj的變化在實(shí)踐問題中反映為可用資源數(shù)量的變化。原問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解最優(yōu)解可行解非可行解用單純形法求解最優(yōu)解非可行解可行解用對(duì)偶單純形法求解最優(yōu)解非可行解非可行解引入人工變量求解最優(yōu)解5靈敏度分析靈敏度分析第二章 例7：在美佳公司的例子中：(

45、1)假設(shè)設(shè)備A和調(diào)試工序的每天才干不變，而設(shè)備B每天的才干添加到32小時(shí)，分析公司最優(yōu)方案的變化?Cj21000CBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2 j=cj-zj000-1/4-1/2解：由于：080b22100802/ 34/ 102/ 14/ 102/154/ 511bBb5靈敏度分析靈敏度分析第二章以X2為換出變量，X4為換入變量，列新單純形表得：?jiǎn)栴}的最優(yōu)解：X5，0，15，2，0Cj21000CBXBbx1x2x3x4x50 x335/20015/4-15/22x111/21001/4-

46、1/21x2-1/2010-1/43/2 j=cj-zj000-1/4-1/2Cj21000CBXBbx1x2x3x4x50 x315051002x15110011x420-401-6 j=cj-zj0-100-25靈敏度分析靈敏度分析第二章單純形表中b列數(shù)字為：(2)假設(shè)設(shè)備A和B每天可用才干不變，那么調(diào)試工序才干在什么范圍內(nèi)變化時(shí)，問題的最優(yōu)基不變?設(shè)調(diào)試工序每天可用才干為5+小時(shí)，因有2321215002/ 34/ 102/ 14/ 102/154/ 511bBb23232127215215b當(dāng)b 0時(shí)問題的最優(yōu)基不變，解得：-1 1因此調(diào)試工序的才干應(yīng)在4小時(shí)-6小時(shí)之間。5靈敏度分析

47、靈敏度分析第二章(1)、bj 改動(dòng)？改動(dòng)？ B-1 b仍仍0時(shí)，最優(yōu)方案不變。時(shí)，最優(yōu)方案不變。例中例中b1改動(dòng)改動(dòng)2 -1-1 1b120B-1 b= 010 b1 20 2b1 -20 0-b1+20 0Cj58600CBXBbx1x2x3x4x55x14100218x2801111 j=cj-zj00223前面例子：前面例子：第二章CB XB 5 X1 40 1 0 0 2 -1 8 X2 -10 0 1 1 (-1) 1 0 0 -2 -2 -3 5 X1 20 1 2 2 0 1 0 X4 10 0 -1 -1 1 -1 0 -2 -4 0 -5(2)、 b1改動(dòng)改動(dòng), b1=30

48、，2 -1-1 13020B-1 b= 40-10第二章三、添加一個(gè)變量三、添加一個(gè)變量xj的分析的分析添加一個(gè)變量在實(shí)踐問題中反映為添加一種新的產(chǎn)品。其分析步驟為：miiijjjjjyaczc1*計(jì)算. 1jjPBP1計(jì)算. 23.假設(shè) ，原最優(yōu)解不變，只需將計(jì)算得到的 和 直接寫入最終單純 形表中；假設(shè) ，那么按單純形法繼續(xù)迭代計(jì)算找出最優(yōu)。0jjPj0j5靈敏度分析靈敏度分析第二章 例8 在美佳公司例子中，設(shè)該公司又方案推出新型號(hào)的家電III，消費(fèi)一件所需設(shè)備A、B及調(diào)試工序的時(shí)間分別為3小時(shí)、4小時(shí)、2小時(shí)，該產(chǎn)品的預(yù)期盈利為3元件。試分析該種產(chǎn)品能否值得投產(chǎn)，如投產(chǎn)，對(duì)該公司的最優(yōu)消

49、費(fèi)汁劃有何變化。1243)21,41, 0(32072432/ 34/ 102/ 14/ 102/154/ 516P解：設(shè)該公司消費(fèi)家電III 件，有TPc)2 , 4 , 3(, 3665靈敏度分析靈敏度分析第二章以x2 為換出變量， x6 為換入變量，列新單純形表得：Cj210003CBXBbx1x2x3x4x5x60 x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/22 j=cj-zj000-1/4-1/215靈敏度分析靈敏度分析第二章問題的最優(yōu)解：X7/2，0，51/4，0，0，3/4T。所以，該公司新的消費(fèi)方案應(yīng)為每天消費(fèi)家電I

50、7/2件，消費(fèi)家電III 3/4件。Cj210003CBXBbx1x2x3x4x5x60 x351/407/213/8-9/402x17/21001/41/203x63/401/20-1/83/41 j=cj-zj0-1/20-1/8-5/405靈敏度分析靈敏度分析第二章現(xiàn)有新產(chǎn)品現(xiàn)有新產(chǎn)品D D，知消費(fèi)，知消費(fèi)1 1個(gè)單位個(gè)單位D D要耗費(fèi)：要耗費(fèi)： 甲：甲：3 3 乙：乙：2 2 ，可以得利潤，可以得利潤1010。問：投產(chǎn)產(chǎn)品問：投產(chǎn)產(chǎn)品D D能否有利？能否有利？Cj58600CBXBbx1x2x3x4x55x14100218x2801111 j=cj-zj00223 A B C 備用資源

51、備用資源 甲甲 1 1 1 12 乙乙 1 2 2 20 利潤利潤 5 8 6 產(chǎn)品產(chǎn)品原料原料前面例子：前面例子：第二章結(jié)論：無利結(jié)論：無利 6 = C6 - CBB-1 P6 = 10 - (5 8) 2 -1 3 -1 1 2 = 10 - 12 = -2 0 得 C6 122 2 C6 =15 C6 =15 時(shí)時(shí) ，原問題的最優(yōu)解為多少？，原問題的最優(yōu)解為多少？ 6 =3 6 =3 P6 = B-1 P6 = 2 -1 3 = 4 -1 1 2 -1 第二章 5 8 6 0 0 15 5 8 6 0 0 15 XB X1 XB X1 X2 X3 X4 X5 X6X2 X3 X4 X5

52、X6 X1 4 1 0 X1 4 1 0 0 2 -1 (4)0 2 -1 (4) X2 8 0 1 X2 8 0 1 1 -1 1 -11 -1 1 -1 0 0 0 0 -2 -2 -3 3-2 -2 -3 3 X6 1 1/4 0 X6 1 1/4 0 0 -1/2 -1/4 1 0 -1/2 -1/4 1 X2 9 1/4 1 X2 9 1/4 1 1 -1/2 3/4 0 1 -1/2 3/4 0 -3/4 0 - -3/4 0 -2 -7/2 -9/4 02 -7/2 -9/4 0第二章四、分析參數(shù)四、分析參數(shù)aij的變化的變化 aij的變化使線性規(guī)劃的約束系數(shù)矩陣A發(fā)生變化。假設(shè)

53、變量xj在最終單純形表中為非基變量，其約束條件中系數(shù)aij的變化分析步驟可參照本節(jié)之三；假設(shè)變量xi在最終單純形表中為基變量，那么aij的變化將使相應(yīng)的B和B-1 發(fā)生變化因此有能夠出現(xiàn)原問題和對(duì)偶問題均為非可行解的情況。出現(xiàn)這種情況時(shí)，需引進(jìn)入工變量將原問題的解轉(zhuǎn)化為可行解，再用單純形法求解。5靈敏度分析靈敏度分析第二章例9 在美佳公司的例子中，假設(shè)家電II每件需設(shè)備A，B和調(diào)試工時(shí)變?yōu)?小時(shí)、4小時(shí)、1小時(shí)，該產(chǎn)品的利潤變?yōu)?元/件，試重新確定該公司最優(yōu)消費(fèi)方案。解：將消費(fèi)工時(shí)變化后的新家電II看作是一種新產(chǎn)品，消費(fèi)量為x2。2/3148)21,41, 0(322/ 12/ 12/1114

54、82/ 34/ 102/ 14/ 102/154/ 512P5靈敏度分析靈敏度分析第二章因x2已變換為x2 ，故用單純形算法將x2交換出基變量中的x2 ，并在單純形表中不再保管x2。Cj213000CBXBbx1x2x2x3x4x50 x315/20011/215/4-15/22x17/2101/201/4-1/21x23/2011/20-1/43/2 j=cj-zj003/20-1/4-1/2Cj23000CBXBbx1x2x3x4x50 x3-90014-242x121001/2-23x2 30101/23 j=cj-zj0001/2-55靈敏度分析靈敏度分析第二章添加人工變量。Cj230

55、00CBXBbx1x2x3x4x50 x3-90014-242x121001/2-23x2 30101/23 j=cj-zj0001/2-5Cj23000-MCBXBbx1x2x3x4x5x6-Mx3900-1-42412x121001/2-203x2 30101/230 j=cj-zj00-M1/2-4M-5+24M0X3+ 4X4 - 24X5= -95靈敏度分析靈敏度分析第二章美佳公司的最優(yōu)消費(fèi)方案為每天消費(fèi)家電I 11/4件，新家電II 15/8件。Cj23000-MCBXBbx1x2x3x4x5x60 x53/800-1/24-1/611/242x111/410-1/121/301/

56、123x2 15/8011/800-1/8 j=cj-zj00-5/24-2/30-M-5/245靈敏度分析靈敏度分析第二章前面例子：產(chǎn)品前面例子：產(chǎn)品A工藝改動(dòng)，對(duì)甲、乙需求變?yōu)楣に嚫膭?dòng)，對(duì)甲、乙需求變?yōu)?，2。 利潤為利潤為7，問最優(yōu)方案如何？，問最優(yōu)方案如何？先計(jì)算先計(jì)算 p1= 2 -1 2 = 2 -1 1 2 0 1=7-2*5= -3 放入最優(yōu)表Cj58600CBXBbx1x2x3x4x55x14100218x2801111 j=cj-zj00223第二章 X1 X1 X2 X1 X1 X2 X3 X4 X5X3 X4 X5 5 X1 4 1 2 5 X1 4 1 2 0 0 2

57、 -10 0 2 -1 8 X2 8 0 0 8 X2 8 0 0 1 1 -1 11 1 -1 1 0 -3 0 -3 0 -2 -2 -30 -2 -2 -3 7 X1 2 1 7 X1 2 1 0 0 1 -1/20 0 1 -1/2 8 X2 8 0 8 X2 8 0 1 1 -1 1 1 1 -1 1 0 0 0 -2 1 -3/20 -2 1 -3/2 0 X4 2 1 0 X4 2 1 0 0 1 -1/2 0 0 1 -1/2 8 X2 10 1 8 X2 10 1 1 1 0 1/2 1 1 0 1/2 -1 -1 0 -2 0 -10 -2 0 -1換入？換出？第二章 X1

58、 X1 X2 X1 X1 X2 X3 X4 X5X3 X4 X5 5 X1 4 1 2 5 X1 4 1 2 0 0 2 -10 0 2 -1 8 X2 8 0 0 8 X2 8 0 0 1 1 -1 11 1 -1 1 0 -3 0 -3 0 -2 -2 -30 -2 -2 -3 7 X1 2 1 7 X1 2 1 0 0 1 -1/20 0 1 -1/2 8 X2 8 0 8 X2 8 0 1 1 -1 1 1 1 -1 1 0 0 0 -2 1 -3/20 -2 1 -3/2 0 X4 2 1 0 X4 2 1 0 0 1 -1/2 0 0 1 -1/2 8 X2 10 1 8 X2 1

59、0 1 1 1 0 1/2 1 1 0 1/2 -1 -1 0 -2 0 -10 -2 0 -1第二章五、添加一個(gè)約束條件的分析五、添加一個(gè)約束條件的分析 添加一個(gè)約束條件在實(shí)踐問題中相當(dāng)增添一道工序。從圖形二維上分析相當(dāng)于添加了一條直線。分析的方法是先將原問題最優(yōu)解的變量值代入新增的約束條件。如滿足，闡明新增的約束未起到限制造用，原最優(yōu)解不變。否那么，將新增的約束直接反映到最終單純形表中再進(jìn)步分析。5靈敏度分析靈敏度分析第二章例10 仍以美佳公司為例，設(shè)家電I，II經(jīng)調(diào)試后，還需經(jīng)過道環(huán)境實(shí)驗(yàn)工序。家電I每件須環(huán)境實(shí)驗(yàn)3小時(shí)，家電II每件2小時(shí)，又環(huán)境實(shí)驗(yàn)工序每天消費(fèi)才干為12小時(shí)試分析添加

60、該工序后的美佳公司最優(yōu)消費(fèi)方案。解：先將原問題的最優(yōu)解x1 =7/2, x2 =3/2代入環(huán)境實(shí)驗(yàn)工序的約束條件： 3x1 +2 x2 12。由于37/2 + 23/2 12，故原問題最優(yōu)解不是本例的最優(yōu)解。5靈敏度分析靈敏度分析第二章在實(shí)驗(yàn)工序中參與松馳變量得：3X1+ 2X2 +X6= 12Cj210000CBXBbx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x612320001 j=cj-zj000-1/4-1/205靈敏度分析靈敏度分析第二章Cj210000CBXBbx1x2x3x4x5x60