【精品】lindo_lingo与优化模型（可编辑.ppt

《【精品】lindo_lingo与优化模型（可编辑.ppt》由会员分享，可在线阅读，更多相关《【精品】lindo_lingo与优化模型（可编辑.ppt（89页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、LINDO_LINGO与优化模型例例1加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶时间时间480小时小时 至多加工至多加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：1桶牛奶 3公斤A1 1

2、2小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天模型求解模型求解 max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1”（或（或“=”（或（或“=”）功能相同）功能相同2.变量与系数间可有空格变量与系数间

3、可有空格(甚至回车甚至回车),但无运算符但无运算符3.变量名以字母开头，不能超过变量名以字母开头，不能超过8个字符个字符4.变量名不区分大小写（包括变量名不区分大小写（包括LINDO中的关键字）中的关键字）5.目标函数所在行是第一行，第二行起为约束条件目标函数所在行是第一行，第二行起为约束条件6.行号行号(行名行名)自动产生或人为定义。行名以自动产生或人为定义。行名以“）”结束结束7.行中注有行中注有“!”符号的后面部分为注释。如符号的后面部分为注释。如:8.!ItsComment.8.在模型的任何地方都可以用在模型的任何地方都可以用“TITLE”对模型命名对模型命名（最多（最多72个字符），

4、如：个字符），如：TITLEThisModelisonlyanExample9.变量不能出现在一个约束条件的右端变量不能出现在一个约束条件的右端10.表达式中不接受括号表达式中不接受括号“()”和逗号和逗号“,”等任何符号等任何符号,例例:400(X1+X2)需写为需写为400X1+400X211.表达式应化简，如表达式应化简，如2X1+3X2-4X1应写成应写成-2X1+3X212.缺省假定所有变量非负；可在模型的缺省假定所有变量非负；可在模型的“END”语句语句后用后用“FREEname”将变量将变量name的非负假定取消的非负假定取消13.可在可在“END”后用后用“SUB”或或“SLB

5、”设定变量上下界设定变量上下界14.例如：例如：“subx110”的作用等价于的作用等价于“x1=10”但用但用“SUB”和和“SLB”表示的上下界约束不计入模型表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析。的约束，也不能给出其松紧判断和敏感性分析。14.“END”后对后对0-1变量说明：变量说明：INTn或或INTname15.“END”后对整数变量说明：后对整数变量说明：GINn或或GINname使用使用LINDOLINDO的一些注意事项的一些注意事项LINGOLINGO求解举例求解举例 例：选址问题例：选址问题某公司有某公司有6个建筑工地，位置坐标为个建筑工地，位置

