數(shù)學(xué)建模優(yōu)化問(wèn)題

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

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

3、每天: 50桶牛奶 時(shí)間480小時(shí) A1至多加工100公斤制訂生產(chǎn)計(jì)劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？獲利24元/公斤獲利16元/公斤1桶牛奶12小時(shí)8小時(shí)3公斤A14公斤A2或每天： 50桶牛奶 時(shí)間480小時(shí) A1至多加工100公斤決策變量x1桶牛奶生產(chǎn)A1x2桶牛奶生產(chǎn)A2目標(biāo)函數(shù)獲利243x1獲利164x2每天獲利 Max z =72x1 +64 x2約束條件原料供應(yīng)勞動(dòng)時(shí)間加工能力非負(fù)約束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目標(biāo)函數(shù)Max z =72x1 +64 x2z=c(常數(shù))等值線在B(20,30)點(diǎn)得到最優(yōu)解最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得目標(biāo)函數(shù)和約束條件是線性函數(shù)可行域?yàn)橹本€段圍成的凸多邊形目標(biāo)函數(shù)的等值線為直線4l5l1l2l3lc01x2xABCD0Z2400Z3600Z模型求解軟件實(shí)現(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，利潤(rùn)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三種資源原料無(wú)剩余時(shí)間無(wú)剩余加工能力剩余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單位時(shí)“效益”的增量。影子價(jià)格原料增加1單位,利潤(rùn)增長(zhǎng)48。時(shí)間增加1單位,利潤(rùn)增長(zhǎng)2。加工能力增長(zhǎng)不影響利潤(rùn)。聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？35

8、元可買到1桶牛奶，要買嗎？35 48,應(yīng)該買！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í)，目標(biāo)函數(shù)系數(shù)允許變化范圍(約束條件不變)x1系數(shù)范圍(64,96)x2系數(shù)范圍(48,72)x1系數(shù)為303=90 在允許范圍內(nèi)A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？生產(chǎn)計(jì)劃不變！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é)果解釋 影子價(jià)格有意義時(shí)約束右端的允許變化范圍(目標(biāo)函數(shù)不變)原料最多可增加10時(shí)間最多可增加

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

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

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

14、各銷售點(diǎn)的貨物總量應(yīng)小于貨棧的可供應(yīng)量，設(shè)貨棧i的可供應(yīng)量為wi，則有)6 , 2 , 1( ,81iwxijij每個(gè)銷售點(diǎn)的需求量必須滿足，設(shè)銷售點(diǎn)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!目標(biāo)函數(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）目標(biāo)

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

17、，線性規(guī)劃模型用例中數(shù)據(jù)計(jì)算，最優(yōu)解為i123456ci1(料場(chǎng)料場(chǎng)A)350701ci2 (料場(chǎng)料場(chǎng)B)0040610總噸公里數(shù)為136.2選址問(wèn)題:NLP2）重建兩個(gè)新料場(chǎng)，需要確定新料場(chǎng)的位置(xj,yj) 和運(yùn)量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、求點(diǎn)的位置需求點(diǎn)的位置;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; !供應(yīng)量供應(yīng)量;enddatainit:endinit!目標(biāo)函數(shù)目標(biāo)函數(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););!供應(yīng)約束供應(yīng)約束;for(supply(j):Supply_comsum(dem

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

20、4米1根6米1根8米1根余料3米4米1根6米1根6米1根余料3米8米1根8米1根鋼管下料問(wèn)題1合理切割模式模式 4米鋼管根數(shù) 6米鋼管根數(shù) 8米鋼管根數(shù)余料(米)14003231013201341203511116030170023為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)?。?jī)煞N標(biāo)準(zhǔn)1. 原料鋼管剩余總余量最小2. 所用原料鋼管總根數(shù)最少?zèng)Q策變量xi按第i種模式切割的原料鋼管根數(shù)(i=1,2,7)目標(biāo)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鋼管下料問(wèn)題1目標(biāo)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與目標(biāo)1的結(jié)果“共切割27根,余料27米”相比按模式1切割5根按模式2切割5根按模式5切割15根共25根，余料35米雖

