《數(shù)學模型》第五節(jié)_Lingo軟件的最優(yōu)化求解

1、第四節(jié)第四節(jié)優(yōu)化模型優(yōu)化模型/LINGO優(yōu)化軟件優(yōu)化軟件張軍本張軍本山東農(nóng)業(yè)大學數(shù)學系山東農(nóng)業(yè)大學數(shù)學系 TelMail：簡要提綱簡要提綱 優(yōu)化模型簡介優(yōu)化模型簡介 LINGO軟件的使用簡介軟件的使用簡介 建模與求解實例（結(jié)合軟件使用）建模與求解實例（結(jié)合軟件使用）優(yōu)化模型優(yōu)化模型 實際問題中實際問題中的優(yōu)化模型的優(yōu)化模型mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x決策變量決策變量f(x)目標函數(shù)目標函數(shù)gi(x) 0約束條件約束條件數(shù)學規(guī)劃數(shù)學規(guī)劃線性規(guī)劃線性規(guī)劃(LP)二次規(guī)劃二次規(guī)劃(QP)非線性規(guī)劃非線性規(guī)劃(

2、NLP)純整數(shù)規(guī)劃純整數(shù)規(guī)劃(PIP)混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃(MIP)整數(shù)規(guī)劃整數(shù)規(guī)劃(IP)0-1整數(shù)規(guī)劃整數(shù)規(guī)劃一般整數(shù)規(guī)劃一般整數(shù)規(guī)劃連續(xù)規(guī)劃連續(xù)規(guī)劃LINDOLINDO和和LINGOLINGO軟件能求解的優(yōu)化模型軟件能求解的優(yōu)化模型 LINGO LINDO優(yōu)化模型優(yōu)化模型線性規(guī)劃線性規(guī)劃(LP)非線性規(guī)劃非線性規(guī)劃(NLP)二次規(guī)劃二次規(guī)劃(QP)連續(xù)優(yōu)化連續(xù)優(yōu)化整數(shù)規(guī)劃整數(shù)規(guī)劃(IP) LP QP NLP IP 全局優(yōu)化全局優(yōu)化(選選) ILP IQP INLP LINDO/LINGO軟件的求解過程 LINDO/LINGO預處理程序預處理程序線性優(yōu)化求解程序線性優(yōu)化求解程序非線性優(yōu)

3、化求解程序非線性優(yōu)化求解程序分枝定界管理程序分枝定界管理程序1. 確定常數(shù)確定常數(shù)2. 識別類型識別類型1. 單純形算法單純形算法2. 內(nèi)點算法內(nèi)點算法(選選)1、順序線性規(guī)劃法、順序線性規(guī)劃法(SLP) 2、廣義既約梯度法、廣義既約梯度法(GRG) (選選) 3、多點搜索、多點搜索(Multistart) (選選) 建模時需要注意的幾個基本問題建模時需要注意的幾個基本問題 1、盡量使用實數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量盡量使用實數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個數(shù)盡量使用光滑優(yōu)化，減少非光滑約束的個數(shù) 如：盡量少使用絕對值、符號函數(shù)、多個變量求如：盡量少使用

4、絕對值、符號函數(shù)、多個變量求最大最大/最小值、四舍五入、取整函數(shù)等最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變盡量使用線性模型，減少非線性約束和非線性變量的個數(shù)量的個數(shù) （如（如x/y 5 改為改為x5y）4、合理設定變量上下界，盡可能給出變量初始值合理設定變量上下界，盡可能給出變量初始值 5、模型中使用的參數(shù)數(shù)量級要適當模型中使用的參數(shù)數(shù)量級要適當 (如小于如小于103)Lingo需要掌握的幾個重要方面需要掌握的幾個重要方面 掌握集合掌握集合(SETS)的應用；的應用； 正確閱讀求解報告；正確閱讀求解報告； 正確理解求解狀態(tài)窗口；正確理解求解狀態(tài)窗口； 學會設置

