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

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

2、應用和從求解例題的圖解法揭示了最優(yōu)解的一些重要特征。關鍵詞 單純形法，靈敏度分析，最優(yōu)解，資源條件，價值系數(shù)Sensitivity Analysis of Linear ProgrammingChen Hong(School of Mathematical Science,Huaibei Normal University ,Huaibei,235000)AbstractThis thesis is mainly from the variety of the cost coefficient , the variety of technology coefficient , the vari

3、ety of the resources conditionand 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 optical so

4、lution 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 conditionin the economic management shadow price problem. Keywords simplex method, sensitivity analysis, optimum solution， re

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

6、的基礎上，對靈敏度分析的應用進行分析.在研究線性規(guī)劃的靈敏度分析之前，先了解幾個定義：定義 線性規(guī)劃的標準形： （） 其中為行向量，均為列向量，為矩陣；，并假設的秩為，在問題（）中，約束方程（1.2）的系數(shù)矩陣的任意一個階滿秩子矩陣（）稱為線性規(guī)劃問題的一個基解或基.這就是說，基矩陣是由矩陣中個線形無關的列向量組成的，不失一般性，可假設并稱為基向量，與基向量相對應的變量稱為基變量不在中的列向量稱為非基向量，與非基變量相對應的變量稱為非基變量，并記，則系數(shù)矩陣可以寫成分塊形式，不失一般性 ， （1.4）將基變量和非基變量組成的向量分別記為，則向量X相應的寫成分塊形式 （1.5）再將（1.5）代入

7、約束方程組（1.2）中，得，由矩陣的乘法可得，又因為是非奇異方陣，所以存在，將上式兩邊乘以，移項后，得現(xiàn)在可以把看作一組自由變量（又稱獨立變量），給他們?nèi)我庖唤M值，則相應的的一組值，于是 便是約束方程組（1.2）的一個解.特別令時，則，現(xiàn)把約束方程組的這種特殊形式的解 ，稱為基本解.滿足變量非負約束條件（1.3）的基本解稱為基本可行解. 現(xiàn)在來研究線性規(guī)劃的靈敏度分析.靈敏度分析的含義是指對系統(tǒng)或事物因為周圍條件變化顯示出來的敏感度.具體說來就是要研究初始單純形表上的系數(shù)變化對最優(yōu)解的影響，研究這些系數(shù)在什么范圍內(nèi)變化時原最優(yōu)基仍然是最優(yōu)的.若原最優(yōu)基不是最優(yōu)的，如何用簡便的方法找到新的最優(yōu)解

8、.現(xiàn)考慮標準形線性規(guī)劃問題：（） 當線性規(guī)劃問題中的一個或幾個參數(shù)變化時，可以用單純形法從頭計算，看最優(yōu)解有沒有變化.但這樣做即麻煩又沒有必要，因為單純形法的迭代過程是從一組基向量變換為另一種基向量，每次迭代都和基變量的系數(shù)矩陣有關，表中每次迭代得到的數(shù)據(jù)只隨基向量的不同選擇而改變，因此可以把個別參數(shù)的變化直接在計算得到的最優(yōu)解的單純形表上反映出來.這樣就不需要從頭計算，而直接在最優(yōu)性單純形表進行審查，看一些數(shù)字變化后，是否仍滿足最優(yōu)性的條件，如果不滿足的話再從這個表開始進行迭代計算，求得最優(yōu)解.可按下表中的幾種情況進行處理：原問題對偶問題結(jié)論或繼續(xù)計算的步驟可行解可行解表中的解仍是最優(yōu)解可行

9、解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進人工變量，編制新的單純形表求最優(yōu)解下面就各個參數(shù)改變后的情況進行討論：一、 價值系數(shù)的變化分析（一）非基變量的價值系數(shù)的變化若非基變量的價值系數(shù)的改變?yōu)?，則變化后的檢驗數(shù)為，0要保持原最優(yōu)基不變，即當變化為后，最終單純形表中這個檢驗數(shù)小于或等于零，即，因此 ，這就確定里在保持最優(yōu)解不變時非基變量的目標函數(shù)，的變化范圍，當超出這個范圍時，原最優(yōu)解將不是最優(yōu)解了.為了求新的最優(yōu)解，必須在原最優(yōu)單純形表的基礎上，繼續(xù)進行迭代以求得新的最優(yōu)解.例1 已知線性規(guī)劃問題的最優(yōu)單純形表如下所示：（表1.1）

