使用LINDO一些注意事項

1、使用使用LINDOLINDO的一些注意事項的一些注意事項 “”（或（或“=”（或（或“=”）功能相同）功能相同 變量與系數(shù)間可有空格變量與系數(shù)間可有空格(甚至回車甚至回車), 但無運算符但無運算符 變量名以字母開頭，不能超過變量名以字母開頭，不能超過8個字符個字符 變量名不區(qū)分大小寫（包括變量名不區(qū)分大小寫（包括LINDO中的關鍵字）中的關鍵字） 目標函數(shù)所在行是第一行，第二行起為約束條件目標函數(shù)所在行是第一行，第二行起為約束條件 行號行號(行名行名)自動產生或人為定義。行名以自動產生或人為定義。行名以“）”結結 束束 行中注有行中注有“!”符號的后面部分為注釋。如符號的后面部分為注釋。如:

2、! Its Comment. 在模型的任何地方都可以用在模型的任何地方都可以用“TITLE” 對模型命名對模型命名 （最多（最多72個字符），如：個字符），如： TITLE This Model is only an Example 變量不能出現(xiàn)在一個約束條件的右端變量不能出現(xiàn)在一個約束條件的右端 表達式中不接受括號表達式中不接受括號“( )”和逗號和逗號“,”等任何符號等任何符號, 例例: 400(X1+X2)需寫為需寫為400X1+400X2 表達式應化簡，如表達式應化簡，如2X1+3X2- 4X1應寫成應寫成 -2X1+3X2 缺省假定所有變量非負；可在模型的缺省假定所有變量非負；可在模

3、型的“END”語句語句 后用后用“FREE name”將變量將變量name的非負假定取消的非負假定取消 可在可在 “END”后用后用“SUB” 或或“SLB” 設定變量上設定變量上 下界下界 例如：例如： “sub x1 10”的作用等價于的作用等價于“x1=10” 但用但用“SUB”和和“SLB”表示的上下界約束不計入模表示的上下界約束不計入模 型的約束，也不能給出其松緊判斷和敏感性分析。型的約束，也不能給出其松緊判斷和敏感性分析。 14. “END”后對后對0-1變量說明：變量說明：INT n 或或 INT name 15. “END”后對整數(shù)變量說明：后對整數(shù)變量說明：GIN n 或或

4、GIN name 使用使用LINDOLINDO的一些注意事項的一些注意事項 二次規(guī)劃規(guī)劃(QP)問題 LINDO可求解二次規(guī)劃可求解二次規(guī)劃(QP)問題，但輸入方式較問題，但輸入方式較 復雜，因為在復雜，因為在LINDO中不許出現(xiàn)非線性表達式中不許出現(xiàn)非線性表達式 需要為每一個實際約束增加一個對偶變量需要為每一個實際約束增加一個對偶變量 （LAGRANGE乘子），在實際約束前增加有關乘子），在實際約束前增加有關 變量的一階最優(yōu)條件，轉化為互補問題變量的一階最優(yōu)條件，轉化為互補問題 “END”后面使用后面使用QCP命令指明實際約束開始的命令指明實際約束開始的 行號，然后才能求解行號，然后才能求解

5、 建議總是用建議總是用LINGO解解QP 注意注意對對QP和和IP: 敏感性分析意義不大敏感性分析意義不大 狀態(tài)窗口狀態(tài)窗口（LINDO Solver Status） 當前狀態(tài)：已達最優(yōu)解當前狀態(tài)：已達最優(yōu)解 迭代次數(shù)：迭代次數(shù)：18次次 約束不滿足的約束不滿足的“量量”(不不 是是“約束個數(shù)約束個數(shù)”)：0 當前的目標值：當前的目標值：94 最好的整數(shù)解：最好的整數(shù)解：94 整數(shù)規(guī)劃的界：整數(shù)規(guī)劃的界：93.5 分枝數(shù)：分枝數(shù)：1 所用時間：所用時間：0.00秒（太快秒（太快 了，還不到了，還不到0.005秒）秒） 刷新本界面的間隔刷新本界面的間隔:1(秒秒) 選項設置選項設置 Prepro