5、基本的求解選項學會設置基本的求解選項(OPTIONS) ； 掌握與外部文件的基本接口方法掌握與外部文件的基本接口方法例例1 加工奶制品的生產(chǎn)計劃加工奶制品的生產(chǎn)計劃1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時間時間480小時小時 至多加工至多加工100公斤公斤A1 制訂生產(chǎn)計劃，使每天獲利最大制訂生產(chǎn)計劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到的獲利增加到

6、 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每天獲利每天獲利約束條件約束條件非負約束非負約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時間時間480小時小時 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛

7、奶 每天每天模型求解模型求解 Global optimal solution found. Objective value: 3360.000 Infeasibilities: 0.000000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40

8、.00000 0.00000020桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤，利潤3360元。元。 model:max=72*x1+64*x2;milk x1+x250;time 12*x1+8*x2480;cpct 3*x1100; end模型求解模型求解 reduced cost值表值表示當該非基變量示當該非基變量增加一個單位時增加一個單位時（其他非基變量（其他非基變量保持不變）目標保持不變）目標函數(shù)減少的量函數(shù)減少的量(對對max型問題型問題) Global optimal solution found. Objective value: 3360.000 Infeasibi

9、lities: 0.000000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000也可理解為：也可理解為：為了使該非基變?yōu)榱耸乖摲腔兞孔兂苫兞浚孔兂苫兞?，目標函?shù)中對應目標函數(shù)中對應系數(shù)應增加的量系數(shù)應增加

10、的量 Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Pric 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000原料無剩余原料無剩余時間無剩余時間無剩余加工能力

11、剩余加工能力剩余40model:max=72*x1+64*x2;milk x1+x250;time 12*x1+8*x2480;cpct 3*x1100; end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 結(jié)果解釋結(jié)果解釋 Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Sl

12、ack or Surplus Dual Pric 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000結(jié)果解釋結(jié)果解釋 最優(yōu)解下最優(yōu)解下“資源資源”增增加加1單位時單位時“效益效益”的的增量增量 原料增原料增1單位單位, 利潤增利潤增48 時間加時間加1單位單位, 利潤增利潤增2 能力增減不影響利潤能力增減不影響利潤影子價格影子價格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？ 35 48, 應該買！應該買！ 聘用臨時工人付出的工資最多每小時幾元？聘用臨時工人付

13、出的工資最多每小時幾元？ 2元！元！Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00

14、000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000最優(yōu)解不變時目標最優(yōu)解不變時目標系數(shù)允許變化范圍系數(shù)允許變化范圍 DO RANGE(SENSITIVITY) ANALYSIS x1系數(shù)范圍系數(shù)范圍(64,96) x2系數(shù)范圍系數(shù)范圍(48,72) A1獲利增加到獲利增加到 30元元/千克，應否改變生產(chǎn)計劃千克，應否改變生產(chǎn)計劃 x1系數(shù)由系數(shù)由24 3= 72 增加增加為為30 3= 90，在，在允許范允許范圍內(nèi)圍內(nèi) 不變！不變！(約束條件不變約束條件不變)結(jié)果解釋結(jié)果解釋

15、 結(jié)果解釋結(jié)果解釋 Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable AllowableVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side RangesRow Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.000

16、00 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000影子價格有意義影子價格有意義時約束右端的允時約束右端的允許變化范圍許變化范圍 原料最多增加原料最多增加10 時間最多增加時間最多增加53 35元可買到元可買到1桶牛奶，每天最多買多少？桶牛奶，每天最多買多少？最多買最多買10桶？桶？(目標函數(shù)不變目標函數(shù)不變)注意注意: 充分但充分但可能不必要可能不必要LINGO軟件簡介軟件簡介目標與約束段目標與約束段 集合段（集合段（SETS ENDSETS） 數(shù)據(jù)段（數(shù)據(jù)段（DATA ENDDATA）初始段（

17、初始段（INIT ENDINIT）計算段（計算段（CALC ENDCALC）LINGO9.0模型的構(gòu)成：模型的構(gòu)成：5個段個段LINGO模型的優(yōu)點模型的優(yōu)點提供了靈活的編程語言（矩陣生成器）提供了靈活的編程語言（矩陣生成器）LINGOLINGO模型模型 例：選址問題例：選址問題某公司有某公司有6個建筑工地，位置坐標為個建筑工地，位置坐標為(ai, bi) (單位：公里單位：公里),水泥日用量水泥日用量di (單位：噸）單位：噸）ia1.258.750.55.7537.25b1.250.754.7556.57.75d35476111)現(xiàn)有 2 料場，位于 A (5, 1), B (2, 7),記

