1、 優優 化化 建建 模模第二章第二章 LINDOLINDO軟件的基本使用方法軟件的基本使用方法原書相關信息原書相關信息, , , 2005年年7月第月第1版版.優化建模與優化建模與LINDO/LINGO軟件軟件 優優 化化 建建 模模內容提要內容提要: 例例2.4 例例2.5 2.2 敏感性分析敏感性分析 優優 化化 建建 模模例例2.4 某家具公司制造書桌、餐桌和椅子，所用的資源有某家具公司制造書桌、餐桌和椅子，所用的資源有三種：木料、木工和漆工。生產數據如下表所示。三種：木料、木工和漆工。生產數據如下表所示。每個書桌每個餐桌每個椅子現有資源總數木料8單位6單位1單位48單位漆工4單位2單位

2、1.5單位20單位木工2單位1.5單位0.5單位8單位成品單價60單位30單位20單位 若要求桌子的生產量不超過若要求桌子的生產量不超過5件，如何安排三種產品的件，如何安排三種產品的生產可使利潤最大？生產可使利潤最大？ 優優 化化 建建 模模解：解： 用用DESKS、TABLES和和CHAIRS分別表示三種分別表示三種產品的生產量（決策變量），容易建立產品的生產量（決策變量），容易建立LP模型。模型。在在LINDO模型窗口中輸入模型：模型窗口中輸入模型：MAX 60 DESKS + 30 TABLES + 20 CHAIRSSUBJECT TO 2) 8 DESKS + 6 TABLES +

3、CHAIRS = 48 3) 4 DESKS + 2 TABLES + 1.5 CHAIRS = 20 4) DESKS + 1 5 TABLES + O 5 CHAIRS = 8 5) TABLES = 5END解這個模型，并對彈出的對話框解這個模型，并對彈出的對話框 “ DO RANGE (SENSITIVITY) ANALYSIS? ” 選擇選擇“是（是（Y）”按鈕，這表示你需要做靈敏性分析。按鈕，這表示你需要做靈敏性分析。然后，查看輸出結果。然后，查看輸出結果。 優優 化化 建建 模模LP OPTIMUM FOUND AT STEP 1 OBJECTIVE FUNCTION VALUE

4、 1) 280.0000 VARIABLE VALUE REDUCED COST DESKS 2.000000 0.000000 TABLES 0.000000 5.000000 CHAIRS 8.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 24.000000 0.000000 3) 0.000000 10.000000 4) 0.000000 10.000000 5) 5.000000 0.000000 NO. ITERATIONS= 1輸出結果的前半部分：輸出結果的前半部分： 優優 化化 建建 模模前半部分的輸出結果的解釋與前一節

5、例前半部分的輸出結果的解釋與前一節例2.1的結果類似：的結果類似：“LP OPTIMUM FOUND AT STEP2”表示兩次迭代（旋轉變換）后得到最優解。表示兩次迭代（旋轉變換）后得到最優解。“OBJECTIVE FUNCTION VALUE 1）280.000000”表示最優目標值為表示最優目標值為280。 “VALUE”給出最優解中各變量的值：造給出最優解中各變量的值：造2個書桌（個書桌（desks）, 0個餐桌（個餐桌（tables）, 8個椅子（個椅子（chairs）。所以）。所以desks、chairs是基變量（取值非是基變量（取值非0），），tables是非基變量（取值為是非基

6、變量（取值為0）。）。 “SLACK OR SURPLUS”給出松馳變量的值：給出松馳變量的值： 第第2行松馳變量行松馳變量 =24 （第（第1行表示目標函數，第行表示目標函數，第2行對應第行對應第1個約束）個約束） 第第3行松馳變量行松馳變量 =0 第第4行松馳變量行松馳變量 =0 第第5行松馳變量行松馳變量 =5 優優 化化 建建 模模“REDUCED COST”列出最優單純形表中判別數所在行的變量的系數，表示當變量列出最優單純形表中判別數所在行的變量的系數，表示當變量有微小變動時有微小變動時, 目標函數的變化率目標函數的變化率. 其中基變量的其中基變量的reduced cost值應為值應

7、為0， 對于非基變量對于非基變量 Xj（請注意，非基變量的取值（請注意，非基變量的取值一定是一定是0），）， 相應的相應的 reduced cost值表示當某個變量值表示當某個變量Xj 增加增加一個單位時目標函數減少的量一個單位時目標函數減少的量( max型問題型問題)。本例中：變量本例中：變量TABLES對應的對應的reduced cost值為值為5，表示當非，表示當非基變量基變量TABLES 的值從的值從0變為變為 1時（此時假定其他非基變量保時（此時假定其他非基變量保持不變持不變,但為了滿足約束條件，基變量顯然會發生變化），最但為了滿足約束條件，基變量顯然會發生變化），最優的目標函數值優

