1、 優(yōu)化建模優(yōu)化建模與LINDO/LINGO軟件第二章LINDO軟件的基本使用方法原書(shū)相關(guān)信息謝金星, 薛毅編著, 清華大學(xué), 2005年7月第1版./jxie/lindo 優(yōu)化建模2.2敏感性分析內(nèi)容提要: 例2.4 例2.5 優(yōu)化建模例2.4某家具公司制造書(shū)桌、餐桌和椅子，所用的資源有 三種：木料、木工和漆工。生產(chǎn)數(shù)據(jù)如下表所示。若要求桌子的生產(chǎn)量不超過(guò)5件，如何安排三種產(chǎn)品的生產(chǎn)可使利潤(rùn)最大？每個(gè)書(shū)桌每個(gè)餐桌每個(gè)椅子現(xiàn)有資源總數(shù)木料8單位6單位1單位48單位漆工4單位2單位1.5單位20單位木工2單位1.5單位0.5單位8

2、單位成品單價(jià)60單位30單位20單位 優(yōu)化建模解：用DESKS、TABLES和CHAIRS分別表示三種產(chǎn)品的生產(chǎn)量（決策變量），容易建立LP模型。在LINDO模型窗口中輸入模型：解這個(gè)模型，并對(duì)彈出的對(duì)話框“ DO RANGE (SENSITIVITY) ANALYSIS? ”選擇“是（Y）”按鈕，這表示你需要做靈敏性分析。然后，查看輸出結(jié)果。MAX60 DESKS + 30 TABLES + 20 CHAIRS SUBJECT TO2) 8 DESKS + 6 TABLES + CHAIRS =483) 4 DESKS + 2 TABLES + 1.5 CHAIRS =204) DESKS

3、+ 1 5 TABLES + O 5 CHAIRS = 85) TABLES = 5 END 優(yōu)化建模輸出結(jié)果的前半部分：LP OPTIMUM FOUND AT STEP 1 OBJECTIVE FUNCTION VALUE 1) 280.0000VARIABLEVALUEREDUCED COST DESKS2.0000000.000000TABLES0.0000005.000000CHAIRS8.0000000.000000ROWSLACK OR SURPLUSDUAL PRICES 2)24.0000000.0000003)0.00000010.0000004)0.00000010.000

4、0005)5.0000000.000000NO. ITERATIONS=1 優(yōu)化建模前半部分的輸出結(jié)果的解釋與前一節(jié)例2.1的結(jié)果類似：“LP OPTIMUM FOUND AT STEP2”表示兩次迭代（旋轉(zhuǎn)變換）后得到最優(yōu)解?！癘BJECTIVE FUNCTION VALUE表示最優(yōu)目標(biāo)值為280?！癡ALUE”1）280.000000”給出最優(yōu)解中各變量的值：造2個(gè)書(shū)桌（desks）, 0個(gè)餐桌（tables）, 8個(gè)椅子（chairs）。所以desks、chairs是基變量（取值非0）， tables是非基變量（取值為0）。“SLACK OR SURPLUS”給出松馳變量的值：第2行松馳

5、變量 =24（第1行表示目標(biāo)函數(shù)，第2行對(duì)應(yīng)第1個(gè)約束）第3行松馳變量 =0第4行松馳變量 =0第5行松馳變量 =5 優(yōu)化建模“REDUCED COST”列出最優(yōu)單純形表中判別數(shù)所在行的變量的系數(shù)，表示當(dāng)變量有微小變動(dòng)時(shí), 目標(biāo)函數(shù)的變化率. 其中基變量的reduced cost值應(yīng)為0， 對(duì)于非基變量 Xj（請(qǐng)注意，非基變量的取值一定是0）， 相應(yīng)的 reduced cost值表示當(dāng)某個(gè)變量Xj 增加一個(gè)單位時(shí)目標(biāo)函數(shù)減少的量( max型問(wèn)題)。本例中：變量TABLES對(duì)應(yīng)的reduced cost值為5，表示當(dāng)非基變量TABLES 的值從0變?yōu)?1時(shí)（此時(shí)假定其他非基變量保持不變,但為了滿

