第1頁，共47頁，2023年，2月20日，星期六上機實踐一具體內(nèi)容◆運輸問題(P11)◆選址問題(P13)◆最短路問題(P25)◆鋼管運輸問題(P27,CUMCM-2000B)◆課上練習(xí)─聘用方案(P31)◆

CH4習(xí)題(P130第2題─LP)(P40)◆

CH4習(xí)題(P134第11題─NLP)(P42)◆

課后問題(P45-47)、。。。第2頁，共47頁，2023年，2月20日，星期六優(yōu)化模型實際問題中的優(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ī)劃第3頁，共47頁，2023年，2月20日，星期六建模時需要注意的幾個基本問題

1、盡量使用實數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個數(shù)如：盡量少使用絕對值、符號函數(shù)、多個變量求最大/最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變量的個數(shù)（如x/y<5改為x<5y,或x-5y<0）4、合理設(shè)定變量上下界，盡可能給出變量初始值5、模型中使用的參數(shù)數(shù)量級要適當(dāng)(如小于103)第4頁，共47頁，2023年，2月20日，星期六使用LINDO的一些注意事項“>”（或“<”）號與“>=”（或“<=”）功能相同變量與系數(shù)間可有空格(甚至回車),但無運算符變量名以字母開頭，不能超過8個字符變量名不區(qū)分大小寫（包括LINDO中的關(guān)鍵字）目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件行號(行名)自動產(chǎn)生或人為定義。行名以“）”結(jié)束行中注有“!”符號的后面部分為注釋。如:

!It’sComment.在模型的任何地方都可以用“TITLE”對模型命名（最多72個字符），如：

TITLEThisModelisonlyanExample變量不能出現(xiàn)在一個約束條件的右端第5頁，共47頁，2023年，2月20日，星期六表達式中不接受括號“()”和逗號“,”等任何符號,例:400(X1+X2)需寫為400X1+400X2表達式應(yīng)化簡,如2X1+3X2-4X1應(yīng)寫成-2X1+3X2缺省假定所有變量非負；可在模型的“END”語句后用“FREEname”可將變量name的非負假定取消可在“END”后用“SUB”或“SLB”設(shè)定變量上下界例如：“subx110”的作用等價于“x1<=10”,

但用“SUB”和“SLB”表示的上下界約束不計入模型的約束，也不能給出其松緊判斷和敏感性分析14.“END”后對0-1變量說明：INTn

或INTname15.“END”后對整數(shù)變量說明：GINn

或GINname使用LINDO的一些注意事項第6頁，共47頁，2023年，2月20日，星期六當(dāng)前狀態(tài)：已達最優(yōu)解迭代次數(shù)：18次約束不滿足的“量”(不是“約束個數(shù)”)：0當(dāng)前的目標(biāo)值：94最好的整數(shù)解：94整數(shù)規(guī)劃的界：93.5分枝數(shù)：1所用時間：0.00秒（太快了，還不到0.005秒）刷新本界面的間隔:1(秒)狀態(tài)窗口（LINDOSolverStatus）第7頁，共47頁，2023年，2月20日，星期六NonzeroLimit：非零系數(shù)的個數(shù)上限；IterationLimit：最大迭代步數(shù)；InitialContraintTol：約束的初始誤差上限；FinalContraintTol：約束的最后誤差上限；EnteringVarTol：進基變量的REDUCEDCOST的誤差限；PivotSizeTol：旋轉(zhuǎn)元的誤差限選項設(shè)置

Preprocess：預(yù)處理(生成割平面)；

PreferredBranch：優(yōu)先的分枝方式：“Default”（缺省方式）、“Up”（向上取整優(yōu)先）、“Down”（向下取整優(yōu)先）；

IPOptimalityTol：IP最優(yōu)值允許的誤差上限（一個百分?jǐn)?shù)，如5%即0.05）；