6、cess：預處理：預處理(生成割平面生成割平面)； Preferred Branch：優(yōu)先的分枝方式：優(yōu)先的分枝方式： “Default”（缺省方式）、（缺省方式）、 “Up”（向上取整優(yōu)先）、（向上取整優(yōu)先）、 “Down”（向下取整優(yōu)先）；（向下取整優(yōu)先）； IP Optimality Tol：IP最優(yōu)值允許的誤最優(yōu)值允許的誤 差上限（一個百分數(shù)，如差上限（一個百分數(shù)，如5%即即0.05）；）； IP Objective Hurdle：IP目標函數(shù)的籬目標函數(shù)的籬 笆值，即只尋找比這個值更優(yōu)最優(yōu)解笆值，即只尋找比這個值更優(yōu)最優(yōu)解 （如當知道當前模型的某個整數(shù)可行解（如當知道當前模型的某個整

7、數(shù)可行解 時，就可以設置這個值）；時，就可以設置這個值）； IP Var Fixing Tol：固定一個整數(shù)變量：固定一個整數(shù)變量 取值所依據(jù)的一個上限（如果一個整數(shù)取值所依據(jù)的一個上限（如果一個整數(shù) 變量的判別數(shù)（變量的判別數(shù)（REDUCED COST）的）的 值很大，超過該上限，則以后求解中把值很大，超過該上限，則以后求解中把 該整數(shù)變量固定下來）。該整數(shù)變量固定下來）。 Nonzero Limit： 非零系數(shù)的個數(shù)上限；非零系數(shù)的個數(shù)上限； Iteration Limit： 最大迭代步數(shù)；最大迭代步數(shù)； Initial Contraint Tol： 約束的初始誤差上限；約束的初始誤差上限

