優(yōu)化模型與lindolingo優(yōu)化軟件（清華，謝金星）

1、數(shù)學(xué)建模講座（2004年7月~8月?江西）優(yōu)化模型與LINDO/LINGO優(yōu)化軟件,謝金星清華大學(xué)數(shù)學(xué)科學(xué)系 Tel: 010-62787812Email:jxie@math.tsinghua.edu.cn http://faculty.math.tsinghua.edu.cn/~jxie,簡(jiǎn)要提綱,優(yōu)化模型簡(jiǎn)介 LINDO公司的主要軟件產(chǎn)品及功能簡(jiǎn)介 LINDO軟件的使用簡(jiǎn)介 LINGO軟件的使用簡(jiǎn)介 建

2、模與求解實(shí)例（結(jié)合軟件使用）,優(yōu)化模型,實(shí)際問(wèn)題中的優(yōu)化模型,x~決策變量,f(x)~目標(biāo)函數(shù),gi(x)?0~約束條件,數(shù)學(xué)規(guī)劃,線性規(guī)劃(LP)二次規(guī)劃(QP)非線性規(guī)劃(NLP),純整數(shù)規(guī)劃(PIP)混合整數(shù)規(guī)劃(MIP),整數(shù)規(guī)劃(IP),,,,0-1整數(shù)規(guī)劃一般整數(shù)規(guī)劃,連續(xù)規(guī)劃,,LINDO 公司軟件產(chǎn)品簡(jiǎn)要介紹,美國(guó)芝加哥(Chicago)大學(xué)的Linus Schrage教授于1980年前后開(kāi)發(fā), 后來(lái)成立 LI

3、NDO系統(tǒng)公司（LINDO Systems Inc.）， 網(wǎng)址：http://www.lindo.com,LINDO: Linear INteractive and Discrete Optimizer (V6.1)LINGO: Linear INteractive General Optimizer (V8.0)LINDO API: LINDO Application P

4、rogramming Interface (V2.0)What’s Best!: (SpreadSheet e.g. EXCEL) (V7.0),演示(試用)版、學(xué)生版、高級(jí)版、超級(jí)版、工業(yè)版、擴(kuò)展版… （求解問(wèn)題規(guī)模和選件不同）,LINDO和LINGO軟件能求解的優(yōu)化模型,,LINGO,LINDO,優(yōu)化模型,線性規(guī)劃(LP),非線性規(guī)劃(NLP),二次規(guī)劃(QP),,

5、,,連續(xù)優(yōu)化,整數(shù)規(guī)劃(IP),,,,,,LP QP NLP IP 全局優(yōu)化(選) ILP IQP INLP,LINDO/LINGO軟件的求解過(guò)程,LINDO/LINGO預(yù)處理程序,線性?xún)?yōu)化求解程序,非線性?xún)?yōu)化求解程序,,,,分枝定界管理程序,,,1. 確定常數(shù)2. 識(shí)別類(lèi)型,

6、,1. 單純形算法2. 內(nèi)點(diǎn)算法(選),,1、順序線性規(guī)劃法(SLP) 2、廣義既約梯度法(GRG) (選) 3、多點(diǎn)搜索(Multistart) (選),,建模時(shí)需要注意的幾個(gè)基本問(wèn)題,1、盡量使用實(shí)數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個(gè)數(shù) 如：盡量少使用絕對(duì)值、符號(hào)函數(shù)、多個(gè)變量求最大/最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變量的個(gè)數(shù)

7、 （如x/y <5 改為x<5y）4、合理設(shè)定變量上下界，盡可能給出變量初始值 5、模型中使用的參數(shù)數(shù)量級(jí)要適當(dāng) (如小于103),需要掌握的幾個(gè)重要方面,1、LINDO: 正確閱讀求解報(bào)告（尤其要掌握敏感性分析）2、LINGO： 掌握集合(SETS)的應(yīng)用；正確閱讀求解報(bào)告；正確理解求解狀態(tài)窗口； 學(xué)會(huì)設(shè)置基本的求解選項(xiàng)(OPTIONS) ；

