LINGO模型實(shí)例及求解PPT課件

1、 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/91LINGO模型實(shí)例與求解模型實(shí)例與求解下料問題下料問題背包問題背包問題選址問題選址問題指派問題指派問題 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/92問題問題1. 如何下料最節(jié)省如何下料最節(jié)省 ? 下料問題下料問題 問題問題2. 客戶增加需求：客戶增加需求：原料鋼管原料鋼管: :每根每根19米米 4米米50根根 6米米20根根 8米米15根根 客戶需求客戶需求節(jié)省的標(biāo)準(zhǔn)是什么？節(jié)省的標(biāo)準(zhǔn)是什么？由于采用不同切割模式太多，會增加生產(chǎn)和管理成本，由于采用不同切割模

2、式太多，會增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過規(guī)定切割模式不能超過3種。如何下料最節(jié)省？種。如何下料最節(jié)省？5米米10根根 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/93按照客戶需要在一根原料鋼管上安排切割的一種組合。按照客戶需要在一根原料鋼管上安排切割的一種組合。 切割模式切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根 余料余料3米米 4米米1根根 6米米1根根 6米米1根根 合理切割模式合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸的余料應(yīng)小于客戶需要鋼管的最小尺寸余料余料3米米 8米米1根根 8米米1根根 鋼管下料鋼管

3、下料 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/94為滿足客戶需要，按照哪些種合理模式，每種模式為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)?。壳懈疃嗌俑箱摴?，最為節(jié)?。亢侠砬懈钅Ｊ胶侠砬懈钅Ｊ?. 所用原料鋼管總根數(shù)最少所用原料鋼管總根數(shù)最少 模式模式 4米鋼管根數(shù)米鋼管根數(shù)6米鋼管根數(shù)米鋼管根數(shù)8米鋼管根數(shù)米鋼管根數(shù)余料余料(米米)14003231013201341203511116030170023鋼管下料問題鋼管下料問題1 1 兩種兩種標(biāo)準(zhǔn)標(biāo)準(zhǔn)1. 原料鋼管剩余總余量最小原料鋼管剩余總余量最小 安陽師范學(xué)院數(shù)學(xué)與

4、統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/95xi 按第i 種模式切割的原料鋼管根數(shù)(i=1,2,7) 約束約束滿足需求滿足需求 決策變量決策變量 目標(biāo)目標(biāo)1（總余量）（總余量）765432113333xxxxxxxZMin5023454321xxxxx20326542xxxx152753xxx按模式按模式2切割切割12根根, ,按模式按模式5切割切割15根，余料根，余料27米米 模模式式4米米根數(shù)根數(shù)6米米根數(shù)根數(shù)8米米根數(shù)根數(shù)余余料料14003231013201341203511116030170023需需求求502015最優(yōu)解：最優(yōu)解：x2=12, x5=15,

5、 其余為其余為0；最優(yōu)值：最優(yōu)值：27整數(shù)約束：整數(shù)約束： xi 為整數(shù)為整數(shù) 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/96當(dāng)余料沒有用處時，當(dāng)余料沒有用處時，通常以總根數(shù)最少為目標(biāo)通常以總根數(shù)最少為目標(biāo) 76543212xxxxxxxZMin目標(biāo)目標(biāo)2（總根數(shù)）（總根數(shù)）約束條約束條件不變件不變 最優(yōu)解：最優(yōu)解：x2=15, x5=5, x7=5, 其余為其余為0；最優(yōu)值：最優(yōu)值：25。5023454321xxxxx20326542xxxx152753xxxxi 為整數(shù)按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式

6、7切割切割5根，根，共共25根，余料根，余料35米米 雖余料增加雖余料增加8米，但減少了米，但減少了2根根 與與目標(biāo)目標(biāo)1的結(jié)果的結(jié)果“共切割共切割27根，余料根，余料27米米” 相比相比 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/97鋼管下料問題鋼管下料問題2 2對大規(guī)模問題，用模型的約束條件界定合理模式對大規(guī)模問題，用模型的約束條件界定合理模式增加一種需求：增加一種需求：5米米10根；切割根；切割模式不超過模式不超過3種。種。現(xiàn)有現(xiàn)有4種種需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，用枚舉法確定合理切割模式，過

