靈敏度分析與參數(shù)規(guī)劃

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

2、規(guī)劃問題的最優(yōu)解會(huì)有什最優(yōu)解會(huì)有什么變化么變化？ 這些數(shù)據(jù)在什么范圍內(nèi)變化什么范圍內(nèi)變化時(shí)，已求得的線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變最優(yōu)基不變？ 若原最優(yōu)基不再是最優(yōu)基，如何在先前優(yōu)化的基礎(chǔ)上迅速求得新的最優(yōu)方案迅速求得新的最優(yōu)方案？靈敏度分析 以上三個(gè)問題正是靈敏度分析所要討論的問題 靈敏度分析（Sensitivity analysis） 又稱為優(yōu)化后分析（Post-optimality analysis） 因?yàn)樗窃谝亚蟮镁€性規(guī)劃最優(yōu)解的基在已求得線性規(guī)劃最優(yōu)解的基礎(chǔ)上礎(chǔ)上，來討論這些數(shù)據(jù)的變化對(duì)最優(yōu)解討論這些數(shù)據(jù)的變化對(duì)最優(yōu)解的影響的影響參數(shù)規(guī)劃 參數(shù)規(guī)劃問題 Parametric Pr

3、ogramming 研究當(dāng)某些數(shù)據(jù)是某一個(gè)參數(shù)的線性函當(dāng)某些數(shù)據(jù)是某一個(gè)參數(shù)的線性函數(shù)時(shí)數(shù)時(shí)，該參數(shù)的連續(xù)變化對(duì)線性規(guī)劃問該參數(shù)的連續(xù)變化對(duì)線性規(guī)劃問題最優(yōu)解的影響題最優(yōu)解的影響目錄1 靈敏度分析的基本原理基本原理2 目標(biāo)函數(shù)系數(shù)的目標(biāo)函數(shù)系數(shù)的靈敏度分析3 右端常數(shù)的右端常數(shù)的靈敏度分析4 技術(shù)系數(shù)的技術(shù)系數(shù)的靈敏度分析5 參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃1 靈敏度分析的基本原理 當(dāng)其中的某些數(shù)據(jù)發(fā)生變化時(shí)，就可能使這個(gè)最優(yōu)解或最優(yōu)基發(fā)生變化靈敏度分析的任務(wù)任務(wù) 研究這些數(shù)據(jù)的變化這些數(shù)據(jù)的變化對(duì)最優(yōu)解或最優(yōu)基對(duì)最優(yōu)解或最優(yōu)基的影響的影響優(yōu)化后分析 因?yàn)樗窃谝亚蟮米顑?yōu)解的基礎(chǔ)上在已求得最優(yōu)解的基礎(chǔ)

4、上進(jìn)行分析靈敏度分析的理論依據(jù)理論依據(jù) 就是看條件是否仍成立就是看條件是否仍成立靈敏度分析所研究的問題所研究的問題 為了保持現(xiàn)有的最優(yōu)解或最優(yōu)基不變，找出這些數(shù)據(jù)變化的范圍，即所謂數(shù)據(jù)數(shù)據(jù)的穩(wěn)定性區(qū)間的穩(wěn)定性區(qū)間 當(dāng)這些數(shù)據(jù)的變化超出了范圍時(shí)，如何在原有最優(yōu)解或最優(yōu)基的基礎(chǔ)上，作微小的調(diào)整，盡快求出新的最優(yōu)解盡快求出新的最優(yōu)解或最優(yōu)基單純形法的優(yōu)點(diǎn)優(yōu)點(diǎn) 某些數(shù)據(jù)只和表中的某些塊有關(guān)某些數(shù)據(jù)只和表中的某些塊有關(guān)，因而當(dāng)這些數(shù)據(jù)發(fā)生變化時(shí)，只需對(duì)上表中只需對(duì)上表中的某些塊進(jìn)行修改的某些塊進(jìn)行修改，便可得到新問題的單純形表，從而能夠進(jìn)行判別和迭代，而不必從頭開始計(jì)算不必從頭開始計(jì)算線性規(guī)劃問題發(fā)生變

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

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

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

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

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

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

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

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