18、(xj,yj),j=1,2, 日儲量 ej各有 20 噸。假設：假設：料場料場和工地之間和工地之間有直線道路有直線道路目標：制定每天的供應計劃，即從 A, B 兩料場分別向各工地運送多少噸水泥，使總的噸公里數(shù)最小。用例中數(shù)據(jù)計算，最優(yōu)解為i1234561ic（料料場場 A）3507012ic（料料場場 B）00406102 , 1,6,.,1,. .)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij線性規(guī)劃模型線性規(guī)劃模型決策變量：決策變量：ci j (料場料場j到到工地工地i的的運量）運量）12維維選址問題：選址問題：NLPNLP2）改建兩個新

19、料場，需要確定新料場位置）改建兩個新料場，需要確定新料場位置(xj,yj)和和運量運量cij ，在其它條件不變下使總噸公里數(shù)最小。，在其它條件不變下使總噸公里數(shù)最小。2 , 1,6,.,1,. .)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij決策變量：決策變量：ci j，(xj,yj)16維維非線性規(guī)劃模型非線性規(guī)劃模型LINGO模型的構(gòu)成：模型的構(gòu)成：4個段個段集合段（集合段（SETS ENDSETS）數(shù)據(jù)段（數(shù)據(jù)段（DATA ENDDATA）初始段（初始段（INIT ENDINIT） 目標與目標與約束段約束段 局部最優(yōu)：局部最優(yōu)：89.8

20、835(噸公里噸公里 ) LP：移到數(shù)據(jù)段：移到數(shù)據(jù)段邊界集合的類型集合的類型 集合集合 派生集合派生集合 基本集合基本集合 稀疏集合稀疏集合 稠密集合稠密集合 元素列表法元素列表法 元素過濾法元素過濾法 直接列舉法直接列舉法 隱式列舉法隱式列舉法setname /member_list/ : attribute_list;setname(parent_set_list) /member_list/ : attribute_list;SETS: CITIES /A1,A2,A3,B1,B2/; ROADS(CITIES, CITIES)/ A1,B1 A1,B2 A2,B1 A3,B2/:D;

21、 ENDSETSSETS: STUDENTS /S1.S8/; PAIRS( STUDENTS, STUDENTS) | &2 #GT# &1: BENEFIT, MATCH;ENDSETS最短路問題求求S到到T最短路長最短路長模型模型( )0,()min ( )( ,),YXL SL XL Yd Y XXS匹配問題 某班級8名同學準備分成4個調(diào)查隊（每隊2人）前往4個地區(qū)進行社會調(diào)查，假設8名同學兩兩組隊效率如表所示，問如何組隊可以使總效率最高？模型min( , )( , );. .( ,)1,1,2,3,4,( ,)0,1I JJIK IBENEFIT I JMatch I

22、 JstMatch J KIMatch J K或(,)1ijMatch S S表示兩同學組隊，等于零表示不組隊表示兩同學組隊，等于零表示不組隊集合元素的集合元素的隱式列舉隱式列舉類型類型隱式列舉格式隱式列舉格式示例示例示例集合的元素示例集合的元素數(shù)字型數(shù)字型 1.n1.51, 2, 3, 4, 5字符字符-數(shù)字型數(shù)字型stringM.stringNCar101.car208 Car101, car102, , car208星期型星期型 dayM.dayNMON.FRIMON, TUE, WED, THU, FRI月份型月份型 monthM.monthN OCT.JANOCT, NOV, DEC

23、, JAN年份年份-月份型月份型monthYearM.monthYearNOCT2001.JAN2002OCT2001, NOV2001, DEC2001, JAN2002運算符的優(yōu)先級運算符的優(yōu)先級 優(yōu)先級優(yōu)先級運算符運算符最高最高#NOT# （負號）（負號）* /+ （減法）（減法）#EQ# #NE# #GT# #GE# #LT# #LE# #AND# #OR#最低最低(=)三類運算符：三類運算符： 算術運算符算術運算符 邏輯運算符邏輯運算符 關系運算符關系運算符集合循環(huán)函數(shù)集合循環(huán)函數(shù)四個集合循環(huán)函數(shù)：四個集合循環(huán)函數(shù)：FOR、SUM 、 MAX、MINfunction( setname

