運(yùn)籌學(xué) 第二章 靈敏度分析課件

1、第二章第二章 線性規(guī)劃的線性規(guī)劃的靈敏度分析靈敏度分析在根據(jù)一定數(shù)據(jù)求得最優(yōu)解后，當(dāng)這些數(shù)據(jù)中某在根據(jù)一定數(shù)據(jù)求得最優(yōu)解后，當(dāng)這些數(shù)據(jù)中某一個或某幾個發(fā)生變化時，對最優(yōu)解會產(chǎn)生什么影響。一個或某幾個發(fā)生變化時，對最優(yōu)解會產(chǎn)生什么影響?；蛘哒f，要使最優(yōu)解保持不變，各個數(shù)據(jù)可以有多大或者說，要使最優(yōu)解保持不變，各個數(shù)據(jù)可以有多大的幅度的變動。這種研究線性規(guī)劃模型的原始數(shù)據(jù)變的幅度的變動。這種研究線性規(guī)劃模型的原始數(shù)據(jù)變化對最優(yōu)解產(chǎn)生的影響就叫做線性規(guī)劃的靈敏度分析?；瘜ψ顑?yōu)解產(chǎn)生的影響就叫做線性規(guī)劃的靈敏度分析。這些系數(shù)在什么范圍內(nèi)發(fā)生變化時，最優(yōu)基不變（即最這些系數(shù)在什么范圍內(nèi)發(fā)生變化時，最優(yōu)基

2、不變（即最優(yōu)解或最優(yōu)解結(jié)構(gòu)不變）？優(yōu)解或最優(yōu)解結(jié)構(gòu)不變）？系數(shù)變化超出上述范圍時，如何用最簡便的方法求出新系數(shù)變化超出上述范圍時，如何用最簡便的方法求出新的最優(yōu)解？的最優(yōu)解？回答兩個問題：回答兩個問題：例例1.1 max z = 300 x1 + 500 x2 x1 4 s.t. 2x2 12 3x1 + 2x2 18 x1, x2 0下列模型中，對最優(yōu)值有影響的因素有哪些？ 靈敏度分析的內(nèi)容靈敏度分析的內(nèi)容（單個變化和多個變化）目標(biāo)函數(shù)系數(shù)目標(biāo)函數(shù)系數(shù) 變化的靈敏度分析變化的靈敏度分析jc約束右端值約束右端值 變化的靈敏度分析變化的靈敏度分析ib（單個變化和多個變化）約束條件系數(shù)約束條件系數(shù)

3、 變化的靈敏度分析變化的靈敏度分析ija約束條件數(shù)量變化的靈敏度分析約束條件數(shù)量變化的靈敏度分析變量變量 變化的靈敏度分析變化的靈敏度分析jx2.2 單個目標(biāo)函數(shù)系數(shù)變化的靈敏度分析單個目標(biāo)函數(shù)系數(shù)變化的靈敏度分析jc只有一個系數(shù)只有一個系數(shù) 發(fā)生變化，即其他條件均不變，把發(fā)生變化，即其他條件均不變，把 300 改成改成 500jc12121212max3005004212. .3218,0zxxxxstxxx x12121212max5004212. .3218,0500zxxxxstxxx x最優(yōu)解沒有改變最優(yōu)解沒有改變用用Excel求解求解2.2.1 敏感性報告敏感性報告幾個基本概念幾個

4、基本概念遞減成本：遞減成本： 它的絕對值表示目標(biāo)函數(shù)中決策變量的系數(shù)必須改進(jìn)多少，才能得到該決策變量的正數(shù)解。0表示不需再改進(jìn)。表示不需再改進(jìn)。目標(biāo)式系數(shù)：目標(biāo)式系數(shù)： 指目標(biāo)函數(shù)中的系數(shù)允許增量、允許減量：允許增量、允許減量：表示目標(biāo)函數(shù)中的系數(shù)在允許的增量與減量范圍內(nèi)變化時，原問題的最優(yōu)解不變。450450和和1E+301E+30的含義是什么？的含義是什么？2.2.2 圖解法圖解法 2x1x2 4 6 82468 71531753可行域c1=0(z=0 x1+500 x2)c1=750(z=750 x1+500 x2)c1=300(z=300 x1+500 x2)0=c1=7502.3 多

5、個目標(biāo)函數(shù)系數(shù)同時變化多個目標(biāo)函數(shù)系數(shù)同時變化多個系數(shù)多個系數(shù) 發(fā)生變化，即其他條件均不變，把發(fā)生變化，即其他條件均不變，把300改成改成450，把把500改成改成400jc12121212max3005004212. .3218,0zxxxxstxxx x12121212max4212. .3218,0450400zxxxxstxxx x最優(yōu)解沒有改變最優(yōu)解沒有改變 敏感性報告敏感性報告不能反映多個目標(biāo)函數(shù)系數(shù)改變時帶來的影響不能反映多個目標(biāo)函數(shù)系數(shù)改變時帶來的影響 敏感性報告敏感性報告百分之百法則百分之百法則p定義定義 如果目標(biāo)函數(shù)系數(shù)同時變化，計算出每一系數(shù)變化量占該系數(shù)允許變化量的百分