8、掌握與外部文件的基本接口方法,例1 加工奶制品的生產(chǎn)計(jì)劃,50桶牛奶,時(shí)間480小時(shí),至多加工100公斤A1,制訂生產(chǎn)計(jì)劃，使每天獲利最大,35元可買(mǎi)到1桶牛奶，買(mǎi)嗎？若買(mǎi)，每天最多買(mǎi)多少?,可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?,A1的獲利增加到 30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？,每天：,x1桶牛奶生產(chǎn)A1,x2桶牛奶生產(chǎn)A2,獲利 24×3x1,獲利 16×4 x2,原料供應(yīng),勞動(dòng)時(shí)間,加工能力,決

9、策變量,目標(biāo)函數(shù),每天獲利,約束條件,非負(fù)約束,線性規(guī)劃模型(LP),時(shí)間480小時(shí),至多加工100公斤A1,模型求解,max 72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUC

10、ED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000

11、 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,DO RANGE (SENSITIVITY) ANALYSIS?,No,20桶牛奶生產(chǎn)A1, 30桶生產(chǎn)A2，利潤(rùn)3360元。,模型求解,reduced cost值表示當(dāng)該非基

12、變量增加一個(gè)單位時(shí)（其他非基變量保持不變）目標(biāo)函數(shù)減少的量(對(duì)max型問(wèn)題),OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.

13、000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000

14、 0.000000 NO. ITERATIONS= 2,也可理解為：為了使該非基變量變成基變量，目標(biāo)函數(shù)中對(duì)應(yīng)系數(shù)應(yīng)增加的量,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000

15、 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.

16、000000 4) 40.000000 0.000000,原料無(wú)剩余,時(shí)間無(wú)剩余,加工能力剩余40,max 72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end,三種資源,“資源” 剩余為零的約束為緊約束（有效約束）,結(jié)果解釋,OBJECTIVE FUNCTION VALUE 1)

17、 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)

18、 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000,結(jié)果解釋,最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量,原料增1單位, 利潤(rùn)增48,時(shí)間加1單位, 利潤(rùn)增2,能力增減不影響

19、利潤(rùn),影子價(jià)格,35元可買(mǎi)到1桶牛奶，要買(mǎi)嗎？,35 <48, 應(yīng)該買(mǎi)！,聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？,2元！,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE

20、 COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RA

21、NGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000

22、 53.333332 80.000000 4 100.000000 INFINITY 40.000000,最優(yōu)解不變時(shí)目標(biāo)系數(shù)允許變化范圍,DO RANGE(SENSITIVITY) ANALYSIS?,Yes,x1系數(shù)范圍(64,96),x2系數(shù)范圍(48,72),A1獲利增加到 30元/千克，應(yīng)否改變生產(chǎn)計(jì)劃,x1系數(shù)由24?3=

23、72 增加為30?3= 90，在允許范圍內(nèi),不變！,(約束條件不變),結(jié)果解釋,結(jié)果解釋,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INC

24、REASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW

25、 CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.3333

26、32 80.000000 4 100.000000 INFINITY 40.000000,影子價(jià)格有意義時(shí)約束右端的允許變化范圍,原料最多增加10,時(shí)間最多增加53,35元可買(mǎi)到1桶牛奶，每天最多買(mǎi)多少？,最多買(mǎi)10桶？,(目標(biāo)函數(shù)不變),注意: 充分但可能不必要,使用LINDO的一些注意事項(xiàng),“>”（或“=”（或“<=”）功能相同變

27、量與系數(shù)間可有空格(甚至回車(chē)), 但無(wú)運(yùn)算符變量名以字母開(kāi)頭，不能超過(guò)8個(gè)字符變量名不區(qū)分大小寫(xiě)（包括LINDO中的關(guān)鍵字）目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件行號(hào)(行名)自動(dòng)產(chǎn)生或人為定義。行名以“）”結(jié)束行中注有“!”符號(hào)的后面部分為注釋。如: ! It’s Comment.在模型的任何地方都可以用“TITLE” 對(duì)模型命名（最多72個(gè)字符），如： TITLE This Mode

