1、第五章 線性規劃問題的靈敏度分析什么是靈敏度分析？ 研究線性規劃模型某些參數或限制量的變化對最優解的影響及其程度的分析過程稱為靈敏度分析（優化后分析）。靈敏度分析研究內容： 目標函數系數的變化對最優解的影響； 約束方程右端系數的變化對最優解的影響； 約束方程組系數矩陣的變化對最優解的影響。需要關注兩個問題：這些系數在什么范圍內波動將不影響最優解或最優基？若最優解發生變化，應如何用最簡單的方法找到新的最優解。為討論方便，以下列出標準型線性規劃問題最優單純形表的一般形式，其中B為線性規劃問題的最優基：cjc1 c2 cn cB cB b x1 x2 xn cB1 xB1 B-1b B-1A=B-1

2、(P1，P2，Pn) cB2 xB2 : : cBm xBm cj-zjc-cBB-1A 第一節 邊際值及其應用邊際值第i種資源的邊際值是將一單位的第i行約束條件方程所代表的資源從現在用途中抽出來而使利潤減少的數字，用qi表示。將一單位的第i個約束條件方程所表示的資源從現在的用途抽出，意味著使第i個約束條件方程的松弛變量xn+i增加一個單位。xn+i增加一單位而損失利潤 ，所以有qi =zn+i單純形表中第i種資源的邊際值qi等于該表中第i行約束條件方程的松弛變量xn+i的機會費用。1n iBn izc B P11mjiijBjizc ac BP 1mjijiiza q為了生產一個單位的xj必

3、須消耗aij個單位的第i行約束條件方程對應的資源i，及需將aij個單位的第i種資源從現有用途中抽出，此時損失的利潤為aijqi，zj可直接用下式表示機會費用zj12341234123412341234max534232800(1)54341200(2). .34531000(3),0zxxxxxxxxxxxxs txxxxxxxx資 源資 源資 源令x5,x6,x7分別為資源1，2，3的松弛變量，下表給出此問題的最優解。在一定范圍內，資源i增加1單位，利潤增加qi，資源2增加1單位，利潤增加1/4元，資源3增加一單位，利潤增加1元，資源1增加1單位，利潤不增加。 例例1 1 增加新變量的靈敏度

4、分析增加新變量的靈敏度分析增加一個新變量，相當于系數矩陣A增加一列，這種在現實的管理中經常發生，例如經過調查研究，獲得某一種新產品的消耗系數和價格等參數，如何決定該產品是否值得投入生產。設新增的變量為xN，它對應的價值系數為cN，消耗各種資源的單位消耗系數為ai,N,即在系數矩陣A中增加的系數列向量為PN=(a1,N, a2,N, am,N)T,則把xN看成非基變量，在原來的最優單純形表中增加一列，系數向量為 （ 5-1 ）11,2,(,)TNNNNm NPB Paaa非基變量的技術系數的變化將會影響其最優性，則非基變量xN的檢驗數 （ 5-2 ）若 則原問題最優解不變，說明增加這種新產品不能

5、使原最優目標函數值得到改進，所以增加該新產品不利；反之， ，則原問題最優解變化，生產該新產品有利，其新的最優解可將式（ 5-2 ）加入原最優單純形表繼續迭代求解。例2 建議增加一新產品，設產量為xN，PN=(5,4,3)T，cN=9，問該產品是否值得投產？已知a18=5, a28=4 a38=3,c8=9,由最優單純形表知q1=0, q2=1/4, q3=1.z8=5*0+4 *()+3*1=4c8-z8=9-4=50所以該產品值得生產。1NNBNcc B P0N0N10NNNmNiNiiczzaq第第2節節 價值系數價值系數 cj 的靈敏度分析的靈敏度分析cj變動可能由于市場價格的波動，或生

6、產成本的變動cj的靈敏度分析是在保證最優解的基變量不變的情況下，分析cj 允許的變動范圍cj cj的變化會引起檢驗數的變化，有兩種情況：非基變量對應的價值系數變化，只影響 一個檢驗數基變量對應的價值系數變化，影響所有非基變量檢驗數j1 1、非基變量、非基變量x xj的價值系數的靈敏度分析的價值系數的靈敏度分析 若xj為非基變量，則cj的變化僅影響xj對應的檢驗數。當cj變化為cj +cj 后，為使最優解基變量及其取值不變，xj對應的檢驗數滿足 = ()0 ()jjjjjjjcczccz 即 例例3 3 設有以下線性規劃問題設有以下線性規劃問題: :12341234123412341234max

