1、優(yōu)化方法建模侯為根安徽工業(yè)大學數(shù)理學院Email：優(yōu)化模型和算法的重要意義最優(yōu)化: 在一定條件下，尋求使目標最大(小)的決策最優(yōu)化是工程技術(shù)、經(jīng)濟管理、科學研究、社會生活中經(jīng)常遇到的問題, , 如: :運輸方案結(jié)構(gòu)設計 資源分配 生產(chǎn)計劃 經(jīng)驗積累，主觀判斷 作試驗，比優(yōu)劣 建立數(shù)學模型，求解最優(yōu)策略解決優(yōu)化問題的手段CUMCM賽題：約有一半為優(yōu)化問題須用軟件求解(最)優(yōu)化理論是運籌學的重要內(nèi)容OR/MS/DS運籌學(OR: Operations/Operational Research)管理科學(MS: Management Science)決策科學(DS: Decision Science

2、)優(yōu)化(Optimization), 規(guī)劃(Programming)線性規(guī)劃無約束優(yōu)化非線性規(guī)劃網(wǎng)絡優(yōu)化組合優(yōu)化整數(shù)規(guī)劃多目標規(guī)劃目標規(guī)劃動態(tài)規(guī)劃優(yōu)化問題的一般形式優(yōu)化問題三要素：決策變量；目標函數(shù)；約束條件njiDxljxgmixhtsxf, 2 , 1, 0)(, 2 , 1, 0)(. .)(min目標函數(shù)約束條件決策變量可行解(滿足約束條件)，可行域(可行解的集合)，最優(yōu)解(使目標達到最大/最小的可行解)無約束優(yōu)化:只有目標函數(shù); 約束優(yōu)化:有目標函數(shù)和約束條件。實際問題一般總有約束。例1 加工奶制品的生產(chǎn)計劃獲利24元/公斤獲利16元/公斤1桶牛奶12小時8小時3公斤A14公斤A2或

3、每天: 50桶牛奶 時間480小時 A1至多加工100公斤制訂生產(chǎn)計劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時工人，付出的工資最多是每小時幾元?A1的獲利增加到30元/公斤，應否改變生產(chǎn)計劃？獲利24元/公斤獲利16元/公斤1桶牛奶12小時8小時3公斤A14公斤A2或每天： 50桶牛奶 時間480小時 A1至多加工100公斤決策變量x1桶牛奶生產(chǎn)A1x2桶牛奶生產(chǎn)A2目標函數(shù)獲利243x1獲利164x2每天獲利 Max z =72x1 +64 x2約束條件原料供應勞動時間加工能力非負約束x1+x250線性規(guī)劃模型(LP)12x1+8x24803x1100 x

4、1, x20模型求解圖解法約束條件x1+x25012x1+8x24803x1100 x1, x20l1:x1+x2=50l2:12x1+8x2=480l3: 3x1=100l4: x1=0, l5: x2=0目標函數(shù)Max z =72x1 +64 x2z=c(常數(shù))等值線在B(20,30)點得到最優(yōu)解最優(yōu)解一定在凸多邊形的某個頂點取得目標函數(shù)和約束條件是線性函數(shù)可行域為直線段圍成的凸多邊形目標函數(shù)的等值線為直線4l5l1l2l3lc01x2xABCD0Z2400Z3600Z模型求解軟件實現(xiàn) Objective value: 3360.000 Variable Value Reduced Cos

5、t X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000max=72*x1+64*x2;x1+x2=50;12*x1+8*x2=480;3*x1=100;endLingo 8.020桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤3360元。未做敏感性分析結(jié)果解釋Global optimal solution found at iteration:4 Ob

6、jective value: 3360.000 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 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000max=72*x1+64*x2;x1+x2=50;12*x1+8*x2=480;3*x1=100;end三種資源原料無剩余時間無剩余加工能力剩余40“資源”剩余為零的約束為緊約束（有效約束）

7、結(jié)果解釋 Objective value: 3360.000Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000最優(yōu)解下 “資源”增加1單位時“效益”的增量。影子價格原料增加1單位,利潤增長48。時間增加1單位,利潤增長2。加工能力增長不影響利潤。聘用臨時工人付出的工資最多每小時幾元？35

8、元可買到1桶牛奶，要買嗎？35 48,應該買！2元！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 Ranges Row Current Allowable Allowable RHS Increase Decrease 2 5

9、0.00000 10.00000 6.666667 3 480.0000 53.33333 80.00000 4 100.0000 INFINITY 40.00000結(jié)果解釋作敏感性分析最優(yōu)解不變時，目標函數(shù)系數(shù)允許變化范圍(約束條件不變)x1系數(shù)范圍(64,96)x2系數(shù)范圍(48,72)x1系數(shù)為303=90 在允許范圍內(nèi)A1的獲利增加到30元/公斤，應否改變生產(chǎn)計劃？生產(chǎn)計劃不變！Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable AllowableVariable

10、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 2 50.00000 10.00000 6.666667 3 480.0000 53.33333 80.00000 4 100.0000 INFINITY 40.00000結(jié)果解釋 影子價格有意義時約束右端的允許變化范圍(目標函數(shù)不變)原料最多可增加10時間最多可增加

11、5335元可買到1桶牛奶，每天最多買多少？最多買10桶!Lingo軟件包能求解的優(yōu)化模型優(yōu)化模型連續(xù)優(yōu)化整數(shù)規(guī)劃線性規(guī)劃（LP）二次規(guī)劃QP非線性規(guī)劃NLPLingo軟件的求解過程1、確定常數(shù)Lingo預處理程序線性規(guī)劃求解程序非線性規(guī)劃求解程序分支定界管理程序LPNLPQPIP全局優(yōu)化ILPIQPINLP2、識別類型1、單純形算法2、內(nèi)點算法1、順序線性規(guī)劃法2、廣義既約梯度法3、多點搜索建模時要注意的幾個基本問題1、盡量使用實數(shù)優(yōu)劃，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)劃，減少非光滑約束個數(shù)如：盡量少使用絕對值、符號函數(shù)、多個變量求最大值/最小值，四舍五入，取整函數(shù)等3、盡量使用線性模