IPObjectiveHurdle：IP目標(biāo)函數(shù)的籬笆值，即只尋找比這個值更優(yōu)最優(yōu)解（如當(dāng)知道當(dāng)前模型的某個整數(shù)可行解時，就可以設(shè)置這個值）；

IPVarFixingTol：固定一個整數(shù)變量取值所依據(jù)的一個上限（如果一個整數(shù)變量的判別數(shù)（REDUCEDCOST）的值很大，超過該上限，則以后求解中把該整數(shù)變量固定下來）。第8頁，共47頁，2023年，2月20日，星期六Report/Statistics第一行：模型有5行（約束4行），4個變量，兩個整數(shù)變量（沒有0-1變量），從第4行開始是二次規(guī)劃的實際約束。第二行：非零系數(shù)19個，約束中非零系數(shù)12個(其中6個為1或-1)，模型密度為0.760(密度=非零系數(shù)/[行數(shù)＊(變量數(shù)＋１)])。第三行的意思：按絕對值看，系數(shù)最小、最大分別為0.3和277。第四行的意思：模型目標(biāo)為極小化；小于等于、等于、大于等于約束分別有２、０、２個；廣義上界約束（GUBS）不超過１個；變量上界約束（VUBS）不少于０個。所謂GUBS，是指一組不含有相同變量的約束；所謂VUBS，是指一個蘊涵變量上界的約束，如從約束X1+X2-X3=0可以看出，若X3=0，則X1=0，X2=0（因為有非負限制），因此X1+X2-X3=0是一個VUBS約束。第五行的意思：只含１個變量的約束個數(shù)=０個；冗余的列數(shù)=０個ROWS=5VARS=4INTEGERVARS=2(0=0/1)QCP=4NONZEROS=19CONSTRAINTNONZ=12(6=+-1)DENSITY=0.760SMALLESTANDLARGESTELEMENTSINABSOLUTEVALUE=0.300000277.000OBJ=MIN,NO.<,=,>:202,GUBS<=1VUBS>=0SINGLECOLS=0REDUNDANTCOLS=0 第9頁，共47頁，2023年，2月20日，星期六目標(biāo)與約束段集合段（SETSENDSETS）數(shù)據(jù)段（DATAENDDATA）初始段（INITENDINIT）LINGO軟件簡介LINGO模型的構(gòu)成：4個段LINGO模型的優(yōu)點包含了LINDO的全部功能提供了靈活的編程語言（矩陣生成器）LINGO教程可以幫助你了解及指導(dǎo)如何掌握這一軟件,如查找@free,@bin,就可獲知相關(guān)信息.第10頁，共47頁，2023年，2月20日，星期六例1運輸問題

使用LINGO軟件計算6個發(fā)點8個收點的最小費用的。產(chǎn)銷單位運價如下表。

銷地產(chǎn)地

B1B2B3B4B5B6B7B8產(chǎn)量A16267425960A24953858255A35219743351A47673927143A52395726541A65522814352銷量3537223241324338

編寫程序如下,并在LINGO軟件下實現(xiàn)!單位運價第11頁，共47頁，2023年，2月20日，星期六model:!6發(fā)點8收點運輸問題;sets:warehouses/wh1..wh6/:capacity;vendors/v1..v8/:demand;links(warehouses,vendors):cost,volume;!待求的決策變量是volume;endsets!目標(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));!這里是數(shù)據(jù);data:capacity=605551434152;demand=3537223241324338;cost=626742594953858252197433767392712395726555228143;enddataetza-8AMg-3bHp-?f7v-?%Q4-4gAt-Xkyj-Y#5D-Zk43-aGe#-D?z2當(dāng)輸入LINGO8.0的注冊碼后,所有變量個數(shù)、約束條件個數(shù)就不受限制了!操作方法是將下面的SN碼復(fù)制后在LINGO8.0下的“Lingopassword”命令窗口中粘貼即可!LINGO11不要注冊碼！第12頁，共47頁，2023年，2月20日，星期六例2:選址問題某公司有6個建筑工地，位置坐標(biāo)為(ai,bi)(單位：公里),水泥日用量di