24、 ( set_index_list) | condition : expression_list);objective MAX = SUM( PAIRS( I, J): BENEFIT( I, J) * MATCH( I, J);FOR(STUDENTS( I): constraints SUM( PAIRS( J, K) | J #EQ# I #OR# K #EQ# I: MATCH( J, K) =1);FOR(PAIRS( I, J): BIN( MATCH( I, J);MAXB=MAX(PAIRS( I, J): BENEFIT( I, J);MINB=MIN(PAIRS( I, J

25、): BENEFIT( I, J);Example:PAIRSJIJIMATCHJIBENEFIT),(),(*),(1),(),(IKorIJPAIRSKJKJMATCH狀態(tài)窗口狀態(tài)窗口Solver Type:B-and-BGlobal MultistartModel Class: LP， QP，ILP， IQP，PILP, PIQP，NLP，INLP，PINLP State:Global OptimumLocal OptimumFeasibleInfeasibleUnboundedInterruptedUndetermined7 7個選項卡個選項卡( (可設置可設置80-9080-90個控

26、制參數(shù)個控制參數(shù)) ) 程序與數(shù)據(jù)分離程序與數(shù)據(jù)分離文文本本文文件件使用外部數(shù)據(jù)文件使用外部數(shù)據(jù)文件 Cut (or Copy) Paste 方法方法 FILE 輸入數(shù)據(jù)、輸入數(shù)據(jù)、TEXT輸出數(shù)據(jù)（文本文件）輸出數(shù)據(jù)（文本文件） OLE函數(shù)與電子表格軟件（如函數(shù)與電子表格軟件（如EXCEL）連接）連接 ODBC函數(shù)與數(shù)據(jù)庫連接函數(shù)與數(shù)據(jù)庫連接 LINGO命令腳本文件命令腳本文件 LG4 （LONGO模型文件）模型文件） LNG （LONGO模型文件）模型文件） LTF （LONGO腳本文件）腳本文件） LDT （LONGO數(shù)據(jù)文件）數(shù)據(jù)文件） LRP （LONGO報告文件）報告文件）常用文件

27、后綴常用文件后綴FILEFILE和和TEXTTEXT：文本文件輸入輸出：文本文件輸入輸出MODEL:SETS: MYSET / FILE(myfile.txt) / : FILE(myfile.txt);ENDSETSMIN = SUM( MYSET( I): SHIP( I) * COST( I); FOR( MYSET( I): CON1 SHIP( I) NEED( I); CON2 SHIP( I) NEED( I); CON2 SHIP( I) SUPPLY( I);DATA: MYSET =OLE(D:JXIEBJ2004MCMmydata.xls,CITIES); COST,NE

28、ED,SUPPLY =OLE(mydata.xls); OLE(mydata.xls,SOLUTION)=SHIP; ENDDATAEND mydata.xls文件中必須有下列名稱(及數(shù)據(jù))： CITIES， COST，NEED，SUPPLY，SOLUTION 在在EXCEL中還可以通過中還可以通過“宏宏”自動調(diào)用自動調(diào)用LINGO(略略) 也可以將也可以將EXCEL表格嵌入到表格嵌入到LINGO模型中模型中(略略)演示演示 MydataExample.lg4ODBC ODBC ：與數(shù)據(jù)庫連接：與數(shù)據(jù)庫連接輸入基本集合元素：輸入基本集合元素：setname/ODBC(datasource ,

29、tablename , columnname)/輸入派生集合元素：輸入派生集合元素：setname/ODBC(source,table , column1, column2)/目前支持下列目前支持下列DBMS: (如為其他數(shù)據(jù)庫，則需自行安裝驅(qū)動如為其他數(shù)據(jù)庫，則需自行安裝驅(qū)動)ACCESS， DBASE，EXCEL，F(xiàn)OXPRO，ORACLE，PARADOX，SQL SERVER， TEXE FILES使用數(shù)據(jù)庫之前，數(shù)據(jù)源需要在使用數(shù)據(jù)庫之前，數(shù)據(jù)源需要在ODBC管理器注冊管理器注冊輸入數(shù)據(jù)：輸入數(shù)據(jù)：Attr_list=ODBC(source,table , column1, colum

30、n2)輸出數(shù)據(jù)：輸出數(shù)據(jù)：ODBC(source,table , column1, column2)= Attr_list具體例子略具體例子略建模實例與求解建模實例與求解最短路問題最短路問題下料問題下料問題露天礦的運輸問題露天礦的運輸問題鋼管運輸問題鋼管運輸問題最短路問題最短路問題求各點到求各點到T的最短路的最短路56774968658336C1B1C2B2A1A2A3TS6shortestPath.lg4jijAjiiLcL),(min問題問題1. 如何下料最節(jié)省如何下料最節(jié)省 ? 例例 鋼管下料鋼管下料 問題問題2. 客戶增加需求：客戶增加需求：原料鋼管原料鋼管: :每根每根19米米 4米

31、米50根根 6米米20根根 8米米15根根 客戶需求客戶需求節(jié)省的標準是什么？節(jié)省的標準是什么？由于采用不同切割模式太多，會增加生產(chǎn)和管理成本，由于采用不同切割模式太多，會增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過規(guī)定切割模式不能超過3種。如何下料最節(jié)?。糠N。如何下料最節(jié)?。?米米10根根 按照客戶需要在一根原料鋼管上安排切割的一種組合。按照客戶需要在一根原料鋼管上安排切割的一種組合。 切割模式切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根 余料余料3米米 4米米1根根 6米米1根根 6米米1根根 合理切割模式合理切割模式的余料應小于客戶需要鋼管的最小尺寸的余料應小于客戶需

32、要鋼管的最小尺寸余料余料3米米 8米米1根根 8米米1根根 鋼管下料鋼管下料 為滿足客戶需要，按照哪些種合理模式，每種模式為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)省？切割多少根原料鋼管，最為節(jié)?。亢侠砬懈钅Ｊ胶侠砬懈钅Ｊ?. 所用原料鋼管總根數(shù)最少所用原料鋼管總根數(shù)最少 模式模式 4米鋼管根數(shù)米鋼管根數(shù)6米鋼管根數(shù)米鋼管根數(shù)8米鋼管根數(shù)米鋼管根數(shù)余料余料(米米)14003231013201341203511116030170023鋼管下料問題鋼管下料問題1 1 兩種兩種標準標準1. 原料鋼管剩余總余量最小原料鋼管剩余總余量最小xi 按第按第i 種模式切割的原料鋼管

33、根數(shù)種模式切割的原料鋼管根數(shù)( (i= =1,2,7) ) 約束約束滿足需求滿足需求 決策變量決策變量 目標目標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, 其余為其余為0；最優(yōu)值：最優(yōu)值：27整數(shù)約束：整數(shù)約束： xi 為整

34、數(shù)為整數(shù)當余料沒有用處時，當余料沒有用處時，通常以總根數(shù)最少為目標通常以總根數(shù)最少為目標 76543212xxxxxxxZMin目標目標2（總根數(shù)）（總根數(shù)）鋼管下料問題鋼管下料問題1 1 約束條約束條件不變件不變 最優(yōu)解：最優(yōu)解：x2=15, x5=5, x7=5, 其余為其余為0；最優(yōu)值：最優(yōu)值：25。5023454321xxxxx20326542xxxx152753xxxxi 為整數(shù)按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式7切割切割5根，根，共共25根，余料根，余料35米米 雖余料增加雖余料增加8米，但減少了米，但減少了2根根 與與目標目標1的結(jié)果的

35、結(jié)果“共切割共切割27根，余料根，余料27米米” 相比相比 鋼管下料問題鋼管下料問題2 2對大規(guī)模問題，用模型的約束條件界定合理模式對大規(guī)模問題，用模型的約束條件界定合理模式增加一種需求：增加一種需求：5米米10根；切割根；切割模式不超過模式不超過3種。種?，F(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 種切割模式

36、下，每根原料鋼管種切割模式下，每根原料鋼管生產(chǎn)生產(chǎn)4米、米、5米、米、6米和米和8米長的鋼管的數(shù)量米長的鋼管的數(shù)量滿足需求滿足需求50313212111xrxrxr10323222121xrxrxr20333232131xrxrxrxrxr模式合理：每根模式合理：每根余料不超過余料不超過3米米1986541641312111rrrr1986541642322212rrrr1986541643332313rrrr整數(shù)非線性規(guī)劃模型整數(shù)非線性規(guī)劃模型鋼管下料問題鋼管下料問題2 2目標函數(shù)（目標函數(shù)（總根數(shù)）總根數(shù)）321xxxMin約束約束條件條件整數(shù)約束：整數(shù)約束： x

37、i ,r1i, r2i, r3i, r4i ( (i= =1,2,3) )為整數(shù)為整數(shù)增加約束，縮小可行域，便于求解增加約束，縮小可行域，便于求解321xxx原料鋼管總根數(shù)下界：原料鋼管總根數(shù)下界： 2619158206105504特殊生產(chǎn)計劃：對每根原料鋼管特殊生產(chǎn)計劃：對每根原料鋼管模式模式1：切割成：切割成4根根4米鋼管，需米鋼管，需13根；根；模式模式2：切割成：切割成1根根5米和米和2根根6米鋼管，需米鋼管，需10根；根；模式模式3：切割成：切割成2根根8米鋼管，需米鋼管，需8根。根。原料鋼管總根數(shù)上界：原料鋼管總根數(shù)上界：31 3126321xxx模式排列順序可任定模式排列順序可任

38、定 鋼管下料問題鋼管下料問題2 2需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根根每根原料鋼管長每根原料鋼管長19米米LINGOLINGO求解整數(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.00000

39、0 0.000000R13 0.000000 0.000000R21 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：每根原料鋼管切割成：每根原

40、料鋼管切割成2根根4米、米、1根根5米和米和1根根6米鋼管，米鋼管，共共10根；根；模式模式3：每根原料鋼管切割成：每根原料鋼管切割成2根根8米鋼管，共米鋼管，共8根。根。原料鋼管總根數(shù)為原料鋼管總根數(shù)為28根。根。演示演示cut02a.lg4； cut02b.lg4露天礦里鏟位已分成礦石和巖石露天礦里鏟位已分成礦石和巖石: 平均鐵含量不低于平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個鏟位至多安置一臺電鏟，電鏟平均裝車時間每個鏟位

41、至多安置一臺電鏟，電鏟平均裝車時間5分鐘分鐘卡車在等待時所耗費的能量也是相當可觀的，原則上卡車在等待時所耗費的能量也是相當可觀的，原則上在安排時在安排時不應發(fā)生卡車等待不應發(fā)生卡車等待的情況。的情況。 露天礦生產(chǎn)的車輛安排露天礦生產(chǎn)的車輛安排(CUMCM-2003B) 礦石卸點需要的鐵含量要求都為礦石卸點需要的鐵含量要求都為29.5% 1%(品位限品位限制），搭配量在一個班次（制），搭配量在一個班次（8小時）內(nèi)滿足品位限制即小時）內(nèi)滿足品位限制即可。卸點在一個班次內(nèi)不變?？ㄜ囕d重量為可。卸點在一個班次內(nèi)不變?？ㄜ囕d重量為154噸，平噸，平均時速均時速28km,平均卸車時間為平均卸車時間為3分鐘

42、。分鐘。問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛卡車，分別在哪些路線上各運輸多少次卡車，分別在哪些路線上各運輸多少次 ?平面示意圖問題數(shù)據(jù)問題數(shù)據(jù) 距離鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.265.194.214.002.952.742.461.900.641.27倒裝1.900.991.901.131.272.251.482.043.093.51巖場5.895.615.614.563.513.652.462.461.060.57巖石漏0.641.761.271.832.742.604.213.725.056

43、.10倒裝4.423.863.723.162.252.810.781.621.270.50鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量095105100105110125105130135125巖石量125110135105115135105115135125鐵含量30%28%29%32%31%33%32%31%33%31%問題分析問題分析 與典型的運輸問題明顯有以下不同：與典型的運輸問題明顯有以下不同：這是運輸?shù)V石與巖石兩種物資的問題；這是運輸?shù)V石與巖石兩種物資的問題；屬于產(chǎn)量大于銷量的不平衡運輸問題；屬于產(chǎn)量大于銷量的不平衡運輸問題；為了完成品位約束，礦石要搭配運輸

44、；為了完成品位約束，礦石要搭配運輸；產(chǎn)地、銷地均有單位時間的流量限制；產(chǎn)地、銷地均有單位時間的流量限制；運輸車輛只有一種，每次滿載運輸，運輸車輛只有一種，每次滿載運輸，154噸噸/車次；車次；鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于7個個產(chǎn)地作為最后結(jié)果中的產(chǎn)地；產(chǎn)地作為最后結(jié)果中的產(chǎn)地；1. 最后求出各條路線上的派出車輛數(shù)及安排。最后求出各條路線上的派出車輛數(shù)及安排。近似處理：近似處理：先求出產(chǎn)位、卸點每條線路上的運輸量先求出產(chǎn)位、卸點每條線路上的運輸量(MIP模型模型)然后求出各條路線上的派出車輛數(shù)及安排然后求出各條路線上的派出車輛數(shù)及安排模型假設模

45、型假設 卡車在一個班次中不應發(fā)生等待或熄火后再啟動卡車在一個班次中不應發(fā)生等待或熄火后再啟動的情況；的情況； 在鏟位或卸點處由兩條路線以上造成的沖突問題在鏟位或卸點處由兩條路線以上造成的沖突問題面前，我們認為只要平均時間能完成任務，就認面前，我們認為只要平均時間能完成任務，就認為不沖突。我們不排時地進行討論；為不沖突。我們不排時地進行討論； 空載與重載的速度都是空載與重載的速度都是28km/h，耗油相差很大；，耗油相差很大； 卡車可提前退出系統(tǒng)，等等?？ㄜ嚳商崆巴顺鱿到y(tǒng)，等等。如理解為嚴格不等待，難以用數(shù)學規(guī)劃模型來解如理解為嚴格不等待，難以用數(shù)學規(guī)劃模型來解 個別參數(shù)隊找到了可行解個別參數(shù)隊

46、找到了可行解 （略）（略）符號符號 xij ：從：從i鏟位到鏟位到j號卸點的石料運量號卸點的石料運量 （車）（車） 單位：單位： 噸；噸； cij ：從：從i號鏟位到號鏟位到j號卸點的距離號卸點的距離 公里；公里； Tij :從從i號鏟位到號號鏟位到號j卸點路線上運行一個周期平均時間卸點路線上運行一個周期平均時間 分；分； Aij ：從號鏟位到號卸點最多能同時運行的卡車數(shù)：從號鏟位到號卸點最多能同時運行的卡車數(shù) 輛；輛； Bij ：從號鏟位到號卸點路線上一輛車最多可運行的次數(shù)：從號鏟位到號卸點路線上一輛車最多可運行的次數(shù) 次；次； pi：i號鏟位的礦石鐵含量號鏟位的礦石鐵含量 p=(30,28

47、,29,32,31,33,32,31,33,31) % qj : j號卸點任務需求，號卸點任務需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 噸噸 cki ：i號鏟位的鐵礦石儲量號鏟位的鐵礦石儲量 萬噸萬噸 cyi ：i號鏟位的巖石儲量號鏟位的巖石儲量 萬噸萬噸 fi :描述第描述第i號鏟位是否使用的號鏟位是否使用的0-1變量，取變量，取1為使用；為使用；0為關閉。為關閉。532平均速度距離到jiTij5ijijTAijijijTAB5) 1(608(近似近似)優(yōu)化模型cxijijij10151min5 , 1,10, 1,jiBAxijijij10, 1, 5/60851ifxijij5 , 1,208101jiijx10, 1,154/10000154/1000043521icyxxckxxxiiiiiii（1）道路能力道