7、534232800(1)54341200(2). .34531000(3),0zxxxxxxxxxxxxs txxxxxxxx資 源資 源資 源1313,1311,44xxcc 為 非 基 變 量所 以令x5,x6,x7分別為資源1，2，3的松弛變量，下表給出此問題的最優解若超出穩定范圍，非基變量的檢驗數 ，當前解已不是最優解。此時必須以修改后的單純形表出發，重新進行單純形迭代，直至求出新的最優解。jx0j2、基變量基變量x xj對應的價值系數的靈敏度分析對應的價值系數的靈敏度分析由于基變量xj對應的價值系數cj在cB中出現，它會影響所有非基變量的機會費用和檢驗數。設xj為第r個約束方程對應的

8、基變量，SN為非基變量下標的集合。當cj變化為cj +cj 時，則cB變化為cB+cB,其中非基變量xk的檢驗數應滿足10(0,0,0,0)Bjrcc 個11111010()0()(0,0,0,0)(0,0,0,0)00,min0,0,maxkBBkkBBkkBkjkrkkjkkkjrkrjrkkkkkrkjrkNrkrkjcccBPcccBPcc BPcBPczcPczc ac aczczacakSaac 個個即若若0,kkrkNrkczakSa 12kkkrkmkaaPaa max0,min0,kkkkrkNjrkNrkrkczczakScakSaa 其中xj為第r個約束條件對應的基變量。

9、 時，cj的變化的不影響zk；因基變量的檢驗數始終為0，故不考慮基變量。由上兩式可知， cj 變動的上下限為：0rka 例例4 4 在最優表中，被檢驗基變量所在的行。在最優表中，被檢驗基變量所在的行。對對x4的價值系數的價值系數c4的的靈敏度分析，靈敏度分析，x4的價值系數增加的價值系數增加 c4，對應，對應r=2441311111444maxmin121214cc ，即221113111444maxmin1113313444cc ， 即對對x2的價值系數的價值系數c2的的靈敏度分析，靈敏度分析，x2的價值系數增加的價值系數增加 c2，對應，對應r=3對bi值的靈敏度分析，就是求最優解基變量保

10、持不變但基變量的取值可以變動的條件下bi的變動范圍。bi的變化僅影響基變量的取值，在bi的允許變動范圍內，新解的基變量的取值要滿足非負約束。若有基變量不滿足非負約束，就說明bi的變動超出了靈敏度的范圍。第第3節節 右端項右端項 bi 的靈敏度分析的靈敏度分析設 xB=B1b 是最優解，則有xB=B1b0b 的變化不會影響檢驗數b 的變化量 b 可能導致原最優解變為非可行解在將“”形式的約束條件方程轉化為“=”形式時，對第i行的約束條件方程的左端加一個松弛變量xn+i，最優解表中B-1可表示為1,11,21,2,12,22,1,1,2,nnn mnnn mm nm nm n maaaaaaBaa

11、a令資源k的數量bk的變化數量為bk，其他系數不變，新解基變量的取值為其中為保證最優解的基變量不發生變化，必須滿足1()NBxBbb10(0,0,0,0)Tkkbb 個0NBx11111,1122,221,()0000NBkn kkn kkn kkmkm n kmmxBbbB bBbbb abbbb abbBb Pbbb abb由此可得 即由此可得此時，基變量的解值和目標函數值會發生變化其中,01,2,iki n kbb aim,1,2,ki n kib abim ,0ii nkki nkbaba若則,0ii nkki nkbaba若則,max0,1,2,min0,1,2,iii n kki

12、n ki n ki n kbbaimbaimaa 0Nkn kxxb P0Nn kn kxxPx新的解向量；原來的解向量；在最優單純形表中對應的列向量。以b2為例, x6是對應的初始基變量(松弛變量），所以有.222100200100m ax,m in1 41344002003400010003bbb /資源2降低到1000或增加到4000/3,最優解的基變量不變；在這個范圍內增加或減少任何數目的資源2，它的邊際值都是0.25，如果能多獲得100單位的資源2，每單位資源2都可使利潤增加0.25元，總利潤增加25元。取 原來最優解x0=(100,200,100)T2100b 5421001/ 4

13、12520010013001003/ 425NNNNxxxx總利潤為1325，比原來增加25元。6Tn kPP （1/4,1,-3/4）技術系數aij變化的影響比較復雜對應基變量的 aij ，且資源bi已全部用完對應基變量的 aij ，但資源bi未用完 對應非基變量的 aij ，且資源bi全用完或未用完第四節第四節 技術系數技術系數 aij 的靈敏度分析的靈敏度分析1、對應基變量的 aij ,且資源bi已全部用完 aij=0 資源i全部用完，若aij0,即單位產品j消耗的資源i增加，原有資源i就不夠用，原來的解不再是可行解，必須有aij0； 若aij0,則節約下來的資源可移作他用，資源已經用完，即松弛變量xn+i=0為非基變量，其檢驗數為負數，xn+i為正數，資源i的邊際值為正數，節約下來的資源可增加利潤，現行最優解不再是最優解,不能有aij0，就減少松弛變量xn+i ，