LINDO_LINGO与优化模型.ppt

实际问题中的优化模型,x决策变量,f(x)目标函数,gi(x)0约束条件,数学规划,线性规划(LP)二次规划(QP)非线性规划(NLP),纯整数规划(PIP)混合整数规划(MIP),整数规划(IP),0-1整数规划一般整数规划,连续规划,LINDO_LINGO与优化模型,例1加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到30元/公斤，应否改变生产计划？,每天：,x1桶牛奶生产A1,x2桶牛奶生产A2,获利243x1,获利164x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,模型求解,max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2,DORANGE(SENSITIVITY)ANALYSIS?,No,20桶牛奶生产A1,30桶生产A2，利润3360元。,模型求解,reducedcost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题),OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2,也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量,OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000,原料无剩余,时间无剩余,加工能力剩余40,max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,三种资源,“资源”剩余为零的约束为紧约束（有效约束）,结果解释,OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000,结果解释,最优解下“资源”增加1单位时“效益”的增量,原料增1单位,利润增48,时间加1单位,利润增2,能力增减不影响利润,影子价格,35元可买到1桶牛奶，要买吗？,35”（或“=”（或“=”）功能相同变量与系数间可有空格(甚至回车),但无运算符变量名以字母开头，不能超过8个字符变量名不区分大小写（包括LINDO中的关键字）目标函数所在行是第一行，第二行起为约束条件行号(行名)自动产生或人为定义。行名以“）”结束行中注有“!”符号的后面部分为注释。如:!ItsComment.在模型的任何地方都可以用“TITLE”对模型命名（最多72个字符），如：TITLEThisModelisonlyanExample,变量不能出现在一个约束条件的右端表达式中不接受括号“()”和逗号“,”等任何符号,例: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的一些注意事项,LINGO求解举例例：选址问题,某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）,假设：料场和工地之间有直线道路,用例中数据计算，最优解为,总吨公里数为136.2,线性规划模型,决策变量：cij(料场j到工地i的运量）12维,选址问题：NLP,2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij，在其它条件不变下使总吨公里数最小。,决策变量：cij，(xj,yj)16维,非线性规划模型,LINGO模型的构成：4个段,集合段（SETSENDSETS）,数据段（DATAENDDATA）,初始段（INITENDINIT）,目标与约束段,局部最优：89.8835(吨公里),LP：移到数据段,边界,ailco公司需要决定下四个季度的帆船生产量下四个季度的帆船需求量分别为40、60、75、25条，这些需求必须满足。每个季度正常的生产能力是40条帆船，每条帆船的生产费用为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(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,25,ailco公司生产计划的数学模型,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+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组成一队时的效率(已知)(ij)minijenefit(Si,Sj)*Match(Si,Sj)STj=i或k=iMatch(Sj,Sk)=1,i=1,2,3,4,8,其中Match(Sj,Sk)0,1,匹配问题的数学模型,匹配问题的LINGO程序,model:sets:students/s1.s8/;Pairs(students,students)|end,集合的类型,集合派生集合基本集合稀疏集合稠密集合元素列表法元素过滤法直接列举法隐式列举法,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;ENDSETS,SETS:STUDENTS/S1.S8/;PAIRS(STUDENTS,STUDENTS)|ENDSETS,集合元素的隐式列举,运算符的优先级,三类运算符：算术运算符逻辑运算符关系运算符,集合循环函数,四个集合循环函数：FOR、SUM、MAX、MINfunction(setname(set_index_list)|condition:expression_list);,objectiveMAX=SUM(PAIRS(I,J):BENEFIT(I,J)*MATCH(I,J);FOR(STUDENTS(I):constraintsSUM(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:,状态窗口,SolverType:B-and-BGlobalMultistart,ModelClass:LP，QP，ILP，IQP，PILP,PIQP，NLP，INLP，PINLP,State:GlobalOptimumLocalOptimumFeasibleInfeasibleUnboundedInterruptedUndetermined,7个选项卡(可设置80-90个控制参数),ABS(X)返回的绝对值COS(X)返回的余弦值SIN(X)返回的正弦值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,false_result)例IF(X#LT#100,20,15)当X100时为20,否则为15,集合循环函数,变量定界函数,BND(L,X,U)限制L=10;x1*r31+x2*r32+x3*r33=20;x1*r41+x2*r42+x3*r43=15;4*r11+5*r21+6*r31+8*r41=16;4*r12+5*r22+6*r32+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);end,model:SETS:NEEDS/1.4/:LENGTH,NUM;!定义基本集合NEEDS及其属性LENGTH,NUM;CUTS/1.3/:X;!定义基本集合CUTS及其属性X;PATTERNS(NEEDS,CUTS):R;!定义派生集合PATTERNS（是一个稠密集合）及其属性R;ENDSETSDATA:LENGTH=4568;NUM=50102015;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(I):X(I)X(I+1);!人为增加的约束;FOR(CUTS(J):GIN(X(J);FOR(PATTERNS(I,J):GIN(R(I,J);end,LINGO求解整数非线性规划模型,Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.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：每根原料钢管切割成2根8米钢管，共8根。原料钢管总根数为28根。,演示cut02a.lg4；,cut02b.lg4；,露天矿里铲位已分成矿石和岩石:平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟,卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。,露天矿生产的车辆安排(CUMCM-2003B),矿石卸点需要的铁含量要求都为29.5%1%(品位限制），搭配量在一个班次（8小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为154吨，平均时速28km,平均卸车时间为3分钟。,问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次?,平面示意图,问题数据,问题分析,与典型的运输问题明显有以下不同：这是运输矿石与岩石两种物资的问题；属于产量大于销量的不平衡运输问题；为了完成品位约束，矿石要搭配运输；产地、销地均有单位时间的流量限制；运输车辆只有一种，每次满载运输，154吨/车次；铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地；最后求出各条路线上的派出车辆数及安排。,近似处理：先求出产位、卸点每条线路上的运输量(MIP模型)然后求出各条路线上的派出车辆数及安排,模型假设,卡车在一个班次中不应发生等待或熄火后再启动的情况；在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；空载与重载的速度都是28km/h，耗油相差很大；卡车可提前退出系统，等等。,如理解为严格不等待，难以用数学规划模型来解个别参数队找到了可行解（略）,符号,xij：从i铲位到j号卸点的石料运量（车）单位：吨；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.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:titleCUMCM-2003B-01;sets:cai/1.10/:crate,cnum,cy,ck,flag;xie/1.5/:xsubject,xnum;link(xie,cai):distance,lsubject,number,che,b;endsetsdata:crate=30282932313332313331;xsubject=1.21.31.31.91.3;distance=5.265.194.214.002.952.742.461.900.641.271.900.991.901.131.272.251.482.043.093.515.895.615.614.563.513.652.462.461.060.570.641.761.271.832.742.604.213.725.056.104.423.863.723.162.252.810.781.621.270.50;cy=1.251.101.351.051.151.351.051.151.351.25;ck=0.951.051.001.051.101.251.051.301.351.25;enddata,!目标函数;min=sum(cai(i):sum(xie(j):number(j,i)*154*distance(j,i);!max=sum(link(i,j):number(i,j);!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)/28*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):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)=0;!关于车辆的具体分配;for(link(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,计算结果（LINGO软件）,计算结果（派车）,结论：铲位1、2、3、4、8、9、10处各放置一台电铲。一共使用了13辆卡车；总运量为85628.62吨公里；岩石产量为32186吨；矿石产量为38192吨。,此外：6辆联合派车（方案略）,最大化产量,结论：（略）,目标函数变化此外：车辆数量（20辆）限制（其实上面的模型也应该有）,四、实例二:钢管订购和运输问题的数学模型(2000B),由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道,1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）,（1）制定钢管的订购和运输计划，使总费用最小.,（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？,（3）讨论管道为树形图的情形,问题1的基本模型和解法,总费用最小的优化问题,总费用：订购，运输（由各厂Si经铁路、公路至各点Aj,i=1,7;j=1,15），铺设管道AjAj+1（j=1,14),由Si至Aj的最小购运费用路线及最小费用cij由Si至Aj的最优运量xij由Aj向AjAj-1段铺设的长度zj及向AjAj+1段铺设的长度yj,最优购运计划,约束条件,钢厂产量约束：上限和下限（如果生产的话）运量约束：xij对i求和等于zj加yj；yj与zj+1之和等于AjAj+1段的长度lj,基本模型,由Aj向AjAj-1段铺设的运量为1+zj=zj(zj+1)/2由Aj向AjAj+1段铺设的运量为1+yj=yj(yj+1)/2,二次规划,求解步骤,1）求由Si至Aj的最小购运费用路线及最小费用cij,难点：公路运费是里程的线性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。,A1,需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。,如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的最小购运费,xij=1表示从点i到点j购运1单位钢管,求解时要针对规模问题寻求改进算法,2）最小费用网络流模型,线性费用网络(只有产量上限),非线性费用网络(只有产量上限),边的标记（流量上限，单位费用）,用标准算法(如最小费用路算法)求解,无单位费用概念(f(f+1)/2),需修改最小费用路算法,2）最小费用网络流模型,产量有下限ri时的修正,3)最小面积模型,作图：Si到管道x单位钢管的最小购运费用c,由各条Si首尾相连(横坐标)组成的一条折线对应一个购运方案，折线下面的面积对应方案的费用,在产量约束下找面积最小的折线,论文中发现的主要问题,1）针对题目给的数据用凑的方法算出结果，没有解决这类问题的一般模型,2）局部最优，如将管道分为左右两段，分别寻求方案；如将问题分为购运和铺设两部分，分别寻优（会导致每段管道都从两端铺到中点）,4）由Si至Aj的最小购运费用路线及最小费用cij不对,5）数字结果相差较大(如最小费用应127.5至128.2亿元),问题2：分析对购运计划和总费用影响（哪个钢厂销价的变化影响最大；哪个钢厂产量上限的变化影响最大）,规划问题的灵敏度分析,问题3：管道为树形图,(jk)是连接Aj,Ak的边，E是树形图的边集，ljk是(jk)的长度，yjk是由Aj沿(jk)铺设的钢管数量,返回第一页,fi表示钢厂i是否使