常見(jiàn)的運(yùn)籌學(xué)靈敏分析

常見(jiàn)的運(yùn)籌學(xué)靈敏度分析現(xiàn)在是1頁(yè)\一共有32頁(yè)\編輯于星期日2靈敏度分析或maxz=cx現(xiàn)在是2頁(yè)\一共有32頁(yè)\編輯于星期日3靈敏度分析（2）面對(duì)市場(chǎng)變化，靈敏度分析的任務(wù)是須解決以下兩類問(wèn)題一、當(dāng)系數(shù)A、b、C中的某個(gè)發(fā)生變化時(shí),目前的最優(yōu)基是否仍最優(yōu)（即目前的最優(yōu)生產(chǎn)方案是否要變化）?(稱為模型參數(shù)的靈敏度分析)二、增加一個(gè)變量或增加一個(gè)約束條件時(shí)，目前的最優(yōu)基是否仍最優(yōu)（即目前的最優(yōu)生產(chǎn)方案是否要變化）(稱為模型結(jié)構(gòu)的靈敏度分析)

靈敏度分析的方法是在目前最優(yōu)基B下進(jìn)行的。即當(dāng)參數(shù)A、b、c中的某一個(gè)或幾個(gè)發(fā)生變化時(shí)，考察是否影響以下兩式的成立？

現(xiàn)在是3頁(yè)\一共有32頁(yè)\編輯于星期日41、對(duì)于參數(shù)b的靈敏度分析從矩陣形式的單純形表中可以看出，b的變化只影響最優(yōu)解的變化和最優(yōu)值的變化。bXXBB-1bB-1AZCBB-1bCBB-1A-C因此，當(dāng)時(shí)，最優(yōu)基不變（即生產(chǎn)產(chǎn)品的品種不變，但數(shù)量及最優(yōu)值會(huì)變化）。是一個(gè)不等式組，從中可以解得b的變化范圍若B-1b中有小于0的分量，則需用對(duì)偶單純形法迭代，以求出新的最優(yōu)方案。b變化的時(shí)候，僅對(duì)B-1b有影響此時(shí)，基變量不變因?yàn)榛兞恐恍枰鄳?yīng)的B可逆就可以了僅關(guān)心B-1b>=0?若新的B-1b不滿足>=0，可以由對(duì)偶單純性算法調(diào)整可行性可能（因?yàn)榛A(chǔ)解已經(jīng)得到，為B-1b）保證當(dāng)前最優(yōu)基變化后仍未最優(yōu)基現(xiàn)在是4頁(yè)\一共有32頁(yè)\編輯于星期日5P33例題16對(duì)于生產(chǎn)計(jì)劃問(wèn)題，為使最優(yōu)方案不變，試討論第二個(gè)約束條件b2的變化范圍。cj4300CBXBbx1x2x3x4

34x2x146013/5-2/510-2/53/5Z36001/56/5解：生產(chǎn)計(jì)劃問(wèn)題的數(shù)學(xué)模型和最優(yōu)單純形表為：現(xiàn)在是5頁(yè)\一共有32頁(yè)\編輯于星期日6

從矩陣形式的單純形表中可知，b2的變化只影響解的可行性B-1b≥0,因此，為使最優(yōu)解不變，只需變化以后的B-1b≥0即可。由解得：當(dāng)數(shù)據(jù)量十分大的時(shí)候，十分麻煩寫為B-1（24,26）+B-1b現(xiàn)在是6頁(yè)\一共有32頁(yè)\編輯于星期日7若b2變化超過(guò)范圍，則需用對(duì)偶單純形法進(jìn)行求解。如b2=6，則cj4300CBXBbx1x2x3x4

34x2x112-6013/5-2/510-2/53/5Z12001/56/5將上述數(shù)字替換最優(yōu)單純形表中相應(yīng)位置的數(shù)據(jù)得：現(xiàn)在是7頁(yè)\一共有32頁(yè)\編輯于星期日8cj4300CBXBbx1x2x3x4

