十章線性規(guī)劃的靈敏度分析

1、第十五章線性規(guī)劃的靈敏度分析15.1邊際值（影子價(jià)格）q以（max,©為例，邊際值（影子價(jià)格其實(shí)指在最優(yōu)解的基礎(chǔ)上，當(dāng)?shù)趇個(gè)約束行的右端項(xiàng)bi減少一個(gè)單位時(shí)，目標(biāo)函數(shù)的變化量mf（x）=CbB*（CbBj）ibi4q=£f（x）/=（CBB）i,偏導(dǎo)數(shù)，機(jī)會成本Zn+=CbBPe=（CbB）i因此"Zn1L松弛變量，人工變量nTrqi=L-Zn+剩余變量mm機(jī)會成本的另外表達(dá)形式Zj=CBBPj（CBB）*日='qiaij舊i=4例15.1.1maxf（x）=x45x23x34x4'2x1+3x2+x3+2x4<8005x1+4x2+3x3+

2、4x4<1200其最優(yōu)單純表形式如下：st3x14x25x33x4"000xi,x2,x3,x40表15.1.1xix2x3x4x5x6*CBXBb15340000x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251Z-Cj3.2502.75000.251關(guān)丁影子價(jià)的一些說明影子價(jià)是資源最優(yōu)配置下資源的理想價(jià)格，資源的影子價(jià)與資源的緊缺度有關(guān)松弛變量增加一個(gè)單位等丁資源減少一個(gè)單位剩余變量增加一個(gè)單位等丁資源增加一個(gè)單位資源有剩余，在最優(yōu)解中就有對應(yīng)松弛變量存在，且其影子價(jià)為

3、0影子價(jià)為0,資源并不一定有剩余15.2價(jià)值系數(shù)Cj的靈敏度分析cj變動可能由丁市場價(jià)格的波動，或生產(chǎn)成本的變動q的靈敏度分析是在保證最優(yōu)解的基變量不變的情況下，分析cj允許的變動范圍gQ的變化會引起檢驗(yàn)數(shù)的變化，有兩種情況：非基變量對應(yīng)的價(jià)值系數(shù)變化，不影響其它檢驗(yàn)數(shù)基變量對應(yīng)的價(jià)值系數(shù)變化，影響所有非基變量檢驗(yàn)數(shù)15.2.1非基變量對應(yīng)的價(jià)值系數(shù)的靈敏度分析要保持-(g+Aq)芝0故有*<cj<zj-cj例15.2.1maxf(x)=x15x23x34x4'2x1+3x2+x3+2x48005x1+4x2+3x3+4x4<1200st<3x14x25x33x

