《運(yùn)籌學(xué)》胡運(yùn)權(quán) 第4版 第二章線(xiàn)性規(guī)劃的對(duì)偶理論及靈敏度分析

1、Operational Research( OR )|線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題|對(duì)偶問(wèn)題的基本性質(zhì)|影子價(jià)格|對(duì)偶單純形法|靈敏度分析|參數(shù)線(xiàn)性規(guī)劃對(duì)偶問(wèn)題概念：任何一個(gè)線(xiàn)性規(guī)劃問(wèn)題都有一個(gè)伴生的線(xiàn)性規(guī)劃問(wèn)題，稱(chēng)為其“對(duì)偶”問(wèn)題。對(duì)偶問(wèn)題是對(duì)原問(wèn)題從另一角度進(jìn)行的描述，其最優(yōu)解與原問(wèn)題的最優(yōu)解有著密切的聯(lián)系，在求得一個(gè)線(xiàn)性規(guī)劃最優(yōu)解的同時(shí)也就得到對(duì)偶線(xiàn)性規(guī)劃的最優(yōu)解，反之亦然。對(duì)偶理論就是研究線(xiàn)性規(guī)劃及其對(duì)偶問(wèn)題的理論，是線(xiàn)性規(guī)劃理論的重要內(nèi)容之一。 項(xiàng)目每天可用能力設(shè)備A（h）0515設(shè)備B（h）6224調(diào)試工序（h）115利潤(rùn)（元）21例2-1我們引用第一章中美佳公司的例子，如表1其線(xiàn)性規(guī)劃問(wèn)題

2、為：122121212max25156224. .5,0zxxxxxstxxx x假定有某個(gè)公司想把美佳公司的資源收買(mǎi)過(guò)來(lái)，它至少應(yīng)付出多大代價(jià)，才能使美佳公司愿意放棄生產(chǎn)活動(dòng)，出讓自己的資源？（LP1）2312362521yyyyy 例2-1條件：出讓代價(jià)應(yīng)不低于用同等數(shù)量資源由自己組織生產(chǎn)活動(dòng)時(shí)獲取的贏利。y1,y2,y3分別代表單位時(shí)間（h）設(shè)備A、設(shè)備B和調(diào)試工序的出讓代價(jià)。 y1,y2,y3的取值應(yīng)滿(mǎn)足：美佳公司用6h設(shè)備B和1h調(diào)試可生產(chǎn)一件家電I,贏利2元用5h設(shè)備A,2h設(shè)備B及1h調(diào)試可生產(chǎn)一件家電，贏利1元該公司希望用最小代價(jià)把美佳公司的全部資源收買(mǎi)過(guò)來(lái)，即：123min1

3、524zyyy123minw1524yyy例2-1綜上所述，2312312362. . 521,0yystyyyy yy（LP2）LP1和LP2兩個(gè)線(xiàn)性規(guī)劃問(wèn)題，通常稱(chēng)LP1為原問(wèn)題，LP2為前者的對(duì)偶問(wèn)題。nnxcxcxcZ2211max0,. .212121212222111211nmnmnmmnnxxxbbbxxxaaaaaaaaatsmmybybybW2211min0,. .212121212221212111mnmmnnnmmyyycccyyyaaaaaaaaats對(duì)稱(chēng)形式的對(duì)偶問(wèn)題對(duì)稱(chēng)形式的對(duì)偶問(wèn)題CXZ maxTTYbW min0. .TTTTYCYAts0. .XbAXts對(duì)偶

