運(yùn)籌學(xué)單純形法的靈敏度分析

§5.2單純形法的靈敏度分析

目標(biāo)函數(shù)系數(shù)Cj的改變對(duì)原問題的影響約束條件右側(cè)常數(shù)bi改變對(duì)原問題的影響

約束條件系數(shù)矩陣A發(fā)生變動(dòng)對(duì)原問題的影響

運(yùn)籌學(xué)單純形法的靈敏度分析例：某工廠計(jì)劃生產(chǎn)甲、乙、丙三種產(chǎn)品，這三種產(chǎn)品的單位利潤(rùn)分別為2元、3元、1元，生產(chǎn)單位產(chǎn)品所需要的勞動(dòng)力和材料如下表所列，現(xiàn)工廠計(jì)劃部門列出線性規(guī)劃的模型，以確定最優(yōu)的生產(chǎn)方案。甲乙丙可使用資源勞動(dòng)力材料1/31/31/34/31/37/313利潤(rùn)231運(yùn)籌學(xué)單純形法的靈敏度分析設(shè)計(jì)劃生產(chǎn)三種產(chǎn)品產(chǎn)量分別為x1，x2，x3引入松弛變量x4，x5，得如下單純形表運(yùn)籌學(xué)單純形法的靈敏度分析解到第三段得到最優(yōu)解：x1=1（甲產(chǎn)品生產(chǎn)1單位），x2=2（乙產(chǎn)品生產(chǎn)2單位），x3=0（丙產(chǎn)品不生產(chǎn)），maxZ=8（最大利潤(rùn)達(dá)到8元）段Cj↓→基0b2x13x21x30x40x5Qi100x4x5131/31/31/3（4/3）1/37/3100139/4→Cj-Zj→23100203x4x21/49/4（1/4）1/401-1/47/410-1/43/419→Cj-Zj→5/40-17/40-9/4323x1x2121001-124-1-11Cj-Zj→-800-3-5-1運(yùn)籌學(xué)單純形法的靈敏度分析一、目標(biāo)函數(shù)系數(shù)Cj的改變對(duì)原問題的影響討論：上例中甲、乙、丙三種產(chǎn)品單位利潤(rùn)發(fā)生變化時(shí)對(duì)原問題的影響。思考：數(shù)學(xué)模型中，cj變化將影響數(shù)學(xué)模型中哪些因素？如：丙產(chǎn)品單位利潤(rùn)的變化將影響到模型中哪些因素？

c3=1c3=2或c3=1c3=6再如：甲、乙產(chǎn)品單位利潤(rùn)發(fā)生變化時(shí)，將影響到哪些因素？

