圖解法的靈敏度分析課件

1、3 圖解法的靈敏度分析線性規(guī)劃的標準形式為：目標函數(shù)：約束條件：（或 ）其中 為第 個決策變量 的系數(shù)；為第 個約束條件中的第個決策變量 的系數(shù)；為第 個約束條件的常數(shù)項，且13 圖解法的靈敏度分析線性規(guī)劃的標準形式為：目標函數(shù)：約束所謂靈敏度分析就是在建立數(shù)學模型和求得最優(yōu)解之后，究線性規(guī)劃的一些系數(shù) 變化時，對最優(yōu)解有什么影響？研 3.1 目標函數(shù)中的系數(shù) 的靈敏度分析設目標函數(shù)為:改寫為:顯然,目標函數(shù)等直線的斜率為:對于前面的例 1,如左圖:100200300400100200300400直線E(設備臺時約束條件)直線G(原料A的約束條件)直線F(原料B的約束條件)目標函數(shù)直線ABCD

2、P162所謂靈敏度分析就是在建立數(shù)學模型和求得最優(yōu)解之后，究線性規(guī)劃2）當 時，BC上任一點都是其最優(yōu)解。3)當 時,AB上任意一點都是最優(yōu)解.1）當 時,仍是最優(yōu)解。B點，即為了計算出 在什么范圍內(nèi)變化時頂點B仍是其最優(yōu)解，單位產(chǎn)品的利潤為100元不變，假設即則有解不等式得即單位產(chǎn)品的利潤為100元，單位產(chǎn)品的利潤在0與100元之間變化時，仍是最優(yōu)解。32）當 時，BC上任一點都是即要計算出 在什么范圍內(nèi)變化時頂點B仍是其最優(yōu)解，單位產(chǎn)品的利潤為50元不變，假設則有解不等式得且即也即單位產(chǎn)品的利潤為50元，單位產(chǎn)品的利潤只要大于等于50元時，仍是最優(yōu)解。同樣，在 和 中一個值確定不變時，可以

3、求出另一個值的變化范圍，使其最優(yōu)解在C點（或在D點，或在A點）。若 和 都變化時，可通過目標函數(shù)的斜率 判斷B點、C點、D點或A點為最優(yōu)解。4即要計算出 在什么范圍內(nèi)變化時頂點B仍是其最優(yōu)解，單3.2 約束條件中右邊系數(shù) 的靈敏度分析當約束條件右邊系數(shù) 發(fā)生變化時,線性規(guī)劃的可行域也將發(fā)生變化，就可能引起最優(yōu)解的變化。將例1中的約束條件改為最優(yōu)解為 點，解得最優(yōu)解即增加了10個臺時的設備。100200300400100200300400ABCD100200300400100200300400ABCD53.2 約束條件中右邊系數(shù) 的靈敏度分析當約束條件右邊系此時的最大利潤為：比原來增加了：這主要

4、是由于增加了10個設備臺時而獲得的。即每增加一個臺時的設備就可多獲得的利潤。對偶價格：在約束條件右邊常數(shù)增加一個單位，而使最優(yōu)目標函值得到改進的數(shù)量，稱為這個約束條件的對偶價格。約束條件：的對偶價格。若將例1中的原料A增加10千克，改為則約束條件6此時的最大利潤為：比原來增加了：這主要是由于增加了10個設備最優(yōu)解仍為 點，100200300400100200300400ABCD100200300400100200300400ABCD最優(yōu)值還是27500元。原料A的對偶價格為：即最優(yōu)解仍為： 即原料A 增加10千克，只增加了庫存，沒有轉化為利潤。原因：原料 A 只用了：還有：沒用。7最優(yōu)解仍為