4、問(wèn)題的特點(diǎn)若原問(wèn)題目標(biāo)是求極大化，則對(duì)偶問(wèn)題的目標(biāo)是極小化，反之亦然原問(wèn)題的約束系數(shù)矩陣與對(duì)偶問(wèn)題的約束系數(shù)矩陣互為轉(zhuǎn)置矩陣極大化問(wèn)題的每個(gè)約束對(duì)應(yīng)于極小化問(wèn)題的一個(gè)變量，其每個(gè)變量對(duì)應(yīng)于對(duì)偶問(wèn)題的一個(gè)約束。 一般線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題nnxcxcxcZ2211maxmmybybybW2211minnjjmnmnmmnnnnxbxaxaxabxaxaxabxaxaxa1), 0(0),(),(),(22112222212111212111或符號(hào)不限mijnmmnnnmmmmycyayayacyayayacyayaya1),0(0),(),(),(22112222211211221111或符號(hào)不

5、限對(duì)偶問(wèn)題對(duì)應(yīng)表原問(wèn)題（對(duì)偶問(wèn)題） 對(duì)偶問(wèn)題（原問(wèn)題）目標(biāo)函數(shù)maxZ目標(biāo)函數(shù)minZ約束條件： m個(gè)第i個(gè)約束類(lèi)型為“”第i個(gè)約束類(lèi)型為“”第i個(gè)約束類(lèi)型為“” 變量數(shù)： m個(gè)第i個(gè)變量0第i個(gè)變量0第i個(gè)變量是自由變量 變量數(shù)：n個(gè)第j個(gè)變量0第j個(gè)變量0第j個(gè)變量是自由變量 約束條件：n個(gè)第j個(gè)約束類(lèi)型為“”第j個(gè)約束類(lèi)型為“”第j個(gè)約束類(lèi)型為“” |例22 標(biāo)準(zhǔn)型對(duì)偶問(wèn)題 nnxcxcxcZ2211max0,. .2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxat s符號(hào)不限mnmmnnnmmmmyyycyayayacy

6、ayayacyayaya,2122112222211211221111mmybybybW2211min|例23321324minxxxZ 0,32121321321, 01413121110987654xxxxxxxxxxx符號(hào)不限32114117maxyyyW0y0,y,3212132132131062139541284符號(hào)不限yyyyyyyyy|例2-4 寫(xiě)出下列問(wèn)題的對(duì)偶問(wèn)題1 1223311112133221 122223331ax. .00zc xc xc xa xa xa xba xa xa xbsta xa xa xbxxx， 無(wú)約束（2.4a）（2.4

7、b）（2.4c）（2.4d）11223333max zc xc xc xc x11112213313321122223323321122223323331132233333312331223. .0000a xa xa xa xba xa xa xa xbsta xa xa xa xba xa xa xa xbxxxx ，對(duì)偶變量y1 y2 y2 y3先轉(zhuǎn)換成對(duì)稱(chēng)形式，如下：|例2-4令各約束對(duì)應(yīng)的對(duì)偶變量分別為y1、y2、y2、 -y311222233minwb yb yb yb y1112122123131212222223231312322323331312322323331233122

8、3. .0000a ya ya ya yca ya ya ya ycsta ya ya ya yca ya ya ya ycyyyy ，令y2= y2-y2， y3=-y3，原問(wèn)題的對(duì)偶問(wèn)題為112233minwb yb yb y112131122232132333123112321233123. .0y0a ya ya yca ya ya ycsta ya ya ycyy， 無(wú)約束，項(xiàng)目原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）A約束系數(shù)矩陣其約束系數(shù)矩陣的轉(zhuǎn)置b約束條件的右端項(xiàng)向量目標(biāo)函數(shù)中的價(jià)格系數(shù)向量C目標(biāo)函數(shù)中的價(jià)格系數(shù)向量約束條件的右端項(xiàng)向量目標(biāo)函數(shù)max z=CjXjmin w= bi

9、yi(1,., )00jjjjxjnxxx變量無(wú)約束ijijijijijijnja yca yca ycmi=1mi=1mi=1有 個(gè)（ =1，.,n）約束條件nijijnijijnijijmjma xba xba xbi=1i=1i=1有個(gè)（ =1，.,）約束條件y(1,.,)00jjjjjmyyy變量無(wú)約束|線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題|對(duì)偶問(wèn)題的基本性質(zhì)|影子價(jià)格|對(duì)偶單純形法|靈敏度分析|參數(shù)線(xiàn)性規(guī)劃|單純形法計(jì)算的矩陣描述對(duì)稱(chēng)形式線(xiàn)性規(guī)劃矩陣表達(dá)式加上松弛變量Xs后為：max0. .0,0zCXXsAXIXsbstXXs其中松弛變量Xs=（xn+1,xn+2,.,xn+m）,I為mm單位矩陣項(xiàng)

10、目基變量基變量XB XNXs0 Xs bB NIcj-zjCB CN0選取I為初始基，對(duì)應(yīng)基變量為Xs。設(shè)迭代若干步后，基變量為XB，XB在初始單純形表中的系數(shù)矩陣為B。A中去掉B的若干列后剩下的列組成矩陣N。進(jìn)一步迭代,新的單純形表如下：項(xiàng)目基變量非基變量XBXN XsCB XB B-1bIB-1N B-1cj-zj0CN-CBB-1N CBB-1 對(duì)應(yīng)初始單純形表中的單位矩陣I，迭代后的單純形 表中為B-1初始單純形表中基變量Xs=b，迭代后的表中XB=B-1b初始單純形表中約束系數(shù)矩陣為 A,I=B,N,I， 迭代后的表中約束系數(shù)矩陣為 B-1A,B-1I=B-1B,B-1N,B-1I=

11、I,B-1N,B-1若初始矩陣中變量xj的系數(shù)向量為Pj，迭代后為 Pj，則有Pj=B-1Pj當(dāng)B為最優(yōu)基時(shí)，表中應(yīng)有 CN-CBB-1N0,-CBB-10|例2-5參看例2-1中的原問(wèn)題和對(duì)偶問(wèn)題，并分別加上松弛變量和剩余變量，如下：12345max2000zxxxxx231241255156224. .50(1,.,5)jxxxxxstxxxxj12345min1524500wyyyyy234123562. . 5210(1,.,5)iyyystyyyyyi對(duì)偶變量y1y2y3對(duì)偶變量x1x2兩個(gè)問(wèn)題的最終單純形表如下：項(xiàng)目原問(wèn)題變量原問(wèn)題松弛變量x1x2x3x4x5x315/20015/

12、4-15/2x17/21001/4-1/2x23/2010-1/43/2zj-cj0001/41/2變量對(duì)偶問(wèn)題的剩余變量對(duì)偶問(wèn)題變量y4y5y1y2y3項(xiàng)目對(duì)偶問(wèn)題變量對(duì)偶問(wèn)題剩余變量y1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2cj-zj15/2007/23/2變量原問(wèn)題松弛變量原問(wèn)題變量x3x4x5x1x21.弱對(duì)偶性 如果xj（j=1，.，n）是原問(wèn)題的可行解，yi（i=1，.，m）是其對(duì)偶問(wèn)題的可行解，則恒有11jjnmiijic xb y|弱對(duì)偶性的推論：(1) 原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界；反之對(duì)偶問(wèn)題任一

13、可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界。(2) 如原問(wèn)題有可行解且目標(biāo)函數(shù)值無(wú)界(具有無(wú)界解)，則其對(duì)偶問(wèn)題無(wú)可行解；反之對(duì)偶問(wèn)題有可行解且目標(biāo)函數(shù)值無(wú)界，則其原問(wèn)題無(wú)可行解。注意：本點(diǎn)性質(zhì)的逆不成立，當(dāng)對(duì)偶問(wèn)題無(wú)可行解時(shí)，其原問(wèn)題或具有無(wú)界解或無(wú)可行解，反之亦然。(3) 若原問(wèn)題有可行解而其對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題目標(biāo)函數(shù)值無(wú)界；反之對(duì)偶問(wèn)題有可行解而其原問(wèn)題無(wú)可行解，則對(duì)偶問(wèn)題的目標(biāo)函數(shù)值無(wú)界。|最優(yōu)性如果 (j=1,.,n)是原問(wèn)題的可行解，(i=1,.,m)是其對(duì)偶問(wèn)題的可行解，且有j xi ynmjji ij=1i=1cx =by則 (j=1,.,n)是原問(wèn)題的最優(yōu)解， (i

14、=1,.,m)是其對(duì)偶問(wèn)題的最優(yōu)解。j xi y| 強(qiáng)對(duì)偶性(或稱(chēng)對(duì)偶定理) 若原問(wèn)題及其對(duì)偶問(wèn)題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。|互補(bǔ)松弛性 在線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。也即i y若 0，則有 ，即1nij jija xb0six 若 ，即 ，則有1nij jija xb0six 0iy 因此一定有 ， six0iy |線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題|對(duì)偶問(wèn)題的基本性質(zhì)|影子價(jià)格|對(duì)偶單純形法|靈敏度分析|參數(shù)線(xiàn)性規(guī)劃對(duì)偶最優(yōu)解的經(jīng)濟(jì)含義影子價(jià)格 *22

15、*11*mmybybybZ 代表著當(dāng)?shù)趇個(gè)右端常數(shù)增加一個(gè)單位時(shí)，最優(yōu)目標(biāo)函數(shù)值的相應(yīng)增量。 其含義是在目前已給定的情況下，最優(yōu)目標(biāo)值隨資源數(shù)量變化的變化率； 其經(jīng)濟(jì)含義是為約束條件所付出的代價(jià)。 當(dāng)B是原問(wèn)題的最優(yōu)基時(shí)，Y=CBB-1就是影子價(jià)格向量。|資源的市場(chǎng)價(jià)格是其價(jià)值的客觀(guān)體現(xiàn)，相對(duì)比較穩(wěn)定，而它的影子價(jià)格則有賴(lài)于資源的利用情況，是未知數(shù)。因企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價(jià)格也隨之改變。|影子價(jià)格是一種邊際價(jià)格。|資源的影子價(jià)格實(shí)際上又是一種機(jī)會(huì)成本。隨著資源的買(mǎi)進(jìn)賣(mài)出，其影子價(jià)格也將隨之發(fā)生變化，一直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平時(shí)，才處于平衡狀態(tài)。|生產(chǎn)過(guò)程中

