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

1、淮北師范大學(xué)2011屆學(xué)士學(xué)位論文學(xué)院、專業(yè) 研究方向 學(xué)生姓名 學(xué) 號(hào)線性規(guī)劃靈敏度分析數(shù)學(xué)科學(xué)學(xué)院數(shù)學(xué)與應(yīng)用數(shù)學(xué)運(yùn)籌學(xué)陳紅20071101008 指導(dǎo)教師姓名 張發(fā)明指導(dǎo)教師職稱 副教授2011年4月10日線性規(guī)劃的靈敏度分析陳紅（淮北師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，淮北，235000）摘要本文主要從價(jià)值系數(shù)”的變化，技術(shù)系數(shù)%的變化，右端常數(shù)的變化以 及增加新的約束條件和增加一個(gè)新變量的靈敏度這幾個(gè)方面來進(jìn)行研究；資源條 件是線性規(guī)劃靈敏度分析中的主要應(yīng)用內(nèi)容，而對(duì)于資源條件8的一個(gè)重要應(yīng)用 是：“影子價(jià)格問題”的實(shí)際應(yīng)用，最后簡述了線性規(guī)劃在經(jīng)濟(jì)及管理問題上的 典型應(yīng)用和從求解例題的圖解法揭示了

2、最優(yōu)解的一些重要特征。關(guān)鍵詞單純形法，靈敏度分析，最優(yōu)解.，資源條件，價(jià)值系數(shù)4Sensitivity Analysis of Linear ProgrammingChen Hong(School of Mathematical Science, Huaibei NormalUniversity ,Huaibei, 235000)AbstractThis thesis is mainly from the variety of the cost coefficient ' cj ' the variety of technology coefficient aii , the

3、variety of the resources condition 4 bj and increase the new restraint and new variable to analytical linear programming of sensitivity analysis. This thesis is mainly based on the simplex method and dual simplex method of linear programming to system analytical the influence of the variety upon the

4、 optical solution of the coefficient of the simplex table. Linear programming of sensitivity analysis in physically of application is mainly about application of the variety of resources condition ' in the economic management 4shadow price problem'.Keywords simplex method, sensitivity analys

5、is, optimum solution ， resources condition, cost coefficient引言1一、價(jià)值系數(shù)的變化分析2二、技術(shù)系數(shù)的變化分析 5三、右端常數(shù)的變化分析 6四、增加新約束條件的靈敏度分析 8五、增加一個(gè)新變量的靈敏度分析9七、線性規(guī)劃在經(jīng)濟(jì)及管理問題上的典型應(yīng)用14八、從求解例題的圖解法揭示了最優(yōu)解的一些重要特征16結(jié)論17參考文獻(xiàn)18致謝19引言靈敏度分析是運(yùn)籌學(xué)中一個(gè)比較重要的問題，在現(xiàn)實(shí)生活中，尤其是在經(jīng)濟(jì) 管理與投資中有著廣泛的應(yīng)用.隨著經(jīng)濟(jì)的發(fā)展，已有不少學(xué)者對(duì)其進(jìn)行研究， 本文基于已有的研究上進(jìn)行歸納總結(jié)，并在對(duì)其研究理論的基礎(chǔ)上，對(duì)靈