10、153400001001/40-13/4011/4-1420020-2101-15100-3/4111/4003/411300-13/40-11/400-1/4-1（）為保持原最優(yōu)解不變，分別求非基變量的系數(shù)的變化范圍（）當變?yōu)?時，求新的最優(yōu)解.解 （i）由圖表可知：，于是由公式知，保持原最優(yōu)解不變，則有 ，當，時，原最優(yōu)解不變.（ii）當時，已經(jīng)超出了的變化范圍，最優(yōu)解發(fā)生了變化，下面來求新的最優(yōu)解.首先求出的檢驗數(shù)：故為換入基，用新的檢驗數(shù)代替原來的檢驗數(shù)，其余數(shù)據(jù)不變，得到新的單純形表，并繼續(xù)迭代得：序號 5534000b 01001/40-13/4011/4-1420020-2101

11、-15100-1/4111/400-3/41 3/40-11/400-1/4-107500-31/811/8-7/8510010-1201/2-1/251750123/80-3/85/8 00-2-3/80-5/8-5/8 表（1.2）由表中可看出已得到新的最優(yōu)解及新的目標函數(shù)最優(yōu)值 .（二）基變量的價值系數(shù)的變化若是基變量的價值系數(shù)，因為，當變?yōu)闀r，就引起的變化，則其中 是矩陣的第行.于是，變化后的檢驗數(shù)為 （j = 1，2，n）若要求最優(yōu)解不變，則必須滿足 （j = 1，2，n）由此可以導出 當時，有 ； 當時，有.因此，的允許范圍是使用此公式時，首先要在最優(yōu)表上查出基變量所在行中的元素，

12、而且只取與非基變量所在列相對應的元素，將其中的正元素放在不等式的左邊，負元素放在不等式右邊，分別求出的上下界.例2 為保持現(xiàn)有最優(yōu)解不變，分別求出例1 中基變量的變化范圍.若當由（0，4，5）改變?yōu)椋?，6，2）時，原最優(yōu)解是否保持最優(yōu)，如果不是，該怎么辦？解 根據(jù)上述公式，利用表（1.1），為使最優(yōu)基變量不變，的變化范圍是即故當時，原最優(yōu)解不變， 現(xiàn)在變?yōu)?，已超出了的允許變化范圍.同樣的，的允許范圍是，即故當時，原最優(yōu)解不變，現(xiàn)在變?yōu)?，也不在的允許變化范圍內(nèi)，當由（0，4，5）變?yōu)椋?，6，2）即變?yōu)?，變?yōu)?，都超過了它們的允許變化范圍，需要求新的最優(yōu)解.為此用變換后的代替，將表（1.

13、2）改成表1.3（I），在繼續(xù)進行迭代求得新的最優(yōu)解，由該表知，已求得最優(yōu)解及目標函數(shù)最優(yōu)值.序號 1236000 0100 1/40-13/401-1/20620020-2101/402100-3/4111/400-3/41-1400-19/2019/200-3/200200-1/21-1/201-1/2063005/413/4101/400100-3/4111/400-3/41-1800-13/2-4-3/200-3/20 從價值系數(shù)的變化的分析中，現(xiàn)可以得到一個特征：最優(yōu)解對目標函數(shù)中的價值系數(shù)的改變不十分靈敏，而對價值系數(shù)的靈敏度分析的應用意義是：企業(yè)可以在不改變資源優(yōu)化分配的前提下，

14、在一定幅度內(nèi)改變價值系數(shù)的值，來積極應對市場挑戰(zhàn).二、 技術(shù)系數(shù)的變化分析由于對價值系數(shù)的分析分為基變量價值系數(shù)和非基變量價值系數(shù)，現(xiàn)也可以按這種方法把對技術(shù)系數(shù)的分析分為兩類：（一）、非基向量列改變?yōu)?這種情況指初始表中的到數(shù)據(jù)改變?yōu)?，而第個列向量在原最終表上是非基向量.這一改變直接影響最優(yōu)單純形表上的第列數(shù)據(jù)與第個檢驗數(shù).最終單純形表上的第j列數(shù)據(jù)變?yōu)?，而新的檢驗數(shù)，若，則原最優(yōu)解仍是新問題的最優(yōu)解.若，則最優(yōu)基在非退化情況下不再是最優(yōu)基.這是，應在原來最優(yōu)單純形表的基礎上，換上改變后的第j列數(shù)據(jù)和，把作為換入變量，用單純形法繼續(xù)迭代.（二）、基向量列改變?yōu)檫@種情況指初始表中的列數(shù)據(jù)改變?yōu)?/p>