c1=2c1=4或c2=3c2=2運(yùn)籌學(xué)單純形法的靈敏度分析結(jié)論在單純形法中，cj的變化→cj-zj變化→基變量的調(diào)出、入。分兩種情況：非基變量的cj發(fā)生變化只影響其本身對(duì)應(yīng)的檢驗(yàn)數(shù)cj-zj；如上例中x3為非基變量，則丙產(chǎn)品單位利潤(rùn)發(fā)生變化只影響本身的檢驗(yàn)數(shù)。基變量的cj發(fā)生變化，由于影響到cB，從而所有非基變量的檢驗(yàn)數(shù)均受到影響（基變量的檢驗(yàn)數(shù)仍保持為0）。如上例中x1、x2為基變量，則甲、乙產(chǎn)品單位利潤(rùn)變化，將影響除甲、乙外其他變量的檢驗(yàn)數(shù)。運(yùn)籌學(xué)單純形法的靈敏度分析（一）非基變量目標(biāo)函數(shù)系數(shù)的改變上例中，x1、x2為基變量，x3為非基變量，它的最優(yōu)解為x3=0，既不安排生產(chǎn)。為什么不生產(chǎn)丙產(chǎn)品呢？因?yàn)閤3所對(duì)應(yīng)的檢驗(yàn)數(shù)Cj-Zj不是絕對(duì)值最大者，無法調(diào)入成為基變量。如果要生產(chǎn)丙產(chǎn)品，意味著x3>0，則必須將x3調(diào)入成為基變量，考察單純形表最后一段，此時(shí)檢驗(yàn)數(shù)Cj-Zj均為非正，如果此時(shí)改變c3，則C3-Z3會(huì)發(fā)生變化，當(dāng)它變成＞0時(shí)，就可以調(diào)入。所以，分析c3-z3的變動(dòng)：運(yùn)籌學(xué)單純形法的靈敏度分析C3變動(dòng)范圍∴當(dāng)C3-Z3＞0即C3＞4時(shí)，調(diào)入成為基變量，則x3>0。也就是說，此時(shí)當(dāng)改變丙產(chǎn)品的單位利潤(rùn)c3到大于4元時(shí)，它的產(chǎn)量就大于零，即需考慮生產(chǎn)丙產(chǎn)品了。運(yùn)籌學(xué)單純形法的靈敏度分析所以，丙產(chǎn)品單位利潤(rùn)的變動(dòng)范圍是c3<4；討論：假設(shè)此時(shí)c3增加到6元，產(chǎn)量應(yīng)為多少？運(yùn)籌學(xué)單純形法的靈敏度分析C3已超出變動(dòng)范圍代入單純形表最后一段繼續(xù)計(jì)算。即當(dāng)丙產(chǎn)品利潤(rùn)增加到6元時(shí)，最優(yōu)解為x1=2，x3=1，x2=0，最優(yōu)值為maxZ=10。段Cj↓→基0b2x13x26x30x40x5Qi123x1x2121001（-1）24-1-11→Cj-Zj→-8002-5-1226x1x321101/21/2017/2-1/2-1/21/2Cj-Zj→-100-10-4-2運(yùn)籌學(xué)單純形法的靈敏度分析（二）基變量目標(biāo)函數(shù)系數(shù)的改變討論：甲產(chǎn)品單位利潤(rùn)的變化對(duì)原問題的影響。單純形法最后一段如下：段Cj↓→基0b2x13x21x30x40x5Qi323x1x2121001-124-1-11Cj-Zj→-800-3-5-1運(yùn)籌學(xué)單純形法的靈敏度分析分析結(jié)果從單純表最后一段可知：x1為基變量，x1>0，意味著生產(chǎn)甲產(chǎn)品。再進(jìn)一步分析，如果C1降到某一程度之后，即利潤(rùn)非常小，從實(shí)際意義上講，是不應(yīng)該安排甲產(chǎn)品生產(chǎn)的。另一方面，當(dāng)甲產(chǎn)品利潤(rùn)增加到很高一個(gè)水平時(shí)，就可以考慮只生產(chǎn)甲產(chǎn)品而不生產(chǎn)其他產(chǎn)品，那么究竟甲產(chǎn)品利潤(rùn)必須變動(dòng)到什么程度才可能發(fā)生以上變化呢？運(yùn)籌學(xué)單純形法的靈敏度分析（二）基變量目標(biāo)函數(shù)系數(shù)的改變∵x1是基變量，基變量的檢驗(yàn)數(shù)C1-Z1=0，而C1變化會(huì)影響到非基變量的檢驗(yàn)數(shù)?！辔覀兛梢苑治鏊蟹腔兞康臋z驗(yàn)數(shù)運(yùn)籌學(xué)單純形法的靈敏度分析C1的變動(dòng)范圍∴C1的變動(dòng)范圍為〔3/4，3〕