6、坐标为(ai,bi)(单位：公里单位：公里),水泥日用量水泥日用量di(单位：吨）单位：吨）假设：假设：料场料场和工地之间和工地之间有直线道路有直线道路用例中数据计算，最优解为总吨公里数为总吨公里数为总吨公里数为总吨公里数为136.2136.2线性规划模型线性规划模型决策变量：决策变量：ci j(料场料场j到到工地工地i的的运量）运量）12维维选址问题：选址问题：NLPNLP2）改建两个新料场，需要确定新料场位置）改建两个新料场，需要确定新料场位置(xj,yj)和和运量运量cij，在其它条件不变下使总吨公里数最小。，在其它条件不变下使总吨公里数最小。决策变量：决策变量：ci j，(xj,yj)

7、16维维非线性规划模型非线性规划模型LINGO模型的构成：模型的构成：4个段个段集合段（集合段（SETSENDSETS）数据段（数据段（DATAENDDATA）初始段（初始段（INITENDINIT）目标与目标与约束段约束段局部最优：局部最优：89.8835(吨公里吨公里)LP：移到数据段：移到数据段边界ailco公司需要决定下四个季度的帆船生产公司需要决定下四个季度的帆船生产量下四个季度的帆船需求量分别为量下四个季度的帆船需求量分别为40、60、75、25条，这些需求必须满足。每个条，这些需求必须满足。每个季度正常的生产能力是季度正常的生产能力是40条帆船，每条帆条帆船，每条帆船的生产费用为

8、船的生产费用为400美元。如果加班生产，美元。如果加班生产，每条船的生产费用为每条船的生产费用为450美元。每个季度末，美元。每个季度末，每条船的库存费用为每条船的库存费用为20美元。假定生产提美元。假定生产提前期为前期为0，初始库存为，初始库存为10条船，如何安排生条船，如何安排生产可使总费用最小？产可使总费用最小？ailco公司的生产计划公司的生产计划用c(i)（已知）,x(i),y(i),w(i)分别表示第i季度的需求量、正常生产量、加班生产量、库存量，数学模型如下：mini=1,2,3,4400*x(i)+450*y(i)+20*w(i)STx(i)40,i=1,2,3,4w(i)=w

9、(i-1)+x(i)+y(i)-c(i),i=2,3,4W(1)=10+x(1)+y(1)-c(1)其中c(i)=40,60,75,25ailco公司生产计划的数学模型公司生产计划的数学模型Sailco公司生产计划的LINGO程序model:sets:quarters/1,2,3,4/:c,x,y,w;endsetsdata:c=40,60,75,25;enddatamin=sum(quarters:400*x+450*y+20*w);for(quarters(i):x(i)40);for(quarters(i)|i#GT#1:w(i)=w(i-1)+x(i)+y(i)-c(i););w(1)

10、=10+x(1)+y(1)-c(1);end某班某班8名同学准备分成名同学准备分成4个调查队个调查队(每队两人每队两人)前前4个地区进行个地区进行社会调查社会调查.假设这假设这8名同学两两之间给队的效率如下名同学两两之间给队的效率如下:学生学生S1S2S3S4S5S6S7S8S19342156S2173521S344292S41552S5876S623S74S8如何组队可使总效率最高？如何组队可使总效率最高？匹配问题匹配问题用Match(Si,Sj)=1表示同学Si和Sj组成一队(ij),Match(Si,Sj)=0表示同学Si和Sj不组队(ij)用enefit(Si,Sj)表示同学Si和Sj

11、组成一队时的效率(已知)(ij)minijenefit(Si,Sj)*Match(Si,Sj)STj=i或k=i Match(Sj,Sk)=1,i=1,2,3,4,8,其中Match(Sj,Sk)0,1匹配问题的数学模型匹配问题的数学模型匹配问题的匹配问题的LINGO程序model:sets:students/s1.s8/;Pairs(students,students)|&2#GT#&1:BENEFIT,MATCHendsetsdata:BENEFIT=9 3 4 2 1 5 6 1 7 3 5 2 1 4 4 2 9 2 1 5 5 2 8 7 6 2 3 4;enddataobjecti

12、ve 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);end集合的类型集合的类型集合集合派生集合派生集合基本集合基本集合稀疏集合稀疏集合稠密集合稠密集合元素列表法元素列表法元素过滤法元素过滤法直接列举法直接列举法隐式列举法隐式列举法setname/member_list/:attribute_list;setname(parent_set_list)/

13、member_list/:attribute_list;SETS:CITIES/A1,A2,A3,B1,B2/;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集合元素的集合元素的隐式列举隐式列举类类型型隐隐式列式列举举格式格式示例示例示例集合的元素示例集合的元素数字型数字型 1.n1.51,2,3,4,5字符字符-数字型数字型stringM.stringNCar101.car208

14、 Car101,car102,car208星期型星期型 dayM.dayNMON.FRIMON,TUE,WED,THU,FRI月份型月份型 monthM.monthN OCT.JANOCT,NOV,DEC,JAN年份年份-月份型月份型monthYearM.monthYearNOCT2001.JAN2002OCT2001,NOV2001,DEC2001,JAN2002运算符的优先级运算符的优先级 优优先先级级运算符运算符最高最高#NOT#（负负号）号）*/+（减法）（减法）#EQ#NE#GT#GE#LT#LE#AND#OR#最低最低(=)三类运算符：三类运算符：算术运算符算术运算符逻辑运算符逻辑

15、运算符关系运算符关系运算符集合循环函数集合循环函数四个集合循环函数：四个集合循环函数：FOR、SUM、MAX、MINfunction(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):BENE

16、FIT(I,J);MINB=MIN(PAIRS(I,J):BENEFIT(I,J);Example:状态窗口状态窗口Solver Type:B-and-BGlobal MultistartModel Class:LP，QP，ILP，IQP，PILP,PIQP，NLP，INLP，PINLP State:Global OptimumLocal OptimumFeasibleInfeasibleUnboundedInterruptedUndetermined7 7个选项卡个选项卡(可设置可设置80-9080-90个控制参数个控制参数)ABS(X)返回的绝对值COS(X)返回的余弦值SIN(X)返回的

17、正弦值TAN(X)返回的正切值EXP(X)返回e的值FLOOR(X)向靠近的方向取整LOG(X)自然对数值MOD(X，Y)返回X除以Y的余数POW(X,Y)返回XY的值SIGN(X)符号函数(X=0为+1)SMAX(list)返回一列数list的最大值SMIN(list)返回一列数list的最小值SQR(X)返回X*X的值SQRT(X)返回X的正平方根的值基本的数学函数基本的数学函数FOR(集合元素的循环函数)SUM(集合属性的求和函数)MAX(集合属性的最大值函数)MIN(集合属性的最小值函数)PROD(集合属性的乘积函数)IF(logical_condition,true_result,f

18、alse_result)例IF(X#LT#100,20,15)当X100时为20,否则为15集合循环函数集合循环函数变量定界函数变量定界函数BND(L,X,U)限制L=X NEED(I);CON2 SHIP(I)NEED(I);CON2 SHIP(I)=50;x1*r21+x2*r22+x3*r23=10;x1*r31+x2*r32+x3*r33=20;x1*r41+x2*r42+x3*r43=15;4*r11+5*r21+6*r31+8*r41=19;4*r12+5*r22+6*r32+8*r42=19;4*r13+5*r23+6*r33+8*r43=16;4*r12+5*r22+6*r32

19、+8*r42=16;4*r13+5*r23+6*r33+8*r43=16;!x1+x2+x3=26;!x1+x2+x3=x2;!x2=x3;gin(x1);gin(x2);gin(x3);gin(r11);gin(r12);gin(r13);gin(r21);gin(r22);gin(r23);gin(r31);gin(r32);gin(r33);gin(r41);gin(r42);gin(r43);endmodel:SETS:NEEDS/1.4/:LENGTH,NUM;!定义基本集合NEEDS及其属性LENGTH,NUM;CUTS/1.3/:X;!定义基本集合CUTS及其属性X;PATTER

20、NS(NEEDS,CUTS):R;!定义派生集合PATTERNS（是一个稠密集合）及其属性R;ENDSETSDATA:LENGTH=4 5 6 8;NUM=50 10 20 15;CAPACITY=19;ENDDATAmin=SUM(CUTS(I):X(I);!目标函数;FOR(NEEDS(I):SUM(CUTS(J):X(J)*R(I,J)NUM(I);!满足需求的约束;FOR(CUTS(J):SUM(NEEDS(I):LENGTH(I)*R(I,J)CAPACITY -MIN(NEEDS(I):LENGTH(I);!合理切割模式的约束;SUM(CUTS(I):X(I)26;SUM(CUTS

21、(I):X(I)X(I+1);!人为增加的约束;FOR(CUTS(J):GIN(X(J);FOR(PATTERNS(I,J):GIN(R(I,J);endLINGOLINGO求解整数非线性规划模型求解整数非线性规划模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.00000

22、00.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000模式模式1：每根原料钢管切割成：每根原料钢管切割成3根根4米和米和1根根6米钢管，共米钢管，共10根；根；模式模式2：每根原料钢管切割成：每根原料钢管切割成2根根4米、米、1根根5米和米和1根根6米钢管，米钢管，共共10根；根；模式模式3：

23、每根原料钢管切割成：每根原料钢管切割成2根根8米钢管，共米钢管，共8根。根。原料钢管总根数为原料钢管总根数为28根。根。演示演示cut02a.lg4；cut02b.lg4；露天矿里铲位已分成矿石和岩石露天矿里铲位已分成矿石和岩石:平均铁含量不低于平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间每个铲位至多安置一台电铲，电铲平均装车时间5分钟分钟卡车在等待时所耗费的能量也是相当可观的，原则上在卡车在

24、等待时所耗费的能量也是相当可观的，原则上在安排时安排时不应发生卡车等待不应发生卡车等待的情况。的情况。露天矿生产的车辆安排露天矿生产的车辆安排(CUMCM-2003B)矿石卸点需要的铁含量要求都为矿石卸点需要的铁含量要求都为29.5%1%(品位限制）品位限制），搭配量在一个班次（，搭配量在一个班次（8小时）内满足品位限制即可。小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为卸点在一个班次内不变。卡车载重量为154吨，平均时吨，平均时速速28km,平均卸车时间为平均卸车时间为3分钟。分钟。问题：出动几台电铲，分别在哪些铲位上；出动几辆问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车

25、，分别在哪些路线上各运输多少次卡车，分别在哪些路线上各运输多少次?平面示意图问题数据问题数据 距离铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏5.265.194.214.002.952.742.461.900.641.27倒装1.900.991.901.131.272.251.482.043.093.51岩场5.895.615.614.563.513.652.462.461.060.57岩石漏0.641.761.271.832.742.604.213.725.056.10倒装4.423.863.723.162.252.810.781.621.270.50铲位1铲位2铲位

26、3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石量095105100105110125105130135125岩石量125110135105115135105115135125铁含量30%28%29%32%31%33%32%31%33%31%问题分析问题分析 与典型的运输问题明显有以下不同：与典型的运输问题明显有以下不同：1.这是运输矿石与岩石两种物资的问题；这是运输矿石与岩石两种物资的问题；2.属于产量大于销量的不平衡运输问题；属于产量大于销量的不平衡运输问题；3.为了完成品位约束，矿石要搭配运输；为了完成品位约束，矿石要搭配运输；4.产地、销地均有单位时间的流量限制；产地、销地均有单位时

27、间的流量限制；5.运输车辆只有一种，每次满载运输，运输车辆只有一种，每次满载运输，154吨吨/车次；车次；6.铲位数多于铲车数意味着要最优的选择不多于铲位数多于铲车数意味着要最优的选择不多于7个个产地作为最后结果中的产地；产地作为最后结果中的产地；7.最后求出各条路线上的派出车辆数及安排。最后求出各条路线上的派出车辆数及安排。近似处理：近似处理：先求出产位、卸点每条线路上的运输量先求出产位、卸点每条线路上的运输量(MIP模型模型)然后求出各条路线上的派出车辆数及安排然后求出各条路线上的派出车辆数及安排模型假设模型假设卡车在一个班次中不应发生等待或熄火后再启动卡车在一个班次中不应发生等待或熄火后

28、再启动的情况；的情况；在铲位或卸点处由两条路线以上造成的冲突问题在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；为不冲突。我们不排时地进行讨论；空载与重载的速度都是空载与重载的速度都是28km/h，耗油相差很大；，耗油相差很大；卡车可提前退出系统，等等。卡车可提前退出系统，等等。如理解为严格不等待，难以用数学规划模型来解如理解为严格不等待，难以用数学规划模型来解个别参数队找到了可行解个别参数队找到了可行解（略）（略）符号符号xij：从：从i铲位到铲位到j号卸点的石料运量号卸点的石料运量

29、（车）（车）单位：单位：吨；吨；cij：从：从i号铲位到号铲位到j号卸点的距离号卸点的距离公里；公里；Tij:从从i号铲位到号号铲位到号j卸点路线上运行一个周期平均时间卸点路线上运行一个周期平均时间分；分；Aij：从号铲位到号卸点最多能同时运行的卡车数：从号铲位到号卸点最多能同时运行的卡车数辆；辆；Bij：从号铲位到号卸点路线上一辆车最多可运行的次数：从号铲位到号卸点路线上一辆车最多可运行的次数次；次；pi：i号铲位的矿石铁含量号铲位的矿石铁含量p=(30,28,29,32,31,33,32,31,33,31)%qj:j号卸点任务需求，号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.

30、3)*10000吨吨cki：i号铲位的铁矿石储量号铲位的铁矿石储量万吨万吨cyi：i号铲位的岩石储量号铲位的岩石储量万吨万吨fi:描述第描述第i号铲位是否使用的号铲位是否使用的0-1变量，取变量，取1为使用；为使用；0为关闭。为关闭。(近似近似)优化模型（1）道路能力道路能力(卡车数卡车数)约束约束（2）电铲能力约束（3）卸点能力约束（4）铲位储量约束（5）产量任务约束（6）铁含量约束（7）电铲数量约束（8）整数约束.xij为非负整数fi 为0-1整数model:title CUMCM-2003B-01;sets:cai/1.10/:crate,cnum,cy,ck,flag;xie/1.5/

31、:xsubject,xnum;link(xie,cai):distance,lsubject,number,che,b;endsetsdata:crate=30 28 29 32 31 33 32 31 33 31;xsubject=1.2 1.3 1.3 1.9 1.3;distance=5.26 5.19 4.21 4.00 2.95 2.74 2.46 1.90 0.64 1.27 1.90 0.99 1.90 1.13 1.27 2.25 1.48 2.04 3.09 3.51 5.89 5.61 5.61 4.56 3.51 3.65 2.46 2.46 1.06 0.57 0.64

32、 1.76 1.27 1.83 2.74 2.60 4.21 3.72 5.05 6.10 4.42 3.86 3.72 3.16 2.25 2.81 0.78 1.62 1.27 0.50;cy=1.25 1.10 1.35 1.05 1.15 1.35 1.05 1.15 1.35 1.25;ck=0.95 1.05 1.00 1.05 1.10 1.25 1.05 1.30 1.35 1.25;enddata!目标函数;min=sum(cai(i):sum(xie(j):number(j,i)*154*distance(j,i);!max=sum(link(i,j):number(i,j

33、);!max=xnum(3)+xnum(4)+xnum(1)+xnum(2)+xnum(5);!min=sum(cai(i):!sum(xie(j):!number(j,i)*154*distance(j,i);!xnum(1)+xnum(2)+xnum(5)=340;!xnum(1)+xnum(2)+xnum(5)=341;!xnum(3)=160;!xnum(4)=160;!卡车每一条路线上最多可以运行的次数;for(link(i,j):b(i,j)=floor(8*60-(floor(distance(i,j)/28*60*2+3+5)/5)-1)*5)/(distance(i,j)/2

34、8*60*2+3+5);!b(i,j)=floor(8*60/(distance(i,j)/28*60*2+3+5);!t(i,j)=floor(distance(i,j)/28*60*2+3+5)/5);!b(i,j)=floor(8*60-(floor(distance(i,j)/28*60*2+3+5)/5)*5)/(distance(i,j)/28*60*2+3+5);!每一条路线上的最大总车次的计算;for(link(i,j):lsubject(i,j)=(floor(distance(i,j)/28*60*2+3+5)/5)*b(i,j);!计算各个铲位的总产量;for(cai(j

35、):cnum(j)=sum(xie(i):number(i,j);!计算各个卸点的总产量;for(xie(i):xnum(i)=sum(cai(j):number(i,j);!道路能力约束;for(link(i,j):number(i,j)=lsubject(i,j);!电铲能力约束;for(cai(j):cnum(j)=flag(j)*8*60/5);!电铲数量约束-;sum(cai(j):flag(j)=7;!卸点能力约束;for(xie(i):xnum(i)=8*20);!铲位产量约束;for(cai(i):number(1,i)+number(2,i)+number(5,i)=ck(i

36、)*10000/154);for(cai(i):number(3,i)+number(4,i)=xsubject(i)*10000/154);!铁含量约束;sum(cai(j):number(1,j)*(crate(j)-30.5)=0;sum(cai(j):number(2,j)*(crate(j)-30.5)=0;sum(cai(j):number(5,j)*(crate(j)-30.5)=0;sum(cai(j):number(2,j)*(crate(j)-28.5)=0;sum(cai(j):number(5,j)*(crate(j)-28.5)=0;!关于车辆的具体分配;for(li

37、nk(i,j):che(i,j)=number(i,j)/b(i,j);!各个路线所需卡车数简单加和;hehe=sum(link(i,j):che(i,j);!整数约束;for(link(i,j):gin(number(i,j);for(cai(j):bin(flag(j);!车辆能力约束;hehe=20;ccnum=sum(cai(j):cnum(j);end计算结果（计算结果（LINGOLINGO软件）软件）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿漏131354541111倒42424343岩场70701515岩漏81814343倒13132 27070铲位1铲位2

38、铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏0.8671.8620.314倒场1.0771.162岩场1.8920.326岩石漏1.8411.229倒场0.6840.11.489cumcm2003b1.lg4计算结果（派车）计算结果（派车）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏1(29)倒场1(39)1(37)岩场1(37)岩石漏1(44)1(35)倒场1(47)结论：结论：铲位铲位1、2、3、4、8、9、10处各放置一台电铲。处各放置一台电铲。一共使用了一共使用了13辆卡车；总运量为辆卡车；总运量为85628.62吨公里；吨公里；岩石产量为岩石产量为

39、32186吨；矿石产量为吨；矿石产量为38192吨。吨。此外：此外：6辆联合派车（方案略）辆联合派车（方案略）最大化产量最大化产量结论：结论：（略）（略）目标函数变化目标函数变化此外：车辆数量（此外：车辆数量（20辆）限制（其实上面的模型也辆）限制（其实上面的模型也应该有）应该有）四、实例二四、实例二:钢管订购和运输问题的钢管订购和运输问题的数学模型数学模型(2000B)由钢管厂订购钢管，经铁由钢管厂订购钢管，经铁路、公路运输，铺设一条路、公路运输，铺设一条钢管管道钢管管道A132580101031201242701088107062703020203045010430175060619420

40、5201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1S7 钢管厂火车站450 里程（km）（沿管道建有公路）钢厂的产量和销价（1单位钢管=1km管道钢管）钢厂产量的下限：500单位钢管1单位钢管的铁路运价1000km以上每增加1至100km运价增加5万元1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）（1）制定钢管的订购和运输计划，使总费用最小）制定钢管的

41、订购和运输计划，使总费用最小.（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？变化影响最大；哪个钢厂钢管产量上限的变化影响最大？A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4

42、S5S6S7A16130A17A18A19A20A21190260100（3）讨论管道为树形图的情形）讨论管道为树形图的情形问题问题1的基本模型和解法的基本模型和解法总费用最小的优化问题总费用：订购，运输（由各厂Si经铁路、公路至各点Aj,i=1,7;j=1,15），铺设管道Aj Aj+1（j=1,14)由Si至Aj的最小购运费用路线及最小费用cij 由Si至Aj的最优运量xij由Aj向Aj Aj-1段铺设的长度zj及向Aj Aj+1段铺设的长度yj最优购运计划最优购运计划约束条件约束条件钢厂产量约束：上限和下限（如果生产的话）运量约束：xij对i求和等于zj 加yj；yj与 zj+1之和等于

43、Aj Aj+1段的长度lj基本模型基本模型由Aj向Aj Aj-1段铺设的运量为 1+zj=zj(zj+1)/2由Aj向Aj Aj+1段铺设的运量为 1+yj=yj(yj+1)/2二次规划求解步骤求解步骤1）求由Si至Aj的最小购运费用路线及最小费用cij 难点：公路运费是里程的线性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。A17010881070627030202030300220210420500170690462160320160110290A10A11A12A13A14A15S4S5S6S7需要对铁路网和公路网

44、进行预处理，才能使用常用需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。算法，得到最小购运费用路线。如S7至A10的最小费用路线先铁路1130km，再公路70km,运费为77（万元）先公路（经A15）40km,再铁路1100km，再公路70km,运费为76（万元）实际上只有S4和S7需要分解成子问题求解3)每个子问题是标准的二次规划，决策变量为xij,yj,zj,不超过135个。问题问题1的其它模型和解法的其它模型和解法1）运输问题的0-1规划模型将全长5171km的管道按公里分段，共5171个需求点，钢厂为7个供应点，构成如下的运输问题cij为从供应点i到需求点j的最

45、小购运费xij=1表示从点i到点j购运1单位钢管求解时要针对规模问题寻求改进算法2）最小费用网络流模型）最小费用网络流模型SourceS1S2S7A1A2A15P11P1l1P21Sink(si,pi)(+,cij)(1,1),(1,li)(1,0)SourceS1S2S7A1A2A15P1P2Sink(si,pi)(+,cij)(li,f(f+1)/2)(li,0)线性费用网络线性费用网络(只有产量上限只有产量上限)非线性费用网络非线性费用网络(只有产量上限只有产量上限)边的标记（流量上限，单位费用）用标准算法(如最小费用路算法)求解无单位费用概念(f(f+1)/2),需修改最小费用路算法2

46、）最小费用网络流模型）最小费用网络流模型产量有下限ri时的修正SourceSiSi(si-ri,pi)(ri,0)(+,0)得到的结果应加上 才是最小费用S1S2S3S6S5S1S2S2S3S3S5S5S63)最小面积模型A1A2A3A4A5A6A7A8A9A10A11A12A13A14A15cx作图：Si到管道x单位钢管的最小购运费用c由各条Si首尾相连(横坐标)组成的一条折线对应一个购运方案，折线下面的面积对应方案的费用在产量约束下找面积最小的折线论文中发现的主要问题论文中发现的主要问题1）针对题目给的数据用凑的方法算出结果，没有解决这类问题的一般模型2）局部最优，如将管道分为左右两段，分

47、别寻求方案；如将问题分为购运和铺设两部分，分别寻优（会导致每段管道都从两端铺到中点）4）由Si至Aj的最小购运费用路线及最小费用cij 不对5）数字结果相差较大(如最小费用应127.5至128.2亿元)问题问题2：分析对购运计划和总费用影响（哪个钢厂销价：分析对购运计划和总费用影响（哪个钢厂销价的变化影响最大；哪个钢厂产量上限的变化影响最大）的变化影响最大；哪个钢厂产量上限的变化影响最大）规划问题的灵敏度分析规划问题的灵敏度分析问题问题3：管道为树形图：管道为树形图701088107062300220210170690462160320160A10A11A12S4S5S6130A17A18A1

48、9A20190260100(jk)是连接是连接Aj,Ak的边，的边，E是树形图的边集，是树形图的边集，ljk是是(jk)的长度，的长度，yjk是由是由Aj沿沿(jk)铺设的钢管数铺设的钢管数量量返回返回第一页第一页fi表示钢厂表示钢厂i是否使用；是否使用；xij是从钢厂是从钢厂i运到节点运到节点j的钢管量的钢管量yj是从节点是从节点j向左铺设的钢管量；向左铺设的钢管量；zj是向右铺设的钢管量是向右铺设的钢管量 (LINGO求解)钢管运输问题钢管运输问题（CUMCM-CUMCM-2000B)2000B)得到的结果比得到的结果比matlab得到的好得到的好cumcm2000b.lg4 MODEL:

49、TITLE Pipline Transportation;SETS:SUPPLY/S1.S7/:S,P,f;NEED/A1.A15/:b,y,z;LINK(Supply,need):C,X;ENDSETSDATA:S=800 800 1000 2000 2000 2000 3000;P=160 155 155 160 155 150 160;b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,;c=170.7 160.3 140.2 98.6 38.0 20.5 3.1 21.2 64.2 92.0 96.0 106.0 121.

50、2 128.0 142.0215.7 205.3 190.2 171.6 111.0 95.5 86.0 71.2 114.2 142.0 146.0 156.0 171.2 178.0 192.0230.7 220.3 200.2 181.6 121.0 105.5 96.0 86.2 48.2 82.0 86.0 96.0 111.2 118.0 132.0260.7 250.3 235.2 216.6 156.0 140.5 131.0 116.2 84.2 62.0 51.0 61.0 76.2 83.0 97.0255.7 245.3 225.2 206.6 146.0 130.5