6、比，然后將各個系數(shù)變化的百分比相加。 如果所得的變化的百分比總和不超過如果所得的變化的百分比總和不超過100%，則最優(yōu)，則最優(yōu)解不會改變；如果超過了解不會改變；如果超過了100%，則不能確定最優(yōu)解，則不能確定最優(yōu)解是否改變，可通過重新運(yùn)行是否改變，可通過重新運(yùn)行“規(guī)劃求解規(guī)劃求解”命令來判命令來判斷斷 敏感性報告敏感性報告百分之百法則百分之百法則p作用作用 1. 可用于確定在保持最優(yōu)解不變的條件下，目標(biāo)函數(shù)系數(shù)的變化范圍； 2. 百分之百法則通過將允許的增加量或減少量在各個系數(shù)之間進(jìn)行分?jǐn)?，從而可以直接顯示出每個系數(shù)允許的變化值； 3. 線性規(guī)劃求解后，如果將來條件變化，致使目標(biāo)函數(shù)中一部分或

7、所有系數(shù)都發(fā)生變化，那么百分之百法則可以直接表明最初最優(yōu)解是否保持不變例例1.1百分比總和百分比總和100% 最優(yōu)解變化與否不確定最優(yōu)解變化與否不確定p門的單位利潤c1=300 c1=600，占允許增加量的百分比p窗的單位利潤c2=500 c2=300 ，占允許減少量的百分比600300100%66.67%450500300100%66.67%300變化的百分比總和為變化的百分比總和為133.34%，所以所以最優(yōu)解變化與否不確定，需通過最優(yōu)解變化與否不確定，需通過“規(guī)劃求解規(guī)劃求解”重新計算重新計算重新重新“規(guī)劃求解規(guī)劃求解”得到得到最優(yōu)解改變，最大利潤改變最優(yōu)解改變，最大利潤改變例例1.1

8、百分比總和百分比總和=100% 最優(yōu)解不變最優(yōu)解不變p門的單位利潤c1=300 c1=525，占允許增加量的百分比p窗的單位利潤c2=500 c2=350 ，占允許減少量的百分比525300100%50%450500350100%50%300變化的百分比總和為變化的百分比總和為100%，所以所以最優(yōu)解不變最優(yōu)解不變2.6 約束條件系數(shù)變化的靈敏度分析約束條件系數(shù)變化的靈敏度分析p約束條件中的技術(shù)（工藝）系數(shù) ，往往涉及車間生產(chǎn)能力、產(chǎn)品消耗資源數(shù)等比較確定的數(shù)據(jù)，這些參數(shù)變化的時候也會對最優(yōu)解產(chǎn)生影響。ija1212121231.max300500412. .32,518,0zxxxxstxx

9、x x x12121212max3005004212. .3218,0zxxxxstxxx x規(guī)劃求解得到規(guī)劃求解得到2.7 增加一個新變量增加一個新變量在例1.1中，如果增加一個變量x3，比如考慮增加一種新產(chǎn)品：防盜門，單位利潤400元，生產(chǎn)一扇防盜門會占用車間1、車間2、車間3各2、1、1小時，此時，新的線性規(guī)劃模型變?yōu)椋?1212121233333max3005004212. .321840,002,xxxzxxxxsxxxxtxx12121212max3005004212. .3218,0zxxxxstxxx x規(guī)劃求解得到規(guī)劃求解得到2.8 增加一個約束條件增加一個約束條件p增加一個

10、約束條件，比如增加電力供應(yīng)限制時，最優(yōu)解是否會發(fā)生變化？p假設(shè)生產(chǎn)一扇門和窗需要消耗電力分別為20kw和10kw，工廠可供電量最多為90kw，此時應(yīng)該在原有的模型中加入新的約束條件： 12201090 xx模型模型12121212max3005004212. .3218,0zxxxxstxxx x1212111222max3005004212. . 3220109108,0 xxzxxxxstxxx x2.4 單個約束右端值變化的靈敏度分析單個約束右端值變化的靈敏度分析p只有一個約束右端值 發(fā)生變化，即如果其他條件均不變，把12改成13ib12121212max3005004212. .321

11、8,0zxxxxstxxx x12121212max30050042. .3218,013zxxxxstxxx x最優(yōu)解改變，利潤增加最優(yōu)解改變，利潤增加最優(yōu)解不改變，利潤不變最優(yōu)解不改變，利潤不變?nèi)绻囬g如果車間2的可用工時不斷增加，會出現(xiàn)什么情況？的可用工時不斷增加，會出現(xiàn)什么情況？為什么？為什么？2.4.1 敏感性報告敏感性報告陰影價格陰影價格，顯示了約束右端值每增加（或減少），顯示了約束右端值每增加（或減少）1個單位，目標(biāo)函數(shù)值（或最優(yōu)值）相應(yīng)的增加個單位，目標(biāo)函數(shù)值（或最優(yōu)值）相應(yīng)的增加量（減少量）量（減少量）可從敏感性報告中獲得的信息？可從敏感性報告中獲得的信息？p影子價格的解釋：