16、如果某種資源未得到充分利用時(shí)，該種資源的影子價(jià)格為零；又當(dāng)資源的影子價(jià)格不為零時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完畢。|影子價(jià)格反映單純形表中各個(gè)檢驗(yàn)數(shù)的經(jīng)濟(jì)意義。|一般說(shuō)對(duì)線(xiàn)性規(guī)劃問(wèn)題的求解是確定資源的最優(yōu)分配方案，而對(duì)于對(duì)偶問(wèn)題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)，這種估價(jià)直接涉及資源的最有效利用。ABC擁有量工 時(shí)1113材 料1479單件利潤(rùn)23321)9 , 3(minyyW0332714111. .2121yyyyts y1=5/3, y2=1/3 即工時(shí)的影子價(jià)格為5/3，材料的影子價(jià)格為1/3。如果目前市場(chǎng)上材料的價(jià)格低于1/3，則企業(yè)可以購(gòu)進(jìn)材料來(lái)擴(kuò)大生產(chǎn)，反之可以賣(mài)掉部分材料。 如果

17、有客戶(hù)以高于5/3的價(jià)格購(gòu)買(mǎi)工時(shí)，則可以出售一些工時(shí)，反之則反|線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題|對(duì)偶問(wèn)題的基本性質(zhì)|影子價(jià)格|對(duì)偶單純形法|靈敏度分析|參數(shù)線(xiàn)性規(guī)劃|對(duì)偶單純形法并不是求解對(duì)偶問(wèn)題解的方法，而是利用對(duì)偶理論求解原問(wèn)題的解的方法。|求解單純形法的基本思路： 對(duì)原問(wèn)題的一個(gè)基可行解，判別是否所有檢驗(yàn)數(shù)cj-zj0(j=1,n)。若是，又基變量中無(wú)非零人工變量，即找到了問(wèn)題最優(yōu)解；若為否，再找出相鄰的目標(biāo)函數(shù)值更大的基可行解，并繼續(xù)判別，只要最優(yōu)解存在，就一直循環(huán)進(jìn)行到找出最優(yōu)解為止。對(duì)于標(biāo)準(zhǔn)線(xiàn)性規(guī)劃問(wèn)題：可行基可行基B 若B對(duì)應(yīng)的基本解是可行解最優(yōu)基最優(yōu)基B 若B對(duì)應(yīng)的基本解是最優(yōu)解對(duì)偶可行基

18、對(duì)偶可行基B B 若CBB-1是對(duì)偶問(wèn)題可行解 即 C-CBB-1A0 或 檢驗(yàn)數(shù)0 CXZ maxCYAts. .0. .XbAXtsYbW min對(duì)于標(biāo)準(zhǔn)線(xiàn)性規(guī)劃問(wèn)題：CXZ maxCYAts. .0. .XbAXtsYbW min最優(yōu)基B可行基B 對(duì)偶可行基B單純形法可行基B 保持可行性 對(duì)偶可行基B對(duì)偶單純形法可行基B 保持對(duì)偶可行性 對(duì)偶可行基B對(duì)于標(biāo)準(zhǔn)線(xiàn)性規(guī)劃問(wèn)題：CXZ max0. .XbAXts對(duì)偶單純形法可行基B 保持對(duì)偶可行性 對(duì)偶可行基B 找一個(gè)基，建立初始對(duì)偶單純形表，檢驗(yàn)數(shù)全部非正； 若b列元素非負(fù)，則已經(jīng)是最優(yōu)基。反之，則取相應(yīng)行的基變量為出基變量； 為保證能對(duì)基的

19、可行性有所改進(jìn)，則將來(lái)的主元應(yīng)該為負(fù)數(shù)；為保證下一個(gè)基還能是對(duì)偶可行基，應(yīng)使檢驗(yàn)數(shù)仍為非正的。 主元變換12323123123min1524562. . 521,0wyyyyystyyyy yy例26 用對(duì)偶單純形法求解： 123452341235max152450062. .5210(1,.,5)iwyyyyyyyystyyyyyicj-15-24-500CB基by1y2y3y4y50y4-20-6-1100y5-1-5-2-101cj-zj-15-24-500-24y21/3011/6-1/600y3-1/3-50-2/3-1/31cj-zj-150-1-40-24y21/4-5/410-

20、1/41/4-5y31/215/2011/2-3/2cj-zj-15/200-7/2-3/2|練習(xí)：用對(duì)偶單純形法求解 123123123123min524324. . 63510,0zxxxxxxstxxxx x x|線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題|對(duì)偶問(wèn)題的基本性質(zhì)|影子價(jià)格|對(duì)偶單純形法|靈敏度分析|參數(shù)線(xiàn)性規(guī)劃 在生產(chǎn)計(jì)劃問(wèn)題的一般形式中，A代表企業(yè)的技術(shù)狀況，b代表企業(yè)的資源狀況，而C代表企業(yè)產(chǎn)品的市場(chǎng)狀況，在這些因素不變的情況下企業(yè)的最優(yōu)生產(chǎn)計(jì)劃和最大利潤(rùn)由線(xiàn)性規(guī)劃的最優(yōu)解和最優(yōu)值決定。 在實(shí)際生產(chǎn)過(guò)程中，上述三類(lèi)因素均是在不斷變化的，如果按照初始的狀況制訂了最佳的生產(chǎn)計(jì)劃，而在計(jì)劃實(shí)施前或?qū)?/p>