30x2x33153/2101/2-5/201-3/2Z91/2003/2用對(duì)偶單純形法迭代，求出的最優(yōu)單純形表如下：得到新的最優(yōu)解為：x1=0,x2=3;maxz=9現(xiàn)在是8頁(yè)\一共有32頁(yè)\編輯于星期日92.對(duì)價(jià)值系數(shù)Cj變化的分析（1）當(dāng)CN（非基變量的目標(biāo)函數(shù)系數(shù)）中某個(gè)Cj發(fā)生變化時(shí)，只影響到非基變量xj的檢驗(yàn)數(shù)由于所以,當(dāng)即當(dāng)時(shí),最優(yōu)解不變（最小值）反之,當(dāng)時(shí),最優(yōu)解改變,需要用單純形法重新進(jìn)行迭代,以求得新的最優(yōu)解.現(xiàn)在是9頁(yè)\一共有32頁(yè)\編輯于星期日10例題17對(duì)于下列線性規(guī)劃模型,為使最優(yōu)解不變，討論非基變量y1的目標(biāo)函數(shù)系數(shù)c3的變化范圍。用單純形法求得其最優(yōu)表為：cj43200CBXBbx1x2

y1x3x4

34x2x14601-1/53/5-2/5104/5-2/53/5Z36003/51/56/5現(xiàn)在是10頁(yè)\一共有32頁(yè)\編輯于星期日11解：因?yàn)閥1為非基變量，其目標(biāo)函數(shù)系數(shù)c3的變化只會(huì)影響到y(tǒng)1的檢驗(yàn)數(shù)，因此為使最優(yōu)解不變，只需即若C3=3,則代入最優(yōu)單純形表中相應(yīng)位置繼續(xù)迭代以求出新的最優(yōu)解。cj43200CBXBbx1x2y1x3x4

34x2x14601-1/53/5-2/5104/5-2/53/5Z3600-2/51/56/5現(xiàn)在是11頁(yè)\一共有32頁(yè)\編輯于星期日12（2）當(dāng)CB(即基變量的目標(biāo)函數(shù)系數(shù))中某個(gè)Cj發(fā)生變化時(shí)則會(huì)影響到所有變量的檢驗(yàn)數(shù)σ=CBB-1A－C解不等式組例18設(shè)基變量x1的系數(shù)C1變化為，在最優(yōu)性不變的條件下，試確定的范圍解：現(xiàn)在是12頁(yè)\一共有32頁(yè)\編輯于星期日13將上述數(shù)字替換單純形表中相應(yīng)位置的數(shù)字得：cj4300CBXBbx1x2x3x4

35x2x146013/5-2/510-2/53/5Z4200-1/58/5現(xiàn)在是13頁(yè)\一共有32頁(yè)\編輯于星期日14用單純形法迭代得最優(yōu)解表如下：cj4300CBXBbx1x2x3x4

05x3x120/326/305/31-2/312/301/3Z130/301/3016/15（3）技術(shù)系數(shù)aij變化的分析

第一種情況（當(dāng)jJN）：即aij為非基變量xj的技術(shù)系數(shù)時(shí)，它的變化只影響xj的系數(shù)列B-1Pj和檢驗(yàn)數(shù)，為使最優(yōu)方案不變，只需

現(xiàn)在是14頁(yè)\一共有32頁(yè)\編輯于星期日15cj43200CBXBbx1x2

y1x3x4

34x2x14601-1/53/5-2/5104/5-2/53/5Z36003/51/56/5例18對(duì)于下列規(guī)劃問(wèn)題的最優(yōu)解，若由于工藝改進(jìn)，y1的技術(shù)系數(shù)改為p3=(1,1)T，試討論最優(yōu)解的變化。解：最優(yōu)解改變。此時(shí)其系數(shù)列改為：現(xiàn)在是15頁(yè)\一共有32頁(yè)\編輯于星期日16

第二種情況（當(dāng)jJB）：由于B中元素的改變影響到B-1的變化，因此也影響到整個(gè)單純形表T(B)的變化。目前的基B對(duì)應(yīng)的解有可能既不是原始可行，也不是對(duì)偶可行。于是不如重新求解將上述數(shù)據(jù)替換最優(yōu)表中相應(yīng)位置的數(shù)據(jù)，然后再用單純形法求得新的最優(yōu)解。cj43200CBXBbx1x2

y1x3x4

