1、第四章 靈敏度分析與參數規劃前面的假設 前幾章討論線性規劃問題時，總是假設是不變的常數不變的常數 但實際上這些數據往往是根據以往資料，或估計值、或預測值，不可能很精確不可能很精確，而且隨著情況的變化，這些數據也會經經常發生變化常發生變化實際的情況面對市場經濟： 價格的波動價格的波動會引起價值系數價值系數的變化； 工藝的改進工藝的改進引起消耗系數消耗系數的變化； 資源儲量的變化資源儲量的變化會引起右端常數右端常數的變化； 增加新產品增加新產品會引起決策變量決策變量的增加； 增加新的資源限制增加新的資源限制會引起約束條件約束條件的增加等等。三個問題 當這些數據中有一個或幾個發生變化時，已求得的線性

2、規劃問題的最優解會有什最優解會有什么變化么變化？ 這些數據在什么范圍內變化什么范圍內變化時，已求得的線性規劃問題的最優解或最優基不變最優基不變？ 若原最優基不再是最優基，如何在先前優化的基礎上迅速求得新的最優方案迅速求得新的最優方案？靈敏度分析 以上三個問題正是靈敏度分析所要討論的問題 靈敏度分析（Sensitivity analysis） 又稱為優化后分析（Post-optimality analysis） 因為它是在已求得線性規劃最優解的基在已求得線性規劃最優解的基礎上礎上，來討論這些數據的變化對最優解討論這些數據的變化對最優解的影響的影響參數規劃 參數規劃問題 Parametric Pr

3、ogramming 研究當某些數據是某一個參數的線性函當某些數據是某一個參數的線性函數時數時，該參數的連續變化對線性規劃問該參數的連續變化對線性規劃問題最優解的影響題最優解的影響目錄1 靈敏度分析的基本原理基本原理2 目標函數系數的目標函數系數的靈敏度分析3 右端常數的右端常數的靈敏度分析4 技術系數的技術系數的靈敏度分析5 參數線性規劃參數線性規劃1 靈敏度分析的基本原理 當其中的某些數據發生變化時，就可能使這個最優解或最優基發生變化靈敏度分析的任務任務 研究這些數據的變化這些數據的變化對最優解或最優基對最優解或最優基的影響的影響優化后分析 因為它是在已求得最優解的基礎上在已求得最優解的基礎

4、上進行分析靈敏度分析的理論依據理論依據 就是看條件是否仍成立就是看條件是否仍成立靈敏度分析所研究的問題所研究的問題 為了保持現有的最優解或最優基不變，找出這些數據變化的范圍，即所謂數據數據的穩定性區間的穩定性區間 當這些數據的變化超出了范圍時，如何在原有最優解或最優基的基礎上，作微小的調整，盡快求出新的最優解盡快求出新的最優解或最優基單純形法的優點優點 某些數據只和表中的某些塊有關某些數據只和表中的某些塊有關，因而當這些數據發生變化時，只需對上表中只需對上表中的某些塊進行修改的某些塊進行修改，便可得到新問題的單純形表，從而能夠進行判別和迭代，而不必從頭開始計算不必從頭開始計算線性規劃問題發生變

5、化的對象在實際問題中，下面這些數據或條件是會經常發生變化的： 目標函數系數目標函數系數的變化； 右端常數右端常數的變化； 消耗系數消耗系數的變化 包括增加新的變量新的變量 增加新的約束條件新的約束條件2 目標函數系數的靈敏度分析 目標函數系數的變化目標函數系數的變化會引起檢驗數的變檢驗數的變化化，從而影響最優性條件最優性條件是否成立分情況討論 可分為對應的是非基變量的系數是非基變量的系數或基變基變量的系數量的系數兩種情況來討論2.1 非基變量的價值系數非基變量的價值系數的變化 這就是保持原最優解不變時，基變量的基變量的目標系數的變化范圍目標系數的變化范圍 當超出這個范圍時，原最優解將不再是最優

6、解了， 為了求新的最優解，必須在原最優單純形表的基礎上，繼續往下迭代以求得新的最優解例1 為保持現有最優解不變，分別求非基變量x1,x3的系數c1,c3的變化范圍 當c1變為5時，求新的最優解53/42.2 基變量的價值系數基變量的價值系數的變化BrCc 怎么記？怎么記？ 首先，要在最優表上查出基變量xr所在行中的元素arj 然后，只取與非基變量非基變量所在列相對應的元素，將其中的正元素放在不等式左邊，負元素放在不等式右邊， 最后，分別求出cr的上下界然后，只取與非基變量非基變量所在列相對應的元素，將其中的正元素放在不等式左邊，負元素放在不等式右邊，Why?NBCCBNN1基變量xr的價值系數