15、，而第個列向量在原最終表上是基向量，此時，原最優(yōu)解的可行性和最優(yōu)性都可能遭到破壞，需要重新計算.三、 右端常數(shù)的變化分析右端常數(shù)的變化在實際問題中表明可用資源的數(shù)量發(fā)生變化.當?shù)趥€約束方程的右端常數(shù)由原來的變?yōu)?，其它系?shù)都不變，即初始表上新的限定向量，其中設原最優(yōu)解為，則新的最優(yōu)解為若原最優(yōu)基仍是最優(yōu)的，則新的最優(yōu)解，即其中是的第列，即故 因此，的允許變化范圍是：如果超出上述范圍，則新的解不是可行解.但由于的變化不影響檢驗數(shù)，故仍保持檢驗數(shù)，即 滿足對偶可行性，這時可在原最終表的基礎上，用對偶單純形法繼續(xù)迭代，以求出新的最優(yōu)解.一般來說，當變?yōu)闀r，也可以直接計算，若有，則原最優(yōu)基仍是最優(yōu)基，但

16、最優(yōu)解和最優(yōu)值要重新計算.若不恒大于零，則原最優(yōu)基對于新問題來說不再是可行基，但由于所有檢驗數(shù)，現(xiàn)行的基本解仍是對偶可行的，因此，只要把原最終表的右端列改為，就可用對偶單純形法求解新問題.例3 線性規(guī)劃問題分別分析在什么范圍內(nèi)變化，問題的最優(yōu)基不變.解 先分析的變化，由公式知，使問題最優(yōu)基不變的條件是由此推得 同理由 得，從而. 四、 增加新約束條件的靈敏度分析若在線性規(guī)劃問題中再增加一個新的約束條件，即有，即 （4.1）其中 ，由于增加一個約束，則可行域有可能減小，但不會使可行域增大，因此，若原問題的最優(yōu)解滿足這個新的約束，則在新問題中仍是最優(yōu)解；若原來的最優(yōu)解不滿足這個新約束，那么現(xiàn)再來求

17、新的最優(yōu)解.設原來的最優(yōu)基為，各基向量集中于的前列，最優(yōu)解為對新增加的約束（4.1），引進松弛變量，又因為，則（4.1）式變成 （4.2）顯然，是約束（4.2）的基變量.增加約束后，新的基、及右端向量如下：，對于新增加約束后的新問題，在現(xiàn)行基下對應變量，的檢驗數(shù)是：它與不增加約束時相同.又因為是基變量，故.因此，現(xiàn)行的基本解是對偶可行的，現(xiàn)行基本解是：，若，則現(xiàn)行的對偶可行的基本解是新問題的可行解，即最優(yōu)解.若，則在原來最終解的基礎上增加新約束（4.2）的數(shù)據(jù)，通過矩陣的初等行變換，把原最終表上的各基向量列及新增列化為單位陣，再用對偶單純形法繼續(xù)求解.五、 增加一個新變量的靈敏度分析假設要增加

18、一個非負的新變量，其相應的系數(shù)列向量為，價值系數(shù)為.又知原問題的最優(yōu)解是，顯然，增加這個新變量，對原最優(yōu)解的可行性沒有影響.現(xiàn)計算新的檢驗數(shù)若，則原最優(yōu)解是新問題的最優(yōu)解；若則原最優(yōu)解不再是最優(yōu)解.這時，把加入到原最終表內(nèi)，并以新變量作為換入變量，按單純形法繼續(xù)迭代，即可得到新的最優(yōu)解.六、線性規(guī)劃靈敏度分析的應用線性規(guī)劃靈敏度分析的應用主要是資源條件的應用，而對資源條件的分析的一個重要應用是：“影子價格問題”定義 設線性規(guī)劃對偶問題 （） （） 右端常數(shù)表示第種資源的現(xiàn)有量下面討論增加個單位時所引起的目標函數(shù)最優(yōu)值的變化.設是問題（）的最優(yōu)基，則，當變?yōu)闀r（其余右端常數(shù)不變，并假設這種變化不