(單位：噸）假設(shè)：料場和工地之間有直線道路用LINGO實現(xiàn)第13頁，共47頁，2023年，2月20日，星期六總噸公里數(shù)為136.2275線性規(guī)劃LP模型決策變量：cij(料場j到工地i的運量）~12維A,B兩料場分別向各工地運送水泥的每天供應(yīng)量第14頁，共47頁，2023年，2月20日，星期六MODEL:TitleLocationProblem;sets:demand/1..6/:a,b,d;supply/1..2/:x,y,e;link(demand,supply):c;endsetsData:a=1.25,8.75,0.5,5.75,3,7.25;

!locationsforthedemand(需求點的位置);b=1.25,0.75,4.75,5,6.5,7.75;d=3,5,4,7,6,11;

e=20,20;

!quantitiesofthedemandandsupply(供需量);x,y=5,1,2,7;enddata!Objectivefunction（目標(biāo)）;[OBJ]min=@sum(link(i,j):c(i,j)*((x(j)-a(i))^2+(y(j)-b(i))^2)^(1/2));!demandconstraints（需求約束）;@for(demand(i):[DEMAND_CON]@sum(supply(j):c(i,j))=d(i););!supplyconstraints（供應(yīng)約束）;@for(supply(i):[SUPPLY_CON]@sum(demand(j):c(j,i))<=e(i););@for(supply:@free(X);!@for(supply:@bnd(0.5,X,8.75);@free(Y););!@bnd(0.75,Y,7.75);END第15頁，共47頁，2023年，2月20日，星期六選址問題2）改建兩個新料場，需要確定新料場位置(xj,yj)和運量cij，在其它條件不變下使總噸公里數(shù)最小。決策變量：cij，(xj,yj)~16維非線性規(guī)劃模型第16頁，共47頁，2023年，2月20日，星期六MODEL:TitleLocationProblem;sets:demand/1..6/:a,b,d;supply/1..2/:x,y,e;link(demand,supply):c;endsetsData:a=1.25,8.75,0.5,5.75,3,7.25;

!locationsforthedemand(需求點的位置);b=1.25,0.75,4.75,5,6.5,7.75;d=3,5,4,7,6,11;

e=20,20;

!quantitiesofthedemandandsupply(供需量);enddatainit:x,y=5,1,2,7;!x,y=5,1,2,7;

!initiallocationsforthesupply（初始點）;Endinit!Objectivefunction（目標(biāo)）;[OBJ]min=@sum(link(i,j):c(i,j)*((x(j)-a(i))^2+(y(j)-b(i))^2)^(1/2));!demandconstraints（需求約束）;@for(demand(i):[DEMAND_CON]@sum(supply(j):c(i,j))=d(i););!supplyconstraints（供應(yīng)約束）;@for(supply(i):[SUPPLY_CON]@sum(demand(j):c(j,i))<=e(i););@for(supply:@free(X);!@for(supply:@bnd(0.5,X,8.75);@free(Y););!@bnd(0.75,Y,7.75);END第17頁，共47頁，2023年，2月20日，星期六LINGO模型的構(gòu)成：“段”集合段（SETS/ENDSETS）數(shù)據(jù)段（DATA/ENDDATA）初始段（INIT/ENDINIT）目標(biāo)函數(shù)與約束段新料廠約在(5.7,4.9),(7.3,7.8);局部最優(yōu)解:89.9(噸公里)第18頁，共47頁，2023年，2月20日，星期六集合的類型集合派生集合基本集合稀疏集合稠密集合元素列表法元素過濾法直接列舉法隱式列舉法setname[/member_list/][:attribute_list];setname(parent_set_list)[/member_list/][:attribute_list];SETS:CITIES/A1,A2,A3,B1,B2/;ROADS(CITIES,CITIES)/ A1,B1A1,B2A2,B1A3,B2/:D;ENDSETSSETS:STUDENTS/S1..S8/;PAIRS(STUDENTS,STUDENTS)|&2#GT#&1:BENEFIT,MATCH;ENDSETS第19頁，共47頁，2023年，2月20日，星期六集合元素的隱式列舉類型隱式列舉格式示例示例集合的元素數(shù)字型1..n1..51,2,3,4,5字符-數(shù)字型stringM..stringNCar101..car208Car101,car102,…,car208星期型dayM..dayNMON..FRIMON,TUE,WED,THU,FRI月份型monthM..monthNOCT..JANOCT,NOV,DEC,JAN年份-月份型monthYearM..monthYearNOCT2001..JAN2002OCT2001,NOV2001,DEC2001,JAN2002第20頁，共47頁，2023年，2月20日，星期六運算符的優(yōu)先級優(yōu)先級運算符最高#NOT#—（負號）^*/+—（減法）#EQ##NE##GT##GE##LT##LE##AND##OR#最低<(=)=>(=)三類運算符：算術(shù)運算符邏輯運算符關(guān)系運算符第21頁，共47頁，2023年，2月20日，星期六集合循環(huán)函數(shù)四個集合循環(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(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:第22頁，共47頁，2023年，2月20日，星期六狀態(tài)窗口SolverType:B-and-BGlobalMultistartModelClass:LP，QP，ILP，IQP，PILP,PIQP，NLP，INLP，PINLPState:GlobalOptimumLocalOptimumFeasibleInfeasibleUnboundedInterruptedUndetermined第23頁，共47頁，2023年，2月20日，星期六7個選項卡(可設(shè)置80-90個控制參數(shù))第24頁，共47頁，2023年，2月20日，星期六例3:最短路問題

(ShortestPathProblem-SPP)

求各點到

T

的最短路56774968658336C1B1C2B2A1A2A3TS6第25頁，共47頁，2023年，2月20日，星期六model:SETS:

!CITIES表示由1~9組成的集合，是一個基本集合;CITIES/1..9/:L; !屬性L(i)表示城市i到城市1的最優(yōu)行駛路線的路長;ROADS(CITIES,CITIES)/!ROADS表示網(wǎng)絡(luò)中的弧,是由CITIES派生的集合;9,69,79,8 !由于并非所有城市間都有道路直接連接，所以將弧具體列出;6,46,57,47,58,48,54,24,35,25,32,13,1/:D; !屬性D(i,j)是城市i到j(luò)的直接距離（已知）;ENDSETSDATA:D= !D賦值的順序?qū)?yīng)于ROADS中的弧的順序;633658674678956;ENDDATAL(1)=0; !邊界條件;@FOR(CITIES(i)|i#GT#1: !集合循環(huán)語句,#GT#表示邏輯關(guān)系"大于";L(i)=@MIN(ROADS(i,j):D(i,j)+L(j)) !這就是動態(tài)規(guī)劃基本方程;);end第26頁，共47頁，2023年，2月20日，星期六A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7鐵路運價表里程≤300301～350351～400401～450451～500…運價2023262932…例4鋼管運輸問題（CUMCM-2000B)第27頁，共47頁，2023年，2月20日，星期六xij是從鋼廠i運到節(jié)點j的鋼管量;fi表示鋼廠i是否使用；yj是從節(jié)點j向左鋪設(shè)的鋼管量；zj是向右鋪設(shè)的鋼管量.

第28頁，共47頁，2023年，2月20日，星期六MODEL:TITLEPiplineTransportation;SETS: SUPPLY/S1..S7/:S,P,f; NEED/A1..A15/:b,y,z; LINK(Supply,need):C,X;ENDSETSDATA:S=80080010002000200020003000;P=160155155160155150160;b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,;c=170.7160.3140.298.638.020.53.121.264.292.096.0106.0121.2128.0142.0215.7205.3190.2171.6111.095.586.071.2114.2142.0146.0156.0171.2178.0192.0230.7220.3200.2181.6121.0105.596.086.248.282.086.096.0111.2118.0132.0260.7250.3235.2216.6156.0140.5131.0116.284.262.051.061.076.283.097.0用lingo求解該NP問題第29頁，共47頁，2023年，2月20日，星期六255.7245.3225.2206.6146.0130.5121.0111.279.257.033.051.071.273.087.0265.7255.3235.2216.6156.0140.5131.0121.284.262.051.045.026.211.028.0275.7265.3245.2226.6166.0150.5141.0131.299.276.066.056.038.226.02.0;ENDDATA[obj]MIN=@sum(link(i,j):(c(i,j)+p(i))*x(i,j))+0.05*@sum(need(j):y(j)^2+y(j)+z(j)^2+z(j));@for(supply(i):[con1]@sum(need(j):x(i,j))<=S(i)*f(i));@for(supply(i):[con2]@sum(need(j):x(i,j))>=500*f(i));@for(need(j):[con3]@sum(supply(i):x(i,j))=y(j)+z(j));@for(need(j)|j#NE#15:[con4]z(j)+y(j+1)=b(j));y(1)=0;z(15)=0;@for(supply:@bin(f));END第30頁，共47頁，2023年，2月20日，星期六某服務(wù)部門一周中每天需要不同數(shù)目的雇員:周一到周四每天至少50人,周五和周日每天至少80人,周六至少90人.現(xiàn)規(guī)定應(yīng)聘者需連續(xù)工作5日,試確定聘用方案,即周一到周日每天聘多少人,使在滿足需求條件下聘用總?cè)藬?shù)最少.上面指的是全時雇員(一天工作8小時)，如果可以用兩個臨時聘用的半時雇員(一天工作4小時,不需要連續(xù)工作)代替一個全時雇員，但規(guī)定半時雇員的工作量不得超過總工作量的四分之一.又設(shè)全時雇員和半時雇員每小時的酬金分別為5元和3元，試確定聘用方案,使在滿足需要的條件下所付酬金總額最小．課上練習(xí)1.聘用方案第31頁，共47頁，2023年，2月20日，星期六⑴設(shè)所聘雇員皆為全時雇員記周一到周日每天聘用人數(shù)分別為則目標(biāo)函數(shù)(聘用總?cè)藬?shù))為:

解

典型的線性(整數(shù))規(guī)劃問題

第32頁，共47頁，2023年，2月20日，星期六

minx1+X2+x3+X4+X5+X6+X7st1)x1+X4+X5+X6+X7>=502)x1+X2+X5+X6+X7>=503)x1+X2+X3+X6+X7>=504)x1+X2+X3+X4+X7>=505)x1+X2+x3+X4+X5>=806)x2+X3+X4+X5+X6>=907)x3+X4+X5+X6+X7>=80end運行后,需對結(jié)果進行分析第33頁，共47頁，2023年，2月20日，星期六model:sets:

days/1..7/:p,x;!x決策變量,P每周每一天需要的服務(wù)員數(shù)量;endsetsdata:p=50505050809080;enddata

min=@sum(days(i):x(i));@for(days(j):@sum(days(i)|i#le#5:x(@wrap(i+j+2,7)))=p(j));!用來描繪必須連續(xù)工作5天;

end第34頁，共47頁，2023年，2月20日，星期六⑵考慮聘用半時雇員,記周一到周日每天聘用半時雇員人數(shù)分別為則目標(biāo)函數(shù)(酬金總額)為:條件B條件A第35頁，共47頁，2023年，2月20日，星期六min200x1+200X2+200x3+200X4+200X5+200X6+200X7+12y1+12y2+12y3+12y4+12y5+12y6+12y7stx1+X4+X5+X6+X7+0.5y1>=50x1+X2+X5+X6+X7+0.5y2>=50x1+X2+X3+X6+X7+0.5y3>=50x1+X2+X3+X4+X7+0.5y4>=50x1+X2+x3+X4+X5+0.5y5>=80x2+X3+X4+X5+X6+0.5y6>=90x3+X4+X5+X6+X7+0.5y7>=80

y1+y2+y3+y4+y5+y6+y7<=225end條件A第36頁，共47頁，2023年，2月20日，星期六model:sets:

days/1..7/:p,x,y;

!x,y決策變量,P每周每天需要的服務(wù)員數(shù)量;endsetsdata:p=50505050809080;enddatamin=@sum(days(i):200*x(i)+12*y(i));@sum(days(j):y(j))<=225;@for(days(j):@sum(days(i)|i#le#5:!描繪必須連續(xù)工作5天;x(@wrap(i+j+2,7)))+0.5*y(j)=p(j));@for(days(j):@gin(x);@gin(y));end第37頁，共47頁，2023年，2月20日，星期六MIN200x1+200X2+200x3+200X4+200X5+200X6+200X7+12y1+12y2+12y3+12y4+12y5+12y6+12y7stx1+X4+X5+X6+X7+0.5y1>=50x1+X2+X5+X6+X7+0.5y2>=50x1+X2+X3+X6+X7+0.5y3>=50x1+X2+X3+X4+X7+0.5y4>=50x1+X2+x3+X4+X5+0.5y5>=80x2+X3+X4+X5+X6+0.5y6>=90x3+X4+X5+X6+X7+0.5y7>=803y1+3y2+3y3+3y4+3y5+3y6+3y7-2x1-2X2-2X3-2X4-2X5-2X6-2X7<=0end

●

在end后加入命令:gin14

代表什么?加入此語句死循環(huán)條件B第38頁，共47頁，2023年，2月20日，星期六model:sets:

days/1..7/:p,x,y;!x,y決策變量,P每周每天需服務(wù)生數(shù);endsetsdata:p=50505050809080;enddatamin=@sum(days(i):200*x(i)+12*y(i));@for(days(j):@sum(days(i)|i#le#5:x(@wrap(i+j+2,7)))+0.5*y(j)>=p(j));

!描繪必須連續(xù)工作5天;@sum(days(i):3*y(i))-@sum(days(i):2*x(i))<=0;@for(days(i):@gin(x(i));@gin(y(i)));end第39頁，共47頁，2023年，2月20日，星期六設(shè)Pi表示第i個“大學(xué)生區(qū)“的大學(xué)生人數(shù)，i=1,…,7表示第i區(qū)與第j區(qū)相鄰(i<j),且共有一售書點否則x12,x13,x23,x24,x25,x34,x45,x46,x47,x56,x67.1234567教材P130第四章習(xí)題─題2課上練習(xí)第40頁，共47頁，2023年，2月20日，星期六

Max63x12+76x13+71x23+50x24+85x25+63x34+77x45+39x46+92x47+74x56+89x67用lindo求解得到：最優(yōu)解為x25=x47=1(其它取0值)，最優(yōu)值為177千人.s.t.1)x12+x13+x23+x24+x25+x34+x45+x46+x47+x56+x67<=22)x12+x13<=13)x12+x23+x24+x25<=14)x13+x23+x34<=15)X24+X34+X45+X46+X47<=16)x25+x45+x56<=17)x46+x56+x67<=18)x47+x67<=1int11end用lindo下求解第41頁，共47頁，2023年，2月20日，星期六設(shè)tij─第i大學(xué)生參加第j階段面試所需時間,i=1,…,4,j=1,2,3設(shè)yik─各階段面試時第k大學(xué)生是否排在第i之前,即設(shè)xij─第i大學(xué)生參加第j階段面試的開始時間(初時刻為0)請用lingo的循環(huán)語句編程.教材P134CH4─題11課上練習(xí)第42頁，共47頁，2023年，2月20日，星期六model:

SETS:

student/s1..s4/;phase/p1..p3/;!4名student,3階段考核;TEST(student,phase):x,t;sole(student,student):y;ENDSETSMin=mm;@for(student(i):(x(i,3)+t(i,3))<=mm);!第i人被測試后不超過總用時;!第i