28、l is only an Example,變量不能出現(xiàn)在一個(gè)約束條件的右端表達(dá)式中不接受括號(hào)“( )”和逗號(hào)“,”等任何符號(hào), 例: 400(X1+X2)需寫(xiě)為400X1+400X2表達(dá)式應(yīng)化簡(jiǎn)，如2X1+3X2- 4X1應(yīng)寫(xiě)成 -2X1+3X2缺省假定所有變量非負(fù)；可在模型的“END”語(yǔ)句后用“FREE name”將變量name的非負(fù)假定取消可在 “END”后用“SUB” 或“SLB” 設(shè)定變量上下界 例如： “

29、sub x1 10”的作用等價(jià)于“x1<=10” 但用“SUB”和“SLB”表示的上下界約束不計(jì)入模型的約束，也不能給出其松緊判斷和敏感性分析。14. “END”后對(duì)0-1變量說(shuō)明：INT n 或 INT name15. “END”后對(duì)整數(shù)變量說(shuō)明：GIN n 或 GIN name,使用LINDO的一些注意事項(xiàng),二次規(guī)劃(QP)問(wèn)題,LINDO可求解二次規(guī)劃(QP)問(wèn)題，但輸入方式較復(fù)雜，因?yàn)樵贚INDO中不許出

30、現(xiàn)非線性表達(dá)式需要為每一個(gè)實(shí)際約束增加一個(gè)對(duì)偶變量（LAGRANGE乘子），在實(shí)際約束前增加有關(guān)變量的一階最優(yōu)條件，轉(zhuǎn)化為互補(bǔ)問(wèn)題“END”后面使用QCP命令指明實(shí)際約束開(kāi)始的行號(hào)，然后才能求解建議總是用LINGO解QP[注意]對(duì)QP和IP: 敏感性分析意義不大,狀態(tài)窗口（LINDO Solver Status）,當(dāng)前狀態(tài)：已達(dá)最優(yōu)解迭代次數(shù)：18次約束不滿足的“量”(不是“約束個(gè)數(shù)”)：0當(dāng)前的目標(biāo)值：94最好的整數(shù)

31、解：94整數(shù)規(guī)劃的界：93.5分枝數(shù)：1所用時(shí)間：0.00秒（太快了，還不到0.005秒）刷新本界面的間隔:1(秒),選項(xiàng)設(shè)置,Preprocess：預(yù)處理(生成割平面)； Preferred Branch：優(yōu)先的分枝方式： “Default”（缺省方式）、“Up”（向上取整優(yōu)先）、“Down”（向下取整優(yōu)先）； IP Optimality Tol：IP最優(yōu)值允許的誤差上限（一個(gè)百分?jǐn)?shù)，如5%即0.05）； IP O

32、bjective Hurdle：IP目標(biāo)函數(shù)的籬笆值，即只尋找比這個(gè)值更優(yōu)最優(yōu)解（如當(dāng)知道當(dāng)前模型的某個(gè)整數(shù)可行解時(shí)，就可以設(shè)置這個(gè)值）； IP Var Fixing Tol：固定一個(gè)整數(shù)變量取值所依據(jù)的一個(gè)上限（如果一個(gè)整數(shù)變量的判別數(shù)（REDUCED COST）的值很大，超過(guò)該上限，則以后求解中把該整數(shù)變量固定下來(lái)）。,Nonzero Limit：非零系數(shù)的個(gè)數(shù)上限；Iteration Limit：最大迭代步數(shù)；Initi

33、al Contraint Tol：約束的初始誤差上限；Final Contraint Tol：約束的最后誤差上限；Entering Var Tol：進(jìn)基變量的REDUCED COST的誤差限；Pivot Size Tol：旋轉(zhuǎn)元的誤差限,Report/Statistics,第一行：模型有5行（約束4行），4個(gè)變量，兩個(gè)整數(shù)變量（沒(méi)有0-1變量），從第4行開(kāi)始是二次規(guī)劃的實(shí)際約束。第二行：非零系數(shù)19個(gè)，約束中非零系數(shù)1