21、施中上述狀況發(fā)生了改變，則決策者所關(guān)心的是目前所執(zhí)行的計(jì)劃還是不是最優(yōu)，如果不是應(yīng)該如何修訂原來(lái)的最優(yōu)計(jì)劃。更進(jìn)一步，為了防止在各類(lèi)狀況發(fā)生時(shí)，來(lái)不及隨時(shí)對(duì)其變化作出反應(yīng)，即所謂“計(jì)劃不如變化快”，企業(yè)應(yīng)當(dāng)預(yù)先了解，當(dāng)各項(xiàng)因素變化時(shí)，應(yīng)當(dāng)作出什么樣的反應(yīng)。 靈敏度分析的步驟可歸納如下：1.將參數(shù)的改變通過(guò)計(jì)算反映到最終單純形表上來(lái)。2.檢查原問(wèn)題是否仍為可行解。3.檢查對(duì)偶問(wèn)題是否仍為可行解。4.按下表所列情況得出結(jié)論或決定繼續(xù)計(jì)算的步驟。原問(wèn)題對(duì)偶問(wèn)題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解問(wèn)題的最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解非

22、可行解非可行解引進(jìn)人工變量，編制新的單純形表重新計(jì)算 CB XB cjCBCN xj b XBTXNTCBTXBB-1b B-1BB-1N- CB B-1b CB- CB B-1BCN- CB B-1N若B是最優(yōu)基，則最優(yōu)表形式如下靈敏度分析總是在最優(yōu)表上進(jìn)行 當(dāng)系數(shù)A，b，C發(fā)生改變時(shí)，目前最優(yōu)基是否還最優(yōu)？ 為保持目前最優(yōu)基還是最優(yōu)，系數(shù)A，b，C的允許變化范圍是什么？假設(shè)每次只有一種系數(shù)變化目標(biāo)系數(shù)C變化 基變量系數(shù)發(fā)生變化； 非基變量系數(shù)發(fā)生變化；右端常數(shù)b變化增加一個(gè)變量增加一個(gè)約束技術(shù)系數(shù)A發(fā)生變化|分析cj的變化例2-7 在第一章例1的美佳公司例子中：（1）若家電的利潤(rùn)降至1.5

