運籌學_lingo軟件

1、 lingo軟件簡介軟件簡介 -優(yōu)化及數(shù)學規(guī)劃數(shù)學規(guī)劃模型數(shù)學規(guī)劃模型 實際問題中實際問題中的優(yōu)化模型的優(yōu)化模型mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x決策變量決策變量f(x)目標函數(shù)目標函數(shù)gi(x) 0約束條件約束條件多元函數(shù)多元函數(shù)條件極值條件極值 決策變量個數(shù)決策變量個數(shù)n和和約束條件個數(shù)約束條件個數(shù)m較大較大 最優(yōu)解在可行域最優(yōu)解在可行域的邊界上取得的邊界上取得 數(shù)數(shù)學學規(guī)規(guī)劃劃線性規(guī)劃線性規(guī)劃非線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃線性規(guī)劃問題的線性規(guī)劃問題的標準形式標準形式1 12 211 112 2111 12 21max 00

2、n nn nmmmn nmnZcxc xc xa xa xa xba xa xa xbxx目標函數(shù)：目標函數(shù)：約束條件：約束條件：非線性規(guī)劃非線性規(guī)劃( ) 0,1 ,.,( ) 0,1 ,.,injg xipXx Rh xjq約束集或可行域約束集或可行域例例1 加工奶制品的生產(chǎn)計劃加工奶制品的生產(chǎn)計劃1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時間時間480小時小時 至多加工至多加工100公斤公斤A1 制訂生產(chǎn)計劃，使每天獲利最大制訂生產(chǎn)計劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？

3、若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應否改變生產(chǎn)計劃？公斤，應否改變生產(chǎn)計劃？ 每天：每天：1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應原料供應 5021 xx勞動時間勞動時間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標函數(shù)目標函數(shù) 216472xxzMax每天獲利每天獲利約束條件約束

4、條件非負約束非負約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時間時間480小時小時 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型求解模型求解 圖解法圖解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx約約束束條條件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMax目標目標函數(shù)函數(shù) Z=0Z=2400Z=3600z=c (常數(shù)常數(shù)) 等值線等值線c在在B(20,30)點得到最優(yōu)解點得到最優(yōu)解目標函數(shù)和約束條件是線性函數(shù)目標函數(shù)和約束條件是線性函數(shù)

5、 可行域為直線段圍成的凸多邊形可行域為直線段圍成的凸多邊形 目標函數(shù)的等值線為直線目標函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊最優(yōu)解一定在凸多邊形的某個頂點取得。形的某個頂點取得。 模型求解模型求解 軟件實現(xiàn)軟件實現(xiàn) LINDO 6.1 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUA

6、L PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤，利潤3360元。元。 結果解釋結果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SU

7、RPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2原料無剩余原料無剩余時間無剩余時間無剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 結果解釋結果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED

8、 COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2最優(yōu)解下最優(yōu)解下“資源資源”增加增加1單位時單位時“效益效益”的增的增量量 原料增加原料增加1單位單位, 利潤增長利潤增長48 時間增加時間增加1單位單位, 利潤增長利潤增長2 加工能力增長不影響利潤加工能力增長不影響利潤影子價格影子價格 35元可買到元可買到1桶牛奶，

9、要買嗎？桶牛奶，要買嗎？35 48, 應該買！應該買！ 聘用臨時工人付出的工資最多每小時幾元？聘用臨時工人付出的工資最多每小時幾元？ 2元！元！RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWAB

10、LE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000最優(yōu)解不變時目標函最優(yōu)解不變時目標函數(shù)系數(shù)允許變化范圍數(shù)系數(shù)允許變化范圍 DO RANGE(SENSITIVITY) ANALYSIS? Yesx1系數(shù)范圍系數(shù)范圍(64,96) x2系數(shù)范圍系數(shù)范圍(48,72) A1獲利增加到獲利增加到 30元元/千克，應否改變生產(chǎn)計劃千克，應否改變生產(chǎn)計劃 x1系數(shù)由系數(shù)由24 3=72增加增加為為

11、30 3=90，在在允許范圍內(nèi)允許范圍內(nèi) 不變！不變！(約束條件不變約束條件不變)結果解釋結果解釋 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCRE

12、ASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000影子價格有意義時約束右端的允許變化范圍影子價格有意義時約束右端的允許變化范圍 原料最多增加原料最多增加10 時間最多增加時間最多增加53 35元可買到元可買到1桶牛奶，每天最多買多少？桶牛奶，每天最多買多少？最多買最多買10桶桶!(目標函數(shù)不變目標函數(shù)不變)例例2 奶制品的生產(chǎn)銷售計劃奶制品的生產(chǎn)銷售計劃 在例在例1基礎上深加工基礎上深加工1桶桶牛奶牛奶 3千克千克A1 12小時小