7、Cr的變化引起CB的變化，從而導致所有非基變量的檢驗數發生變化。 的變化超出此范圍時，破壞了基B的對偶可行性，此時可用單純形法繼續迭代例2 為保持現有最優解不變分別求例1中基變量x2,x4的變化范圍，并問當CB由(0,4,5)改變為(0,6,2)時，原最優解是否仍然保持最優？如果不是，該怎么辦？注意！注意！進基出基法則不能絕對化！進基出基法則不能絕對化！3 右端常數的右端常數的靈敏度分析 右端常數 bi的變化，和B-1、A、C不相關，沒有變化， 會影響到原最優解的可行性最優解的可行性與目標函數目標函數值值怎么記？怎么記？ 當br在此范圍內變化時，基B的最優性雖然仍可保持，但最優解中基變量的值最

8、優解中基變量的值和目標函數值目標函數值同時改變 當br變化超出范圍時，必須破壞基B的可行性，可用對偶單純形法對偶單純形法繼續迭代 首先，要在最優表中查出最優基最優基 B的逆的逆矩陣矩陣 （它就在與初始表中單位矩陣初始基相對應的位置 其次，將B-1的第的第r列列中的正元素放在不等式左邊，負元素放在不等式右邊 最后，再按公式求出br的上下界例1在上一節例l中 為保持現有最優解不變，分別求b1,b2,b3的允許變化范圍 如果b3減少150，驗證原最優解是否可行？如果不可行，求出改變后的最優解及最優值 這是因為在B-1中的第l列只有一個非零元素1，故上界無限制4 技術系數的靈敏度分析 4.1 個別技術

9、系數的變化 4.2 增加新變量的靈敏度分析 新產品 4.3 增加新約束條件的靈敏度分析 增加一道工序4.1 個別技術系數的變化 根據變動的系數aij處于矩陣A中的哪一列又可分為兩種情況來考慮：一是aij處于非基變量列中；二是aij處于基變量列中 非基變量xj的系數列向量Pj的變化 基變量xj的系數列向量Pj的變化1. 非基變量xj的系數列向量Pj的變化?0iy 非基變量的技術系數的變化，僅影響基B地對偶可行性，不影響B的可行性2基變量xj的系數列向量Pj的變化例1上一節例1 為保持現有最優解不變，分別求非基變量x1,x3的系數的變化范圍； 若非基變量x1 的系數由(1,3,5)T變為(1,4,

10、1)T，考察原最優解是否仍然保持最優？若不是，該怎么辦？例2 在 上一節例 1中，若基變量x2的技術系數列向量由 P2=(3,4,4)T變為 P2=(4,5,6)T，而它在目標函數中的系數由c2=5變為c2=6試求變化后的最優解 并不是一個正規的單純形表，因為沒有單位矩陣為了得到一個單位矩陣，注意到x2仍為第3個基變量，故必須將x2 所在列變成單位列向量，同時將2=-7/2變為0，即以a32=9/4為主元進行矩陣的初等變換（這種變換沒有換基， x2 仍為基變量)不換基！不換基！ 若基變量系數的變化導致原始可行性條件和對偶可行性條件均被破壞，即產生了對原問題和對偶問題均為非可行解時，這就需要引入

11、人工變量重新求解，或者用第三章中介紹的求初始正則解的方法求解這里就不詳細討論了4.2 增加新變量的靈敏度分析建模時漏掉了建模時漏掉了例3 在上一節例1中新增一個決策變量由（相當于生產計劃中增加一種新產品）已知價值系數c8=7，技術系數P8=(3,2,5)T問該產品是否值得投產？如果值得投產，求新的最優解4.3 增加新約束條件的靈敏度分析 具體作法是在原最優單純形表上增加一行和一列，增加的行中以xn+1（松弛變量）為基變量，并在變量又下面填入am+1,j(j=1,2,n) ,增加的列Pn+1是一個單位列向量它的最下面的一個元素為1，其余元素均為0（包括n+1=0)這樣增加一行以后，可能破壞了原最

12、優表上的單位矩陣（最優基)要用矩陣的初等行變換將原單位矩陣恢復然后再繼續迭代求解例4 在上一節例1中增加一個新的約束條件，問原最優解是否仍然保持？若不能，則求出新的最優解 事實上，并不是一張正規單純形表，因為將新約束條件的系數填入基變量x8所在的行以后，破壞了原來的單位矩陣（最優基).為了恢復原來的單位矩陣，需要用矩陣的初等行變換將單位列向量中新出現的非零元素變為零，這樣得表 將最優解代入，判斷是起作用約束，還是不起作用約束 增加等式約束條件，一般地將使約束矩陣A的秩增加，故需增加基變量顯然，增加一個不等式約束也可以看作是增加一個等式約束，但是，此時引入的松弛變量正好成為基變量，故可立即得到新問題的一個正則解而增加一個等式約束時，沒有明顯的可添加的基變量，故需引入人工變量xn+1作為基變量，再用大M法或兩階法將它剔除增加等式約束與不等式約束 增加等式約束R(A)增大需要增加基變量沒有明顯的可增加的基變量引入人工變量作為基變量再用大M法或兩階段法 增加不等式約束R(A)增大需要增加基變量引入的松弛變量正好成為基變量立即得到新問題的一個正則解例5 綜合實例本章小結考察數據變化對現行最優方案的影響，實際上考查對基B最優性的影響。因此，可考慮