6、敏度分 析的應(yīng)用進(jìn)行分析.在研究線性規(guī)劃的靈敏度分析之前，先了解幾個(gè)定義：定義線性規(guī)劃的標(biāo)準(zhǔn)形：maxZ = CX(1.1)(LP ) AX =b(1.2)s.t.<X>0(1.3)其中c =億,c，2,c“)為行向量，x =(x1,x2,.,xn)/ ,。=(4也，也J均為列向 量，A = (q )為機(jī)x矩陣；/*0,并假設(shè)A的秩為機(jī)，在問題(LP)中，約 "J /mx/r束方程(1.2)的系數(shù)矩陣A的任意一個(gè)?x?階滿秩子矩陣8 (忸性0)稱為線 性規(guī)劃問題的一個(gè)基解或基.這就是說，基矩陣8是由矩陣A中“個(gè)線形無關(guān)的 Cl Cl>n列向量組成的，不失一般性，可假

7、設(shè)B= ："：=(p:p”.,p“J并稱Pi (i = 127)為基向量，與基向量相對(duì)應(yīng)的變量X, (，= 1,2,7)稱為基變 量不在8中的列向量,(/="7 + 1,? + 2,)稱為非基向量，與非基變量相對(duì)應(yīng)的 變量Xj(' = "? + l,z+2)稱為非基變量，并記a1.加+1?！?旭N =：=(P"WP,”+2.，P“)，/ (1 m.m+1mn /則系數(shù)矩陣4可以寫成分塊形式，不失一般性A = (B,N),(1.4)將基變量和非基變量組成的向量分別記為Xs =(小，4)'， Xn =(小，/+2,，玉)/，則向量X相應(yīng)的寫成

8、分塊形式X= B(1.5)1xj(x、再將(1.5)代入約束方程組(1.2)中，得(B,N) b =b,由矩陣的乘法可得 BXb + NXn=1), 乂因?yàn)?是非奇異方陣，所以87存在，將上式兩邊乘以8", 移項(xiàng)后，得Xb = B"B-'NXn現(xiàn)在可以把X.v看作一組自由變量（乂稱獨(dú)立變量），給他們?nèi)我庖唤M值文八 則一 相應(yīng)的Xs的一組值58,于是夕=丫 便是約束方程組（1.2）的一個(gè)解.特 卜"別令耳、,=0時(shí)，則用v=8-%,現(xiàn)把約束方程組的這種特殊形式的解乂= ”,稱為基本解.滿足變量非負(fù)約束條件（1.3）的基本解稱為基本可行解.現(xiàn)在來研究線性規(guī)劃的

9、靈敏度分析.靈敏度分析的含義是指對(duì)系統(tǒng)或事物因?yàn)橹車鷹l件變化顯示出來的敏感度. 具體說來就是要研究初始單純形表上的系數(shù)變化對(duì)最優(yōu)解的影響，研究這些系數(shù) 在什么范圍內(nèi)變化時(shí)原最優(yōu)基仍然是最優(yōu)的.若原最優(yōu)基不是最優(yōu)的，如何用簡 便的方法找到新的最優(yōu)解.現(xiàn)考慮標(biāo)準(zhǔn)形線性規(guī)劃問題：max Z = CX（LP）AX=bs.t.<X>0當(dāng)線性規(guī)劃問題中的一個(gè)或幾個(gè)參數(shù)變化時(shí)，可以用單純形法從頭計(jì)算，看 最優(yōu)解有沒有變化.但這樣做即麻煩乂沒有必要，因?yàn)閱渭冃畏ǖ牡^程是從 一組基向量變換為另一種基向量，每次迭代都和基變量的系數(shù)矩陣B有關(guān)，表中 每次迭代得到的數(shù)據(jù)只隨基向量的不同選擇而改變，因此

10、可以把個(gè)別參數(shù)的變化 直接在計(jì)算得到的最優(yōu)解的單純形表上反映出來.這樣就不需要從頭計(jì)算，而直 接在最優(yōu)性單純形表進(jìn)行審查，看一些數(shù)字變化后，是否仍滿足最優(yōu)性的條件， 如果不滿足的話再從這個(gè)表開始進(jìn)行迭代計(jì)算，求得最優(yōu)解.可按下表中的幾種情況進(jìn)行處理:原問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解表中的解仍是最優(yōu)解可行解非可行解用單純形法繼續(xù)迭代求 最優(yōu)解非可行解可行解用對(duì)偶單純形法繼續(xù)迭 代求最優(yōu)解非可行解非可行解引進(jìn)人工變量，編制新的 單純形表求最優(yōu)解下面就各個(gè)參數(shù)改變后的情況進(jìn)行討論:價(jià)值系數(shù)匕的變化分析（一）非基變量L的價(jià)值系數(shù)”的變化若非基變量乙的價(jià)值系數(shù)Cj的改變?yōu)?。?勺+拉小則變

11、化后的檢驗(yàn)數(shù)為 b,'=Cj+A,G/4pj，0要保持原最優(yōu)基不變，即當(dāng),變化為.后，最終單 純形表中這個(gè)檢驗(yàn)數(shù)小于或等于零，即因此 這就確定里在保持最優(yōu)解不變時(shí)非基變量弓的目標(biāo)函數(shù)“，的變 化范圍，當(dāng)超出這個(gè)范圍時(shí)，原最優(yōu)解將不是最優(yōu)解了.為了求新的最優(yōu)解，必 須在原最優(yōu)單純形表的基礎(chǔ)上，繼續(xù)進(jìn)行迭代以求得新的最優(yōu)解.例1已知線性規(guī)劃問題max Z =玉 + 5x2 + 3x3 +4x42x + 3x2 +x3 + 2x4 < 8005 內(nèi) + 4x2 + 3演 + 4x4 < 12003內(nèi) + 4x2 + 5xy + 3x4 < 1000x?>0（j = l

12、,2,3,4）的最優(yōu)單純形表如下所示：（表LI）%1534000CbXBbX2與z兒V70七1001/40-13/4011/4-14%20020-2101-154100-3/4111/4003/41Z = cz1300-13/40-11/400-1/4-1（I）為保持原最優(yōu)解不變，分別求非基變量為,占的系數(shù)G9的變化范圍 （II）當(dāng)q變?yōu)?時(shí)，求新的最優(yōu)解.解 （i）由圖表可知：5=73/4, 4=-11/4,于是由公式Ac產(chǎn)-知, 保持原最優(yōu)解不變，則有 M « 13/4, Aq < 11/4 ,當(dāng) c； = c, +Aq <1 + 13/4 = 17/4 , c； =

13、 q + Ac. 43 +11 /4 = 23/4時(shí)，原最優(yōu)解不變.（ii）當(dāng)q=5>17/4時(shí)，已經(jīng)超出了 q的變化范圍，最優(yōu)解發(fā)生了變化，下 面來求新的最優(yōu)解.首先求出的檢驗(yàn)數(shù)：，1/4、 b；=q'-G8"p1=5-（0,4,5） 2=3/4>0<-3/4；故再為換入基，用新的檢驗(yàn)數(shù)b； =3/4代替原來的檢驗(yàn)數(shù)巧=73/4,其余數(shù)據(jù) 不變，得到新的單純形表，并繼續(xù)迭代得：序號(hào)%5534000%XbbA2與%招/X、I01001/40-13/4011/4-1420020-2101-15X?100-1/4111/400-3/41Z = j-Zj-1300

14、3/40-11/400-1/4-1II07500-31/811/8-7/85王10010T201/2-1/25X21750123/80-3/85/8z = (l,-137500-2-3/80-5/8-5/8表(1.2)由表中可看出已得到新的最優(yōu)解9 =(100,175,0,0,75)/ 及新的目標(biāo)函數(shù)最優(yōu)值Z4=1375.(二)基變量勺的價(jià)值系數(shù)%的變化若%是基變量%的價(jià)值系數(shù)，因?yàn)楫?dāng)g變?yōu)?小寸，就引起品的變化，則其中卜/“；，4：)是矩陣8%的第r行.于是，變化后的檢驗(yàn)數(shù)為cr/ =Cj -ClBlpt -Acrar- = <7, -cra (j = 1, 2, ，n) 若要求最優(yōu)解

15、不變，則必須滿足b； =o(j = 1, 2,，n) 由此可以導(dǎo)出當(dāng)與<0時(shí)，有/a；當(dāng)% >0 時(shí)，有jNbJa；.因此，Ac,的允許范圍是max 卜/ /%' a； >o1 < At; < min b, /qj a； < o使用此公式時(shí)，首先要在最優(yōu)表上查出基變量與所在行中的元素%'(/ = 1,2,)，而且只取與非基變量所在列相對(duì)應(yīng)的元素，將其中的正元素 放在不等式的左邊，負(fù)元素放在不等式右邊，分別求出A%的上下界.例2為保持現(xiàn)有最優(yōu)解不變，分別求出例1中基變量乙,的變化范圍.若 當(dāng)品由(0, 4, 5)改變?yōu)?0, 6, 2)時(shí)，原最

16、優(yōu)解是否保持最優(yōu)，如果不是, 該怎么辦？解 根據(jù)上述公式，利用表（L1）,為使最優(yōu)基變量（孫多）不變，的變化范圍是max-13/4 -1/412 ' 1> < Ac4 < min <-13/4 -1/4一3/4 '-3/4故當(dāng)時(shí).，原最優(yōu)解不變，現(xiàn)在j變?yōu)?,已超出了的允許變化范-1 1/4 -11f-13/4 -1/41圍.同樣的，Aq的允許范圍是maxJ-p7p-j-)K Ac? KminJ二即 故當(dāng)44小不時(shí)，原最優(yōu)解不變，現(xiàn)在Q變?yōu)?,也不在此的允許變化范圍內(nèi), 當(dāng)仆由（0, 4, 5）變?yōu)椋?, 6, 2）即q變?yōu)?, C?變?yōu)?,都超過了它們

17、的允許變化范圍，需要求新的最優(yōu)解,為此用變換后的%'代替q，將表（L2）改成 表L3 （I）,在繼續(xù)進(jìn)行迭代求得新的最優(yōu)解，由該表知，已求得最優(yōu)解 寸=（0,0,0,300,200,0,100）'及目標(biāo)函數(shù)最優(yōu)值Z* = 1800.序號(hào)Cj12360005Xbb再X2與%兒XI0X51001/40-13/401-1/206X420020-2101/402V2100-3/4111/400-3/41Z = cZ/-1400-19/2019/200-3/20II0200-1/21-1/201-1/2063005/413/4101/400%7100-3/4111/400-3/41Z =

18、 c"-1800-13/2-4-3/200-3/20從價(jià)值系數(shù)匕的變化的分析中，現(xiàn)可以得到一個(gè)特征:最優(yōu)解對(duì)目標(biāo)函數(shù)中的價(jià)值系數(shù)”的改變不十分靈敏，而對(duì)價(jià)值系數(shù)”的 靈敏度分析的應(yīng)用意義是：企業(yè)可以在不改變資源優(yōu)化分配的前提下，在一定幅 度內(nèi)改變價(jià)值系數(shù)Cj的值，來積極應(yīng)對(duì)市場(chǎng)挑戰(zhàn).二、技術(shù)系數(shù)4的變化分析由于對(duì)價(jià)值系數(shù)Cj的分析分為基變量價(jià)值系數(shù)和非基變量價(jià)值系數(shù),現(xiàn)也可 以按這種方法把對(duì)技術(shù)系數(shù)%的分析分為兩類：% J（一）、非基向量列P,改變?yōu)閜; p）="" 這種情況指初始表中的舄到數(shù)據(jù)改變?yōu)閜;,而第/個(gè)列向量在原最終表上 是非基向量.這一改變直接影響最

19、優(yōu)單純形表上的第j列數(shù)據(jù)與第j個(gè)檢驗(yàn)數(shù). 最終單純形表上的第J列數(shù)據(jù)變?yōu)榻铮?#39;，而新的檢驗(yàn)數(shù)若 <<0,則原最優(yōu)解仍是新問題的最優(yōu)解.若'>0,則最優(yōu)基在非退化情況下 不再是最優(yōu)基.這是，應(yīng)在原來最優(yōu)單純形表的基礎(chǔ)上，換上改變后的第j列數(shù) 據(jù)夕？'和',把弓作為換入變量，用單純形法繼續(xù)迭代.（二）、基向量列"改變?yōu)榘瓦@種情況指初始表中的P,列數(shù)據(jù)改變?yōu)槎?個(gè)列向量在原最終表上 是基向量，此時(shí)，原最優(yōu)解的可行性和最優(yōu)性都可能遭到破壞，需要重新計(jì)算.三、右端常數(shù)內(nèi)的變化分析右端常數(shù)片的變化在實(shí)際問題中表明可用資源的數(shù)量發(fā)生變化.當(dāng)?shù)?，個(gè)

20、約束方程的右端常數(shù)由原來的/乙變?yōu)?quot;其它系數(shù)都不變，即 初始表上新的限定向量4 一'o -飛一-0b20b20/ = /? + M = + 她，其中b = b.= A.XR 0 A. 0設(shè)原最優(yōu)解為Xs= 8-6 =% 9則新的最優(yōu)解為60 X； = B-lbf = B7b + B-b = B-lb + 8“ hr 0若原最優(yōu)基8仍是最優(yōu)的，則新的最優(yōu)解X； NO,即ro X； = B-b + B-i =B-lb+ d； =Xl+brDr>0 一。d'fnr其中。是的第r列，即故XB + 她4； >0(/= 1,2,/?) 因此，么的允許變化范圍是： 、

21、.max < 14, >0><< min , I d： < 0 >f><>T 4r*<如果A超出上述范圍，則新的解不是可行解.但由于。的變化不影響檢驗(yàn)數(shù)， 故仍保持檢驗(yàn)數(shù)b<0,即滿足對(duì)偶可行性，這時(shí)可在原最終表的基礎(chǔ)上，用對(duì) 偶單純形法繼續(xù)迭代，以求出新的最優(yōu)解.一般來說，當(dāng)變?yōu)閆/時(shí)，也可以直 接計(jì)算夕%,若有2 0,則原最優(yōu)基8仍是最優(yōu)基，但最優(yōu)解和最優(yōu)值要重 新計(jì)算.若8-%不恒大于零，則原最優(yōu)基B對(duì)于新問題來說不再是可行基，但由 于所有檢驗(yàn)數(shù)bNO,現(xiàn)行的基本解仍是對(duì)偶可行的，因此，只要把原最終表的 右端列改為,

22、就可用對(duì)偶單純形法求解新問題.-Cb'例3線性規(guī)劃問題max Z = 2x1+ 3x22x +< 12 +AZ?.4x <16 + > s/<5x2 < 15 + 4分別分析仇，打在什么范圍內(nèi)變化，問題的最優(yōu)基不變.解 先分析的變化，由公式XjuXs+B-iMZO知，使問題最優(yōu)基不變 的條件是由此推得3 同理由4 + A,3從而>0得,>0ST%44 + *3 +3四、增加新約束條件的靈敏度分析>0若在線性規(guī)劃問題中再增加一個(gè)新的約束條件，即4Mx <bm+l其中(4. 1)+")，X=(xpx2,.sx/r),由于增加一

23、個(gè)約束，則可行域有可能減小，但不會(huì)使可行域增大，因此，若原問 題的最優(yōu)解滿足這個(gè)新的約束，則在新問題中仍是最優(yōu)解；若原來的最優(yōu)解不滿 足這個(gè)新約束，那么現(xiàn)再來求新的最優(yōu)解.設(shè)原來的最優(yōu)基為8,各基向量集中于A的前加歹U，最優(yōu)解為x =09對(duì)新增加的約束（4.1）,引進(jìn)松弛變量吃 又因?yàn)?7=（4+）,（4+）v），則（4.1）式變成（AhJbX8+（4i）nXn+X“x=2 田（4.2）20顯然，五川是約束（4.2）的基變量.增加約束后，新的基31 （9尸及右端向量/ 如下：B'=，-i0 Pj對(duì)于新增加約束后的新問題，在現(xiàn)行基下對(duì)應(yīng)變量。工7 + 1）,的檢驗(yàn)數(shù) 是：=Cj -Zj

24、= Cj_C/（9尸邛=Cj -G，0） 它與不增加約束時(shí)相同.乂因?yàn)楣ごㄊ腔兞?，?.；=0,因此，現(xiàn)行的基本解 是對(duì)偶可行的，現(xiàn)行基本解是：XbXeB" 0-（心產(chǎn)1若（%（4川）*-町之0,則現(xiàn)行的對(duì)偶可行的基本解是新問題的可行解， 即最優(yōu)解.若（%（4+1）*-町<。，則在原來最終解的基礎(chǔ)上增加新約束（4.2）的 數(shù)據(jù)，通過矩陣的初等行變換，把原最終表上的各基向量列及新增列己,化為單 位陣，再用對(duì)偶單純形法繼續(xù)求解.五、增加一個(gè)新變量的靈敏度分析假設(shè)要增加一個(gè)非負(fù)的新變量X向，其相應(yīng)的系數(shù)列向量為2+1，價(jià)值系數(shù) 為乂知原問題的最優(yōu)解是8,顯然，增加這個(gè)新變量，對(duì)原最

25、優(yōu)解的可行 性沒有影響.現(xiàn)計(jì)算新的檢驗(yàn)數(shù)4+| =-CrB 12+若?”<0,則原最優(yōu)解是新問題的最優(yōu)解；若巴”>0則原最優(yōu)解不再是最 優(yōu)解.這時(shí)，把夕功”加入到原最終表內(nèi)，并以新變量上/作為換入變量，按單 純形法繼續(xù)迭代，即可得到新的最優(yōu)解.六、線性規(guī)劃靈敏度分析的應(yīng)用線性規(guī)劃靈敏度分析的應(yīng)用主要是資源條件的應(yīng)用，而對(duì)資源條件沙的分析 的一個(gè)重要應(yīng)用是：“影子價(jià)格問題”定義設(shè)線性規(guī)劃對(duì)偶問題 nmax Z = Z cjxj = CXmin W = Yb,n、 i>/j=AXW4=3 = 12.,7）（YA>C（P ） s.t.< j-i（ D ） sJ.<

26、Y >0x-20（/ = 1,2廣、）1 *右端常數(shù) （i = 12,7）表示第i種資源的現(xiàn)有量下面討論暫增加1個(gè)單位時(shí)所引起的目標(biāo)函數(shù)最優(yōu)值的變化.設(shè)8是問題（P）的最優(yōu)基，則z = CBB-lb = Y*h = y；a + y2b2 + + ymbm ,當(dāng)變?yōu)?+1時(shí)（其余右端常數(shù)不變，并假設(shè)這種變化不影響最優(yōu)基6） 目標(biāo)函數(shù)最優(yōu)值變?yōu)閆' = >'i 4 + + y：（2 +1） + + ymbm ,于是目標(biāo)函數(shù)最優(yōu)值的改變量為zXZ*=Z,4-Z* = y；,由上式可以看出y；的意義，它表示當(dāng)右端常數(shù)增加1個(gè)單位時(shí)所引起的目標(biāo) 函數(shù)最優(yōu)值的改變量，也可以寫成

27、衛(wèi)= y；（i = l,2,，即y：表示Z.對(duì)白的變 dbi化率.在一對(duì)對(duì)偶問題（P）和（。）中，若（P）的某個(gè)約束條件的右端常數(shù)4 增加1個(gè)單位時(shí)所引起的目標(biāo)函數(shù)最優(yōu)值Z*的改變量），；稱為第，個(gè)約束條件的影 子價(jià)格，乂稱邊際價(jià)格.由定義可知，影子價(jià)格上的經(jīng)濟(jì)意義是在其它條件不變的情況下，單位資 源變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化，即對(duì)偶變量K就是第i個(gè)約束條件的影 子價(jià)格.影子價(jià)格是針對(duì)某一具體的約束條件而言的.而問題中所有其它數(shù)據(jù)保 持不變，因此影子價(jià)格也可以理解為目標(biāo)函數(shù)最優(yōu)值對(duì)資源的一階偏導(dǎo)數(shù).影子價(jià)格乂稱靈敏度系數(shù)，通常指線性規(guī)劃對(duì)偶模型中對(duì)偶變量的最優(yōu)解. 如果原規(guī)劃模型屬于一定

28、資源約束條件下，按一定的生產(chǎn)消耗生產(chǎn)一組產(chǎn)品并需 求總體效益目標(biāo)最大化問題，那么其對(duì)偶模型屬于對(duì)本問題中每一資源以某種方 式進(jìn)行估價(jià)，以便得出與最優(yōu)生產(chǎn)計(jì)劃相一致的一個(gè)企業(yè)最低總價(jià)值.該對(duì)偶模 型中資源的估價(jià)表現(xiàn)為相應(yīng)資源的影子價(jià)格.影子價(jià)格在經(jīng)濟(jì)管理中的應(yīng)用很多，下面就下面這個(gè)問題進(jìn)行分析： 影子價(jià)格指示企業(yè)內(nèi)部挖掘潛力的方向.設(shè)線性規(guī)劃模型（LP ）：max Z = £c：jXjbinZ詢X/ <4(i = 12,7)S.t.< >iA； >0(7 = U2<-JZ)存在最優(yōu)解.對(duì)（LP）標(biāo)準(zhǔn)化后，得：minZ = C'X'rAXf

29、= bXf>0其中c'=（Y,O）,。是卬維行向量， 4=（4/）為7*2單位陣.因?yàn)樵O(shè)（。）有最優(yōu)解，故由線性規(guī)劃單純形法求解，可得最優(yōu)基最優(yōu)解為：Z4 = ycV = Vc；/ ,并可設(shè)= ）” b 1J-110Z，=i>X=i>；£=k；,C）”=斗:（8丁 4所以可令即因此，有>1>-1'/ 0r-1 Li.dZyi=前'了；=。(8'),(i = L2,，機(jī))nm(6. 1)(6.2)，=1>國=£謂 j-lr-l再令了=（£，£，,城）=7'（"）,由單純形

30、法最優(yōu)原則可知:A-cYO即/(A/)<(-c*,O)= -(O)因此，有/>0(6.3)而由（6.2）, （6.3）及線性規(guī)劃的對(duì)偶結(jié)構(gòu)可知：y,是對(duì)偶問題的可行解.再由（6.1）及對(duì)偶定理可知：是對(duì)偶問題的最優(yōu)解.可見，最優(yōu)解一的不起作用約束的影子價(jià)格為零.反之就是，若影子價(jià)格 爐>0,則對(duì)應(yīng)的是/的起作用約束.因此，影子價(jià)格y；=0表示第i種資源4未 得到充分利用；而£>0則表示第i種資源4已得到充分利用.影子價(jià)格直接應(yīng)用到企業(yè)資源最有效的部門中去.當(dāng)影子價(jià)格大于資源的市場(chǎng)價(jià)格時(shí)，企業(yè)應(yīng)購進(jìn)這種產(chǎn)品，使利潤增加；當(dāng)當(dāng)影子價(jià)格小于資源的市場(chǎng)價(jià) 格時(shí)出現(xiàn)多做

31、多賠的情形，應(yīng)出售這種資源.大公司還可借助資源的影子價(jià)格確 定一些內(nèi)部結(jié)算價(jià)格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞.乂 如在社會(huì)上對(duì)一些緊缺資源，借助影子價(jià)格規(guī)定使用這種資源企業(yè)必須上繳的利 潤額，以控制企業(yè)自覺地節(jié)約使用緊缺資源，使有限資源發(fā)揮更大經(jīng)濟(jì)效益.“影子價(jià)格問題”：影子價(jià)格設(shè)線性規(guī)劃模型（LP ） /IMax Z'jXj j-i '£。內(nèi)的（，=1,2 , 7）xf > 0（j = 1,2）有最優(yōu)解父，最優(yōu)解為dzcbi則可令則必有z* = £口；瓦和口；2oMax CjXj j-i .SJ. < j.jXj > 0

32、(y = 1,2)存在最優(yōu)解.對(duì)(LP)標(biāo)準(zhǔn)化后，得min exAx =b/>0其中£ =(局為尸(外為松弛變量,是代維列變量),c' = (-c,O),這里0是機(jī)維行 向量，而4 = (4/)為產(chǎn)單位陣.因?yàn)樵O(shè)(LP)有最優(yōu)解，故由線性規(guī)劃單純 形法求解，可得最優(yōu)基可行解最優(yōu)解為：nnn/khiZ =£cjXjj =（cc：v）= c'b（B ） 1 h =也j-1j-11。 JiT 所以可令以=與，即環(huán)=L(b)t，a = 12,2)c/7.因此有nin=匯jx；=%叫*瓦(6.4)j-TZ-l再令，=(叼*。2*，,S/)= C)(B"

33、)T由單純形法最優(yōu)準(zhǔn)則可知，4一。'=或()-|4'一/<0(6.5)即gt*(A,/) < (-c,0) = -(c,0)因此有g(shù)t" > 0(6. 6)而由(6. 5)和(6. 6),由線性規(guī)劃的對(duì)偶規(guī)劃結(jié)構(gòu)可知:，是對(duì)偶規(guī)劃的可 行解，再由(6. 4),以及對(duì)偶定理可知：，是對(duì)偶規(guī)劃的最優(yōu)解.)稱。為第i種 資源的影子價(jià)格，少=3。喏；)為影子價(jià)格向量.。表示，第i種資源加對(duì) 最優(yōu)值的邊際貢獻(xiàn).從線性規(guī)劃對(duì)偶理論易見，影子價(jià)格就是對(duì)偶規(guī)劃的最優(yōu)解.而由前述對(duì)資 源條件的靈敏度分析可知，對(duì)于最優(yōu)解/的不起作用約束而言，若此約束的資 源條件歷在靈敏

34、度范圍內(nèi)變動(dòng)時(shí)，則最優(yōu)值/不變，所以* &* n= 0dbj可見，最優(yōu)解丁的不起作用約束的影子價(jià)格為零。反之而言就是，若影子價(jià) 格，0,則對(duì)應(yīng)的是/的起作用約束。因此，影子價(jià)格，=0表示第i種資源4未得到充分利用；而，0則表示 第i種資源我已得到完全利用影子價(jià)格直接應(yīng)用到企業(yè)資源的最有效利用中去.當(dāng)影子價(jià)格大于資源的市 場(chǎng)價(jià)格時(shí)，企業(yè)應(yīng)購進(jìn)這種產(chǎn)品，使利潤增加；當(dāng)影子價(jià)格小于市場(chǎng)價(jià)格時(shí)，出 現(xiàn)多做多賠的情形，應(yīng)出售這種資源.大公司還可借助資源的影子價(jià)格確定一些 內(nèi)部結(jié)算價(jià)格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞.乂如在社 會(huì)上對(duì)一些緊缺資源，借助影子價(jià)格規(guī)定使用這種資源單位必

35、須上繳的利潤額， 以控制企業(yè)自覺地節(jié)約使用緊缺資源，使有限資源發(fā)揮更大經(jīng)濟(jì)效益.七、線性規(guī)劃靈敏度分析在經(jīng)濟(jì)與管理問題上的典型應(yīng)用一般應(yīng)用問題的線性規(guī)劃模型為：Maxexsi.Ax< hx>0其中c = (cpc2-,c/f), b = (bb2-bn)>o線性規(guī)劃的靈敏度分析有兩個(gè)主要方面：第一、對(duì)價(jià)值系數(shù)的靈敏度分析在資源條件匕不變的前提下，問最優(yōu)解保持不變時(shí)，每個(gè)價(jià)值系數(shù)可以變動(dòng)的 范圍.第二、對(duì)資源條件的靈敏度分析在價(jià)值系數(shù)C不變的前提下，問最優(yōu)解保持不變時(shí)，每個(gè)資源條件歷可以變動(dòng)的 范圍.線性規(guī)劃的靈敏度分析有重要的經(jīng)濟(jì)與管理的應(yīng)用背景，現(xiàn)通過一個(gè)例子來 了解有關(guān)的

36、概念.現(xiàn)來考慮AB公司的例子.AB公司在一周內(nèi)只生產(chǎn)兩種產(chǎn)品：產(chǎn)品4和8 .產(chǎn)品A和廣”品B由多 種材料混合生成，這些材料都從倉庫中提取.可供一周使用的三種原料數(shù)量如下:原料1 1200Wg原料2 400供g原料3 6000kg產(chǎn)品A 111 60%的原料1和40%的原料2制成,產(chǎn)品B由50%的原料1, 10%的原 料2和40%的原料3制成.產(chǎn)品A的邊際貢獻(xiàn)率為每公斤25元，產(chǎn)品8的邊際 貢獻(xiàn)率為每公斤10元.管理部門必須決定每種產(chǎn)品各生產(chǎn)多少公斤，使得在原料 供應(yīng)計(jì)劃下產(chǎn)品的總貢獻(xiàn)最大.這個(gè)決策問題的線性規(guī)劃模型為：max貢獻(xiàn)= 25 A +10 80.6A + 0.5B< 12000

37、SJ. < 0,4A + 0.1B <40000.48 < 6000 .其中A>0, B>0應(yīng)用圖解法解此線性規(guī)劃問題，可見下圖：原料3的約束43000（圖 1.0）本例的最優(yōu)解為：4 = 6250, 8 = 15000八、從求解例題的圖解法揭示了最優(yōu)解的一些重要特征特征1最優(yōu)解對(duì)目標(biāo)函數(shù)中的價(jià)值系數(shù)（Cj）的改變不是十分靈敏以上例來說，對(duì)于A8公司，在保持（A = 6250, 6 = 15000）仍為最優(yōu)解的 前提下，如果現(xiàn)增加產(chǎn)品A的貢獻(xiàn)，目標(biāo)函數(shù)的斜率會(huì)變得越來越?。繕?biāo)函數(shù) 線變得更加垂直）.（圖1.0）表明，最終目標(biāo)函數(shù)將會(huì)達(dá)到一個(gè)與約束條件2 平行的斜率.那時(shí)，最優(yōu)解即是包括從當(dāng)前頂點(diǎn)到頂點(diǎn)（力= 1000, 8 = 0）的線 段上的所有點(diǎn).運(yùn)用下面的代數(shù)方法，現(xiàn)能計(jì)算出這時(shí)A的單位貢獻(xiàn)為每公斤40 元6250必 +15000 xl0 = l0000/V1150000 = （10000-6250） PAPA = 150000/3750 = 40 （元）現(xiàn)可得到結(jié)論：若A的單位貢獻(xiàn)為25美元到40美元之間（B的單位貢獻(xiàn)保 持10美元不變），產(chǎn)生最大貢獻(xiàn)的最優(yōu)解始終是生產(chǎn)6250kg的產(chǎn)品A和15000依 產(chǎn)品慶注意