6、足約束條件，基變量顯然會(huì)發(fā)生變化），最優(yōu)的目標(biāo)函數(shù)值 = 280 - 5 = 275。 優(yōu)化建模“DUAL PRICE” （對(duì)偶價(jià)格）表示當(dāng)對(duì)應(yīng)約束有微小變動(dòng)時(shí), 目標(biāo)函數(shù)的變化率. 輸出結(jié)果中對(duì)應(yīng)于每一個(gè)約束有一個(gè)對(duì)偶價(jià)格. 若其數(shù)值為p,表示對(duì)應(yīng)約束中不等式右端項(xiàng)若增加1 個(gè)單位, 目標(biāo)函數(shù)將增加p個(gè)單位（max型問(wèn)題)。顯然，如果在最優(yōu)解處約束正好取等號(hào)（也就是“緊約束”， 即起作用約束），對(duì)偶價(jià)格值才可能不是0。本例中：第3、4 行是緊約束，對(duì)應(yīng)的對(duì)偶價(jià)格值為10，表示當(dāng)緊約束3)3)4 DESKS + 2 TABLES + 1.5 CHAIRS =4 DESKS + 2 TABLES

7、 + 1.5 CHAIRS =2021變?yōu)闀r(shí)，目標(biāo)函數(shù)值 = 280 +10 = 290。對(duì)第4行也可類似解釋。對(duì)于非緊約束（如本例中第2、5行是非緊約束），DUAL PRICE 的值為0, 表示對(duì)應(yīng)約束中不等式右端項(xiàng)的微小擾動(dòng)不影響目標(biāo)函數(shù)。有時(shí), 通過(guò)分析DUAL PRICE, 也可對(duì)產(chǎn)生不可行問(wèn)題的原因有所了解。 優(yōu)化建模輸出結(jié)果的后半部分：（報(bào)告中INFINITY表示正無(wú)窮 ）RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREAS

8、EDECREASE DESKS60.00000020.0000004.000000TABLES30.0000005.000000INFINITYCHAIRS20.0000002.5000005.000000RIGHTHAND SIDE RANGESROWCURRENTALLOWABLEALLOWABLE RHSINCREASEDECREASE248.000000INFINITY24.000000320.0000004.0000004.00000048.0000002.0000001.33333355.000000INFINITY5.000000 優(yōu)化建模這個(gè)部分包括兩方面的敏感性分析內(nèi)容：1.

9、目標(biāo)函數(shù)中系數(shù)變化的范圍（OBJ COEFFICIENT RANGES）如本例中：目標(biāo)函數(shù)中DESKS變量當(dāng)前的系數(shù)（CURRENT COEF） = 60，允許增加（Allowable Increase）=4、允許減少（Allowable Decrease）=2，說(shuō)明當(dāng)這個(gè)系數(shù)在60-4，60+20 = 56，80范圍變化時(shí)，最優(yōu)基保持不變。對(duì)TABLES、CHAIRS變量，可以類似解釋。由于此時(shí)約束沒(méi)有變化（只是目標(biāo)函數(shù)中某個(gè)系數(shù)發(fā)生變化），所以最優(yōu)基保持不變的意思也就是最優(yōu)解不變（當(dāng)然，由于目 標(biāo)函數(shù)中系數(shù)發(fā)生了變化，所以最優(yōu)值會(huì)變化）。敏感性分析的作用是給出“RANGES IN WHIC

10、H THE BASIS IS UNCHANGED”，即研究當(dāng)目標(biāo)函數(shù)的系數(shù)和約束右端項(xiàng)在什么范圍變化（此時(shí)假定其他系數(shù)保持不變）時(shí)， 最優(yōu)基（矩陣）保持不變。 優(yōu)化建模2.約束右端項(xiàng)變化的范圍（Right Hand Side RANGES）如本例中：第2行約束中當(dāng)前右端項(xiàng)（CURRENT RHS）=48， 允許增加（Allowable Increase）=INFINITY（無(wú)窮）、允許減少（Allowable Decrease）=24，說(shuō)明當(dāng)它在48-24，48+ ) = 24，）范圍變化時(shí)，最優(yōu)基保持不變。第3、4、5行可以類似解釋。不過(guò)由于此時(shí)約束發(fā)生變化，最優(yōu)基即使不變，最優(yōu)解、最優(yōu) 值