22、余料增加8米，但減少了2根當(dāng)余料沒(méi)有用處時(shí)，通常以總根數(shù)最少為目標(biāo)最優(yōu)解：x1=5, x2=5, x5=15, 其余為0L281.lg4鋼管下料問(wèn)題2增加一種需求：5米10根；切割模式不超過(guò)3種?，F(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、標(biāo) (總根數(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為非負(fù)整數(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ī)劃問(wèn)題可表示為:1516iiixd50.16iiixats1016iiixb2016iiixcxi為整數(shù), i=1,2,1616, 2 , 1iwMxiii3161iiw其中wi為0-1整數(shù)，xi為非負(fù)整數(shù)。程序見L2804r1

25、i, r2i, r3i, r4i第i種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長(zhǎng)的鋼管的數(shù)量鋼管下料問(wèn)題2增加一種需求：5米10根；切割模式不超過(guò)3種。現(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過(guò)于復(fù)雜。對(duì)大規(guī)模問(wèn)題，用模型的約束條件界定合理模式?jīng)Q策變量xi按第i種模式切割的原料鋼管根數(shù)(i=1,2,3)另一種思路鋼管下料問(wèn)題2目標(biāo)函數(shù)（總根數(shù)） Min z=x1+x2+x3模式合理：每根余料不超過(guò)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ī)劃模型鋼管下料問(wèn)題2增加約束，縮小可行域，便于求解需求:4米50根，5米10根 6米20根，8米15根每根原料鋼管長(zhǎng)19米2619158206105504原料鋼管數(shù)量的下界：特殊生產(chǎn)計(jì)劃：對(duì)每根原料鋼管模式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)計(jì)劃考慮與產(chǎn)量無(wú)關(guān)的固定費(fèi)用給優(yōu)化模型求解帶來(lái)新的困難。單階段生產(chǎn)計(jì)劃多階段生產(chǎn)計(jì)劃外部需求和內(nèi)部資源隨時(shí)間變化

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

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

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

32、345x420 x1+15w130 x2+15w240+5w1x3+15w345+5w1+5w2x4+15w420 +5w1+5w2+5w34周內(nèi)設(shè)備檢修一次：增加約束w1+w2+w3+w4=1目標(biāo)函數(shù)不變檢修計(jì)劃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周的庫(kù)存量分別為：y1=0, y2=20, y3=0總費(fèi)用由528降為527 (千元)。檢修所導(dǎo)致的生產(chǎn)能力提高的作用, ,需要更長(zhǎng)的時(shí)間才能得到充分體現(xiàn)。L272.lg4飲料的生產(chǎn)批量問(wèn)題飲料廠使用同一條生產(chǎn)線輪流生產(chǎn)多種飲料。若某周開工生產(chǎn)某種飲料,需支出生產(chǎn)準(zhǔn)備費(fèi)8千元。某種飲料4周的需求量、生產(chǎn)

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

35、in約束;1ttttdyxy;0001tttxxw;ttMx 0, 00ttTyxyyTt, 2 , 1生產(chǎn)批量問(wèn)題的一般提法Ttttttttyhxcwsz1)(minttttdyxyts1. .0001tttxxwttMx 0, 00ttTyxyyTt, 2 , 10tttwMx混合0-1規(guī)劃模型將所給參數(shù)代入模型，用Lingo求解最優(yōu)解：x1x4：30，40，30，0；總費(fèi)用554.0(千元)x1x4：15，40，45，0；也是最優(yōu)解總費(fèi)用一樣L273.lg4集合的類型集合派生集合基本集合稀疏集合 稠密集合元素列表法元素過(guò)濾法直接列舉法 隱式列舉法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個(gè)成員2個(gè)屬性的學(xué)生集合上面為直接列舉法，當(dāng)集合成員很多時(shí)可用隱式列舉法，例如：sets: warehouses/wh1.wh6/:capacity; vendors/v1.v8/:demand;endsets為了定義一個(gè)原始集，必須詳細(xì)聲明：1、集的名字，2、集的成員(可選)，3、集成員的屬性(可選)；用下面的語(yǔ)法（ 表示可選）：setname

37、/member_list/:attribute_list;定義基本集合：集合元素的隱式列舉類型隱式列舉格式示例示例集合的元素?cái)?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、集成員的屬性(可選)定義派生集為了定義一個(gè)派生集，必須詳細(xì)聲明：setname是集的名字。parent_set_list是已定義的集的列表，多個(gè)時(shí)必須用逗號(hào)隔開。定義一個(gè)派生集語(yǔ)法：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上例的派生集合為稠密集合，若為稀疏集合，則可選用元素列表法或元素過(guò)濾法：若派生集合是基本集合構(gòu)成的笛卡兒積,則稱它為稠密集合;派生集合的元素可以只是這個(gè)笛卡兒積的一個(gè)真子集合，這種派生集合稱為稀疏集合例如下二例：元素列表法元素過(guò)濾法運(yùn)算符的優(yōu)先級(jí)三