4、4_1000為法2法3法4一0表15.2.1CbXbbx11x25x33x44x50x60X700x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251Zj-Cj3.2502.75000.251表15.2.2x1x2x3x4x5x6x7CbXbb15340000x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251Zj-Cj3.2502.75000.251X，x3為非基變量，所以要保持Zj-(

5、Cj+ACj)芝0故有-00CCj<Zj-Cj15.2.2基變量對應(yīng)的價(jià)值系數(shù)的靈敏度分析由丁基變量對應(yīng)的價(jià)值系數(shù)Cj在Cb中出現(xiàn)，因此它會影響所有非基變量的檢驗(yàn)數(shù)。只有一個(gè)基變量的cj發(fā)生變化，變化量為Agkk即Cj在Cb中的k分量，研究非基變量xj機(jī)會成本的變化：kmmZj"Zj=L(CjkfCjki)aj=七Cjk%."Cjkakj(=Zj"Zj)i注izi要滿足（zj+AzDCj芝0,貝U有czakcjkW-4-二akjakj：0、-一，.CjZjI1n.一._當(dāng)3kj>0,有ACjkm或國0當(dāng)akj<0,有ACjmax-min為保證所有

6、非基變M檢驗(yàn)數(shù)仍滿足最優(yōu)條件，有CbXbbxi1x25x33x44x50x60x700x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251Zj-Cj3.2502.75000.251Cj-Zj.akjakj0akj<0cj-Zj_akj表15.2.3rCjZj_-'.CjZj_c'由maxj±akj>0修Ag<minj_jakj<0j-遍_kj_akj_設(shè)X4的價(jià)值系數(shù)增加Ac4,對應(yīng)k=2,-3.25-0.25.-2.75-1max,_C4_

7、min,_21_-2-1一0.25三上6三1,3.75三C4三5?有一邊為空集如何處理(右：+8,或左：-8)?為什么akj=0不出現(xiàn)在任何一邊的集合中?與對偶單純型法找入基變量的公式類似。15.3右端項(xiàng)bi的靈敏度分析?設(shè)XB=B”b是最優(yōu)解，則有XB=B1b0?b的變化不會影響檢驗(yàn)數(shù)；?b的變化量可能導(dǎo)致原最優(yōu)解變?yōu)榉强尚薪?。?1gm設(shè)B=:'-.gm1gmmb'=(n,b2,，(bs+Abs),bmT,第s個(gè)分量發(fā)生變化。為保證最優(yōu)解的基變量'&+偵9估不發(fā)生變化，必須滿足XB=B#b%0即B-1b=Bb+Abs:=:lgms.)bm*Absgms當(dāng)bk

8、+gksAbs'0(k=1,2,m)時(shí)，B仍是新問題的最優(yōu)基矩陣。當(dāng)gk,s>0，貝U有Abs業(yè)玉gk,sb當(dāng)gk,s<0，則有Ab要求對所有k都成立，從而有max&gk,s0bs三現(xiàn)nk_gk,sk此時(shí)，基變量的解值和目標(biāo)函數(shù)會發(fā)生變化：XNew=x0|d+AbsPs,OBJNew=OBJ0|d+AbsCBPs即表15.3.1CbXbbx11x25x33x44x50x60x700x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251Zj-Cj3.2502.7500

9、0.251還是對前面的例分析，以b2為例，xs是對應(yīng)的初始基變量,z100'11/4-r800'Bb=200_1,B=(P5,R,P7),B=01-1,b=1200J00>L°-3/41JJ000?A=1200b2有變化,s=1，即取基矩陣B中第二列計(jì)算max-穌力乂匕版min<°kgLkbk,s-100-200人.-100max,_b2已min-_0.251_-0.75-200一b2£133.3,1000%b2£1333.3令A(yù)b2=100,則有100'Z0.25'"125'fxvNewX=

10、200+1001.00=300=x4<100>375/<25><x2)OBJNew=CBXNew=12503004255=1325(XNew=X0|d：bsPs,OBJNeW=OBJ0|dWCbPs)15.4技術(shù)系數(shù)aij的靈敏度分析技術(shù)系數(shù)aij變化的影響比較復(fù)雜對應(yīng)基變量的aij，且資源bi已全部用完對應(yīng)基變量的aij，但資源bi未用完對應(yīng)非基變量的aij，且資源bi全用完或未用完1）對應(yīng)基變量的aij，且資源bi已全部用完Aaj=02）對應(yīng)基變量的aij，但資源bi未用完-D團(tuán)？蘭上述兩個(gè)公式不充分，為什么？引起B(yǎng)"發(fā)生變化，從而引起非基變量的檢驗(yàn)

11、數(shù)z-Q的變化3）對應(yīng)非基變量的aij-只影響對應(yīng)非基變量xj的檢驗(yàn)數(shù)Zj-Q-若：aij>0,不會破壞最優(yōu)解-若Aaij<0,必須保證0zi-Cjm設(shè)Xj為非基變量，則有Z0=£akjQj設(shè)aj變動Aa,j,則有kAzj=z0+Aajq,gz；=gz0Aaq壬0即膈四芝勺一z0對丁第i行約束苴型，q>0,所以C<Aa,牛qi表15.4.1CbXbbX11X25X33X44X50X60X700X51001/40-13/4011/4-14X420020-2101-15X2100-3/4111/400-3/4113004.2555.75400.251zj-Cj3.

12、2502.75000.251q2=0.25,q3=1,故有-二八餡13xi,X3為非基變量，qi=0,-2.75._11=-a23:0.25-275-2.75=-、.a33-b1有剩余，故有100=0.5200-二-an<二-3.25.-13=-心21-0.25-325一3.25=于5£a31立二X2,X4為基變量,X5=100,-二土柘121-二三.治14三10010015.5新增決策變量的分析例15.1.1中，若新增產(chǎn)品X8,單位產(chǎn)品的資源消耗量分別是：5,4,3,單位產(chǎn)品的利潤是：9,問是否生產(chǎn)？-已知C8=9,a18=5,a28=4,a38=3-計(jì)算x8的檢驗(yàn)數(shù)可知生產(chǎn)