11、也會(huì)發(fā)生變化。如何變化呢？我們將在本節(jié)后面結(jié)合第1章1.2.1節(jié)例1.1給出的實(shí)際問(wèn)題來(lái)進(jìn)行說(shuō)明。 優(yōu)化建模最后，如果你對(duì)單純形法比較熟悉，你可以直接查看最優(yōu)解時(shí) 的單純形表，這只要選擇菜單命令Reports | Tableau (Alt+7) 執(zhí)行即可,輸出結(jié)果如下：ROW(BASIS)DESKSTABLESCHAIRS 1ART0.0005.0000.0002SLK20.000-2.0000.0003DESKS1.0001.2500.0004CHAIRS0.000-2.0001.0005SLK50.0001.0000.000ROWSLK2SLK3SLK4SLK510.00010.00010

12、.0000.000280.00021.0002.000-8.0000.00024.00030.0001.500-0.5000.0002.00040.000-4.0002.0000.0008.00050.0000.0000.0001.0005.000 優(yōu)化建模在輸出結(jié)果中， 基變量為BV=SLK2, Chairs, DESKS, SLK5，ART是人工變量（artificial variable）,即相應(yīng)的目標(biāo)值z(mì); 這樣，你就可以知道z = 5 TABLES + 10 SLK3 + 10 SLK4 = 280。敏感性分析結(jié)果表示的是最優(yōu)基保持不變的系數(shù)范圍。由此，也可以進(jìn)一步確定當(dāng)目標(biāo)函數(shù)的系

13、數(shù)和約束右端項(xiàng) 發(fā)生小的變化時(shí)，最優(yōu)解、最優(yōu)值如何變化。下面我們通 過(guò)求解第1章1.2.1節(jié)例1.1的實(shí)際問(wèn)題來(lái)進(jìn)行說(shuō)明。 優(yōu)化建模例2.5繼續(xù)討論例1.1Maxz = 72 x1 + 64x2x1 + x2 5012x1 + 8x2 4803x1 100x1 , x2 0在LINDO模型窗口中輸入模型問(wèn)題的數(shù)學(xué)模型：MAX72 x1 + 64 x2 SUBJECT TO2)x1 +x2 = 503)12 x1 + 8 x2 = 4804)3 x1= 100 END 優(yōu)化建模求解這個(gè)模型并做靈敏性分析，查看報(bào)告窗口（Reports Window）。輸出結(jié)果告訴我們：這個(gè)線性規(guī)劃的最優(yōu)解為x1=

14、20，x2=30，最優(yōu)值為z=3360，即用20桶牛奶生產(chǎn)A1, 30桶牛奶生產(chǎn)A2，可獲最大利潤(rùn)3360元。輸出中除了告訴我們問(wèn)題的最優(yōu)解和最優(yōu)值以外，還有許多對(duì)分析結(jié)果有用的信息，下面結(jié)合題目中提出的3個(gè)附加問(wèn)題給予說(shuō)明。3個(gè)約束條件的右端不妨看作3種“資源”：原料、勞動(dòng)時(shí)間、車間甲的加工能力。輸出中SLACK OR SURPLUS （松弛或剩余）給出這3種資源在最優(yōu)解下是否有剩余：原料、勞動(dòng)時(shí)間的剩余均為零（即約束為緊約束），車間甲尚余40公斤加工能力（不是緊約束）。 優(yōu)化建模目標(biāo)函數(shù)可以看作“效益”，成為緊約束的“資源”一旦增加， “效益”必然跟著增長(zhǎng)。輸出中DUAL PRICES（對(duì)