13、時 8小時小時 4公斤公斤A2 或或獲利獲利24元元/公斤公斤 獲利獲利16元元/公斤公斤 0.8千克千克B12小時小時,3元元1千克千克獲利獲利44元元/千克千克 0.75千克千克B22小時小時,3元元1千克千克獲利獲利32元元/千克千克 制訂生產(chǎn)計劃，使每天凈利潤最大制訂生產(chǎn)計劃，使每天凈利潤最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小時時間，應否投小時時間，應否投資？現(xiàn)投資資？現(xiàn)投資150元，可賺回多少？元，可賺回多少？50桶牛奶桶牛奶, 480小時小時 至多至多100公斤公斤A1 B1，B2的獲利經(jīng)常有的獲利經(jīng)常有10%的波動，對計劃有無影響？的波動，對計劃有無影

14、響？1桶桶牛奶牛奶 3千克千克 A1 12小時小時 8小時小時 4千克千克 A2 或或獲利獲利24元元/千克千克 獲利獲利16元元/kg 0.8千克千克 B12小時小時,3元元1千克千克獲利獲利44元元/千克千克 0.75千克千克 B22小時小時,3元元1千克千克獲利獲利32元元/千克千克 出售出售x1 千克千克 A1, x2 千克千克 A2， X3千克千克 B1, x4千克千克 B2原料原料供應供應 勞動勞動時間時間 加工能力加工能力 決策決策變量變量 目標目標函數(shù)函數(shù) 利潤利潤約束約束條件條件非負約束非負約束 0,61xx x5千克千克 A1加工加工B1， x6千克千克 A2加工加工B26

15、543213332441624xxxxxxzMax50436251xxxx48022)(2)(4656251xxxxxx10051 xx附加約束附加約束 5380 x.x64750 x.x 模型求解模型求解 軟件實現(xiàn)軟件實現(xiàn) LINDO 6.1 5043) 26251xxxx48022)(2)(4)3656251xxxxxx OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.

16、000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2600334) 26521xxxx44804624) 36521xxxxDO RANGE (SENSITIVITY) ANALYSIS? No OBJECTIVE FU

17、NCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000

18、 6) 0.000000 32.000000 NO. ITERATIONS= 2結果解釋結果解釋每天銷售每天銷售168 千克千克A2和和19.2 千克千克B1， 利潤利潤3460.8（元）（元）8桶牛奶加工成桶牛奶加工成A1，42桶桶牛奶加工成牛奶加工成A2，將得到的將得到的24千克千克A1全部全部加工成加工成B1 除加工能力外均除加工能力外均為緊約束為緊約束結果解釋結果解釋 OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X

19、3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000增加增加1桶牛奶使利潤增桶牛奶使利潤增長長3.1612=37.925043)26251xxxx600334) 26521xxxx4增加增加1小時時間使利

20、小時時間使利潤增長潤增長3.26 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小時時間，小時時間，應否投資？現(xiàn)投資應否投資？現(xiàn)投資150元，可賺回多少？元，可賺回多少？投資投資150元增加元增加5桶牛奶，桶牛奶，可賺回可賺回189.6元。（大于元。（大于增加時間的利潤增長）增加時間的利潤增長）結果解釋結果解釋B1,B2的獲利有的獲利有10%的波動，對計劃有無影響的波動，對計劃有無影響 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE

21、 COEF INCREASE DECREASE X1 24.000000 1.680000 INFINITY X2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000 2.026667 INFINITY X5 -3.000000 15.800000 2.533334 X6 -3.000000 1.520000 INFINITY DO RANGE (SENSITIVITY) ANALYSIS? YesB1獲利下降獲利下降10%，超，超出出X3 系數(shù)允許范圍系數(shù)允許范圍B2獲利上升獲利上升10%，超，超出

22、出X4 系數(shù)允許范圍系數(shù)允許范圍波動對計劃有影響波動對計劃有影響生產(chǎn)計劃應重新制訂：如將生產(chǎn)計劃應重新制訂：如將x3的系數(shù)改為的系數(shù)改為39.6計算，會發(fā)現(xiàn)結果有很大變化。計算，會發(fā)現(xiàn)結果有很大變化。 問題問題1. 如何下料最節(jié)省如何下料最節(jié)省 ? 例例3 鋼管下料鋼管下料 問題問題2. 客戶增加需求：客戶增加需求：原料鋼管原料鋼管: :每根每根19米米 4米米50根根 6米米20根根 8米米15根根 客戶需求客戶需求節(jié)省的標準是什么？節(jié)省的標準是什么？由于采用不同切割模式太多，會增加生產(chǎn)和管理成本，由于采用不同切割模式太多，會增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過規(guī)定切割模式不能超過3種。