40、類運(yùn)算符：邏輯運(yùn)算符算術(shù)運(yùn)算符關(guān)系運(yùn)算符優(yōu)先級(jí)運(yùn)算符最高#NOT# -（負(fù)號(hào)）* /+ -(減法）#EG# #NE# #GT# #GE# #LT# #LE#AND# #OR# 最低(=)四個(gè)集合循環(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ù)四個(gè)集合循環(huán)函數(shù) IN、INDEX、WARP、SIZE1in(set_name,primitive_index_1 ,primitive_index_2,)如果元素在指定集中，返回1；否則返回0。例：全集為I，B是I的一個(gè)子集，C是B的補(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í)最好指定集。 例：確定成員在集合中的位置 該函數(shù)返回j=index-k*limit，其中k是一個(gè)整數(shù)，取適當(dāng)值保證j落在集合1,2,limit內(nèi)。該函數(shù)在循環(huán)、多階段計(jì)劃編制中特別有用。3wrap(index,limit)該函數(shù)返回集set_name的成員個(gè)數(shù)

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

44、：x1,x2,x7，則周一到周日工作的人數(shù)為：先考慮周一：因?yàn)橐坏┌才帕斯ぷ骶瓦B續(xù)工作五天，所以周一工作的人員應(yīng)為上周四到本周一安排工作的人數(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；目標(biāo)函數(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 名同學(xué)準(zhǔn)備分成4 個(gè)調(diào)查隊(duì)（每隊(duì)兩人）前往4 個(gè)地區(qū)進(jìn)行社會(huì)調(diào)查。設(shè)兩兩之間組隊(duì)的效率如表所示（由于對(duì)稱性只列出了上三角部分），問(wèn)如何組隊(duì)可以使總效率最高？例8: 匹配問(wèn)題學(xué)生s1s2s3s4s5s6s7s8s1_9342156

46、s2_173521s3_44291s4_1552s5_876s6_23s7_4“元素過(guò)濾”法設(shè)mij為0-1變量，mij=1表示學(xué)生i與j匹配，設(shè)bij為學(xué)生i與j匹配的效率，目標(biāo)為總效率最高：目標(biāo)函數(shù)818jjiijijmbzMax對(duì)學(xué)生i有且只有一個(gè)其他的學(xué)生與其匹配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)中，司機(jī)希望找到一條從一個(gè)城市到另一個(gè)城市的最短路. 假設(shè)圖表示的是該公路網(wǎng), 節(jié)點(diǎn)表示貨車可以?？康某鞘?弧上的權(quán)表示兩個(gè)城市之間的距離（百公里）.那么,貨車從城市S 出發(fā)到達(dá)城市T,如何選擇行路線

48、,使所經(jīng)過(guò)的路程最短?SA1A2A3B1B2C1C2T633658674678956S到T的最優(yōu)行駛路線P先求出從Ck(k=1,2)到T的最優(yōu)行駛路線.從Bk到T的最優(yōu)行駛路線.從Ak到T的最優(yōu)行駛路線.例9 最短路問(wèn)題從S到T的行駛過(guò)程分成4 個(gè)階段,即SAi(i=1,2 或3), Ai Bj(j=1或2), Bj Ck(k=1或2), Ck T記d(Y,X)為城市Y與城市X之間的直接距離（若這兩個(gè)城市之間沒(méi)有道路直接相連，則可以認(rèn)為直接距離為無(wú)窮大），用L(X)表示城市X到城市T的最優(yōu)行駛路線的路長(zhǎng), 則: ),()()(0)(TXYXdYLMinXLTL!最短路問(wèn)題最短路問(wèn)題;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,則點(diǎn)則點(diǎn)i到點(diǎn)到點(diǎn)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個(gè)城市的交通網(wǎng)，我們想找到從城市1到城市10的最短路徑;動(dòng)態(tài)規(guī)劃圖示說(shuō)明SETS:! 這里是這里是10個(gè)城市的基礎(chǔ)集，其中個(gè)城市的基礎(chǔ)集，

51、其中F( i) 表示從城市表示從城市i到最后一個(gè)城到最后一個(gè)城市的最短路徑市的最短路徑; 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: ! 這里是對(duì)應(yīng)于上述直接連接的道路的長(zhǎng)度這里是對(duì)應(yīng)于上述直接連接的道路的長(zhǎng)度 ; 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旅行長(zhǎng)度為旅行長(zhǎng)度為0; F( SIZE( CITIES) = 0;! 下列是經(jīng)典的動(dòng)態(tài)規(guī)劃遞歸式。用語(yǔ)言敘述就是：從城市下列是經(jīng)典的動(dòng)態(tài)規(guī)劃遞歸式。用語(yǔ)言敘述就是：從城市i到城市到城市10的最短路徑為城市的最短路徑為城市i到所有能直達(dá)的城市到所有能直達(dá)的城市j的路徑長(zhǎng)度加上城市的

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

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

55、裝箱之間不留縫隙，其在給定集裝箱尺寸時(shí)已考慮了。2）假定5、6、7三種包裝箱在每節(jié)平板車上裝載的厚度不超過(guò)302.7厘米。模型建立設(shè)xij表示第i輛平板車上裝cj箱的個(gè)數(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) 目標(biāo)