8、的目標函數值 = 280 - 5 = 275。 優優 化化 建建 模模“DUAL PRICE” （對偶價格）表示當對應約束有微小變動時（對偶價格）表示當對應約束有微小變動時, 目標函數的變化率目標函數的變化率. 輸出結果中對應于每一個約束有一個對偶輸出結果中對應于每一個約束有一個對偶價格價格. 若其數值為若其數值為p, 表示對應約束中不等式右端項若增加表示對應約束中不等式右端項若增加1 個個單位單位, 目標函數將增加目標函數將增加p個單位（個單位（max型問題型問題)。 顯然，如果在最優解處約束正好取等號（也就是顯然，如果在最優解處約束正好取等號（也就是“緊約束緊約束”，即起作用約束），對偶價

9、格值才可能不是即起作用約束），對偶價格值才可能不是0。本例中：第。本例中：第3、4行是緊約束，對應的對偶價格值為行是緊約束，對應的對偶價格值為10，表示當緊約束，表示當緊約束 3) 4 DESKS + 2 TABLES + 1.5 CHAIRS = 20變為變為 3) 4 DESKS + 2 TABLES + 1.5 CHAIRS = 21時，目標函數值時，目標函數值 = 280 +10 = 290。對第。對第4行也可類似解釋。行也可類似解釋。 對于非緊約束（如本例中第對于非緊約束（如本例中第2、5行是非緊約束），行是非緊約束），DUAL PRICE 的值為的值為0, 表示對應約束中不等式右端

10、項的微小擾動不表示對應約束中不等式右端項的微小擾動不影響目標函數。有時影響目標函數。有時, 通過分析通過分析DUAL PRICE, 也可對產生不也可對產生不可行問題的原因有所了解。可行問題的原因有所了解。 優優 化化 建建 模模輸出結果的后半部分：輸出結果的后半部分：RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE C O E F I N C R E A S E DECREASE DESKS 60.000000 20.000000 4.00000

11、0 TABLES 30.000000 5.000000 INFINITY CHAIRS 20.000000 2.500000 5.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE R H S I N C R E A S E DECREASE 2 48.000000 INFINITY 24.000000 3 20.000000 4.000000 4.000000 4 8.000000 2.000000 1.333333 5 5.000000 INFINITY 5.000000（報告中（報告中INFINITY表示正無窮表示正無

12、窮 ） 優優 化化 建建 模模 敏感性分析的作用是給出敏感性分析的作用是給出“RANGES IN WHICH THE BASIS IS UNCHANGED”，即研究當目標函數的系數和約束，即研究當目標函數的系數和約束右端項在什么范圍變化（此時假定其他系數保持不變）時，右端項在什么范圍變化（此時假定其他系數保持不變）時，最優基（矩陣）保持不變。最優基（矩陣）保持不變。1. 目標函數中系數變化的范圍目標函數中系數變化的范圍 （OBJ COEFFICIENT RANGES）如本例中：目標函數中如本例中：目標函數中DESKS變量當前的系數（變量當前的系數（CURRENT COEF） = 60，允許增加

13、（，允許增加（Allowable Increase）=4、允、允許減少（許減少（Allowable Decrease）=2，說明當這個系數在，說明當這個系數在60-4，60+20 = 56，80范圍變化時，最優基保持不變。范圍變化時，最優基保持不變。對對TABLES、CHAIRS變量，可以類似解釋。由于此時約變量，可以類似解釋。由于此時約束沒有變化（只是目標函數中某個系數發生變化），所以束沒有變化（只是目標函數中某個系數發生變化），所以最優基保持不變的意思也就是最優解不變（當然，由于目最優基保持不變的意思也就是最優解不變（當然，由于目標函數中系數發生了變化，所以最優值會變化）。標函數中系數發生

14、了變化，所以最優值會變化）。 這個部分包括兩方面的敏感性分析內容：這個部分包括兩方面的敏感性分析內容： 優優 化化 建建 模模2. 約束右端項變化的范圍（約束右端項變化的范圍（Right Hand Side RANGES）如本例中：第如本例中：第2行約束中當前右端項（行約束中當前右端項（CURRENT RHS）=48，允許增加（允許增加（Allowable Increase）=INFINITY（無窮）、允許（無窮）、允許減少（減少（Allowable Decrease）=24，說明當它在，說明當它在 48-24，48+ ) = 24， ）范圍變化時，最優基保持不變。第范圍變化時，最優基保持不變