15、偶價(jià)格） 給出這3種資源在最優(yōu)解下“資源”增加1個(gè)單位時(shí)“效益”的增量：原料增加1個(gè)單位（1桶牛奶）時(shí)利潤(rùn)增長(zhǎng)48（元），勞動(dòng)時(shí)間增加1個(gè)單位（1 小時(shí)）時(shí)利潤(rùn)增長(zhǎng)2（元），而增加非緊約束車間甲的能力顯然不會(huì)使利潤(rùn)增長(zhǎng)。這里，“效益”的增量可以看作“資源”的潛在價(jià)值，經(jīng)濟(jì)學(xué)上稱為價(jià)格（shadow price），即1桶牛奶的價(jià)格為48元，1小時(shí)勞動(dòng)的價(jià)格為2元，車間甲生產(chǎn)能力的價(jià)格為零。可以用直接求解的辦法驗(yàn)證上面的結(jié)論，即將輸入文件中原料約束milk） 右端的50改為51，看看得到的最優(yōu)值（利潤(rùn)）是否恰好增長(zhǎng)48（元）。用價(jià)格的概念很容易回答附加問(wèn)題1）：用35元可以買到1桶牛奶，低于1價(jià)格

16、48，當(dāng)然應(yīng)該作這項(xiàng)投資?；卮鸶郊訂?wèn)題2）：聘用臨時(shí)桶牛奶的工人以增加勞動(dòng)時(shí)間，付給的工資低于勞動(dòng)時(shí)間的 潤(rùn)，所以工資最多是每小時(shí)2元。價(jià)格才可以增加利 優(yōu)化建模目標(biāo)函數(shù)的系數(shù)發(fā)生變化時(shí)（假定約束條件不變），最優(yōu) 解和最優(yōu)值會(huì)改變嗎？這個(gè)問(wèn)題不能簡(jiǎn)單地回答。上面的輸出結(jié)果給出了最優(yōu)基不變條件下目標(biāo)函數(shù)系數(shù)的允許變化范圍：x1的系數(shù)范圍為（72-8，72+24）=（64，96）；x2的系數(shù)范圍為（64-16，64+8）=（48，72）。注意：x1系數(shù)的允許范圍需要x2的系數(shù)64不變，反之亦然。由于目標(biāo)函數(shù)的系數(shù)變化并不影響約束條件，因此此時(shí)最優(yōu)基不變可以保證最優(yōu)解也不變，但最優(yōu)值變化。用這個(gè)結(jié)果

17、很容易回答附加問(wèn)題3）：若每公斤A1的獲利增加到30 元，則x1系數(shù)變?yōu)?03=90，在允許范圍內(nèi)，所以不應(yīng)改變生產(chǎn)計(jì)劃，但最優(yōu)值變?yōu)?020+6430=3720。 優(yōu)化建模下面對(duì)“資源”的價(jià)格作進(jìn)一步的分析。價(jià)格的作用（即在最優(yōu)解下“資源”增加1個(gè)單位時(shí)“效益”的增量）是有限制的。每增加1桶牛奶利潤(rùn)增長(zhǎng)48元（價(jià)格），但是，約束的右端項(xiàng)（CURRENT RHS） 的“允許增加”（ALLOWABLEINCREASE） 和 “允許減少”（ALLOWABLEDECREASE）給出了價(jià)格有意義條件下約束右端的限制范圍（因?yàn)榇藭r(shí)最優(yōu)基不變，所以那么結(jié)果中給出的價(jià)格才有意義；如果最優(yōu)基已經(jīng)變了，價(jià)格也就不正確了）。具體對(duì)本例來(lái)說(shuō)： milk）原料最多增加10（桶牛奶），time） 勞動(dòng)時(shí)間最多增加53（小時(shí)）?，F(xiàn)在可以回答附加問(wèn)題1）的第2問(wèn)：雖然應(yīng)該批準(zhǔn)用35元買1 桶牛奶的投資，但每天最多購(gòu)買10桶牛奶。順便地說(shuō)，可以用低于每小時(shí)2元的工資聘用臨時(shí)工人以增加勞動(dòng)時(shí)間，但最多增 加53.3333小時(shí)。 優(yōu)化