7、于復(fù)雜。根，用枚舉法確定合理切割模式，過于復(fù)雜。決策變量決策變量 (15維)xi 按第按第i 種模式切割的原料鋼管根數(shù)種模式切割的原料鋼管根數(shù)( (i= =1,2,3) ) r1i, r2i, r3i, r4i 第第i 種切割模式下，每根原料鋼管種切割模式下，每根原料鋼管生產(chǎn)生產(chǎn)4米、米、5米、米、6米和米和8米長的鋼管的數(shù)量米長的鋼管的數(shù)量 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/98滿足需求滿足需求50313212111xrxrxr10323222121xrxrxr20333232131xrxrxrxrxr模式合理：每

8、根模式合理：每根余料不超過余料不超過3米米1986541641312111rrrr1986541642322212rrrr1986541643332313rrrr整數(shù)非線性規(guī)劃模型整數(shù)非線性規(guī)劃模型鋼管下料問題鋼管下料問題2 2目標(biāo)函數(shù)（目標(biāo)函數(shù)（總根數(shù)）總根數(shù)）321xxxMin約束約束條件條件整數(shù)約束：整數(shù)約束： xi ,r1i, r2i, r3i, r4i ( (i= =1,2,3) )為整數(shù)為整數(shù) 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/99增加約束，縮小可行域，便于求解增加約束，縮小可行域，便于求解321xxx原料鋼管總根數(shù)下界：原料鋼管

9、總根數(shù)下界：( (最佳切割方式最佳切割方式) ) 2619158206105504特殊生產(chǎn)計劃特殊生產(chǎn)計劃(簡單切割方式簡單切割方式)：對每根原料鋼管：對每根原料鋼管模式模式1：切割成：切割成4根根4米鋼管，需米鋼管，需13根；根；模式模式2：切割成：切割成1根根5米和米和2根根6米鋼管，需米鋼管，需10根；根；模式模式3：切割成：切割成2根根8米鋼管，需米鋼管，需8根。根。原料鋼管總根數(shù)上界：原料鋼管總根數(shù)上界：31 3126321xxx模式排列順序可任定模式排列順序可任定 需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根根每根原料鋼管長每根原料鋼管長19米米

10、安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/910LINGOLINGO求解整數(shù)非線性規(guī)劃模型求解整數(shù)非線性規(guī)劃模型Local optimal solution found at iteration: 12211 Objective value: 28.00000Variable Value Reduced CostX1 10.00000 0.000000X2 10.00000 2.000000X3 8.000000 1.000000R11 3.000000 0.000000R12 2.000000 0.000000R13 0.000000 0.0000

11、00R21 0.000000 0.000000R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000 模式模式1：每根原料鋼管切割成：每根原料鋼管切割成3根根4米和米和1根根6米鋼管，共米鋼管，共10根；根；模式模式2：每根原料鋼管切割成：每根原料鋼管切割成2根根4米、米、1根根5米和米和1根根6米鋼管

12、，米鋼管，共共10根；根；模式模式3：每根原料鋼管切割成：每根原料鋼管切割成2根根8米鋼管，共米鋼管，共8根。根。原料鋼管總根數(shù)為原料鋼管總根數(shù)為28根。根。 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/911 某人打算外出旅游并登山，路程比較遠(yuǎn)，途中要坐火車和飛機(jī)，考慮要帶許多必要的旅游和生活用品，例如照相機(jī)、攝像機(jī)、食品、衣服、雨具、書籍等等，共n件物品，重量分別為ai，而受航空行李重量限制，以及個人體力所限，能帶的行李總重量為b，n件物品的總重量超過了b，需要裁減，該旅行者為了決策帶哪些物品，對這些物品的重要性進(jìn)行了量化，用ci表示，試建立該問題