也就是說，當(dāng)甲產(chǎn)品利潤(rùn)在3/4到3之間變動(dòng)時(shí)，它不會(huì)影響到基變量，即仍安排生產(chǎn)甲產(chǎn)品和乙產(chǎn)品，不生產(chǎn)丙產(chǎn)品，只是隨著C1的變化，最優(yōu)解即甲、乙產(chǎn)品的產(chǎn)量不會(huì)改變，而總利潤(rùn)會(huì)發(fā)生變動(dòng)，如當(dāng)C1=1時(shí)，最優(yōu)解為x1=1，x2=2，而最優(yōu)值Z=7，若C1變動(dòng)超過以上界限，則需重新計(jì)算。運(yùn)籌學(xué)單純形法的靈敏度分析（三）基變量和非基變量的目標(biāo)函數(shù)系數(shù)同時(shí)發(fā)生變化時(shí)思路：參考以上兩種情況，在單純形表最后一段中，用變化后的新Cj代入計(jì)算檢驗(yàn)數(shù)Cj-Zj，若滿足符號(hào)條件，則最優(yōu)解不變，最優(yōu)值變動(dòng)；若不滿足符號(hào)條件，則用變化后的Cj代入最后一段，繼續(xù)進(jìn)行迭代計(jì)算。運(yùn)籌學(xué)單純形法的靈敏度分析如上例，當(dāng)Cj變?yōu)椋篊2=4，C3=4代入最后一段，得∵Cj-Zj≤0，均滿足符號(hào)條件∴最優(yōu)解不變，x1=1，x2=2最優(yōu)值Z=10段Cj↓→基0b2x14x24x30x40x5Qi124x1x2121001-124-1-11Cj-Zj→-1000-2-4-2運(yùn)籌學(xué)單純形法的靈敏度分析當(dāng)Cj變?yōu)镃2=4，C3=8代入最后一段，得∵Cj-Zj≤0，均滿足符號(hào)條件∴經(jīng)過兩段計(jì)算，得到最優(yōu)解，x1=2，x2=1最優(yōu)值Z=12段Cj↓→基0b2x14x28x30x40x5Qi124x1x2121001-1（2）4-1-11Cj-Zj→-10002-4-2228x1x321101/21/2017/2-1/2-1/21/2→Cj-Zj→-120-10-3-3運(yùn)籌學(xué)單純形法的靈敏度分析二、約束條件右側(cè)常數(shù)bi改變對(duì)原問題的影響