23、元/件，而家電的利潤(rùn)增至2元/件時(shí)，美佳公司最優(yōu)生產(chǎn)計(jì)劃有何變化?cj1.52000CB基bx1x2x3x4x50 x315/20015/4-15/21.5x17/21001/4-1/22x23/2010-1/43/2cj-zj0001/8-9/40 x46004/51-61.5x1210-1/5012x23011/500cj-zj00-1/100-3/2即美佳公司隨家電，的利潤(rùn)變化應(yīng)調(diào)整為生產(chǎn)2件，生產(chǎn)3件。項(xiàng)目21+000CB基bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21+x23/2010-1/43/2cj-zj000-1/4+1/4-1/

24、2-3/2（2）若家電的利潤(rùn)不變，則家電的利潤(rùn)在什么范圍內(nèi)變化時(shí)，該公司的最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生變化？ 設(shè)家電的利潤(rùn)為（1+）元，如下為保證最優(yōu)解， -1/4+1/40， -1/2-3/2 0解得-1/3 1即家電的利潤(rùn)c2的變化范圍應(yīng)滿(mǎn)足2/3 c2 2|分析bi的變化例2-8 在美佳公司的例子中：（1）若設(shè)備A和調(diào)試工序的每天能力不變，而設(shè)備B每天的能力增加到32h，分析公司最優(yōu)計(jì)劃的變化；cj21000CB基bx1x2x3x4x50 x335/20015/4-15/22x111/21001/4-1/21x2-1/2010-1/43/2cj-zj000-1/4-1/20 x315051002