12、型、減少非線性約束和非線性變量的個數(shù) （如：x/y5改為x5y)4、合理設定變量上下界，盡可能給出變量初始值。5、模型中使用的參數(shù)數(shù)量級要適當(如小于103)。Lingo模型的優(yōu)點包含Lindo的全部功能提供了靈活的編程語言（矩陣生成器）Lingo模型的構(gòu)成目標與約束段集合段 （SETS ENDSETE）數(shù)據(jù)段（DATA ENDDATA）初始段（INTT ENDINTT）計算段（CALC ENDCALC） LINGO9.0例2、運輸問題某公司有6個貨棧，分別向8個銷售點供應商品，每一個貨棧的供應量都是有限的，每個銷售點需求量必須滿足，不同的貨棧向不同的銷售點運輸單位貨物的成本是不一樣的，問該公

13、司如何調(diào)配各貨棧和銷售點之間的物資運量，才能使運輸費用最小？ wh1wh2wh3wh4wh5wh6V1V2V3V4V5V6V7V8銷售網(wǎng)示意圖48條運輸路線運費V1V2V3V4V5V6V7V8供應量wh16267425960wh24953858255wh35219743351wh47673927143wh52395726541wh65522814352需求量3537223241324338貨棧供應量、銷售點需求量以及各點之間的運費如下表設xij、 cij分別表示從i貨棧向j銷售點運送的貨物量和單位貨物量的運費，目標是總運費為最小：6181ijijijxczMin約束條件：約束條件：每個貨棧運往