34、2個(gè)(其中6個(gè)為1或-1)，模型密度為0.760(密度=非零系數(shù)/[行數(shù)＊(變量數(shù)＋１)]) 。第三行的意思：按絕對(duì)值看，系數(shù)最小、最大分別為0.3和277。第四行的意思：模型目標(biāo)為極小化；小于等于、等于、大于等于約束分別有２、０、２個(gè)；廣義上界約束（GUBS）不超過(guò)１個(gè)；變量上界約束（VUBS）不少于０個(gè)。所謂GUBS，是指一組不含有相同變量的約束；所謂VUBS，是指一個(gè)蘊(yùn)涵變量上界的約束，如從約束X1+X2-X3=0可以看出，若

35、X3=0，則X1=0，X2=0（因?yàn)橛蟹秦?fù)限制），因此X1+X2-X3=0是一個(gè)VUBS約束。第五行的意思：只含１個(gè)變量的約束個(gè)數(shù)=０個(gè)；冗余的列數(shù)=０個(gè),ROWS= 5 VARS= 4 INTEGER VARS= 2( 0 = 0/1) QCP= 4NONZEROS= 19 CONSTRAINT NONZ= 12( 6 = +-1) DENSITY=0.7

36、60SMALLEST AND LARGEST ELEMENTS IN ABSOLUTE VALUE= 0.300000 277.000OBJ=MIN, NO. : 2 0 2, GUBS = 0SINGLE COLS= 0 REDUNDANT COLS= 0,LINDO行命令、命令腳本文件,批處理：可以采用命令腳本（行命令序列）,WINDOWS環(huán)境下行

37、命令的意義不大,Example 演示,,用FILE / TAKE COMMANDS (F11) 命令調(diào)入,,必須是以LINDO PACKED形式（壓縮）保存的文件,FILE / SAVE命令,SAVE行命令,LINGO軟件簡(jiǎn)介,目標(biāo)與約束段 集合段（SETS ENDSETS） 數(shù)據(jù)段（DATA ENDDATA）初始段（INIT ENDINIT）,,,LINGO模型的構(gòu)成：4個(gè)段,LINGO模型的優(yōu)點(diǎn),包含了LIND