13、是否有利3z8-c8='qm-c8=（5040.2531）-9=50i4結(jié)論：生產(chǎn)X8有利。將B1P8加入最優(yōu)單純型表中，以X8為入基變量進(jìn)行迭代。（過程學(xué)生完成）15.6新增約束條件的分析1）將最優(yōu)解代入新的約束條件，若滿足，則最優(yōu)解不變2）若不滿足，則當(dāng)前最優(yōu)解要發(fā)生變化；將新增約束條件加入最優(yōu)單純型表，并變換為標(biāo)準(zhǔn)型3、利用對偶單純型法繼續(xù)迭代為什么可以利用對偶單純型法例15.6.1續(xù)前例15.1.1,如果生產(chǎn)中為提高產(chǎn)品性能，增加一種原料，已知各產(chǎn)品單件生產(chǎn)的該原料消耗量為：1,2,3,3,該原料總量為：650。應(yīng)該如何調(diào)整生產(chǎn)計(jì)劃？解：先把新增加的條件添加到表格中，再典范化：

14、表15.6.1X1X2X3X4X5X6X7X8CBXbb153400000X51001/40-13/4011/4-104X420020-2101-105X2100-3/4(1)11/400-3/4100X865012330001X1X2X3X4X5X6X7X8CbXbb153400000X51001/40-13/4011/4-104X420020-2101-105X2100-3/4(1)11/400-3/4100X8650123300010X51001/40-13/4011/4-104X420020-2(1)01-105X2100-3/4111/400-3/4100X84505/20-5/23

15、01.5-210X51001/40-13/4011/4-104X420020-2101-105X2100-3/4111/400-3/4100X8-150-7/207/200-1.511(以上為典范化的過程。下面先計(jì)算判別數(shù)，可以發(fā)現(xiàn)是對偶可行的，因此利用對偶單純形方法求解。)表15.6.2CbXbbX11X25X33X44X50X60X70X800X51001/40-13/4011/4-104X420020-2101-105X2100-3/4111/400-3/4100X8-150-7/207/200(-1.5)1113004.2555.75400.2510Zj-Cj3.2502.75000.

16、25100X575-0.330-2.67010-0.830.174X4100-0.3300.33100-0.330.675X21751110000.5-0.50X61002.330-2.33001-0.67-0.6712753.6756.334001.170.17Zj-Cj2.6703.330001.170.17注意：最優(yōu)解的目標(biāo)函數(shù)減少了25個(gè)單位15.7靈敏度分析舉例例15.7.1某工廠生產(chǎn)三種產(chǎn)品A,B,C,有五種生產(chǎn)組合方案。下兩表給出有關(guān)數(shù)據(jù)。規(guī)定每天供應(yīng)A產(chǎn)品至少110個(gè)，求收益最大的生產(chǎn)方案。表15.7.1別IIIIIIIVV單位售價(jià)（元）A產(chǎn)品數(shù)量3244010B產(chǎn)品數(shù)量612

17、145C產(chǎn)品數(shù)量265184耗費(fèi)乂別IIIIIIIVV資源限制工人工時(shí)（小時(shí)）0461280小時(shí)/天機(jī)器工時(shí)（小時(shí)）1121150小時(shí)/天每組生產(chǎn)費(fèi)用（元）481930407解：設(shè)為為已選定各種組合方案的組數(shù)（j=1,2,5）X6為A產(chǎn)品的剩余變量，X7,X8分別為工人工時(shí)和機(jī)器工時(shí)的松弛變量。maxf（x）=20x130x240x35x445x53x1+2x2+4x3+4x4-x6=1104x2+6冷十七十2x5+x7=80st<X+x2+2x3+x4+冷+冷=50、xj>0,j=1,2，8表15.7.2x1x2x3x4x5x6x7x8CbXbb20304054500020x12

18、61100.410-0.2-0.20.430x216011.40.50-0.20.3-0.645x58000.2-0.510.4-0.11.213602030594080.544zj-cj00190080.544例15.7.2?最優(yōu)解的B"是什么?產(chǎn)品A的影子價(jià)為多少?第II組方案的生產(chǎn)費(fèi)用提高2元，是否要調(diào)整生產(chǎn)組別?若工人加班費(fèi)為1元/小時(shí)，是否要采取加班措施?若通過租借機(jī)器增加工時(shí)，租費(fèi)的上限應(yīng)為多少?A產(chǎn)品的訂購合同是否有利，A產(chǎn)品的變動范圍多大?若要選用第IV組方案，該組的生產(chǎn)費(fèi)用應(yīng)降低多少?若工人加班費(fèi)為0.3元/小時(shí)，最多允許加班時(shí)間多少?若機(jī)器租費(fèi)低丁44元/小時(shí)，問