25、x15110010 x420-401-6cj-zj0-100-2080b 115/415/201001/41/28201/43/202bBb 例2-8 （2）設(shè)設(shè)備A和設(shè)備B每天可用能力不變，則調(diào)試工序能力在什么范圍內(nèi)變化時(shí)，問(wèn)題的最優(yōu)基不變。 設(shè)調(diào)試工序每天可用能力為（5+）h，因有115215/415/20101/41/20201/43/232bBb 最終單純形表中b列數(shù)字為15/2 15/27/2 1/23/23/2b因b0時(shí)最優(yōu)基不變，故-11。調(diào)試工序的能力應(yīng)在4h6h之間。|增加一個(gè)變量xj的分析 若企業(yè)在計(jì)劃期內(nèi)，有新的產(chǎn)品可以生產(chǎn)，則在知道新產(chǎn)品的單位利潤(rùn)，單件資源消耗量時(shí)，可

26、以在最優(yōu)表中補(bǔ)充一列，其中的前m行可以由基矩陣的逆矩陣得到，而檢驗(yàn)數(shù)行也可以由與其它列相同的方法計(jì)算得到。若檢驗(yàn)數(shù)非正，則原最優(yōu)解仍為最優(yōu)，原生產(chǎn)計(jì)劃不變，不生產(chǎn)這種新產(chǎn)品；否則，當(dāng)檢驗(yàn)數(shù)為正時(shí)，則應(yīng)以該變量進(jìn)基，作單純形迭代，從而找出新的最優(yōu)解。 |增加一個(gè)變量xj的分析增加一個(gè)變量在實(shí)際問(wèn)題中反映為增加一種新的產(chǎn)品。其分析步驟為：3. 若 j0，原最優(yōu)解不變，只需將計(jì)算得到的Pj和j直接寫(xiě)入最終單純形表中；若j0，則按單純形法繼續(xù)迭代計(jì)算找出最優(yōu)。例2-9 設(shè)美佳公司又計(jì)劃推出新型號(hào)的家電，生產(chǎn)一件所需設(shè)備A、B及調(diào)試工序的時(shí)間分別為3h、4h、2h，該產(chǎn)品的預(yù)期盈利為3元/件，試分析該產(chǎn)