討論：例中資源最高限制量改變時(shí)將影響數(shù)學(xué)模型中的哪些因素？段Cj↓→基0b2x13x21x30x40x5Qi100x4x5131/31/31/3（4/3）1/37/3100139/4→Cj-Zj→023100203x4x21/49/4（1/4）1/401-1/47/410-1/43/419→Cj-Zj→-27/45/40-17/40-9/4323x1x2121001-124-1-11Cj-Zj→-800-3-5-1運(yùn)籌學(xué)單純形法的靈敏度分析Bi變化影響哪些因素？當(dāng)bi變化時(shí)，從單純形法計(jì)算過程可知，它不影響檢驗(yàn)數(shù)，只影響b列本身，也就是說，它不影響基變量但會(huì)改變最優(yōu)解的具體數(shù)值，如上例中，假設(shè)b1發(fā)生變化，勞動(dòng)力使用從一個(gè)勞動(dòng)力增加到2個(gè)勞動(dòng)力，即b1=2，則∵b變化不影響檢驗(yàn)數(shù)∴單純形表最后一段基變量結(jié)構(gòu)不變，仍是x1，x2，改變的是x1，x2的數(shù)值用公式表示如下：運(yùn)籌學(xué)單純形法的靈敏度分析運(yùn)籌學(xué)單純形法的靈敏度分析分析從以上計(jì)算結(jié)果表明，增加一個(gè)單位b1（勞動(dòng)力數(shù)量）會(huì)使總利潤(rùn)增加，但在實(shí)際經(jīng)濟(jì)工作中，b1增加不可能是無限的，因?yàn)閯趧?dòng)力增加太多，而其他條件不變時(shí)，勢(shì)必造成勞動(dòng)力過剩，影響生產(chǎn)率，進(jìn)而影響利潤(rùn)率，即Cj會(huì)變化，因此，b1的變化也是有范圍的。從數(shù)學(xué)模型上思考：b取值的制約條件？運(yùn)籌學(xué)單純形法的靈敏度分析bi變動(dòng)的制約條件當(dāng)我們用單純形法解線性規(guī)劃問題時(shí)，要求b≥0∴b的變化必須首先滿足這個(gè)條件用公式表示如下：運(yùn)籌學(xué)單純形法的靈敏度分析設(shè)基變量不變（意味著生產(chǎn)產(chǎn)品結(jié)構(gòu)不變），即B=(P1P2)保持不變，則∴b1變動(dòng)的范圍是〔3/4，3〕也就是說，b1在3/4∽3之間變動(dòng)時(shí)，基變量結(jié)構(gòu)不變（仍是生產(chǎn)甲、乙兩種產(chǎn)品，不生產(chǎn)丙產(chǎn)品），但變量值發(fā)生變動(dòng)（產(chǎn)量變化），最優(yōu)值也會(huì)變動(dòng)（總利潤(rùn)變化），即運(yùn)籌學(xué)單純形法的靈敏度分析運(yùn)籌學(xué)單純形法的靈敏度分析分析例中第二個(gè)資源——材料的最高限制變化時(shí)對(duì)原問題的影響。即討論：b2變動(dòng)的范圍。運(yùn)籌學(xué)單純形法的靈敏度分析B2變動(dòng)的范圍B2的變動(dòng)范圍是[14]運(yùn)籌學(xué)單純形法的靈敏度分析影子價(jià)格的概念“影子價(jià)格”是經(jīng)濟(jì)領(lǐng)域的概念?！坝白觾r(jià)格”是指當(dāng)其他原料數(shù)量都保持不變時(shí)，第k種原料由bk增加一個(gè)單位時(shí)，由此而產(chǎn)生的目標(biāo)函數(shù)值的增加，它對(duì)應(yīng)于單純形表最后一段松弛變量所對(duì)應(yīng)的檢驗(yàn)數(shù)（取正值）。運(yùn)籌學(xué)單純形法的靈敏度分析如例中，b1表示勞動(dòng)力資源①當(dāng)b1變動(dòng)時(shí)運(yùn)籌學(xué)單純形法的靈敏度分析從以上計(jì)算結(jié)果表明b1的影子價(jià)格即松弛變量x4的檢驗(yàn)數(shù)的相反數(shù)

Z4-C4=5，說明每增加一個(gè)單位的勞動(dòng)力會(huì)使得目標(biāo)函數(shù)值Z增加5個(gè)單位。運(yùn)籌學(xué)單純形法的靈敏度分析b2表示材料資源②當(dāng)b2變動(dòng)時(shí)運(yùn)籌學(xué)單純形法的靈敏度分析計(jì)算結(jié)果表明b2的影子價(jià)格即松弛變量x5的檢驗(yàn)數(shù)的相反數(shù)

