数学建模上机实践

第一页，共四十七页，2022年，8月28日上机实践一具体内容◆运输问题(P11)◆选址问题(P13)◆最短路问题(P25)◆钢管运输问题(P27,CUMCM-2000B)◆课上练习─聘用方案(P31)◆

CH4习题(P130第2题─LP)(P40)◆

CH4习题(P134第11题─NLP)(P42)◆

课后问题(P45-47)、。。。第二页，共四十七页，2022年，8月28日优化模型实际问题中的优化模型x~决策变量f(x)~目标函数gi(x)0~约束条件数学规划线性规划(LP)二次规划(QP)非线性规划(NLP)纯整数规划(PIP)混合整数规划(MIP)整数规划(IP)0-1整数规划一般整数规划连续规划第三页，共四十七页，2022年，8月28日建模时需要注意的几个基本问题

1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y<5改为x<5y,或x-5y<0）4、合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当(如小于103)第四页，共四十七页，2022年，8月28日使用LINDO的一些注意事项“>”（或“<”）号与“>=”（或“<=”）功能相同变量与系数间可有空格(甚至回车),但无运算符变量名以字母开头，不能超过8个字符变量名不区分大小写（包括LINDO中的关键字）目标函数所在行是第一行，第二行起为约束条件行号(行名)自动产生或人为定义。行名以“）”结束行中注有“!”符号的后面部分为注释。如:

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

TITLEThisModelisonlyanExample变量不能出现在一个约束条件的右端第五页，共四十七页，2022年，8月28日表达式中不接受括号“()”和逗号“,”等任何符号,例:400(X1+X2)需写为400X1+400X2表达式应化简,如2X1+3X2-4X1应写成-2X1+3X2缺省假定所有变量非负；可在模型的“END”语句后用“FREEname”可将变量name的非负假定取消可在“END”后用“SUB”或“SLB”设定变量上下界例如：“subx110”的作用等价于“x1<=10”,

但用“SUB”和“SLB”表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析14.“END”后对0-1变量说明：INTn

或INTname15.“END”后对整数变量说明：GINn

或GINname使用LINDO的一些注意事项第六页，共四十七页，2022年，8月28日当前状态：已达最优解迭代次数：18次约束不满足的“量”(不是“约束个数”)：0当前的目标值：94最好的整数解：94整数规划的界：93.5分枝数：1所用时间：0.00秒（太快了，还不到0.005秒）刷新本界面的间隔:1(秒)状态窗口（LINDOSolverStatus）第七页，共四十七页，2022年，8月28日NonzeroLimit：非零系数的个数上限；IterationLimit：最大迭代步数；InitialContraintTol：约束的初始误差上限；FinalContraintTol：约束的最后误差上限；EnteringVarTol：进基变量的REDUCEDCOST的误差限；PivotSizeTol：旋转元的误差限选项设置

Preprocess：预处理(生成割平面)；

PreferredBranch：优先的分枝方式：“Default”（缺省方式）、“Up”（向上取整优先）、“Down”（向下取整优先）；

IPOptimalityTol：IP最优值允许的误差上限（一个百分数，如5%即0.05）；

IPObjectiveHurdle：IP目标函数的篱笆值，即只寻找比这个值更优最优解（如当知道当前模型的某个整数可行解时，就可以设置这个值）；

IPVarFixingTol：固定一个整数变量取值所依据的一个上限（如果一个整数变量的判别数（REDUCEDCOST）的值很大，超过该上限，则以后求解中把该整数变量固定下来）。第八页，共四十七页，2022年，8月28日Report/Statistics第一行：模型有5行（约束4行），4个变量，两个整数变量（没有0-1变量），从第4行开始是二次规划的实际约束。第二行：非零系数19个，约束中非零系数12个(其中6个为1或-1)，模型密度为0.760(密度=非零系数/[行数＊(变量数＋１)])。第三行的意思：按绝对值看，系数最小、最大分别为0.3和277。第四行的意思：模型目标为极小化；小于等于、等于、大于等于约束分别有２、０、２个；广义上界约束（GUBS）不超过１个；变量上界约束（VUBS）不少于０个。所谓GUBS，是指一组不含有相同变量的约束；所谓VUBS，是指一个蕴涵变量上界的约束，如从约束X1+X2-X3=0可以看出，若X3=0，则X1=0，X2=0（因为有非负限制），因此X1+X2-X3=0是一个VUBS约束。第五行的意思：只含１个变量的约束个数=０个；冗余的列数=０个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 第九页，共四十七页，2022年，8月28日目标与约束段集合段（SETSENDSETS）数据段（DATAENDDATA）初始段（INITENDINIT）LINGO软件简介LINGO模型的构成：4个段LINGO模型的优点包含了LINDO的全部功能提供了灵活的编程语言（矩阵生成器）LINGO教程可以帮助你了解及指导如何掌握这一软件,如查找@free,@bin,就可获知相关信息.第十页，共四十七页，2022年，8月28日例1运输问题