34x2x146011/53/5-2/5101/5-2/53/5Z3600-3/51/56/5現(xiàn)在是16頁(yè)\一共有32頁(yè)\編輯于星期日17（4）對(duì)增加新產(chǎn)品的分析設(shè)某企業(yè)在計(jì)劃期內(nèi)，擬議生產(chǎn)新產(chǎn)品Xn+1，并已知新產(chǎn)品的單位利潤(rùn)為Cn+1，消耗系數(shù)向量為Pn+1=(a1,n+1,a2,n+1,…am,n+1)T，此時(shí)應(yīng)如何分析才能確定該新產(chǎn)品是否值得投產(chǎn)？增加新產(chǎn)品應(yīng)在不影響企業(yè)目前計(jì)劃期內(nèi)最優(yōu)生產(chǎn)的前提下進(jìn)行。因此可從現(xiàn)行的最優(yōu)基B出發(fā)考慮：若σn+1=CBB-1Pn+1－Cn+1<0，則應(yīng)投產(chǎn)若σn+1=CBB-1Pn+1－Cn+1>0，則不應(yīng)投入。

即新產(chǎn)品的機(jī)會(huì)成本小于目前的市場(chǎng)價(jià)格時(shí)，應(yīng)投產(chǎn)否則不應(yīng)投產(chǎn)。例19現(xiàn)有一新產(chǎn)品丙，經(jīng)預(yù)測(cè)其單位利潤(rùn)為3，技術(shù)消耗系數(shù)為P5=（2，2）T，問(wèn)該產(chǎn)品是否值得投產(chǎn)？現(xiàn)在是17頁(yè)\一共有32頁(yè)\編輯于星期日18解：值得投產(chǎn)。cj43003CBXBbx1x2x3x4

y5

34x2x146013/5-2/52/510-2/53/52/5Z36001/56/5-1/5將此變量加入最優(yōu)單純形表中得：其系數(shù)列為：現(xiàn)在是18頁(yè)\一共有32頁(yè)\編輯于星期日19

在企業(yè)生產(chǎn)過(guò)程中，經(jīng)常有新情況發(fā)生，造成原本不緊缺的某種資源變成為緊缺資源，對(duì)生產(chǎn)計(jì)劃造成影響，如水、電和資源的供應(yīng)不足等，對(duì)生產(chǎn)過(guò)程提出了新約束等。對(duì)增加新約束條件的分析方法步驟是：（5）對(duì)增加新約束條件的分析cj43003CBXBbx1x2x3x4y5

34y5x110205/23/2-111-1-110Z3801/21/210用單純形法迭代求得最優(yōu)解為：現(xiàn)在是19頁(yè)\一共有32頁(yè)\編輯于星期日20

第一步：將目前的最優(yōu)解代入新增加的約束，若能滿足約束條件，則說(shuō)明新增約束對(duì)目前的最優(yōu)解（即最優(yōu)生產(chǎn)方案）不構(gòu)成影響（稱此約束為不起作用約束），可暫時(shí)不考慮新增約束條件。否則轉(zhuǎn)下一步；第二步：把新增約束添加到原問(wèn)題最終表中，并作初等行變換，構(gòu)成對(duì)偶可行的單純形表，并用對(duì)偶單純形法迭代，求出新的最優(yōu)解。例19對(duì)于生產(chǎn)計(jì)劃問(wèn)題，設(shè)增加電力約束，生產(chǎn)1單位甲產(chǎn)品需耗電3個(gè)單位，生產(chǎn)1單位乙產(chǎn)品需耗電4個(gè)單位，且每天供電量不超過(guò)30單位。試分析此時(shí)最優(yōu)解的變化情況?，F(xiàn)在是20頁(yè)\一共有32頁(yè)\編輯于星期日21

解：將最優(yōu)解x1=6,x2=4代入約束條件，不滿足，說(shuō)明約束條件起作用。將約束條件加入松馳變量，化為等式，加入最優(yōu)單純形表中。cj43000

CBXBbx1x2x3x4

x5340x2x1x54630013/5-2/50102/53/50

3

4

0

0