23、如何下料最節(jié)?。糠N。如何下料最節(jié)??？5米米10根根 按照客戶需要在一根原料鋼管上安排切割的一種組合。按照客戶需要在一根原料鋼管上安排切割的一種組合。 切割模式切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根 余料余料3米米 4米米1根根 6米米1根根 6米米1根根 合理切割模式合理切割模式的余料應小于客戶需要鋼管的最小尺寸的余料應小于客戶需要鋼管的最小尺寸余料余料3米米 8米米1根根 8米米1根根 鋼管下料鋼管下料 為滿足客戶需要，按照哪些種合理模式，每種模式為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)?。壳懈疃嗌俑箱摴?，最為節(jié)?。亢侠砬懈钅Ｊ?/p>

24、合理切割模式2. 所用原料鋼管總根數(shù)最少所用原料鋼管總根數(shù)最少 模式模式 4米鋼管根數(shù)米鋼管根數(shù)6米鋼管根數(shù)米鋼管根數(shù)8米鋼管根數(shù)米鋼管根數(shù)余料余料(米米)14003231013201341203511116030170023鋼管下料問題鋼管下料問題1 1 兩種兩種標準標準1. 原料鋼管剩余總余量最小原料鋼管剩余總余量最小xi 按第按第i 種模式切割的原料鋼管根數(shù)種模式切割的原料鋼管根數(shù)( (i= =1,2,7) ) 約束約束滿足需求滿足需求 決策決策變量變量 目標目標1（總余量）（總余量）765432113333xxxxxxxZMin5023454321xxxxx20326542xxxx15

25、2753xxx按模式按模式2切割切割12根根, ,按模式按模式5切割切割15根，余料根，余料27米米 模模式式4米米根數(shù)根數(shù)6米米根數(shù)根數(shù)8米米根數(shù)根數(shù)余余料料14003231013201341203511116030170023需需求求502015最優(yōu)解：最優(yōu)解：x2=12, x5=15, 其余為其余為0；最優(yōu)值：最優(yōu)值：27。整數(shù)約束：整數(shù)約束： xi 為整數(shù)為整數(shù)當余料沒有用處時，當余料沒有用處時，通常以總根數(shù)最少為目標通常以總根數(shù)最少為目標 76543212xxxxxxxZMin目標目標2（總根數(shù)）（總根數(shù)）鋼管下料問題鋼管下料問題1 1 約束條約束條件不變件不變 最優(yōu)解：最優(yōu)解：x2

26、=15, x5=5, x7=5, 其余為其余為0；最優(yōu)值：最優(yōu)值：25。5023454321xxxxx20326542xxxx152753xxxxi 為整數(shù)按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式7切割切割5根，根，共共25根，余料根，余料35米米 雖余料增加雖余料增加8米，但減少了米，但減少了2根根 與與目標目標1的結果的結果“共切割共切割27根，余料根，余料27米米” 相比相比 鋼管下料問題鋼管下料問題2對大規(guī)模問題，用模型的約束條件界定合理模式對大規(guī)模問題，用模型的約束條件界定合理模式增加一種需求：增加一種需求：5米米10根；切割根；切割模式不超過模

27、式不超過3種。種。現(xiàn)有現(xiàn)有4種種需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，用枚舉法確定合理切割模式，過于復雜。根，用枚舉法確定合理切割模式，過于復雜。決策變量決策變量 xi 按第按第i 種模式切割的原料鋼管根數(shù)種模式切割的原料鋼管根數(shù)( (i= =1,2,3) ) r1i, r2i, r3i, r4i 第第i 種切割模式下，每根原料鋼管種切割模式下，每根原料鋼管生產(chǎn)生產(chǎn)4米、米、5米、米、6米和米和8米長的鋼管的數(shù)量米長的鋼管的數(shù)量滿足需求滿足需求50313212111xrxrxr10323222121xrxrxr20333232131xrxrxrxrxr模式合理：每根模式合理：每根余料不超過余料不超過3米米1986541641312111rrrr1986541642322212rrrr1986541643332313rrrr整數(shù)非線性規(guī)劃模型整數(shù)非線性規(guī)劃模型鋼管下料問題鋼管下料問題2目標函數(shù)（目標函數(shù)（總根數(shù)）總根數(shù)）321xxxMin約束約束條件條件整數(shù)約束：整數(shù)約束： xi ,r1i, r2i, r3i, r4i ( (i= =1,2,3) )為整數(shù)為整數(shù)增加約束，縮小可行域，便于求解增加約束，縮小可行域，便于求解321xxx原料鋼管總根數(shù)下界：原料