使用LINGO软件计算6个发点8个收点的最小费用的。产销单位运价如下表。

销地产地

B1B2B3B4B5B6B7B8产量A16267425960A24953858255A35219743351A47673927143A52395726541A65522814352销量3537223241324338

编写程序如下,并在LINGO软件下实现!单位运价第十一页，共四十七页，2022年，8月28日model:!6发点8收点运输问题;sets:warehouses/wh1..wh6/:capacity;vendors/v1..v8/:demand;links(warehouses,vendors):cost,volume;!待求的决策变量是volume;endsets!目标函数;

min=@sum(links:cost*volume);!需求约束;

@for(vendors(J):

@sum(warehouses(I):volume(I,J))=demand(J));!产量约束;

@for(warehouses(I):

@sum(vendors(J):volume(I,J))<=capacity(I));!这里是数据;data:capacity=605551434152;demand=3537223241324338;cost=626742594953858252197433767392712395726555228143;enddataetza-8AMg-3bHp-?f7v-?%Q4-4gAt-Xkyj-Y#5D-Zk43-aGe#-D?z2当输入LINGO8.0的注册码后,所有变量个数、约束条件个数就不受限制了!操作方法是将下面的SN码复制后在LINGO8.0下的“Lingopassword”命令窗口中粘贴即可!LINGO11不要注册码！第十二页，共四十七页，2022年，8月28日例2:选址问题某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di