Z5-C5=1，說明每增加一個(gè)單位的材料會(huì)使得目標(biāo)函數(shù)值Z增加1個(gè)單位。運(yùn)籌學(xué)單純形法的靈敏度分析影子價(jià)格的經(jīng)濟(jì)意義當(dāng)影子價(jià)格Zj-Cj=0時(shí)，表明當(dāng)各種產(chǎn)品的數(shù)量按照最優(yōu)決策，分別生產(chǎn)數(shù)量x1，x2，…，xn并達(dá)到最大收益時(shí)，第j種原料尚有剩余，如果單獨(dú)增加第j種原料的數(shù)量不會(huì)使總收益增加，故影子價(jià)格Zj-Cj=0。當(dāng)影子價(jià)格Zj-Cj>0時(shí)，表明第j種原料已經(jīng)在達(dá)到最大收益時(shí)全部耗盡，生產(chǎn)組織者如果要擴(kuò)大生產(chǎn)增加收益，必須增加第j種原料的購買量，如果市場(chǎng)上該種原料的市場(chǎng)價(jià)格小于或等于Zj-Cj時(shí)，則用增加第j種原料來增加收益是合算的；反之，若市場(chǎng)價(jià)格大于影子價(jià)格時(shí)，那么用增加第j種原料來增加收益的辦法是不利的.所以影子價(jià)格能為企業(yè)或部門提供今后“活動(dòng)”的一種經(jīng)濟(jì)信息。運(yùn)籌學(xué)單純形法的靈敏度分析三、約束條件系數(shù)矩陣A發(fā)生變動(dòng)對(duì)原問題的影響增加新的產(chǎn)品生產(chǎn)，使A矩陣多一列aj現(xiàn)行的產(chǎn)品生產(chǎn)資源消耗量發(fā)生改變，即aij變化時(shí)增加新的約束條件，即增加新的一行ai運(yùn)籌學(xué)單純形法的靈敏度分析（一）增加新的產(chǎn)品生產(chǎn)，使A矩陣多一列aj設(shè)該廠研究出新的產(chǎn)品丁，每生產(chǎn)一單位產(chǎn)品丁，需要一個(gè)勞動(dòng)力和一單位原料，單位利潤(rùn)為3單位，丁產(chǎn)品銷路良好，現(xiàn)在想知道，在原有資源不變的情況下，安排丁生產(chǎn)是否有利。結(jié)合數(shù)學(xué)模型分析：運(yùn)籌學(xué)單純形法的靈敏度分析分析要判斷是否安排丁生產(chǎn)，就看丁所對(duì)應(yīng)的檢驗(yàn)數(shù)Cj-Zj是否滿足符號(hào)條件，若滿足符號(hào)條件，說明原問題最優(yōu)解不變，丁變量不會(huì)成為基變量，解仍為零，即不應(yīng)安排丁產(chǎn)品的生產(chǎn)；相反的，若Cj-Zj不滿足符號(hào)條件，則丁變量就有可能被調(diào)入成為基變量，即應(yīng)考慮生產(chǎn)丁。如例中，原問題變?yōu)椋海ǘ嘁粋€(gè)變量x6）運(yùn)籌學(xué)單純形法的靈敏度分析多一個(gè)變量x6，使A矩陣多了一列若加入最后一段計(jì)算，不能直接用p6，而應(yīng)將p6線性變化后帶入運(yùn)籌學(xué)單純形法的靈敏度分析根據(jù)單純形表最后一段有關(guān)數(shù)據(jù)，得

段Cj↓→基0b2x13x21x30x40x5Qi323x1x2121001-124-1-11Cj-Zj→-800-3-5-1運(yùn)籌學(xué)單純形法的靈敏度分析

分析檢驗(yàn)數(shù)符號(hào)∵C6-Z6滿足符號(hào)條件∴原問題最優(yōu)解不變，仍是x1=1，x2=2，x3=x6=0

即不安排丁產(chǎn)品生產(chǎn)。注意區(qū)別和的不同運(yùn)籌學(xué)單純形法的靈敏度分析若將以上丁產(chǎn)品利潤(rùn)改為

C6=7，

其他條件不變，

情況會(huì)有什么變化？運(yùn)籌學(xué)單純形法的靈敏度分析分析檢驗(yàn)數(shù)符號(hào)∵C6-Z6不滿足符號(hào)條件∴原問題最優(yōu)解將變動(dòng)，將C6代入單純形表最后一段重新計(jì)算。注意：運(yùn)籌學(xué)單純形法的靈敏度分析對(duì)p6進(jìn)行線性變化段Cj↓→基0b2x13x21x30x40x57x6123x1x2121001-124-1-11(3)0Cj-Zj→-800-3-5-11273x6x31/321/3001-1/324/3-1-1/3110Cj-Zj→-25/3-1/30-8/3-19/3-2/30運(yùn)籌學(xué)單純形法的靈敏度分析此時(shí)得到最優(yōu)解，x1=0，x2=2，x3=x4=x5=0x6=1/3，最優(yōu)值Z=25/3。說明由于丁產(chǎn)品利潤(rùn)的增加，應(yīng)考慮生產(chǎn)丁產(chǎn)品。運(yùn)籌學(xué)單純形法的靈敏度分析（二）現(xiàn)行的產(chǎn)品生產(chǎn)資源消耗量發(fā)生改變，即aij變化時(shí)1、當(dāng)非基變量的aij變化時(shí)，如上例，丙產(chǎn)品的技術(shù)條件發(fā)生變化，單位丙產(chǎn)品所需的勞動(dòng)力數(shù)量不變：a13=1/3，所需的材料數(shù)量減少為a23=5/3