15、。第3、4、5行可以類似解釋。行可以類似解釋。不過由于此時約束發生變化，最優基即使不變，最優解、最優不過由于此時約束發生變化，最優基即使不變，最優解、最優值也會發生變化。如何變化呢？我們將在本節后面結合第值也會發生變化。如何變化呢？我們將在本節后面結合第1章章1.2.1節例節例1.1給出的實際問題來進行說明。給出的實際問題來進行說明。 優優 化化 建建 模模最后，如果你對單純形法比較熟悉，你可以直接查看最優解時最后，如果你對單純形法比較熟悉，你可以直接查看最優解時的單純形表，這只要選擇菜單命令的單純形表，這只要選擇菜單命令Reports | Tableau (Alt+7)執行即可執行即可,輸出

16、結果如下：輸出結果如下： ROW (BASIS) DESKS TABLES CHAIRS 1 ART 0.000 5.000 0.000 2 SLK 2 0.000 -2.000 0.000 3 DESKS 1.000 1.250 0.000 4 CHAIRS 0.000 -2.000 1.000 5 SLK 5 0.000 1.000 0.000 ROW SLK 2 SLK 3 SLK 4 SLK 5 1 0.000 10.000 10.000 0.000 280.000 2 1.000 2.000 -8.000 0.000 24.000 3 0.000 1.500 -0.500 0.000

17、 2.000 4 0.000 -4.000 2.000 0.000 8.000 5 0.000 0.000 0.000 1.000 5.000 優優 化化 建建 模模在輸出結果中，在輸出結果中， 基變量為基變量為BV=SLK2, Chairs, DESKS, SLK5，ART是人工變量（是人工變量（artificial variable）,即相應的即相應的目標值目標值z; 這樣，你就可以知道這樣，你就可以知道 z = 5 TABLES + 10 SLK3 + 10 SLK4 = 280。 敏感性分析結果表示的是最優基保持不變的系數范圍。敏感性分析結果表示的是最優基保持不變的系數范圍。由此，也可

18、以進一步確定當目標函數的系數和約束右端項發由此，也可以進一步確定當目標函數的系數和約束右端項發生小的變化時，最優解、最優值如何變化。下面我們通過求生小的變化時，最優解、最優值如何變化。下面我們通過求解第解第1章章1.2.1節例節例1.1的實際問題來進行說明。的實際問題來進行說明。 優優 化化 建建 模模例例2.5 繼續討論例繼續討論例1.11.1 在在LINDO模型窗口中輸入模型模型窗口中輸入模型 問題的數學模型：問題的數學模型：MAX 72 x1 + 64 x2SUBJECT TO 2) x1 + x2 = 50 3) 12 x1 + 8 x2 = 480 4) 3 x1 = 100END

19、優優 化化 建建 模模求解這個模型并做靈敏性分析，查看報告窗口（求解這個模型并做靈敏性分析，查看報告窗口（Reports Window）。輸出結果告訴我們：這個線性規劃的最優解為）。輸出結果告訴我們：這個線性規劃的最優解為x1=20，x2=30，最優值為，最優值為z=3360，即用，即用20桶牛奶生產桶牛奶生產A1, 30桶牛奶生產桶牛奶生產A2，可獲最大利潤，可獲最大利潤3360元。元。 輸出中除了告訴我們問題的最優解和最優值以外，還有許多輸出中除了告訴我們問題的最優解和最優值以外，還有許多對分析結果有用的信息，下面結合題目中提出的對分析結果有用的信息，下面結合題目中提出的3個附加問個附加問

20、題給予說明。題給予說明。 3個約束條件的右端不妨看作個約束條件的右端不妨看作3種種“資源資源”：原料、勞動時間、：原料、勞動時間、車間甲的加工能力。輸出中車間甲的加工能力。輸出中SLACK OR SURPLUS （松弛或（松弛或剩余）給出這剩余）給出這3種資源在最優解下是否有剩余：原料、勞動時種資源在最優解下是否有剩余：原料、勞動時間的剩余均為零（即約束為緊約束），車間甲尚余間的剩余均為零（即約束為緊約束），車間甲尚余40公斤加公斤加工能力（不是緊約束）。工能力（不是緊約束）。 優優 化化 建建 模模目標函數可以看作目標函數可以看作“效益效益”，成為緊約束的，成為緊約束的“資源資源”一旦增加，