12、影子價格的解釋：1. 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題例例1.1的線性規(guī)劃問題為的線性規(guī)劃問題為 補(bǔ)充說明：補(bǔ)充說明： 影子價格影子價格12121212max3005004212. .3218,0zxxxxstxxx x現(xiàn)從另一角度提出問題。假定某現(xiàn)從另一角度提出問題。假定某A公司想把該工廠的資源收購過公司想把該工廠的資源收購過來，它至少應(yīng)付出多大代價，才能使該工廠愿意放棄生產(chǎn)活動，來，它至少應(yīng)付出多大代價，才能使該工廠愿意放棄生產(chǎn)活動，出讓自己的資源？顯然該工廠愿意出讓自己資源的條件是：出讓自己的資源？顯然該工廠愿意出讓自己資源的條件是：出讓出讓代價應(yīng)不低于用同等數(shù)量資源由自己組織生產(chǎn)活

13、動時獲取的贏利代價應(yīng)不低于用同等數(shù)量資源由自己組織生產(chǎn)活動時獲取的贏利。設(shè)分別用設(shè)分別用y1、y2、y3代表單位時間車間代表單位時間車間1、車間、車間2、車間、車間3的出讓代的出讓代價，因該價，因該工廠用工廠用1小時車間小時車間1和和3小時車間小時車間3可生產(chǎn)可生產(chǎn)1扇門，贏利扇門，贏利300元；分別用元；分別用2小時車間小時車間2和車間和車間3可生產(chǎn)可生產(chǎn)1扇窗，贏利扇窗，贏利500元，元，由此，由此，y1、y2、y3的取值應(yīng)滿足：的取值應(yīng)滿足： y1 + 3y3 3002y2 + 2y3 500A公司希望用最小的代價把該工廠的全部資源收買過來，故有公司希望用最小的代價把該工廠的全部資源收買

14、過來，故有 min z = 4y1 + 12 y2 + 18y3 顯然，顯然，yi 0 (i=1,2,3)綜上，現(xiàn)在的問題為：綜上，現(xiàn)在的問題為： 該問題為原問題的該問題為原問題的對偶問題對偶問題該問題的最優(yōu)解的意義：該問題的最優(yōu)解的意義： 代表資源最優(yōu)利用條件下對單位第代表資源最優(yōu)利用條件下對單位第i種資源的估價。種資源的估價。這種這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而做的估價，為區(qū)別起見，稱為獻(xiàn)而做的估價，為區(qū)別起見，稱為影子價格（陰影價格）影子價格（陰影價格）1231323123min412183300. . 22

15、500,0zyyyyystyyy yy影子價格影子價格p資源的市場價格是其價值的客觀體現(xiàn)，相對比較資源的市場價格是其價值的客觀體現(xiàn)，相對比較穩(wěn)定，而它的影子價格則有賴于穩(wěn)定，而它的影子價格則有賴于資源的利用情況資源的利用情況，是未知數(shù)。是未知數(shù)。p影子價格是一種邊際價格影子價格是一種邊際價格p資源的影子價格實際上又是一種機(jī)會成本資源的影子價格實際上又是一種機(jī)會成本2.4.1 敏感性報告敏感性報告陰影價格陰影價格，顯示了約束右端值每增加（或減少），顯示了約束右端值每增加（或減少）1個單位，目標(biāo)函數(shù)值（或最優(yōu)值）相應(yīng)的增加個單位，目標(biāo)函數(shù)值（或最優(yōu)值）相應(yīng)的增加量（減少量）量（減少量）基本概念基本

16、概念約束限制值：允許的增量：針對影子價格不變允許的減量：針對影子價格不變可從敏感性報告中獲得的信息？可從敏感性報告中獲得的信息？2.4.2 圖解法圖解法改變車間改變車間2的約束的約束 2x1x2 4 6 82468 71531753可行域2x2=182x2=122x2=6改變車間改變車間1的約束又會是如何的？的約束又會是如何的？但此時敏感性報告是否有效？但此時敏感性報告是否有效？2.5 多個約束右端值同時變化的靈敏度分析多個約束右端值同時變化的靈敏度分析p分析1小時的工時從車間3移到車間2，對總利潤所產(chǎn)生的影響。p那么，根據(jù)影子價格，可知總利潤變化量如下： 車間2: 12-13，利潤增加？元 車間3: 18-17，利潤減少？元因此，總利潤增加？元2.5.1 敏感性報告敏感性報告百分之百法則百分之百法則p含義：如果約束右端值同時變化，計算每一右端值變化量占該約束右端值允許變化量的百分比，然后將每個約束右端值變化的百分比相加。如果所得的變化的百分比總和不如果所得的變化的百分比總和不超過超過100%，那么影子價格依然有效，那么影子價格依然有效；如果超過了如果超過了100%，那就無法確定影子價格是否依然有效，那就無法確定影