14、各銷售點的貨物總量應小于貨棧的可供應量，設貨棧i的可供應量為wi，則有)6 , 2 , 1( ,81iwxijij每個銷售點的需求量必須滿足，設銷售點j的需求量為vj，則有)8 , 2 , 1( ,61jvxjiijmodel:sets: warehouses/wh1.wh6/: capacity; vendors/v1.v8/: demand; links(warehouses,vendors): cost, volume;endsetsdata: capacity=60 55 51 43 41 52; demand=35 37 22 32 41 32 43 38; cost=6 2 6 7

15、 4 2 9 5 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3;enddata!目標函數(shù); min=sum(links: cost*volume);!需求約束; for(vendors(J): sum(warehouses(I): volume(I,J)=demand(J);!產(chǎn)量約束; for(warehouses(I):sum(vendors(J): volume(I,J)=capacity(I);end集合段 （SETS ENDSETE）數(shù)據(jù)段（DATA ENDDATA）目標

16、與約束段例3：選址問題某公司有6個建筑工地，位置坐標為(ai,bi)(單位：公里)水泥日用量di(單位：頓)i123456a1.258.750.55.7537.25b1.250.754.7556.57.75c3547611假設：料場與工地之間有直線道路1）現(xiàn)有兩個料場，位于A(5,1)，B(2,7) ,記(xj,yj),j=1,2 日儲存量ej各20噸。目標：制定每天的供應計劃，即從A，B兩料場分別向各工地運送多少噸水泥，使總噸公里數(shù)最小。決策變量：cij料場j到工地i的運量12維21612/122)()(minjiijijijbyaxc612121j621. .ijijjiijecidcts

17、，線性規(guī)劃模型用例中數(shù)據(jù)計算，最優(yōu)解為i123456ci1(料場料場A)350701ci2 (料場料場B)0040610總噸公里數(shù)為136.2選址問題:NLP2）重建兩個新料場，需要確定新料場的位置(xj,yj) 和運量cij，在其他條件不變下使總噸公里數(shù)最小。21612/122)()(minjiijijijbyaxc612121j621. .ijijjiijecidcts，決策變量：cij，xj，yj16維非線性規(guī)劃模型Model:sets: demand/1.6/: a,b,d; supply/1.2/:x,y,e; link(demand,supply):c;endsetsdata:!需

18、求點的位置需求點的位置;a=1.25,8.75,0.5,5.75,3,7.25;b=1.25,0.75,4.75,5,6.5,7.75;d=3,5,4,7,6,11; !需求量需求量 ;e=20,20; !供應量供應量;enddatainit:endinit!目標函數(shù)目標函數(shù);OBJmin=sum(link(i,j):c(i,j)*(x(j)-a(i)2+(y(j)-b(i)2)(1/2);!需求約束需求約束;for(demand(i):Demand_Comsum(supply(j):c(i,j)=d(i););!供應約束供應約束;for(supply(j):Supply_comsum(dem

19、and(i):c(i,j)=e(j););for(supply:free(x);free(y););endLingo模型的構(gòu)成：4個段集合段：SETS ENDSETS數(shù)據(jù)段：DATA ENDDATA初始段：SETS ENDSETS目標與約束段：例4 鋼管下料原料鋼管:每根19米客戶需求4米50根6米20根8米15根問題1. 如何下料最節(jié)省?節(jié)省的標準是什么？問題2. 客戶增加需求：5米10根由于采用不同切割模式太多，會增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過3種。如何下料最節(jié)省？鋼管下料切割模式按照客戶需要在一根原料鋼管上安排切割的一種組合合理切割模式的余料應小于客戶需要鋼管的最小尺寸余料1米

20、4米1根6米1根8米1根余料3米4米1根6米1根6米1根余料3米8米1根8米1根鋼管下料問題1合理切割模式模式 4米鋼管根數(shù) 6米鋼管根數(shù) 8米鋼管根數(shù)余料(米)14003231013201341203511116030170023為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)省？兩種標準1. 原料鋼管剩余總余量最小2. 所用原料鋼管總根數(shù)最少決策變量xi按第i種模式切割的原料鋼管根數(shù)(i=1,2,7)目標1(總余量)Min Z=3x1+x2+3x3+3x4+x5+x6+3x7模式4米根數(shù)6米根數(shù)8米根數(shù)余料(米)1400323101320134120351111603

21、0170023需求502015約束滿足需求4x1+3x2+2x3+x4+x550 x2+2x4+x5+3x620 x3+x5+2x715整數(shù)約束xi為整數(shù)最優(yōu)解: x2=12,x5=15,其它為0最優(yōu)值: z=27按模式2切割12根,按模式5切割15根，余料27米L280.lg4鋼管下料問題1目標2(總根數(shù)) Min Z=x1+x2+x3+x4+x5+x6+x7約束條件不變最優(yōu)值：254x1+3x2+2x3+x4+x550 x2+2x4+x5+3x620 x3+x5+2x715與目標1的結(jié)果“共切割27根,余料27米”相比按模式1切割5根按模式2切割5根按模式5切割15根共25根，余料35米雖

22、余料增加8米，但減少了2根當余料沒有用處時，通常以總根數(shù)最少為目標最優(yōu)解：x1=5, x2=5, x5=15, 其余為0L281.lg4鋼管下料問題2增加一種需求：5米10根；切割模式不超過3種。現(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定全部合理切割模式為：模式12345678910 11 12 13 14 15 164米00000011112223345米00112200130120106米03120112000101008米2010101010100000余料3102131320301123決策變量xi按第i種模式切割的原料鋼管根數(shù)(i=1,2, ,16)目

23、標 (總根數(shù))161miniixzx7+x8+x9+x10+2x11+2x12+2x13+3x14+3x15+4x1650 x3+ x4+2x5+2x6+x9+3x10+x12+2x13+x15 103x2+x3+2x4+x6+x7+2x8+x12+x14 202x1+x3+x5+x7+x9+x11 15約束滿足需求16, 2 , 1;0001iMxxxwiiiii其中Mi表示若第i種裁剪模式被選中，按第i種裁剪模式裁剪根數(shù)的上限3161iiw裁剪模式要求wi0-1變量， wi=1選用第i種模式切割 (i=1,2, ,16)裁剪模式約束可改寫為16, 2 , 1iwMxiii3161iiw其中

24、wi為0-1整數(shù)，xi為非負整數(shù)。程序見L2801為方便分別令:a=(0,0,0,0,0,0,1,1,1,1,2,2,2,3,3,4)；b=(0,0,1,1,2,2,0,0,1,3,0,1,2,0,1,0)；c=(0,3,1,2,0,1,1,2,0,0,0,1,0,1,0,0)；d=(2,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0)。16iixZMin規(guī)劃問題可表示為:1516iiixd50.16iiixats1016iiixb2016iiixcxi為整數(shù), i=1,2,1616, 2 , 1iwMxiii3161iiw其中wi為0-1整數(shù)，xi為非負整數(shù)。程序見L2804r1

25、i, r2i, r3i, r4i第i種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長的鋼管的數(shù)量鋼管下料問題2增加一種需求：5米10根；切割模式不超過3種。現(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過于復雜。對大規(guī)模問題，用模型的約束條件界定合理模式?jīng)Q策變量xi按第i種模式切割的原料鋼管根數(shù)(i=1,2,3)另一種思路鋼管下料問題2目標函數(shù)（總根數(shù)） Min z=x1+x2+x3模式合理：每根余料不超過3米約束條件滿足需求r11x1+r12x2+r13x350r21x1+r22x2+r23x310r31x1+r32x2+r33x320r41x

26、1+r42x2+r43x315164r11+5r21+6r31+8r4119164r12+5r22+6r32+8r4219164r13+5r23+6r33+8r4319整數(shù)約束：xi,r1i,r2i,r3i,r4i (i=1,2,3)為整數(shù)。整數(shù)非線性規(guī)劃模型鋼管下料問題2增加約束，縮小可行域，便于求解需求:4米50根，5米10根 6米20根，8米15根每根原料鋼管長19米2619158206105504原料鋼管數(shù)量的下界：特殊生產(chǎn)計劃：對每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數(shù)上界：1

27、3+10+8=3126x1+x2+x3 31 模式排列順序可任定x1x2 x3 Objective value: 28.00000Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 2.00000 X3 8.000000 1.000000R11 2.000000 0.000000R12 3.000000 0.000000R13 0.000000 0.000000R21 1.000000 0.000000R22 0.000000 0.000000R23 0.000000 0.000000R31 1.000000 0.00000

28、0R32 1.000000 0.000000R33 0.000000 0.000000R41 0.000000 0.000000R42 0.000000 0.000000R43 2.000000 0.000000模式2：每根原料鋼管切成3根4米和1根6米鋼管,共10根；Lingo求解整數(shù)非線性規(guī)劃模型原料鋼管總根數(shù)為28根模式1：每根原料鋼管切割成2根4米、1根5米和1根6米鋼管，共10根；模式3：每根原料鋼管切割成2根8米鋼管，共8根L291.lg4例5 飲料廠的生產(chǎn)與檢修企業(yè)生產(chǎn)計劃考慮與產(chǎn)量無關(guān)的固定費用給優(yōu)化模型求解帶來新的困難。單階段生產(chǎn)計劃多階段生產(chǎn)計劃外部需求和內(nèi)部資源隨時間變化

29、生產(chǎn)批量問題飲料廠的生產(chǎn)與檢修計劃某種飲料4周的需求量、生產(chǎn)能力和成本周次需求量(千箱) 生產(chǎn)能力(千箱)成本(千元/千箱)115305.0225405.1335455.4425205.5合計100135存貯費: 每周每千箱飲料0.2(千元)。安排生產(chǎn)計劃,滿足每周的需求,使4周總費用最小。在4周內(nèi)安排一次設備檢修，占用當周15千箱生產(chǎn)能力，能使檢修后每周增產(chǎn)5千箱，檢修應排在哪一周?問題分析除第4周外每周的生產(chǎn)能力超過每周的需求；生產(chǎn)成本逐周上升；前幾周應多生產(chǎn)一些。周次需求 能力成本115305.0225405.1335455.4425205.5合計100135模型假設飲料廠在第1周開始時

30、沒有庫存；從費用最小考慮,第4周末不能有庫存；周末有庫存時需支出一周的存貯費；每周末的庫存量等于下周初的庫存量。模型建立周次需求 能力成本115305.0225405.1335455.4425205.5決策變量x1x4：第14周的生產(chǎn)量y1y3：第13周末庫存量存貯費：0.2(千元/周千箱)目標函數(shù)產(chǎn)量、庫存與需求平衡能力限制)( 2 . 05 . 54 . 51 . 50 . 53214321yyyxxxxzMin約束條件x1-y1=15x2+y1-y2=25x3+y2-y3=35x4+y3=35x130, x2 40 x345, x420 非負約束x1, x2, x3, x4, y1, y

31、2, y30模型求解Lingo求解x1x4：15，40，25，20；y1y3：0，15，5 。最優(yōu)解周次需求產(chǎn)量庫存能力成本115150305.02254015405.1335255455.4425200205.54周生產(chǎn)計劃的總費用為528(千元)L271.lg4在4周內(nèi)安排一次設備檢修，占用當周15千箱生產(chǎn)能力，能使檢修后每周增產(chǎn)5千箱，檢修應排在哪一周?檢修計劃周次需求 能力成本115305.0225405.1335455.4425205.50-1變量wt：wt=1檢修安排在第t周(t=1,2,3,4）檢修安排在任一周均可約束條件產(chǎn)量、庫存與需求平衡條件不變能力限制x130 x240 x

32、345x420 x1+15w130 x2+15w240+5w1x3+15w345+5w1+5w2x4+15w420 +5w1+5w2+5w34周內(nèi)設備檢修一次：增加約束w1+w2+w3+w4=1目標函數(shù)不變檢修計劃Lingo求解Objective value: 527.0000Variable Value Reduced Cost X1 15.00000 0.000000 X2 45.00000 0.000000 X3 15.00000 0.000000 X4 25.00000 0.000000 Y1 0.000000 0.000000 Y2 20.00000 0.000000 Y3 0.00

33、0000 0.100000 W1 1.000000 -0.500000 W2 0.000000 1.500000 W3 0.000000 0.000000 W4 0.000000 0.000000w1=1 在第一周內(nèi)檢修4周的生產(chǎn)量分別為：x1=15, x2=45, x3=15, x4=25.3周的庫存量分別為：y1=0, y2=20, y3=0總費用由528降為527 (千元)。檢修所導致的生產(chǎn)能力提高的作用, ,需要更長的時間才能得到充分體現(xiàn)。L272.lg4飲料的生產(chǎn)批量問題飲料廠使用同一條生產(chǎn)線輪流生產(chǎn)多種飲料。若某周開工生產(chǎn)某種飲料,需支出生產(chǎn)準備費8千元。某種飲料4周的需求量、生產(chǎn)

34、能力和成本周次需求量(千箱) 生產(chǎn)能力(千箱)成本(千元/千箱)115305.0225405.1335455.4425205.5合計100135存貯費:每周每千箱飲料0.2(千元)。 安排生產(chǎn)計劃,滿足每周的需求,使4周總費用最小。生產(chǎn)批量問題的一般提法ct時段t生產(chǎn)費用(元/件)；ht時段t(末)庫存費(元/件)；st時段t生產(chǎn)準備費(元)；dt時段t市場需求(件)；Mt時段t生產(chǎn)能力(件)。假設初始庫存為0制訂生產(chǎn)計劃，滿足需求,并使T個時段的總費用最小。決策變量xt時段t生產(chǎn)量；yt時段t(末)庫存量；wt=1時段t開工生產(chǎn)(wt=0 不開工)。目標Ttttttttyhxcwsz1)(m

35、in約束;1ttttdyxy;0001tttxxw;ttMx 0, 00ttTyxyyTt, 2 , 1生產(chǎn)批量問題的一般提法Ttttttttyhxcwsz1)(minttttdyxyts1. .0001tttxxwttMx 0, 00ttTyxyyTt, 2 , 10tttwMx混合0-1規(guī)劃模型將所給參數(shù)代入模型，用Lingo求解最優(yōu)解：x1x4：30，40，30，0；總費用554.0(千元)x1x4：15，40，45，0；也是最優(yōu)解總費用一樣L273.lg4集合的類型集合派生集合基本集合稀疏集合 稠密集合元素列表法元素過濾法直接列舉法 隱式列舉法setname(parent_set_li

36、st) /member_list/:atribute_list;setname /member_list/:atribute_list;sets: students/John,Jill,Rose,Mike/:sex,age;endsets例如：定義有4個成員2個屬性的學生集合上面為直接列舉法，當集合成員很多時可用隱式列舉法，例如：sets: warehouses/wh1.wh6/:capacity; vendors/v1.v8/:demand;endsets為了定義一個原始集，必須詳細聲明：1、集的名字，2、集的成員(可選)，3、集成員的屬性(可選)；用下面的語法（ 表示可選）：setname

37、/member_list/:attribute_list;定義基本集合：集合元素的隱式列舉類型隱式列舉格式示例示例集合的元素數(shù)字型 1.n1.51,2,3,4,5字符數(shù)字型stringM.stringNCar101.Car108Car102, Car102, Car104,car108星期型 dayM.dayNMon.FriMon, Tue, Wed, Thu, Fri月份型 monthM.monthNOCT.JANOCT,NOV,DEC,JAN年份月份型monthYearM.monthYearNOCT2001.JAN2002OCT2001,NEV2001, DEC2001,JAN2002下表

38、給出了隱式列舉的一些具體方法1、集的名字，2、父集的名字，3、集成員(可選)，4、集成員的屬性(可選)定義派生集為了定義一個派生集，必須詳細聲明：setname是集的名字。parent_set_list是已定義的集的列表，多個時必須用逗號隔開。定義一個派生集語法：setname(parent_set_list)/member_list/:attribute_list;sets: warehouses/wh1.wh6/:capacity; vendors/v1.v8/:demand; links(warehouses,vendors):cost,volume;endsets例如下列集合links

39、就是派生集合：sets: cities/a1,a2,a3,a4/; roads(cities,cities)/a1,b1 a1,b2 a2,b1 a3,b2/:d;endsetssets: students/s1.s8/; pairs(students, students)|&2#GT#&1:Benefit,match;endsets上例的派生集合為稠密集合，若為稀疏集合，則可選用元素列表法或元素過濾法：若派生集合是基本集合構(gòu)成的笛卡兒積,則稱它為稠密集合;派生集合的元素可以只是這個笛卡兒積的一個真子集合，這種派生集合稱為稀疏集合例如下二例：元素列表法元素過濾法運算符的優(yōu)先級三

40、類運算符：邏輯運算符算術(shù)運算符關(guān)系運算符優(yōu)先級運算符最高#NOT# -（負號）* /+ -(減法）#EG# #NE# #GT# #GE# #LT# #LE#AND# #OR# 最低(=)四個集合循環(huán)函數(shù)：FOR、SUM、MAX、MIN集合循環(huán)函數(shù)循環(huán)函數(shù)一般格式function (setname(set_index_list)|condtion:expression_list);例如：),(),(),(jimatchjibenefitpairsjiobjectivemax=sum(pairs(i,j): benefit(i,j)*match(i,j);例如：1),(),(kjmatchikor

41、ijpairskjfor(students(i):condtion sum(pairs(i,j)|j#EQ#i#OR#k#EQ#i: match(j,k)=1);集合操作函數(shù)四個集合循環(huán)函數(shù) IN、INDEX、WARP、SIZE1in(set_name,primitive_index_1 ,primitive_index_2,)如果元素在指定集中，返回1；否則返回0。例：全集為I，B是I的一個子集，C是B的補集。sets: I/x1.x4/; B(I)/x2/; C(I)|#not#in(B,&1):;endsets2index(set_name, primitive_set_elem

42、ent)函數(shù)返回在集set_name中成員primitive_set_element 的索引 sets: girls/debble,sue,alice/; boys/bob,joe,sue,fred/;endsetsI1=index(sue);I2=index(boys,sue) I1的值是2，I2的值是3。我們建議在使用index函數(shù)時最好指定集。 例：確定成員在集合中的位置 該函數(shù)返回j=index-k*limit，其中k是一個整數(shù)，取適當值保證j落在集合1,2,limit內(nèi)。該函數(shù)在循環(huán)、多階段計劃編制中特別有用。3wrap(index,limit)該函數(shù)返回集set_name的成員個數(shù)

43、。在模型中明確給出集大小時最好使用該函數(shù)。它的使用使模型更加數(shù)據(jù)中立，集大小改變時也更易維護。4size(set_name)變量界定函數(shù)實現(xiàn)對變量取值范圍的附加限制，共4種：bin(x) 限制x為0或1；bnd(L,x,U) 限制LxU；free(x) 取消對變量x的默認下界為0的限制；gin(x) 限制x為整數(shù)。變量界定函數(shù)一項工作一周7天都需要有人（比如護士工作），每天（周一至周日）所需的最少職員數(shù)為20、16、13、16、19、14和12，并要求每個職員一周連續(xù)工作5天，試求每周所需最少職員數(shù)，并給出安排。注意這里我們考慮穩(wěn)定后的情況。例7: 職員時序安排模型設周一到周日安排的人數(shù)分別為

44、：x1,x2,x7，則周一到周日工作的人數(shù)為：先考慮周一：因為一旦安排了工作就連續(xù)工作五天，所以周一工作的人員應為上周四到本周一安排工作的人數(shù)之和：所以有x4+x5+x6+x7+x120同理，周二到周日的約束為：x5+x6+x7+x1+x216；x6+x7+x1+x2+x313；x7+x1+x2+x3+x416；x1+x2+x3+x4+x519；x2+x3+x4+x5+x614；x3+x4+x5+x6+x712；目標函數(shù)為 Min Z=x1+x2+x3+x4+x5+x6+x7xi為正整數(shù)。model:sets: days/mon.sun/: required,start;endsetsdata

45、: !每天所需的最少職員數(shù)每天所需的最少職員數(shù); required = 20 16 13 16 19 14 12; enddata!最小化每周所需職員數(shù)最小化每周所需職員數(shù); min=sum(days: start); for(days(J): sum(days(I) | I #le# 5: start(wrap(J-I+1,7) = required(J);end8 名同學準備分成4 個調(diào)查隊（每隊兩人）前往4 個地區(qū)進行社會調(diào)查。設兩兩之間組隊的效率如表所示（由于對稱性只列出了上三角部分），問如何組隊可以使總效率最高？例8: 匹配問題學生s1s2s3s4s5s6s7s8s1_9342156

46、s2_173521s3_44291s4_1552s5_876s6_23s7_4“元素過濾”法設mij為0-1變量，mij=1表示學生i與j匹配，設bij為學生i與j匹配的效率，目標為總效率最高：目標函數(shù)818jjiijijmbzMax對學生i有且只有一個其他的學生與其匹配1ikkijiijmm約束條件mij為0-1變量MODEL:SETS: students / 1.8/; pairs(students,students)|&2#GT#&1:efects,match;ENDSETSDATA: efects = 9 3 4 2 1 5 6 1 7 3 5 2 1 4 4 2 9

47、2 1 5 5 2 8 7 6 2 3 4;ENDDATAMAX=SUM( pairs(I,J):efects(I,J)*match(I,J);FOR(students(I):SUM(pairs(J,K)|J#EQ#I #OR# K#EQ#I:match(J,K)=1);FOR(pairs(I,J):BIN(match(I,J);END結(jié)果為1,8,2,4,3,7,5,6匹配,效率為30。在公路網(wǎng)中，司機希望找到一條從一個城市到另一個城市的最短路. 假設圖表示的是該公路網(wǎng), 節(jié)點表示貨車可以停靠的城市,弧上的權(quán)表示兩個城市之間的距離（百公里）.那么,貨車從城市S 出發(fā)到達城市T,如何選擇行路線

48、,使所經(jīng)過的路程最短?SA1A2A3B1B2C1C2T633658674678956S到T的最優(yōu)行駛路線P先求出從Ck(k=1,2)到T的最優(yōu)行駛路線.從Bk到T的最優(yōu)行駛路線.從Ak到T的最優(yōu)行駛路線.例9 最短路問題從S到T的行駛過程分成4 個階段,即SAi(i=1,2 或3), Ai Bj(j=1或2), Bj Ck(k=1或2), Ck T記d(Y,X)為城市Y與城市X之間的直接距離（若這兩個城市之間沒有道路直接相連，則可以認為直接距離為無窮大），用L(X)表示城市X到城市T的最優(yōu)行駛路線的路長, 則: ),()()(0)(TXYXdYLMinXLTL!最短路問題最短路問題;model

49、:sets: cities/S,A1,A2,A3,B1,B2,C1,C2,T/: L; roads(cities,cities)/ S,A1 S,A2 S,A3 A1,B1 A1,B2 A2,B1 A2,B2 A3,B1 A3,B2 B1,C1 B1,C2 B2,C1 B2,C2 C1,T C2,T /: P,D;endsetsdata: D=6 3 3 6 5 8 6 7 4 6 7 8 9 5 6; L= , , , , , , , ,0;enddata!L(index(T)=0;for(cities(i)|i#LT#INDEX(T):L(i)=min(roads(i,j): D(i,j)

50、+L(j);); !顯然，如果顯然，如果P(i,j)=1,則點則點i到點到點n的最短路徑的第一步是的最短路徑的第一步是i-j，否則就不是。，否則就不是。 由此，我們就可方便的確定出最短路徑由此，我們就可方便的確定出最短路徑; for(roads(i,j):P(i,j)=if(L(i) #eq# D(i,j)+L(j),1,0);end結(jié)果L(S)=20，路徑為：SA3B2C1T1324567891051213121163104121496851052現(xiàn)有10個城市的交通網(wǎng)，我們想找到從城市1到城市10的最短路徑;動態(tài)規(guī)劃圖示說明SETS:! 這里是這里是10個城市的基礎集，其中個城市的基礎集，

51、其中F( i) 表示從城市表示從城市i到最后一個城到最后一個城市的最短路徑市的最短路徑; CITIES /1.10/: F; ! 派生集派生集ROADS列出了城市間所有存在的道路（注：并非所有城市間列出了城市間所有存在的道路（注：并非所有城市間都有道路直接連接，并假定所有直接連接路徑僅有一條都有道路直接連接，并假定所有直接連接路徑僅有一條 ; ROADS( CITIES, CITIES)/ 1,2 1,3 1,4 2,5 2,6 2,7 3,5 3,6 3,7 4,5 4,6 5,8 5,9 6,8 6,9 7,8 7,9 8,10 9,10/: D; ! D( i, j) 是城市是城市 i

52、到到 j的距離的距離;ENDSETSDATA: ! 這里是對應于上述直接連接的道路的長度這里是對應于上述直接連接的道路的長度 ; D = 1 5 2 13 12 11 6 10 4 12 14 3 9 6 5 8 10 5 2;ENDDATA! 如果你已經(jīng)位于城市如果你已經(jīng)位于城市10，則你到城市的，則你到城市的10旅行長度為旅行長度為0; F( SIZE( CITIES) = 0;! 下列是經(jīng)典的動態(tài)規(guī)劃遞歸式。用語言敘述就是：從城市下列是經(jīng)典的動態(tài)規(guī)劃遞歸式。用語言敘述就是：從城市i到城市到城市10的最短路徑為城市的最短路徑為城市i到所有能直達的城市到所有能直達的城市j的路徑長度加上城市的

53、路徑長度加上城市j到到城市城市10的最短路徑的和的最小值的最短路徑的和的最小值; FOR( CITIES( i)| i #LT# SIZE( CITIES): F( i) = MIN( ROADS( i, j): D( i, j) + F( j);例10: 裝車問題要把七種不同規(guī)格的包裝箱裝到兩輛鐵路平板車上去，包裝箱的寬和高都是相等的，但厚度（t以厘米計）及重量（w以千克計）卻不同，下表給出它們的厚度、重量及數(shù)量c1c2c3c4c5c6c7t(厘米)48.752.061.372.048.752.064.0w(千克) 200030001000500400020001000k(箱數(shù))879664

54、8每輛平板車有10.2米長的地方可用于裝箱（像面包片那樣），載重量為40噸，由于當?shù)氐呢涍\的限制，對c3、c6、c7三類包裝箱的總數(shù)有如下特殊約束：他們所占的空間不得超過302.7厘米，是把這些包裝箱裝到車上去，而浪費的空間最小。問題分析包裝箱總重89噸，平板車能載80噸，裝不完，究竟在車上裝那些包裝箱，每種裝多少，必須有一個標準，該標準應遵循：重量、厚度等約束，目標是使車上的剩余空間最小。還要注意：對5、6、7三種包裝箱的厚度約束，問題并沒有給出是每輛車上5、6、7三種包裝箱的厚度不超過302.7厘米，還是兩輛車上的總厚度不超過302.7厘米，應分別加以考慮。問題假設1）集裝箱在裝車時兩個集

55、裝箱之間不留縫隙，其在給定集裝箱尺寸時已考慮了。2）假定5、6、7三種包裝箱在每節(jié)平板車上裝載的厚度不超過302.7厘米。模型建立設xij表示第i輛平板車上裝cj箱的個數(shù)，則有如下約束：自然約束：xij0 且為整數(shù) (1) 箱數(shù)約束：x11+ x21 8 (2) x12+ x22 7 (3) x13+ x23 9 (4) x14+ x24 6 (5) x15+ x25 6 (6) x16+ x26 4 (7) x17+ x27 8 (8) 重量約束：2xi1+ 3xi2+ xi3+ 0.5xi4+ 4xi5+ 2xi6+ xi7+ 40 i=1,2 (9, 10) 厚度約束：0.487xi1+ 0.520 xi2+ 0.613xi3+ 0.72xi4+ 0.487xi5+ 0.520 xi6+ 0.640 xi7+ 10.2 i=1,2 (11, 12) 特殊約束：0.487xi5+ 0.520 xi6+ 0.640 xi7+ 3.027 i=1,2 (13, 14) 目標