5、點，1002003004001002003約束條件(設備臺時的限制條件)(原料A 的限制條件)(原料B 的限制條件)(決策變量非負約束條件)目標函數(shù)由此可知：當某約束條件中的松弛變量（或剩余變量）不為零， 則這個條件的對偶價格為零。總結如下，當約束條件右邊常數(shù)增加一個單位時：1）如果對偶價格大于零，則其最優(yōu)目標函數(shù)值變得更好，即 求最大值時，變得更大；求最小值是變得更小。 2）如果對偶價格小于零，則其最優(yōu)目標函數(shù)值變壞，即求最 大值時變小了；求最小值時變大了。 3）如果對偶價格等于零，則其最優(yōu)目標函數(shù)值不變。 8約束條件(設備臺時的限制條件)(原料A 的限制條件)(原料B第三章 線性規(guī)劃問題的

6、計算機求解輸入中注意以下兩點：解決線性規(guī)劃問題的軟件包分兩種：(1)大規(guī)模的軟件包：可解決包含數(shù)千個決策變量和約束條件的大型線性規(guī)劃問題。(2)用于微型計算機的軟件包: 可解決包含數(shù)百個決策變量的線性規(guī)劃問題。(1)輸入的系數(shù)可以是整數(shù)、小數(shù)，但不能是分數(shù)。(2)輸入前先要合并同類項。 注：本軟件可解決100個決策變量50個約束方程的線性規(guī)劃問題. 9第三章 線性規(guī)劃問題的計算機求解輸入中注意以下兩點：解決線目標函數(shù)最優(yōu)值為: 27500變量 最優(yōu)解 相差值約束 松弛/剩余變量 對偶價格目標函數(shù)系數(shù)范圍:變量 下限 當前值 上限常數(shù)范圍:約束 下限 當前值 上限10目標函數(shù)最優(yōu)值為: 2750

7、0變量 目標函數(shù)最優(yōu)值為: 27500變量 最優(yōu)解 相差值目標函數(shù)最優(yōu)值為: 27500表示:這個問題的最優(yōu)解可得到利潤 27500元;變量:即決策變量;最優(yōu)解:使目標函數(shù)達到最優(yōu)值的解:即生產(chǎn)產(chǎn)品50單位、產(chǎn)品250單位才能使利潤達到最大值;相差值:表示:相應的決策變量的目標系數(shù)需要改進的數(shù)量, 使該決策變量有可能取正值, 當決策變量已經(jīng)取正值, 則相差值為零.如 它們的相差值都為零。如果的相差值為30，則只有當產(chǎn)品的利潤再提高30元, 即達到50+30=80元時,產(chǎn)品才可能生產(chǎn), 即11目標函數(shù)最優(yōu)值為: 27500變量 約束 松弛/剩余變量 對偶價格約束1:表示設備臺時的限制.其剩余量(

8、松弛變量)為0, 即設備臺時數(shù)全部用完.松弛變量:沒有用完的資源數(shù)剩余變量:超出資源數(shù). 對偶價格為50: 表示每增加一個設備臺時, 可使總利潤增加50元.約束2:是對原料A 的限制.其剩余量(松弛變量)為50, 即原料A 還有50千克沒有使用. 對偶價格為0: 因為再增加原料A 只能增加庫存, 不能增加利潤.約束3:是對原料B 的限制.其剩余量(松弛變量)為0, 即原料B 全部用完. 對偶價格為50: 即每增加一千克的原料B可使總利潤增加50元.12約束 松弛/剩余變量 目標函數(shù)系數(shù)范圍:變量 下限 當前值 上限常數(shù)范圍:約束 下限 當前值 上限靈敏度分析：研究目標函數(shù)的系數(shù)、右端常數(shù)及約束

9、方程中的 系數(shù)發(fā)生變化時，對最優(yōu)解的影響。靈敏度分析所研究的問題：（1）為了保持現(xiàn)有的最優(yōu)解或最優(yōu)基不變，找出這些數(shù)據(jù)變化 的范圍；（2）這些數(shù)據(jù)超出了（1）的范圍時，如何盡快求出新的最優(yōu)解 或最優(yōu)基。 靈敏度分析 13目標函數(shù)系數(shù)范圍:變量 下限變量 下限 當前值 上限當前值:表示目標函數(shù)中決策變量當前的系數(shù):上限、下限： 指目標函數(shù)的決策變量的系數(shù)在此范圍內(nèi)變化時， 其線性規(guī)劃的最優(yōu)解不變。 對于此問題：只要 其最優(yōu)解不變。 如：若 其最優(yōu)解仍為 目標函數(shù)最優(yōu)值為 優(yōu)解就要發(fā)生變化。 但若 其最 對于c2有同樣的道理。如何調整生產(chǎn)計劃 ?目標函數(shù)系數(shù)范圍:TP17-對目標函數(shù)的系數(shù)進行靈敏

10、度分析 14變量 下限 約束 下限 當前值 上限當前值: 表示約束條件右邊現(xiàn)在的值: 上限、下限： 是指當約束條件在此范圍內(nèi)變化時，則與其對應的 約束條件的對偶價格不變。 對于此問題： 設備臺時在250325之間變化時，其對偶價格都為50元； 原料A 在350+之間變化時，其對偶價格都為0 ； 原料B 在200300之間變化時，其對偶價格都為50元 。 如：若 而 設備臺時的對偶價 格仍為50元， 但設備臺時比原來減少了20個臺時，利潤減少， 此時目標函數(shù)的最優(yōu)值為：27500-2050=26500（元）。TP18常數(shù)范圍:-對右端常數(shù)進行靈敏度分析 15約束 下限 注： 計算機輸出的關于目標

11、函數(shù)及約束條件的靈敏度分析都是 基于假設：只有一個系數(shù)值發(fā)生變化，而其它系數(shù)值保持不變。 問題： 若有兩個或更多個的系數(shù)同時發(fā)生變化時，如何進行靈敏 度分析？百分之一百法則： 以例1為例： 原來產(chǎn)品的利潤為每件50元、產(chǎn)品的利潤為每件100元， 現(xiàn)在由于市場情況的變化每件產(chǎn)品產(chǎn)品的利潤分別變?yōu)?4元 和78元，最優(yōu)解發(fā)生變化嗎？允許增加值： 對一個目標函數(shù)的決策變量系數(shù)： 該系數(shù)在上限范圍內(nèi)的最大增加量； 允許減少值： 該系數(shù)在下限范圍內(nèi)的最大減少量。 16注： 計算機輸出的關于目標函數(shù)及約束條件的靈敏度分析都是 對于例1：c1的允許增加量為：上限 當前值=100-50=50； c2的允許減少