38、O的全部功能提供了靈活的編程語(yǔ)言（矩陣生成器）,LINGO模型 — 例：選址問(wèn)題,某公司有6個(gè)建筑工地，位置坐標(biāo)為(ai, bi) (單位：公里),水泥日用量di (單位：噸）,假設(shè)：料場(chǎng)和工地之間有直線道路,用例中數(shù)據(jù)計(jì)算，最優(yōu)解為,總噸公里數(shù)為136.2,線性規(guī)劃模型,決策變量：ci j (料場(chǎng)j到工地i的運(yùn)量）~12維,選址問(wèn)題：NLP,2）改建兩個(gè)新料場(chǎng)，需要確定新料場(chǎng)位置(xj,yj)和運(yùn)量cij ，在其它條件不變下使總噸公

39、里數(shù)最小。,決策變量：ci j，(xj,yj)~16維,非線性規(guī)劃模型,LINGO模型的構(gòu)成：4個(gè)段,集合段（SETS ENDSETS）,數(shù)據(jù)段（DATA ENDDATA）,初始段（INIT ENDINIT）,目標(biāo)與約束段,局部最優(yōu)：89.8835(噸公里 ),,,LP：移到數(shù)據(jù)段,邊界,集合的類(lèi)型,集合 派生集合 基本集合

40、稀疏集合 稠密集合 元素列表法 元素過(guò)濾法 直接列舉法 隱式列舉法,setname [/member_list/] [: attribute_list];,setname(parent_set_list) [/member_list/] [: attribute_list];,SETS: CITIES /A1,A2,A3,B1,B2/; ROADS(CITIES, CITIES)/

41、 A1,B1 A1,B2 A2,B1 A3,B2/:D; ENDSETS,SETS: STUDENTS /S1..S8/; PAIRS( STUDENTS, STUDENTS) | &2 #GT# &1: BENEFIT, MATCH;ENDSETS,集合元素的隱式列舉,運(yùn)算符的優(yōu)先級(jí),三類(lèi)運(yùn)算符： 算術(shù)運(yùn)算符 邏輯運(yùn)算符 關(guān)系運(yùn)算符,集合循環(huán)

42、函數(shù),四個(gè)集合循環(huán)函數(shù)：FOR、SUM 、 MAX、MIN@function( setname [ ( set_index_list)[ | condition]] : expression_list);,[objective] MAX = @SUM( PAIRS( I, J): BENEFIT( I, J) * MATCH( I, J));@FOR(STUDENTS( I): [constraints] @SUM(

43、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:,狀態(tài)窗口,Solver Type:B-and-BG

44、lobal Multistart,Model Class: LP， QP，ILP， IQP，PILP, PIQP，NLP，INLP，PINLP,State:Global OptimumLocal OptimumFeasibleInfeasibleUnboundedInterruptedUndetermined,7個(gè)選項(xiàng)卡(可設(shè)置80-90個(gè)控制參數(shù)),程序與數(shù)據(jù)分離,文本文件,使用外部數(shù)據(jù)文件,Cut

45、 (or Copy) – Paste 方法@FILE 輸入數(shù)據(jù)、@TEXT輸出數(shù)據(jù)（文本文件）@OLE函數(shù)與電子表格軟件（如EXCEL）連接@ODBC函數(shù)與數(shù)據(jù)庫(kù)連接LINGO命令腳本文件,LG4 （LONGO模型文件）LNG （LONGO模型文件）LTF （LONGO腳本文件）LDT （LONGO數(shù)據(jù)文件）LRP （LONGO報(bào)告文件）,常用文件后綴,@FILE和@TEXT：文本文件輸入輸出,MODEL:SETS:

46、 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) < SUPPLY(

47、I));DATA: COST = @FILE(‘myfile.txt’); NEED = @FILE(‘myfile.txt’); SUPPLY = @FILE(‘myfile.txt’); @TEXT(‘result.txt’)=SHIP, @DUAL(SHIP), @DUAL(CON1);ENDDATAEND,myfile.txt文件的內(nèi)容、格式：Seattle,Detroit,Chicago,Denve

48、r~COST,NEED,SUPPLY,SHIP~12,28,15,20~1600,1800,1200,1000~1700,1900,1300,1100,演示 MyfileExample.lg4,,@OLE ：與EXCEL連接,MODEL:SETS: MYSET: COST,SHIP,NEED,SUPPLY;ENDSETSMIN = @SUM( MYSET( I): SHIP( I) * COST( I));

49、 @FOR( MYSET( I): [CON1] SHIP( I) > NEED( I); [CON2] SHIP( I) < SUPPLY( I));DATA: MYSET =@OLE('D:\JXIE\BJ2004MCM\mydata.xls','CITIES'); COST,NEED,SUPPLY =@OLE(mydata.xls

50、); @OLE(mydata.xls,'SOLUTION')=SHIP; ENDDATAEND,mydata.xls文件中必須有下列名稱(chēng)(及數(shù)據(jù))： CITIES， COST，NEED，SUPPLY，SOLUTION,在EXCEL中還可以通過(guò)“宏”自動(dòng)調(diào)用LINGO(略)也可以將EXCEL表格嵌入到LINGO模型中(略),演示 MydataExample.lg4,,@ODBC ：與數(shù)據(jù)庫(kù)連接,輸入

51、基本集合元素：setname/@ODBC([‘datasource’ [, ‘tablename’ [, ‘columnname’]]])/輸入派生集合元素：setname/@ODBC([‘source’[,‘table’ [, ‘column1’[, ‘column2’…]]]])/,目前支持下列DBMS: (如為其他數(shù)據(jù)庫(kù)，則需自行安裝驅(qū)動(dòng))ACCESS， DBASE，EXCEL，F(xiàn)OXPRO，ORACLE，PARADO

52、X，SQL SERVER， TEXE FILES,使用數(shù)據(jù)庫(kù)之前，數(shù)據(jù)源需要在ODBC管理器注冊(cè),輸入數(shù)據(jù)：Attr_list=@ODBC([‘source’[,‘table’ [, ‘column1’[, ‘column2’…]]]])輸出數(shù)據(jù)：@ODBC([‘source’[,‘table’ [, ‘column1’[, ‘column2’…]]]])= Attr_list,具體例子略,建模實(shí)例與求解,最短路問(wèn)題下料問(wèn)題

53、露天礦的運(yùn)輸問(wèn)題鋼管運(yùn)輸問(wèn)題,最短路問(wèn)題,求各點(diǎn)到T的最短路,問(wèn)題1. 如何下料最節(jié)省 ?,例 鋼管下料,問(wèn)題2. 客戶(hù)增加需求：,節(jié)省的標(biāo)準(zhǔn)是什么？,由于采用不同切割模式太多，會(huì)增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過(guò)3種。如何下料最節(jié)省？,按照客戶(hù)需要在一根原料鋼管上安排切割的一種組合。,切割模式,合理切割模式的余料應(yīng)小于客戶(hù)需要鋼管的最小尺寸,鋼管下料,為滿足客戶(hù)需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為

54、節(jié)省？,合理切割模式,2. 所用原料鋼管總根數(shù)最少,鋼管下料問(wèn)題1,兩種標(biāo)準(zhǔn),1. 原料鋼管剩余總余量最小,xi ~按第i 種模式切割的原料鋼管根數(shù)(i=1,2,…7),約束,滿足需求,決策變量,目標(biāo)1（總余量）,按模式2切割12根,按模式5切割15根，余料27米,最優(yōu)解：x2=12, x5=15, 其余為0；最優(yōu)值：27,整數(shù)約束： xi 為整數(shù),當(dāng)余料沒(méi)有用處時(shí)，通常以總根數(shù)最少為目標(biāo),目標(biāo)2（

55、總根數(shù)）,鋼管下料問(wèn)題1,約束條件不變,最優(yōu)解：x2=15, x5=5, x7=5, 其余為0；最優(yōu)值：25。,xi 為整數(shù),按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,雖余料增加8米，但減少了2根,與目標(biāo)1的結(jié)果“共切割27根，余料27米” 相比,鋼管下料問(wèn)題2,對(duì)大規(guī)模問(wèn)題，用模型的約束條件界定合理模式,增加一種需求：5米10根；切割模式不超過(guò)3種。,現(xiàn)有4種需求：4米50根，5米10根，6

56、米20根，8米15根，用枚舉法確定合理切割模式，過(guò)于復(fù)雜。,決策變量,xi ~按第i 種模式切割的原料鋼管根數(shù)(i=1,2,3),r1i, r2i, r3i, r4i ~ 第i 種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長(zhǎng)的鋼管的數(shù)量,滿足需求,模式合理：每根余料不超過(guò)3米,整數(shù)非線性規(guī)劃模型,鋼管下料問(wèn)題2,目標(biāo)函數(shù)（總根數(shù)）,約束條件,整數(shù)約束： xi ,r1i, r2i, r3i, r4i (i=1,2,3)為整數(shù),增加

57、約束，縮小可行域，便于求解,原料鋼管總根數(shù)下界：,特殊生產(chǎn)計(jì)劃：對(duì)每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數(shù)上界：31,模式排列順序可任定,鋼管下料問(wèn)題2,需求：4米50根，5米10根，6米20根，8米15根,每根原料鋼管長(zhǎng)19米,LINGO求解整數(shù)非線性規(guī)劃模型,Local optimal solution found a

58、t iteration: 12211 Objective value: 28.00000Variable Value Reduced CostX1 10.00000 0.000000X2 10.00000 2.000000X3 8.000000 1.000

59、000R11 3.000000 0.000000R12 2.000000 0.000000R13 0.000000 0.000000R21 0.000000 0.000000R22 1.000000 0.000000

60、 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33

61、 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000

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

63、多安置一臺(tái)電鏟，電鏟平均裝車(chē)時(shí)間5分鐘,卡車(chē)在等待時(shí)所耗費(fèi)的能量也是相當(dāng)可觀的，原則上在安排時(shí)不應(yīng)發(fā)生卡車(chē)等待的情況。,露天礦生產(chǎn)的車(chē)輛安排(CUMCM-2003B),礦石卸點(diǎn)需要的鐵含量要求都為29.5%?1%(品位限制），搭配量在一個(gè)班次（8小時(shí)）內(nèi)滿足品位限制即可。卸點(diǎn)在一個(gè)班次內(nèi)不變?？ㄜ?chē)載重量為154噸，平均時(shí)速28km,平均卸車(chē)時(shí)間為3分鐘。,問(wèn)題：出動(dòng)幾臺(tái)電鏟，分別在哪些鏟位上；出動(dòng)幾輛卡車(chē)，分別在哪些路線上各運(yùn)輸多少次

64、?,平面示意圖,問(wèn)題數(shù)據(jù),問(wèn)題分析,與典型的運(yùn)輸問(wèn)題明顯有以下不同：這是運(yùn)輸?shù)V石與巖石兩種物資的問(wèn)題；屬于產(chǎn)量大于銷(xiāo)量的不平衡運(yùn)輸問(wèn)題；為了完成品位約束，礦石要搭配運(yùn)輸；產(chǎn)地、銷(xiāo)地均有單位時(shí)間的流量限制；運(yùn)輸車(chē)輛只有一種，每次滿載運(yùn)輸，154噸/車(chē)次；鏟位數(shù)多于鏟車(chē)數(shù)意味著要最優(yōu)的選擇不多于7個(gè)產(chǎn)地作為最后結(jié)果中的產(chǎn)地；最后求出各條路線上的派出車(chē)輛數(shù)及安排。,近似處理：先求出產(chǎn)位、卸點(diǎn)每條線路上的運(yùn)輸量(MIP模型)然

65、后求出各條路線上的派出車(chē)輛數(shù)及安排,模型假設(shè),卡車(chē)在一個(gè)班次中不應(yīng)發(fā)生等待或熄火后再啟動(dòng)的情況；在鏟位或卸點(diǎn)處由兩條路線以上造成的沖突問(wèn)題面前，我們認(rèn)為只要平均時(shí)間能完成任務(wù)，就認(rèn)為不沖突。我們不排時(shí)地進(jìn)行討論；空載與重載的速度都是28km/h，耗油相差很大；卡車(chē)可提前退出系統(tǒng)，等等。,如理解為嚴(yán)格不等待，難以用數(shù)學(xué)規(guī)劃模型來(lái)解 個(gè)別參數(shù)隊(duì)找到了可行解 （略）,符號(hào),xij ：從i鏟位到j(luò)號(hào)卸點(diǎn)的石料運(yùn)量 （車(chē)）

66、 單位： 噸；cij ：從i號(hào)鏟位到j(luò)號(hào)卸點(diǎn)的距離 公里；Tij :從i號(hào)鏟位到號(hào)j卸點(diǎn)路線上運(yùn)行一個(gè)周期平均時(shí)間 分；Aij ：從號(hào)鏟位到號(hào)卸點(diǎn)最多能同時(shí)運(yùn)行的卡車(chē)數(shù) 輛；Bij ：從號(hào)鏟位到號(hào)卸點(diǎn)路線上一輛車(chē)最多可運(yùn)行的次數(shù) 次；pi：i號(hào)鏟位的礦石鐵含量 p=(30,28,29

67、,32,31,33,32,31,33,31) %qj : j號(hào)卸點(diǎn)任務(wù)需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 噸cki ：i號(hào)鏟位的鐵礦石儲(chǔ)量 萬(wàn)噸cyi ：i號(hào)鏟位的巖石儲(chǔ)量 萬(wàn)噸fi :描述第i號(hào)鏟位是否使用的0-1變量，取1為使用

68、；0為關(guān)閉。,,,,(近似),優(yōu)化模型,,（1）道路能力(卡車(chē)數(shù))約束（2）電鏟能力約束（3）卸點(diǎn)能力約束（4）鏟位儲(chǔ)量約束（5）產(chǎn)量任務(wù)約束（6）鐵含量約束（7）電鏟數(shù)量約束（8）整數(shù)約束,.,xij為非負(fù)整數(shù)fi 為0-1整數(shù),計(jì)算結(jié)果（LINGO軟件）,計(jì)算結(jié)果（派車(chē)）,結(jié)論：鏟位1、2、3、4、8、9、10處各放置一臺(tái)電鏟。一共使用了13輛卡車(chē)；總運(yùn)量為85628.62噸公里；巖石產(chǎn)量為321