19、影響最優(yōu)基）目標函數(shù)最優(yōu)值變?yōu)椋谑悄繕撕瘮?shù)最優(yōu)值的改變量為，由上式可以看出的意義，它表示當右端常數(shù)增加個單位時所引起的目標函數(shù)最優(yōu)值的改變量，也可以寫成，即表示對的變化率.在一對對偶問題（）和（）中，若（）的某個約束條件的右端常數(shù)增加個單位時所引起的目標函數(shù)最優(yōu)值的改變量稱為第個約束條件的影子價格，又稱邊際價格.由定義可知，影子價格的經(jīng)濟意義是在其它條件不變的情況下，單位資源變化所引起的目標函數(shù)最優(yōu)值的變化，即對偶變量就是第個約束條件的影子價格.影子價格是針對某一具體的約束條件而言的.而問題中所有其它數(shù)據(jù)保持不變，因此影子價格也可以理解為目標函數(shù)最優(yōu)值對資源的一階偏導數(shù).影子價格又稱靈敏度系

20、數(shù)，通常指線性規(guī)劃對偶模型中對偶變量的最優(yōu)解.如果原規(guī)劃模型屬于一定資源約束條件下，按一定的生產(chǎn)消耗生產(chǎn)一組產(chǎn)品并需求總體效益目標最大化問題，那么其對偶模型屬于對本問題中每一資源以某種方式進行估價，以便得出與最優(yōu)生產(chǎn)計劃相一致的一個企業(yè)最低總價值.該對偶模型中資源的估價表現(xiàn)為相應資源的影子價格.影子價格在經(jīng)濟管理中的應用很多，下面就下面這個問題進行分析：影子價格指示企業(yè)內(nèi)部挖掘潛力的方向.設線性規(guī)劃模型（）：存在最優(yōu)解.對（）標準化后，得： 其中，0是m維行向量， 為單位陣.因為設（）有最優(yōu)解，故由線性規(guī)劃單純形法求解，可得最優(yōu)基，最優(yōu)解為： ，并可設所以可令，即 因此，有 （6.1）再令，由

21、單純形法最優(yōu)原則可知： （6.2）即因此，有 （6.3）而由（6.2），（6.3）及線性規(guī)劃的對偶結(jié)構(gòu)可知：是對偶問題的可行解.再由（6.1）及對偶定理可知：是對偶問題的最優(yōu)解.可見，最優(yōu)解的不起作用約束的影子價格為零.反之就是，若影子價格，則對應的是的起作用約束.因此，影子價格表示第種資源未得到充分利用；而則表示第種資源已得到充分利用.影子價格直接應用到企業(yè)資源最有效的部門中去.當影子價格大于資源的市場價格時，企業(yè)應購進這種產(chǎn)品，使利潤增加；當當影子價格小于資源的市場價格時出現(xiàn)多做多賠的情形，應出售這種資源.大公司還可借助資源的影子價格確定一些內(nèi)部結(jié)算價格，以便控制有限資源的使用和考核下屬企

22、業(yè)經(jīng)營的好壞.又如在社會上對一些緊缺資源，借助影子價格規(guī)定使用這種資源企業(yè)必須上繳的利潤額，以控制企業(yè)自覺地節(jié)約使用緊缺資源，使有限資源發(fā)揮更大經(jīng)濟效益.“影子價格問題”：影子價格 設線性規(guī)劃模型（） 有最優(yōu)解，最優(yōu)解為則可令則必有和 存在最優(yōu)解.對（）標準化后，得 其中（為松弛變量，是維列變量），,這里是維行向量，而為單位陣.因為設（）有最優(yōu)解，故由線性規(guī)劃單純形法求解，可得最優(yōu)基可行解，最優(yōu)解為： 并可設 ，所以可令 ，即，因此有 （6.4）再令 由單純形法最優(yōu)準則可知      （6.5）即 因此有 (6.6)而由(6.5)和(6.6)，由線性規(guī)劃

23、的對偶規(guī)劃結(jié)構(gòu)可知：是對偶規(guī)劃的可行解，再由(6.4)，以及對偶定理可知：是對偶規(guī)劃的最優(yōu)解.）稱為第種資源的影子價格，為影子價格向量.表示，第種資源對最優(yōu)值的邊際貢獻. 從線性規(guī)劃對偶理論易見，影子價格就是對偶規(guī)劃的最優(yōu)解.而由前述對資源條件的靈敏度分析可知，對于最優(yōu)解 的不起作用約束而言，若此約束的資源條件在靈敏度范圍內(nèi)變動時，則最優(yōu)值不變，所以可見，最優(yōu)解的不起作用約束的影子價格為零。反之而言就是，若影子價格，則對應的是的起作用約束。因此，影子價格表示第種資源未得到充分利用；而則表示第種資源已得到完全利用影子價格直接應用到企業(yè)資源的最有效利用中去.當影子價格大于資源的市場價格時，企業(yè)應購