21、一旦增加，“效益效益”必然跟著增長。必然跟著增長。輸出中輸出中DUAL PRICES（對偶價格）（對偶價格） 給出這給出這3種資源在最優解種資源在最優解下下“資源資源”增加增加1個單位時個單位時“效益效益”的增量：原料增加的增量：原料增加1個單位個單位（1桶牛奶）時利潤增長桶牛奶）時利潤增長48（元），勞動時間增加（元），勞動時間增加1個單位（個單位（1小時）時利潤增長小時）時利潤增長2（元），而增加非緊約束車間甲的能力顯（元），而增加非緊約束車間甲的能力顯然不會使利潤增長。然不會使利潤增長。這里，這里，“效益效益”的增量可以看作的增量可以看作“資源資源”的潛在價值，經濟學上稱為影子的潛在價值

22、，經濟學上稱為影子價格（價格（shadow price），即），即1桶牛奶的影子價格為桶牛奶的影子價格為48元，元，1小時勞動的影子小時勞動的影子價格為價格為2元，車間甲生產能力的影子價格為零。元，車間甲生產能力的影子價格為零。可以用直接求解的辦法驗證上面的結論，即將輸入文件中原料約束可以用直接求解的辦法驗證上面的結論，即將輸入文件中原料約束milk）右端的右端的50改為改為51，看看得到的最優值（利潤）是否恰好增長，看看得到的最優值（利潤）是否恰好增長48（元）。用（元）。用影子價格的概念很容易回答附加問題影子價格的概念很容易回答附加問題1）：用）：用35元可以買到元可以買到1桶牛奶，低于桶

23、牛奶，低于1桶牛奶的影子價格桶牛奶的影子價格48，當然應該作這項投資。回答附加問題，當然應該作這項投資。回答附加問題2）：聘用臨時）：聘用臨時工人以增加勞動時間，付給的工資低于勞動時間的影子價格才可以增加利工人以增加勞動時間，付給的工資低于勞動時間的影子價格才可以增加利潤，所以工資最多是每小時潤，所以工資最多是每小時2元。元。 優優 化化 建建 模模目標函數的系數發生變化時（假定約束條件不變），最優解目標函數的系數發生變化時（假定約束條件不變），最優解和最優值會改變嗎？和最優值會改變嗎？這個問題不能簡單地回答。這個問題不能簡單地回答。上面的輸出結果給出了最優基不變條件下目標函數系數的允上面的輸

24、出結果給出了最優基不變條件下目標函數系數的允許變化范圍：許變化范圍：x1的系數范圍為（的系數范圍為（72-8，72+24）=（64，96）；）；x2的系數范圍為（的系數范圍為（64-16，64+8）=（48，72）。）。注意：注意：x1系數的允許范圍需要系數的允許范圍需要x2的系數的系數64不變，反之亦然。不變，反之亦然。由于目標函數的系數變化并不影響約束條件，因此此時最優由于目標函數的系數變化并不影響約束條件，因此此時最優基不變可以保證最優解也不變，但最優值變化。用這個結果基不變可以保證最優解也不變，但最優值變化。用這個結果很容易回答附加問題很容易回答附加問題3）：若每公斤）：若每公斤A1的

25、獲利增加到的獲利增加到30元，元，則則x1系數變為系數變為303=90，在允許范圍內，所以不應改變生，在允許范圍內，所以不應改變生產計劃，但最優值變為產計劃，但最優值變為9020+6430=3720。 優優 化化 建建 模模下面對下面對“資源資源”的影子價格作進一步的分析。的影子價格作進一步的分析。影子價格的作用影子價格的作用（即在最優解下（即在最優解下“資源資源”增加增加1個單位時個單位時“效益效益”的增量）的增量）是有限制的是有限制的。每增加每增加1桶牛奶利潤增長桶牛奶利潤增長48元（影子價格），但是，約束的右端元（影子價格），但是，約束的右端項（項（CURRENT RHS） 的的“允許增加允許增加”（ALLOWABLE INCREASE） 和和 “允許減少允許減少”（ALLOWABLE DECREASE） 給出了影子價格有意義條件下約束右端的限制范圍（因為此時給出了影子價格有意義條件下約束右端的限制范圍（因為此時最優基不變，所以影子價格才有意義；如果最優基已經變了，最優基不變，所以影子價格才有意義；如果最優基已經變了