即：運(yùn)籌學(xué)單純形法的靈敏度分析分析方法非基變量的aij的變化只影響本列的數(shù)值，只影響本列的檢驗(yàn)數(shù)。所以與增添新產(chǎn)品的情況相同，只要重新計(jì)算發(fā)生變化的aij對(duì)應(yīng)的Cj-Zj，根據(jù)Cj-Zj的符號(hào)判斷最優(yōu)解有否改變。如例中，丙產(chǎn)品的技術(shù)條件發(fā)生變化，單位丙產(chǎn)品所需的勞動(dòng)力數(shù)量不變：a13=1/3，所需的材料數(shù)量減少為a23=5/3運(yùn)籌學(xué)單純形法的靈敏度分析計(jì)算檢驗(yàn)數(shù)∵C3-Z3滿足符號(hào)條件∴原問題最優(yōu)解不變，最優(yōu)值也不變。運(yùn)籌學(xué)單純形法的靈敏度分析2、當(dāng)基變量對(duì)應(yīng)的aij變化時(shí)當(dāng)基變量對(duì)應(yīng)的aij變化時(shí)，由于此時(shí)基矩陣CB受到影響，進(jìn)而影響所有檢驗(yàn)數(shù)，即：所以，應(yīng)對(duì)規(guī)劃問題重新計(jì)算。運(yùn)籌學(xué)單純形法的靈敏度分析如上例，甲產(chǎn)品、乙產(chǎn)品的技術(shù)條件發(fā)生變化時(shí)，即a11、a21、a12、a22變化時(shí)將影響到則應(yīng)重新計(jì)算。運(yùn)籌學(xué)單純形法的靈敏度分析（三）增加新的約束條件，

即增加新的一行ai如上例，若增加一個(gè)約束條件分析：最優(yōu)解是否要改變？運(yùn)籌學(xué)單純形法的靈敏度分析對(duì)比數(shù)學(xué)模型運(yùn)籌學(xué)單純形法的靈敏度分析分析將最優(yōu)解帶入新加入的約束條件中，看看是否滿足若滿足新的約束條件，最優(yōu)解不變；若不滿足新的約束條件，則應(yīng)加入新的約束條件于單純形表最后一段，標(biāo)準(zhǔn)化后，繼續(xù)進(jìn)行迭代計(jì)算直至求出最優(yōu)解或判斷無解。運(yùn)籌學(xué)單純形法的靈敏度分析將最優(yōu)解x1=1，x2=2代入上式，得

左邊=1+2*2+0=5，右邊=4顯然不滿足約束條件，則應(yīng)重新計(jì)算最優(yōu)解。運(yùn)籌學(xué)單純形法的靈敏度分析分析加入松弛變量x6，得將標(biāo)準(zhǔn)化后的式子代入單純形表最后一段運(yùn)籌學(xué)單純形法的靈敏度分析分析思考：以上單純形表可否直接計(jì)算？段Cj↓→基0b2x13x21x30x40x50x6Qi3230x1x2x6124101012-1214-10-110001Cj-Zj→-800-3-5-1運(yùn)籌學(xué)單純形法的靈敏度分析應(yīng)進(jìn)行線性變換段Cj↓→基0b2x13x21x30x40x50x6Qi3230x1x2x