19、租幾部機(jī)器才合適(每天8小時(shí)計(jì))?若第III組方案使機(jī)器工時(shí)減少0.5小時(shí)，能否被選入15.8參數(shù)線性規(guī)劃前面只考慮aij,bi,cj一個(gè)發(fā)生變化，如果多個(gè)同時(shí)發(fā)生變化則很難解析。但在一些特殊情況下，用參數(shù)表示變化量，也可以用來進(jìn)行多個(gè)系數(shù)的靈敏度分析。15.8.1參數(shù)Cj的變化分析q第i種資源的單位費(fèi)用變化量，q土不限ajq變化對Cj的影響率nmaxf(x)=、gy尸iXjj4.nI-'ajXj一(=,-)bji=1,2;,ms.tE為油j=1,2，n例15.8.1資源b1變化量01,otj=a1jmaxf(x)=(1_2u1)x(5-3斗)x2(3r)x(4-2"x4&#

20、39;2x1+3x2+x3+2x4壬8005x1+4x2+3x3+4x41200s.t<3x1+4x2+5x3+3x4壬1000、x1,x2,x3,x0表15.8.1CbXbbx11-2,1x25-3%x331x44-261x50x60x700x51001/40-13/4011/4-14-281x420020-2101-15-3Sx2100-3/4111/400-3/411300-700S4.25-15-3e15.75-44-2%00.25+1-%.75%.25610.25%Cj-zj-3.25-0-2.75+00-0.25-1+s0.25*3.25S0.25S例15.8.2資源b1變化

21、量，與任5-0.2501-133.25壬01壬0.8462-0.25一0"-1-1101要求(cj-zj)<0,由上單純型表-3.25-2.75-0.25一1三"三0.8462e1在此范圍內(nèi)不會影響最優(yōu)解15.8.1有(X5,X4,X2)=(100,200,100)maxf(x)=1300-700時(shí)1=-1,X6的檢驗(yàn)數(shù)=0e1=0.8462,X3的檢驗(yàn)數(shù)=0出現(xiàn)多重解現(xiàn)象研究X5松弛變量價(jià)值系數(shù)5maX匚3.250.25-0.250.25C5的變化范圍-2.75-1,-3.25-1-1<:c5壬0.8462結(jié)果與91的一致。15.8.2參數(shù)b的變化分析例15.

22、8.1中，將b1,b2,b3理解為三個(gè)車間的周工時(shí)資源。假設(shè)從第1向2車間調(diào)動工人臼個(gè)，每個(gè)工人的周工時(shí)為40小時(shí)，問調(diào)動多少工人不會破壞最優(yōu)產(chǎn)品組合。解：maxf(x)=CXs.t.，40P=-400要保證X；=B"(b"")_0即XN=XB0B七芯二0/N>乂5門00r30e>N乂4=200+-409>0N2)100l30嘰解得100308-06200-40e-0e100300-00-3.33土5-3.33-3.33主)三5OBJ=CBB一1(b，：)=1300-10口從目標(biāo)函數(shù)中看出什么?習(xí)題151.已知線性規(guī)劃問題和它的最優(yōu)單純形表15.

23、9.1.maxz=4xiX>2x38x13x2x3三2s.t«6x1+x2+x3苴8/芝0,x2占0,x3占0表15.9.1xix2x3x4x右邊1250204831102-2-20-116(1)求原問題和對偶問題的最優(yōu)解(2) 確定最優(yōu)基不改變的前提下變量X1和X3的目標(biāo)函數(shù)系數(shù)的變化范圍確定最優(yōu)基不改變的前提下兩個(gè)右邊項(xiàng)系數(shù)的變化范圍2.已知線性規(guī)劃問題maxz=(q11)x1c2x2c3x30x40x5aiixi*ai2x2*ai3x3*x4=加*3t2S.t<a2x*&22乂2*&23乂3*乂5=b?*t?xj河(j=1,2,.5)當(dāng)t1=t2=0時(shí)求解得最終單純形表如表15.9.2.確定