(单位：吨）假设：料场和工地之间有直线道路用LINGO实现第十三页，共四十七页，2022年，8月28日总吨公里数为136.2275线性规划LP模型决策变量：cij(料场j到工地i的运量）~12维A,B两料场分别向各工地运送水泥的每天供应量第十四页，共四十七页，2022年，8月28日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（目标）;[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（供应约束）;@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第十五页，共四十七页，2022年，8月28日选址问题2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij，在其它条件不变下使总吨公里数最小。决策变量：cij，(xj,yj)~16维非线性规划模型第十六页，共四十七页，2022年，8月28日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（目标）;[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（供应约束）;@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第十七页，共四十七页，2022年，8月28日LINGO模型的构成：“段”集合段（SETS/ENDSETS）数据段（DATA/ENDDATA）初始段（INIT/ENDINIT）目标函数与约束段新料厂约在(5.7,4.9),(7.3,7.8);局部最优解:89.9(吨公里)第十八页，共四十七页，2022年，8月28日集合的类型集合派生集合基本集合稀疏集合稠密集合元素列表法元素过滤法直接列举法隐式列举法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第十九页，共四十七页，2022年，8月28日集合元素的隐式列举类型隐式列举格式示例示例集合的元素数字型1..n1..51,2,3,4,5字符-数字型stringM..stringNCar101..car208Car101,car102,…,car208星期型dayM..dayNMON..FRIMON,TUE,WED,THU,FRI月份型monthM..monthNOCT..JANOCT,NOV,DEC,JAN年份-月份型monthYearM..monthYearNOCT2001..JAN2002OCT2001,NOV2001,DEC2001,JAN2002第二十页，共四十七页，2022年，8月28日运算符的优先级优先级运算符最高#NOT#—（负号）^*/+—（减法）#EQ##NE##GT##GE##LT##LE##AND##OR#最低<(=)=>(=)三类运算符：算术运算符逻辑运算符关系运算符第二十一页，共四十七页，2022年，8月28日集合循环函数四个集合循环函数：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:第二十二页，共四十七页，2022年，8月28日状态窗口SolverType:B-and-BGlobalMultistartModelClass:LP，QP，ILP，IQP，PILP,PIQP，NLP，INLP，PINLPState:GlobalOptimumLocalOptimumFeasibleInfeasibleUnboundedInterruptedUndetermined第二十三页，共四十七页，2022年，8月28日7个选项卡(可设置80-90个控制参数)第二十四页，共四十七页，2022年，8月28日例3:最短路问题

(ShortestPathProblem-SPP)

求各点到

T

的最短路56774968658336C1B1C2B2A1A2A3TS6第二十五页，共四十七页，2022年，8月28日model:SETS:

!CITIES表示由1~9组成的集合，是一个基本集合;CITIES/1..9/:L; !属性L(i)表示城市i到城市1的最优行驶路线的路长;ROADS(CITIES,CITIES)/!ROADS表示网络中的弧,是由CITIES派生的集合;9,69,79,8 !由于并非所有城市间都有道路直接连接，所以将弧具体列出;6,46,57,47,58,48,54,24,35,25,32,13,1/:D; !属性D(i,j)是城市i到j的直接距离（已知）;ENDSETSDATA:D= !D赋值的顺序对应于ROADS中的弧的顺序;633658674678956;ENDDATAL(1)=0; !边界条件;@FOR(CITIES(i)|i#GT#1: !集合循环语句,#GT#表示逻辑关系"大于";L(i)=@MIN(ROADS(i,j):D(i,j)+L(j)) !这就是动态规划基本方程;);end第二十六页，共四十七页，2022年，8月28日A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7铁路运价表里程≤300301～350351～400401～450451～500…运价2023262932…例4钢管运输问题（CUMCM-2000B)第二十七页，共四十七页，2022年，8月28日xij是从钢厂i运到节点j的钢管量;fi表示钢厂i是否使用；yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量.

第二十八页，共四十七页，2022年，8月28日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问题第二十九页，共四十七页，2022年，8月28日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第三十页，共四十七页，2022年，8月28日某服务部门一周中每天需要不同数目的雇员:周一到周四每天至少50人,周五和周日每天至少80人,周六至少90人.现规定应聘者需连续工作5日,试确定聘用方案,即周一到周日每天聘多少人,使在满足需求条件下聘用总人数最少.上面指的是全时雇员(一天工作8小时)，如果可以用两个临时聘用的半时雇员(一天工作4小时,不需要连续工作)代替一个全时雇员，但规定半时雇员的工作量不得超过总工作量的四分之一.又设全时雇员和半时雇员每小时的酬金分别为5元和3元，试确定聘用方案,使在满足需要的条件下所付酬金总额最小．课上练习1.聘用方案第三十一页，共四十七页，2022年，8月28日⑴设所聘雇员皆为全时雇员记周一到周日每天聘用人数分别为则目标函数(聘用总人数)为:

解

典型的线性(整数)规划问题

第三十二页，共四十七页，2022年，8月28日

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运行后,需对结果进行分析第三十三页，共四十七页，2022年，8月28日model:sets:

days/1..7/:p,x;!x决策变量,P每周每一天需要的服务员数量;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));!用来描绘必须连续工作5天;

end第三十四页，共四十七页，2022年，8月28日⑵考虑聘用半时雇员,记周一到周日每天聘用半时雇员人数分别为则目标函数(酬金总额)为:条件B条件A第三十五页，共四十七页，2022年，8月28日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第三十六页，共四十七页，2022年，8月28日model:sets:

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

!x,y决策变量,P每周每天需要的服务员数量;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:!描绘必须连续工作5天;x(@wrap(i+j+2,7)))+0.5*y(j)=p(j));@for(days(j):@gin(x);@gin(y));end第三十七页，共四十七页，2022年，8月28日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

代表什么?加入此语句死循环条件B第三十八页，共四十七页，2022年，8月28日model:sets:

days/1..7/:p,x,y;!x,y决策变量,P每周每天需服务生数;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));

!描绘必须连续工作5天;@sum(days(i):3*y(i))-@sum(days(i):2*x(i))<=0;@for(days(i):@gin(x(i));@gin(y(i)));end第三十九页，共四十七页，2022年，8月28日设Pi表示第i个“大学生区“的大学生人数，i=1,…,7表示第i区与第j区相邻(i<j),且共有一售书点否则x12,x13,x23,x24,x25,x34,x45,x46,x47,x56,x67.1234567教材P130第四章习题─题2课上练习第四十页，共四十七页，2022年，8月28日

Max63x12+76x13+71x23+50x24+85x25+63x34+77x45+39x46+92x47+74x56+89x67用lindo求解得到：最优解为x25=x47=1(其它取0值)，最优值为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下求解第四十一页，共四十七页，2022年，8月28日设tij─第i大学生参加第j阶段面试所需时间,i=1,…,4,j=1,2,3设yik─各阶段面试时第k大学生是否排在第i之前,即设xij─第i大学生参加第j阶段面试的开始时间(初时刻为0)请用lingo的循环语句编程.教材P134CH4─题11课上练习第四十二页，共四十七页，2022年，8月28日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个