8、； Final Contraint Tol： 約束的最后誤差上限；約束的最后誤差上限； Entering Var Tol： 進基變量的進基變量的REDUCED COST的誤差限；的誤差限； Pivot Size Tol： 旋轉元的誤差限旋轉元的誤差限 Report/Statistics 第一行：模型有第一行：模型有5行（約束行（約束4行），行），4個變量，兩個整數(shù)變量（沒有個變量，兩個整數(shù)變量（沒有 0-1變量），從第變量），從第4行開始是二次規(guī)劃的實際約束。行開始是二次規(guī)劃的實際約束。 第二行：非零系數(shù)第二行：非零系數(shù)19個，約束中非零系數(shù)個，約束中非零系數(shù)12個個(其中其中6個為個為1或或

9、-1)， 模型密度為模型密度為0.760(密度密度=非零系數(shù)非零系數(shù)/行數(shù)行數(shù)(變量數(shù)變量數(shù)) 。 第三行的意思：按絕對值看，系數(shù)最小、最大分別為第三行的意思：按絕對值看，系數(shù)最小、最大分別為0.3和和277。 第四行的意思：模型目標為極小化；小于等于、等于、大于等于約第四行的意思：模型目標為極小化；小于等于、等于、大于等于約 束分別有、個；廣義上界約束（束分別有、個；廣義上界約束（GUBS）不超過個；）不超過個； 變量上界約束（變量上界約束（VUBS）不少于個。所謂）不少于個。所謂GUBS，是指一組不，是指一組不 含有相同變量的約束；所謂含有相同變量的約束；所謂VUBS，是指一個蘊涵變量上界

10、的約，是指一個蘊涵變量上界的約 束，如從約束束，如從約束X1+X2-X3=0可以看出，若可以看出，若X3=0，則，則X1=0，X2=0 （因為有非負限制），因此（因為有非負限制），因此X1+X2-X3=0是一個是一個VUBS約束。約束。 第五行的意思：只含個變量的約束個數(shù)第五行的意思：只含個變量的約束個數(shù)=個；冗余的列數(shù)個；冗余的列數(shù)=個個 ROWS= 5 VARS= 4 INTEGER VARS= 2( 0 = 0/1) QCP= 4 NONZEROS= 19 CONSTRAINT NONZ= 12( 6 = +-1) DENSITY=0.760 SMALLEST AND LARGEST E

11、LEMENTS IN ABSOLUTE VALUE= 0.300000 277.000 OBJ=MIN, NO. : 2 0 2, GUBS = 0 SINGLE COLS= 0 REDUNDANT COLS= 0 LINDOLINDO行命令、命令腳本文件行命令、命令腳本文件 批處理：可以采用命令腳本（行命令序列）批處理：可以采用命令腳本（行命令序列） WINDOWS環(huán)境下行命令的意義不大環(huán)境下行命令的意義不大 Example 演示演示 Bat01.txt 用用FILE / TAKE COMMANDS (F11) 命令調入命令調入 必須是以必須是以LINDO PACKED形式形式 （壓縮）保存

12、的文件（壓縮）保存的文件 FILE / SAVE命令命令SAVE行命令行命令 LINGO軟件簡介軟件簡介 目標與約束段目標與約束段 集合段（集合段（SETS ENDSETS） 數(shù)據(jù)段（數(shù)據(jù)段（DATA ENDDATA） 初始段（初始段（INIT ENDINIT） LINGO模型的構成：模型的構成：4個段個段 LINGO模型的優(yōu)點模型的優(yōu)點 包含了包含了LINDO的全部功能的全部功能 提供了靈活的編程語言（矩陣生成器）提供了靈活的編程語言（矩陣生成器） LINGOLINGO模型模型 例：選址問題例：選址問題 某公司有某公司有6個建筑工地，位置坐標為個建筑工地，位置坐標為(ai, bi) (單位：

13、公里單位：公里), 水泥日用量水泥日用量di (單位：噸）單位：噸） i a1.258.750.55.7537.25 b1.250.754.7556.57.75 d3547611 1)現(xiàn)有 2 料場，位于 A (5, 1), B (2, 7), 記(xj,yj),j=1,2, 日儲量 ej各有 20 噸。 假設：料場假設：料場 和工地之間和工地之間 有直線道路有直線道路 目標：制定每天的供應計劃，即從 A, B 兩料場分別 向各工地運送多少噸水泥，使總的噸公里數(shù)最小。 用例中數(shù) 據(jù)計算， 最優(yōu)解為 i123456 1i c（料料場場 A） 350701 2i c（料料場場 B） 0040610

14、 2 , 1, 6,.,1,. . )()(min 6 1 2 1 2 1 6 1 2/122 jec idcts byaxc jij i iij j ji ijijij 線性規(guī)劃模型線性規(guī)劃模型 決策變量：決策變量：ci j (料場料場j到到工地工地i的的 運量）運量）12維維 選址問題：選址問題：NLPNLP 2）改建兩個新料場，需要確定新料場位置）改建兩個新料場，需要確定新料場位置(xj,yj)和和 運量運量cij ，在其它條件不變下使總噸公里數(shù)最小。，在其它條件不變下使總噸公里數(shù)最小。 2 , 1, 6,.,1,. . )()(min 6 1 2 1 2 1 6 1 2/122 jec

15、 idcts byaxc jij i iij j ji ijijij 決策變量：決策變量： ci j， ，(xj,yj)16維 維 非線性規(guī)劃模型非線性規(guī)劃模型 LINGO模型的構成：模型的構成：4個段個段 集合段（集合段（SETS ENDSETS） 數(shù)據(jù)段（數(shù)據(jù)段（DATA ENDDATA） 初始段（初始段（INIT ENDINIT） 目標與目標與 約束段約束段 局部最優(yōu)：局部最優(yōu)：89.8835(噸公里噸公里 ) LP：移到數(shù)據(jù)段：移到數(shù)據(jù)段 邊界 集合的類型集合的類型 集合集合 派生集合派生集合 基本集合基本集合 稀疏集合稀疏集合 稠密集合稠密集合 元素列表法元素列表法 元素過濾法元素過

16、濾法 直接列舉法直接列舉法 隱式列舉法隱式列舉法 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; ENDSETS SETS: STUDENTS /S1.S8/; PAIRS( STUDENTS, STUDENTS) | ENDSETS 集合元素的集合元素的隱式列舉隱式列舉 類型類型隱式列舉

17、格式隱式列舉格式示例示例示例集合的元素示例集合的元素 數(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, JAN 年份年份- 月份型月份型 monthYearM.mo nthYearN OCT2001.JAN 2002 OCT2001, NOV2001, DEC2001, JAN20

18、02 運算符的優(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、MIN function( setname ( set_index_list) | condition : expression_list); objective MAX = SUM( PA

19、IRS( 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): BENEFIT( I, J); Example: PAIRSJI JIMATCHJIBENEFIT ),( ),(*),( 1),(

20、 ),( IK orIJ PAIRSKJ KJMATCH 狀態(tài)窗口狀態(tài)窗口 Solver Type: B-and-B Global Multistart Model Class: LP， QP，ILP， IQP，PILP, PIQP，NLP， INLP，PINLP State: Global Optimum Local Optimum Feasible Infeasible Unbounded Interrupted Undetermined 7 7個選項卡個選項卡( (可設置可設置80-9080-90個控制參數(shù)個控制參數(shù)) ) 程序與數(shù)據(jù)分離程序與數(shù)據(jù)分離 文文 本本 文文 件件 使用外部數(shù)

21、據(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報告文件）報告文件） 常用文件后綴常用文件后綴 FILEFILE和和TEXTTEXT：文本文件輸入輸出：文

22、本文件輸入輸出 MODEL: SETS: MYSET / FILE(my) / : FILE(my); ENDSETS MIN = 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,NEED,SUPPLY =OLE(mydata.xls); OLE(mydata.xls,SOLUT

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

24、合元素： setname/ODBC(source,table , column1, column2)/ 目前支持下列目前支持下列DBMS: (如為其他數(shù)據(jù)庫，則需自行安裝驅動如為其他數(shù)據(jù)庫，則需自行安裝驅動) 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, column2) 輸出數(shù)據(jù)：輸出數(shù)據(jù)： ODBC(source,tabl

25、e , column1, column2)= Attr_list 具體例子略具體例子略 建模實例與求解建模實例與求解 最短路問題最短路問題 下料問題下料問題 露天礦的運輸問題露天礦的運輸問題 鋼管運輸問題鋼管運輸問題 最短路問題最短路問題 求各點到求各點到T的最短路的最短路 5 6 7 7 4 9 6 8 6 5 8 3 3 6 C1 B1 C2 B2 A1 A2 A3 T S 6 shortestPath.lg4 jij Aji i LcL ),( min 問題問題1. 如何下料最節(jié)省如何下料最節(jié)省 ? 例例 鋼管下料鋼管下料 問題問題2. 客戶增加需求：客戶增加需求： 原料鋼管原料鋼管:

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

27、尺寸合理切割模式的余料應小于客戶需要鋼管的最小尺寸 余料余料3米米 8米米1根根 8米米1根根 鋼管下料鋼管下料 為滿足客戶需要，按照哪些種合理模式，每種模式為滿足客戶需要，按照哪些種合理模式，每種模式 切割多少根原料鋼管，最為節(jié)??？切割多少根原料鋼管，最為節(jié)??？ 合理切割模式合理切割模式 2. 所用原料鋼管總根數(shù)最少所用原料鋼管總根數(shù)最少 模式模式 4米鋼管根數(shù)米鋼管根數(shù)6米鋼管根數(shù)米鋼管根數(shù)8米鋼管根數(shù)米鋼管根數(shù)余料余料(米米) 14003 23101 32013 41203 51111 60301 70023 鋼管下料問題鋼管下料問題1 1 兩種兩種 標準標準 1. 原料鋼管剩余總余量最

28、小原料鋼管剩余總余量最小 xi 按第按第i 種模式切割的原料鋼管根數(shù)種模式切割的原料鋼管根數(shù)( (i= =1,2,7) ) 約束約束滿足需求滿足需求 決策變量決策變量 目標目標1（總余量）（總余量） 76543211 3333xxxxxxxZMin 50234 54321 xxxxx 2032 6542 xxxx 152 753 xxx 按模式按模式2切割切割12根根, ,按模式按模式5切割切割15根，余料根，余料27米米 模模 式式 4米米 根數(shù)根數(shù) 6米米 根數(shù)根數(shù) 8米米 根數(shù)根數(shù) 余余 料料 14003 23101 32013 41203 51111 60301 70023 需需 求求

29、 502015 最優(yōu)解：最優(yōu)解：x2=12, x5=15, 其余為其余為0； 最優(yōu)值：最優(yōu)值：27 整數(shù)約束：整數(shù)約束： xi 為整數(shù)為整數(shù) 當余料沒有用處時，當余料沒有用處時，通常以總根數(shù)最少為目標通常以總根數(shù)最少為目標 76543212 xxxxxxxZMin目標目標2（總根數(shù)）（總根數(shù)） 鋼管下料問題鋼管下料問題1 1 約束條約束條 件不變件不變 最優(yōu)解：最優(yōu)解：x2=15, x5=5, x7=5, 其余為其余為0； 最優(yōu)值：最優(yōu)值：25。 50234 54321 xxxxx 2032 6542 xxxx 152 753 xxx xi 為整數(shù) 按模式按模式2切割切割15根，根， 按模式按

30、模式5切割切割5根，根， 按模式按模式7切割切割5根，根， 共共25根，余料根，余料35米米 雖余料增加雖余料增加8米，但減少了米，但減少了2根根 與與目標目標1的結果的結果“共切割共切割 27根，余料根，余料27米米” 相比相比 鋼管下料問題鋼管下料問題2 2 對大規(guī)模問題，用模型的約束條件界定合理模式對大規(guī)模問題，用模型的約束條件界定合理模式 增加一種需求：增加一種需求：5米米10根；切割根；切割模式不超過模式不超過3種。種。 現(xiàn)有現(xiàn)有4種種需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米 15根，用枚舉法確定合理切割模式，過于復雜。根，用枚舉法確定合理切割模式，過

31、于復雜。 決策變量決策變量 xi 按第按第i 種模式切割的原料鋼管根數(shù)種模式切割的原料鋼管根數(shù)( (i= =1,2,3) ) r1i, r2i, r3i, r4i 第第i 種切割模式下，每根原料鋼管種切割模式下，每根原料鋼管 生產生產4米、米、5米、米、6米和米和8米長的鋼管的數(shù)量米長的鋼管的數(shù)量 滿足需求滿足需求 50 313212111 xrxrxr 10 323222121 xrxrxr 20 333232131 xrxrxr 15 343242141 xrxrxr 模式合理：每根模式合理：每根 余料不超過余料不超過3米米 19865416 41312111 rrrr 19865416

32、42322212 rrrr 19865416 43332313 rrrr 整數(shù)非線性規(guī)劃模型整數(shù)非線性規(guī)劃模型 鋼管下料問題鋼管下料問題2 2 目標函數(shù)（目標函數(shù)（總根數(shù)）總根數(shù)） 321 xxxMin 約束約束 條件條件 整數(shù)約束：整數(shù)約束： xi ,r1i, r2i, r3i, r4i ( (i= =1,2,3) )為整數(shù)為整數(shù) 增加約束，縮小可行域，便于求解增加約束，縮小可行域，便于求解 321 xxx 原料鋼管總根數(shù)下界：原料鋼管總根數(shù)下界： 26 19 158206105504 特殊生產計劃：對每根原料鋼管特殊生產計劃：對每根原料鋼管 模式模式1：切割成：切割成4根根4米鋼管，需米鋼

33、管，需13根；根； 模式模式2：切割成：切割成1根根5米和米和2根根6米鋼管，需米鋼管，需10根；根； 模式模式3：切割成：切割成2根根8米鋼管，需米鋼管，需8根。根。 原料鋼管總根數(shù)上界：原料鋼管總根數(shù)上界：31 3126 321 xxx 模式排列順序可任定模式排列順序可任定 鋼管下料問題鋼管下料問題2 2 需求：需求：4米米50根，根，5米米10 根，根，6米米20根，根，8米米15根根 每根原料鋼管長每根原料鋼管長19米米 LINGOLINGO求解整數(shù)非線性規(guī)劃模型求解整數(shù)非線性規(guī)劃模型 Local optimal solution found at iteration: 12211 O

34、bjective value: 28.00000 Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 2.000000 X3 8.000000 1.000000 R11 3.000000 0.000000 R12 2.000000 0.000000 R13 0.000000 0.000000 R21 0.000000 0.000000 R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.00

35、0000 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米鋼管，米鋼管， 共共10根；根； 模式模式3：每根原料鋼管切割成：每根原料鋼管切割成2 根根8米鋼管，共米鋼管，共8根。根。 原料鋼管總根數(shù)為原料鋼管總根數(shù)為28根。根。 演示演示cut02a.lg4； cut02b.lg4 露天礦里鏟

36、位已分成礦石和巖石露天礦里鏟位已分成礦石和巖石: 平均鐵含量不低于平均鐵含量不低于 25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù) 量，以及礦石的平均鐵含量（稱為品位）都是已知的。量，以及礦石的平均鐵含量（稱為品位）都是已知的。 每個鏟位至多安置一臺電鏟，電鏟平均裝車時間每個鏟位至多安置一臺電鏟，電鏟平均裝車時間5分鐘分鐘 卡車在等待時所耗費的能量也是相當可觀的，原則上卡車在等待時所耗費的能量也是相當可觀的，原則上 在安排時不應發(fā)生卡車等待的情況。在安排時不應發(fā)生卡車等待的情況。 露天礦生產的車輛安排露天礦生產的車輛安排(CUMCM-2003B)

37、 礦石卸點需要的鐵含量要求都為礦石卸點需要的鐵含量要求都為29.5% 1%(品位限品位限 制），搭配量在一個班次（制），搭配量在一個班次（8小時）內滿足品位限制即小時）內滿足品位限制即 可。卸點在一個班次內不變。卡車載重量為可。卸點在一個班次內不變。卡車載重量為154噸，平噸，平 均時速均時速28km,平均卸車時間為平均卸車時間為3分鐘。分鐘。 問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛 卡車，分別在哪些路線上各運輸多少次卡車，分別在哪些路線上各運輸多少次 ? 平面示意圖 問題數(shù)據(jù)問題數(shù)據(jù) 距離鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟

38、位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.10 倒裝4.423.863.723.162.252.810.781.621.270.50 鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10 礦石量 095105100105110125105130135125 巖石量 12511

39、0135105115135105115135125 鐵含量30%28%29%32%31%33%32%31%33%31% 問題分析問題分析 與典型的運輸問題明顯有以下不同：與典型的運輸問題明顯有以下不同： 這是運輸?shù)V石與巖石兩種物資的問題；這是運輸?shù)V石與巖石兩種物資的問題； 屬于產量大于銷量的不平衡運輸問題；屬于產量大于銷量的不平衡運輸問題； 為了完成品位約束，礦石要搭配運輸；為了完成品位約束，礦石要搭配運輸； 產地、銷地均有單位時間的流量限制；產地、銷地均有單位時間的流量限制； 運輸車輛只有一種，每次滿載運輸，運輸車輛只有一種，每次滿載運輸，154噸噸/車次；車次； 鏟位數(shù)多于鏟車數(shù)意味著要最

40、優(yōu)的選擇不多于鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于7個個 產地作為最后結果中的產地；產地作為最后結果中的產地； 1. 最后求出各條路線上的派出車輛數(shù)及安排。最后求出各條路線上的派出車輛數(shù)及安排。 近似處理：近似處理： 先求出產位、卸點每條線路上的運輸量先求出產位、卸點每條線路上的運輸量(MIP模型模型) 然后求出各條路線上的派出車輛數(shù)及安排然后求出各條路線上的派出車輛數(shù)及安排 模型假設模型假設 卡車在一個班次中不應發(fā)生等待或熄火后再啟動卡車在一個班次中不應發(fā)生等待或熄火后再啟動 的情況；的情況； 在鏟位或卸點處由兩條路線以上造成的沖突問題在鏟位或卸點處由兩條路線以上造成的沖突問題 面前，我

41、們認為只要平均時間能完成任務，就認面前，我們認為只要平均時間能完成任務，就認 為不沖突。我們不排時地進行討論；為不沖突。我們不排時地進行討論； 空載與重載的速度都是空載與重載的速度都是28km/h，耗油相差很大；，耗油相差很大； 卡車可提前退出系統(tǒng)，等等?？ㄜ嚳商崆巴顺鱿到y(tǒng)，等等。 如理解為嚴格不等待，難以用數(shù)學規(guī)劃模型來解如理解為嚴格不等待，難以用數(shù)學規(guī)劃模型來解 個別參數(shù)隊找到了可行解個別參數(shù)隊找到了可行解 （略）（略） 符號符號 xij ：從：從i鏟位到鏟位到j號卸點的石料運量號卸點的石料運量 （車）（車） 單位：單位： 噸；噸； cij ：從：從i號鏟位到號鏟位到j號卸點的距離號卸點的

42、距離 公里；公里； Tij :從從i號鏟位到號號鏟位到號j卸點路線上運行一個周期平均時間卸點路線上運行一個周期平均時間 分；分； Aij ：從號鏟位到號卸點最多能同時運行的卡車數(shù)：從號鏟位到號卸點最多能同時運行的卡車數(shù) 輛；輛； Bij ：從號鏟位到號卸點路線上一輛車最多可運行的次數(shù)：從號鏟位到號卸點路線上一輛車最多可運行的次數(shù) 次；次； pi：i號鏟位的礦石鐵含量號鏟位的礦石鐵含量 p=(30,28,29,32,31,33,32,31,33,31) % qj : j號卸點任務需求，號卸點任務需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 噸噸 cki ：i號鏟位的鐵礦石儲量

43、號鏟位的鐵礦石儲量 萬噸萬噸 cyi ：i號鏟位的巖石儲量號鏟位的巖石儲量 萬噸萬噸 fi :描述第描述第i號鏟位是否使用的號鏟位是否使用的0-1變量，取變量，取1為使用；為使用；0為關閉。為關閉。 53 2 平均速度 距離到 ji Tij 5 ij ij T A ij ij ij T A B 5) 1(608 (近似近似) 優(yōu)化模型 cx ij ij ij 10 1 5 1 min 5 , 1,10, 1,ji BAxijijij 10, 1, 5/608 5 1 i f x i j ij 5 , 1,208 10 1 j i ijx 10, 1, 154/10000 154/10000 4

44、3 521 i cy xx ckxxx i ii iiii （1）道路能力道路能力(卡車數(shù)卡車數(shù))約束約束 （2）電鏟能力約束 （3）卸點能力約束 （4）鏟位儲量約束 （5）產量任務約束 （6）鐵含量約束 （7）電鏟數(shù)量約束 （8）整數(shù)約束 5 , 1,154/ 10 1 j q x j i ij 5 , 2 , 1, 0)5 .28( 0)5 .30( 10 1 10 1 j p x p x i i ij i i ij . 7 10 1 i i f xij為非負整數(shù) fi 為0-1整數(shù) 計算結果（計算結果（LINGOLINGO軟件）軟件） 鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10 礦漏131354541111 倒42424343 巖