1Z36001/56/50在這個(gè)表中，由于x1,x2是基變量，必須為單位向量，因此將x1,x2化為單位向量得現(xiàn)在是21頁(yè)\一共有32頁(yè)\編輯于星期日22cj43000CBXBbx1x2x3x4x5340x2x1x546-4013/5-2/50102/53/5000-6/5-1/51Z36001/56/50再用對(duì)偶單純形法求得新的最優(yōu)表如下：cj43000CBXBbx1x2x3x4x5340x2x1x3222/310/3010-1/21/21002/3-1/30011/6-5/6Z106/30006/71/6現(xiàn)在是22頁(yè)\一共有32頁(yè)\編輯于星期日23對(duì)于增加新產(chǎn)品和新約束的靈敏度分析，在計(jì)算機(jī)軟件中是用ModifyProgram來(lái)完成的1、增加新產(chǎn)品的靈敏度分析Finaltableau(Totaliteration=3)BasisC(j)X1X2X3S1S2B(i)B(i)4.0003.0003.00000A(i,j)X3X13.0004.00001.0002.500-1.0001.00001.500-1.000-1.0001.00010.0002.00000C(j)-Z(j)*BigM00-0.5000000-0.50000-1.000038.0000現(xiàn)在是23頁(yè)\一共有32頁(yè)\編輯于星期日242、增加新約束的靈敏度分析Finaltableau(Totaliteration=3)BasisC(j)X1X2S1S2S3B(i)B(i)4.0003.000000A(i,j)S1X1X203.0004.00001.0000001.0001.000000.1670.667-0.500-0.833-0.3330.5003.3337.3332.00000C(j)-Z(j)*BigM000000-1.1700-0.167035.3330現(xiàn)在是24頁(yè)\一共有32頁(yè)\編輯于星期日25練習(xí)1：一家企業(yè)制造三種產(chǎn)品，需三種資源，技術(shù)服務(wù)、勞力、行政管理，下表列出了三種產(chǎn)品每單位數(shù)量對(duì)每種資源的需要量產(chǎn)品ABC資源限量技術(shù)服務(wù)111100勞力1045600行政管理226300單位利潤(rùn)1064（1）問(wèn)如何安排生產(chǎn)，可使利潤(rùn)最大？（2）C產(chǎn)品的單位利潤(rùn)為多少時(shí)才值得生產(chǎn)？（3）若勞力資源增加到800小時(shí)，問(wèn)最優(yōu)計(jì)劃是否要改變，若要改變，應(yīng)如何改變？（4）制造部門提出要生產(chǎn)一種產(chǎn)品，需要技術(shù)服務(wù)1小時(shí)、勞力4小時(shí)、行政管理3小時(shí)，問(wèn)其單位利潤(rùn)為多少方可否投產(chǎn)？（5）若有一種原材料，如今受到限制，限制條件為，問(wèn)最優(yōu)計(jì)劃是否受到影響？現(xiàn)在是25頁(yè)\一共有32頁(yè)\編輯于星期日26cj1064000CBXBbx1x2x3x4x5x66100x2x1x6200/3100/3100015/65/3-1/60101/6-2/31/60004-201Z2200/3008/310/32/30解：（1）用單純形法求得最優(yōu)表為（2）（3）最優(yōu)基不變現(xiàn)在是26頁(yè)\一共有32頁(yè)\編輯于星期日27（4）設(shè)新產(chǎn)品為x7值得投產(chǎn)。（5）將x1=100/3,x2=200/3,x3=0代入約束條件左邊得因此，最優(yōu)計(jì)劃不變。現(xiàn)在是27頁(yè)\一共有32頁(yè)\編輯于星期日28練習(xí)2、某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，需消耗A、B、C三種資源，產(chǎn)品的單位利潤(rùn)和單位消耗如下表所示：

產(chǎn)品單位產(chǎn)品消耗資源甲乙丙資源限量A31330B22140C13450產(chǎn)品單位利潤(rùn)436（1）該企業(yè)如何安排生產(chǎn)，才能獲得最大利潤(rùn)？（2）產(chǎn)品甲、的單位利潤(rùn)在多大范圍內(nèi)變化，可保持最優(yōu)基解不變？（3）寫出資源A、B的影子價(jià)格，并解釋其經(jīng)濟(jì)意義。若資源B、C的限量不變，資源A不夠可從市場(chǎng)購(gòu)買，價(jià)格1元/單位，問(wèn)是否要購(gòu)進(jìn)A資源擴(kuò)大生產(chǎn)？現(xiàn)在是28頁(yè)\一共有32頁(yè)\編輯于星期日29（4）若現(xiàn)有一新產(chǎn)品丁，據(jù)市場(chǎng)預(yù)測(cè)，丁的單位價(jià)格5元/單位，對(duì)A、B、C三種資源的單位消耗量為2，1，5，問(wèn)是否值得生產(chǎn)？其最優(yōu)單純形表如下：cj436000CBXBbx1x2x3x4x5x6600x3x5x282068/5013/50-1/540011-1-9/510-4/503/5Z661/5006/503/5練習(xí)3、已知某線性規(guī)劃的最終單純形表如下：其中X1，X2，X3表示生產(chǎn)的三種產(chǎn)品。現(xiàn)在是29頁(yè)\一共有32頁(yè)\編輯于星期日30cj31500CBX