12、量為：當前值- 下限 =100-50=50。 ci允許增加（減少）百分比： c1允許增加百分比為 ： (74-50) /50=48%; c2允許減少百分比為 ： (100-78) /50=44%; c1允許增加百分比與c2允許減少百分比之和為: 48%+44%=92%. 此線性規(guī)劃的最優(yōu)解不變，仍為： 此時最大利潤為：7450+78250=23200（元）。 TP18TP14 17對于例1：c1的允許增加量為：上限 當前值=100-50目標函數(shù)決策變量系數(shù)的百分之一百法則: 對于所有變化的目標函數(shù)決策變量系數(shù),當其所允許增加百分 比和允許減少百分比之和不超過100%時, 最優(yōu)解不變. 約束條件

13、右邊系數(shù)的百分之一百法則: 對于所有變化的約束條件的右邊常數(shù)值,當其所允許增加百分 比和允許減少百分比之和不超過100%時, 其對偶價格不變. 對于例1： 若三個約束條件的變化為：設備臺時數(shù)：從300臺時增加為315臺時； 原料A ：從400千克減少到390千克； 原料B ：從250千克減少到240千克 。 它們的允許增加（減少）百分比分別為： TP1515/25=60%； 10/50=20%； 10/50=20%。 允許增加百分比和允許減少百分比之和為： 18目標函數(shù)決策變量系數(shù)的百分之一百法則: 對于所有變化的目60%+20%+20%=100%。所以此線性規(guī)劃的對偶價格不變。 利潤的增加值

14、為： 5015 - 015 - 5010=250（元） 利潤由原來的27500元增加到27750元。 使用百分之一百法則進行靈敏度分析時，要注意以下三點： 1）當允許增加量（減少量）為 時，則對于任一個增加量 （減少量），其允許增加（減少）百分比都看成 0 。 2）百分之一百法則是判斷最優(yōu)解或對偶價格不變的充分條 件，但不是必要條件。 即當其允許增加和減少百分比之和超過 百分之一百時，我們不能判斷其最優(yōu)解或對偶價格是否發(fā)生變化。 3）若百分之一百法則不能應用于目標函數(shù)決策變量系數(shù)和 約束條件右邊常數(shù)值同時變化的情況，在這種情況下，只能重新 求解。 1960%+20%+20%=100%。所以此線

15、性規(guī)劃的對偶價格不目標函數(shù)： 約束條件： 以 P15 例2為例： 20目標函數(shù)： 約束條件： 以 P15 例2為例： 20目標函數(shù)最優(yōu)值為: 800（萬元） 變量 最優(yōu)解 相差值 約束 松弛/剩余變量 對偶價格 目標函數(shù)系數(shù)范圍:變量 下限 當前值 上限 常數(shù)范圍:約束 下限 當前值 上限 21目標函數(shù)最優(yōu)值為: 800（萬元） 變量 1. 購進A 原料250噸, B 原料100噸時, 購進成本最低為800萬元。 2.約束條件(對所有原料的總需要量)的剩余變量為零; 若把加工時數(shù)從600小時增加到601小時, 總成本將得到改進,價格為- 4, 約束條件(對加工時數(shù)的限制)的松弛變量值為0. 若把購進原料A 和B 的總量從下限350噸增加到351噸,總成本 增加到: 800+4=804萬元; 若購進原料總量從350噸減少到349噸,總成本將會得到改進, 減少到: 800 4=796萬元; 約束條件的剩余變量為125; 其對偶價格為0, 若把購進原料A 的下限由125噸增加到126噸, 總成本的最優(yōu)值 (最低價)不會發(fā)生變化 .其對偶 價格為1, 變?yōu)? 800-1=