13、的數(shù)學(xué)模型這個問題稱為背包問題(Knapsack Problem)背包問題背包問題 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/912.,2 , 1,0或1,s.t.,max1nixbxaxcziiiniii 解：解：若引入0-1型決策變量xi，xi=1表示物品i放入背包中，否則不放，則背包問題等價于如下0-1線性規(guī)劃： 假設(shè)現(xiàn)有8件物品，它們的重量分別為1,3,4,3,3,1,5,10(kg)，價值分別為2,9,3,8,10,6,4,10(元)，假如總重量限制不超過15kg，試決策帶哪些物品，使所帶物品的總價值最大 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范

14、學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/913 編寫LINGO程序如下： MODEL: SETS: WP/W1.W8/:A,C,X; ENDSETS DATA: A=1 3 4 3 3 1 5 10; C=2 9 3 8 10 6 4 10; ENDDATA MAX=SUM(WP:C*X); !目標(biāo)函數(shù); FOR(WP:BIN(X); !限制X為0-1變量; SUM(WP:A*X)=15; END 求解得到結(jié)果：帶16號物品，總價值為38 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/914 選址問題選址問題 某公司有某公司有6個建筑工地，位

15、置坐標(biāo)為個建筑工地，位置坐標(biāo)為(ai, bi) (單位：單位：公里公里),水泥日用量水泥日用量di (單位：噸）單位：噸）假設(shè)：假設(shè)：料場料場和工地之間和工地之間有直線道路有直線道路 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/915用例中數(shù)據(jù)計算，最優(yōu)解為i1234561ic（料料場場 A）3507012ic（料料場場 B）00406102 , 1,6,.,1,. .)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij線性規(guī)劃模型線性規(guī)劃模型決策變量：決策變量：ci j (料場料場j到到工地工地i的的運(yùn)量

16、）運(yùn)量）12維維 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/916選址問題：選址問題：NLPNLP2）改建兩個新料場，需要確定新料場位置）改建兩個新料場，需要確定新料場位置(xj,yj)和和運(yùn)量運(yùn)量cij ，在其它條件不變下使總噸公里數(shù)最小。，在其它條件不變下使總噸公里數(shù)最小。2 , 1,6,.,1,. .)()(min612121612/ 122jecidctsbyaxcjijiiijjjiijijij決策變量：決策變量：ci j，(xj,yj)16維維非線性規(guī)劃模型非線性規(guī)劃模型 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌

17、學(xué)實(shí)驗(yàn)2021/3/917LINGO模型的構(gòu)成：模型的構(gòu)成：4個段個段集合段（集合段（SETS ENDSETS）數(shù)據(jù)段（數(shù)據(jù)段（DATA ENDDATA）初始段（初始段（INIT ENDINIT） 目標(biāo)與目標(biāo)與約束段約束段 局部最優(yōu)：局部最優(yōu)：89.8835(噸公里噸公里 ) LP：移到數(shù)據(jù)段：移到數(shù)據(jù)段 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/918邊界 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/919例例: : 某班某班8名同學(xué)準(zhǔn)備分成名同學(xué)準(zhǔn)備分成4個調(diào)查隊個調(diào)查隊(每隊兩人每隊兩人)前往前往4個地

18、區(qū)個地區(qū)進(jìn)行社會調(diào)查進(jìn)行社會調(diào)查,假設(shè)這假設(shè)這8名同學(xué)兩兩之間組隊的效率如下表名同學(xué)兩兩之間組隊的效率如下表,問問:如何組隊可以使總效率最高如何組隊可以使總效率最高? 學(xué)生學(xué)生 S1 S2 S3 S4 S5 S6 S7 S8S19342156S2173521S344292S41552S5876S623S74S888,()1188,11max. .1,1()01i ji jijjii ji ji jijB Ms tMMijM或指派問題指派問題 安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院安陽師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院運(yùn)籌學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)實(shí)驗(yàn)2021/3/920model:sets: students/s1.s8/; pairs(students, students)|2#gt# 1, BENEFIT, MATCH;EndsetsData BENEFIT= 9 3 4 2 1 5 6 1 7 3 5 2 1 4 4 2 9 2 1 5 5 2 8 7 6 2