24、進這種產(chǎn)品，使利潤增加；當影子價格小于市場價格時，出現(xiàn)多做多賠的情形，應出售這種資源.大公司還可借助資源的影子價格確定一些內(nèi)部結(jié)算價格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞.又如在社會上對一些緊缺資源，借助影子價格規(guī)定使用這種資源單位必須上繳的利潤額，以控制企業(yè)自覺地節(jié)約使用緊缺資源，使有限資源發(fā)揮更大經(jīng)濟效益.七、線性規(guī)劃靈敏度分析在經(jīng)濟與管理問題上的典型應用一般應用問題的線性規(guī)劃模型為：                   

25、;     其中 ,    線性規(guī)劃的靈敏度分析有兩個主要方面：     第一、對價值系數(shù)的靈敏度分析 在資源條件不變的前提下，問最優(yōu)解保持不變時，每個價值系數(shù)可以變動的范圍.    第二、對資源條件的靈敏度分析 在價值系數(shù)不變的前提下，問最優(yōu)解保持不變時，每個資源條件可以變動的范圍.線性規(guī)劃的靈敏度分析有重要的經(jīng)濟與管理的應用背景，現(xiàn)通過一個例子來了解有關的概念.現(xiàn)來考慮公司的例子. 公司在一周內(nèi)只生產(chǎn)兩種產(chǎn)品：產(chǎn)品和.產(chǎn)品和產(chǎn)品由多種材料混合生成，這些

26、材料都從倉庫中提取.可供一周使用的三種原料數(shù)量如下： 原料1        原料2 原料3     產(chǎn)品由的原料1和的原料2制成,產(chǎn)品由的原料1，的原料2和的原料3制成. 產(chǎn)品的邊際貢獻率為每公斤25元，產(chǎn)品的邊際貢獻率為每公斤10元.管理部門必須決定每種產(chǎn)品各生產(chǎn)多少公斤，使得在原料供應計劃下產(chǎn)品的總貢獻最大.這個決策問題的線性規(guī)劃模型為：           貢獻=25+10  &#

27、160;         其中 ，    應用圖解法解此線性規(guī)劃問題，可見下圖 ：                    (圖1.0)本例的最優(yōu)解為：，八、從求解例題的圖解法揭示了最優(yōu)解的一些重要特征特征1 最優(yōu)解對目標函數(shù)中的價值系數(shù)（）的改變不是十分靈敏以上例來說，對于公司，在保持（，）仍為最優(yōu)解的前提下

28、，如果現(xiàn)增加產(chǎn)品的貢獻，目標函數(shù)的斜率會變得越來越?。繕撕瘮?shù)線變得更加垂直）.（圖1.0）表明，最終目標函數(shù)將會達到一個與約束條件2平行的斜率.那時，最優(yōu)解即是包括從當前頂點到頂點（，）的線段上的所有點.運用下面的代數(shù)方法，現(xiàn)能計算出這時的單位貢獻為每公斤40元 (元)現(xiàn)可得到結(jié)論：若的單位貢獻為美元到美元之間（B的單位貢獻保持10美元不變），產(chǎn)生最大貢獻的最優(yōu)解始終是生產(chǎn)的產(chǎn)品和產(chǎn)品.注意如果產(chǎn)品的單位貢獻恰好增加至美元，不僅頂點（，）和（，）為最優(yōu)解，在約束條件2上連接這兩點的線段上的所有點也都為最優(yōu)解，即：有無窮多最優(yōu)解.(圖1.0)說明系數(shù)的靈敏度分析的應用意義是：企業(yè)可以在不改變資源優(yōu)化分配的前提下，在一定的幅度內(nèi)改變價值系數(shù)的值，來積極對市場挑戰(zhàn).特征2 對于一個線性規(guī)劃問題，最優(yōu)解有兩種類型的約束條件：起作用約束和不起作用約束最優(yōu)解的起作用的約束是指線性規(guī)劃的約束方程中，使最優(yōu)解以等式方式滿足的約束方程，也稱為最優(yōu)解的緊約束.在圖形上，