27、品是否值得投產(chǎn)；如投產(chǎn)，對(duì)該公司的最優(yōu)生產(chǎn)計(jì)劃有何影響。 設(shè)生產(chǎn)x6件家電，有c6=3，P6=（3，4，2）T33(1 30,1/4,1/2) 42615/415/23701/41/24001/43/222P cj210003CB基bx1x2x3x4x5x60 x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/22cj-zj000-1/4-1/210 x351/407/213/8-9/402x17/21001/4-1/203x63/401/20-1/83/41cj-zj0-1/20-1/8-5/40最優(yōu)生產(chǎn)計(jì)劃應(yīng)為每天生產(chǎn)7/2件家電，51/

28、4件家電。|分析參數(shù)aij的變化23(3/2 80,1/4,1/2) 41例2-10 在美佳公司的例子中，若家電每件需設(shè)備A,B和調(diào)試工時(shí)變?yōu)?h、4h、1h，該產(chǎn)品的利潤(rùn)變?yōu)?元/件，試重新確定該公司最優(yōu)生產(chǎn)計(jì)劃。設(shè)生產(chǎn)工時(shí)變化后的新家電的生產(chǎn)量為x2，其中：215/415/2811/201/41/241/201/43/211/2P cj23000CB基bx1x2x3x4x50 x315/2011/215/4-15/22x17/211/201/4-1/21x23/201/20-1/43/2cj-zj03/20-1/4-1/20 x3-90014-242x121001/2-23x23010-1

29、/23cj-zj0001/2-5原問(wèn)題和對(duì)偶問(wèn)題均為非可行解上表中第二階段第一行的約束為：x3+4x4-24x5=-9 -x3-4x4+24x5+x6=9替換后重新得表：cj23000-MCB基bx1x2x3x4x5x6-Mx6900-1-42412x121001/2-203x23010-1/230cj-zj00-M1/2-4M-5+24M00 x53/800-1/24-1/611/242x111/410-1/121/601/123x215/8011/800-1/8cj-zj00-5/24-1/30-M+5/24最優(yōu)生產(chǎn)計(jì)劃為每天生產(chǎn)11/4臺(tái)家電，15/8臺(tái)家電|增加一個(gè)約束條件在企業(yè)的生產(chǎn)

30、過(guò)程中，經(jīng)常有一些突發(fā)事件產(chǎn)生，造成原本不緊缺的某種資源變成為緊缺資源，對(duì)生產(chǎn)計(jì)劃造成影響。若把目前的最優(yōu)解代入新增加的約束，能滿(mǎn)足約束條件，則說(shuō)明該增加的約束對(duì)最優(yōu)解不構(gòu)成影響，即不影響最優(yōu)生產(chǎn)計(jì)劃的實(shí)施。若當(dāng)前最優(yōu)解不滿(mǎn)足新增加的約束，則應(yīng)把新的約束添到原問(wèn)題的最優(yōu)表內(nèi)新的一行中去，用對(duì)偶單純形方法來(lái)進(jìn)行迭代，求出新的最優(yōu)解。 |增加一個(gè)約束條件例2-11 設(shè)家電，經(jīng)調(diào)試后，還需經(jīng)過(guò)一道環(huán)境試驗(yàn)工序。家電每件需環(huán)境試驗(yàn)3h，家電每件需2h，又環(huán)境試驗(yàn)工序每天生產(chǎn)能力為12h。試分析增加該工序后的美佳公司最優(yōu)生產(chǎn)計(jì)劃。（1）檢驗(yàn)原問(wèn)題的最優(yōu)解是否仍適用。將x1=7/2，x2=3/2代入3x1

31、+2x212，27/212，所以不適用。（2）加入松弛變量x6，得3x1+2x2+x6=12（3）單純形表求解。cj210000CB基bx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x612320001cj-zj000-1/4-1/200 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x6-3/2000-1/4-3/21cj-zj000-1/4-1/200 x3150015/20-52x141001/30-1/31x20010-1/2010 x510001/61-2/3cj-zj000-1/60-1/3注：表中同，=-3-2。|線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題|對(duì)偶問(wèn)題的基本性質(zhì)|影子價(jià)格|對(duì)偶單純形法|靈敏度分析|參數(shù)線(xiàn)性規(guī)劃當(dāng)目標(biāo)函數(shù)中cj值連續(xù)變化時(shí)，其參數(shù)線(xiàn)性規(guī)劃的形式為：0. .)(max *XbbAXtsCXz當(dāng)約束