利用LINGO开发高级模型选讲.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,例,7.1,求解非线性方程组,代码：,model,:,x2+y2=2;,2*x2+x+y2+y=4;,end,7,综合举例,一条装配线含有一系列的工作站，在最终产品的加工过程中每个工作站执行一种或几种特定的任务。装配线周期是指所有工作站完成分配给它们各自的任务所化费时间中的最大值。平衡装配线的目标是为每个工作站分配加工任务，尽可能使每个工作站执行相同数量的任务，其最终标准是装配线周期最短。不适当的平衡装配线将会产生瓶颈,有较少任务的工作站将被迫等待其前面分配了较多任务的工作站。,问题会因为众多任务间存在优先关系而变得更复杂，任务的分配必须服从这种优先关系。,这个模型的目标是最小化装配线周期。有,2,类约束：,要保证每件任务只能也必须分配至一个工作站来加工；,要保证满足任务间的所有优先关系。,例 有,11,件任务（,AK,）分配到,4,个工作站（,14,），任务的优先次序如下图。每件任务所花费的时间如下表。,例,7.2,装配线平衡模型,（,I,）,（,H,）,（,G,）,（,J,）,（,K,）,（,F,）,（,B,）,（,A,）,（,C,）,（,E,）,（,D,）,MODEL,:,!,装配线平衡模型,;,SETS,:,!,任务集合，有一个完成时间属性,T;,TASK/A B C D E F G H I J K/:T;,!,任务之间的优先关系集合（,A,必须完成才能开始,B,，等等）,;,PRED(TASK,TASK)/A,B B,C C,F C,G F,J G,J J,K D,E E,H E,I H,J I,J/;,!,工作站集合,;,STATION/1.4/;,TXS(TASK,STATION):X;,!X,是派生集合,TXS,的一个属性。如果,X,（,I,，,K,）,1,，则表示第,I,个任务指派给第,K,个工作站完成,;,ENDSETS,DATA,:,!,任务,A B C D E F G H I J K,的完成时间估计如下,;,T=45 11 9 50 15 12,12,12,12,8 9;,ENDDATA,!,当任务超过,15,个时，模型的求解将变得很慢,;,!,每一个作业必须指派到一个工作站，即满足约束,;,FOR,(TASK(I):,SUM,(STATION(K):X(I,K)=1);,!,对于每一个存在优先关系的作业对来说，前者对应的工作站,I,必须小于后,者对应的工作站,J,，即满足约束,;,FOR,(PRED(I,J):,SUM,(STATION(K):K*X(J,K)-K*X(I,K)=0);,!,对于每一个工作站来说，其花费时间必须不大于装配线周期,;,FOR,(STATION(K):,SUM,(TXS(I,K):T(I)*X(I,K)=CYCTIME);,!,目标函数是最小化转配线周期,;,MIN,=CYCTIME;,!,指定,X(I,J),为,0/1,变量,;,FOR,(TXS:,BIN,(X);,END,任务,A,B,C,D,E,F,G,H,I,J,K,时间,45,11,9,50,15,12,12,12,12,8,9,有一个推销员，从城市,1,出发，要遍访城市,2,，,3,，,，,n,各一次，最后返回城市,1,。已知从城市,i,到,j,的旅费为,C,ij,，问他应按怎样的次序访问这些城市，使得总旅费最少？,可以用多种方法把,TSP,表示成整数规划模型。这里介绍的一种建立模型的方法，是把该问题的每个解（不一定是最优的）看作是一次“巡回”。,在下述意义下，引入一些,0-1,整数变量：,例,7.3,旅行售货员问题（又称货郎担问题，,Traveling Salesman Problem,）,其目标只是使,为最小。,这里有两个明显的必须满足的条件：,访问城市,i,后必须要有一个即将访问的确切城市；,访问城市,j,前必须要有一个刚刚访问过的确切城市。,用下面的两组约束分别实现上面的两个条件。,1,2,3,4,5,6,到此得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于,TSP,来说并不充分，仅仅是必要条件。,例如：,以上两个条件都满足，但它显然不是,TSP,的解，它存在两个子巡回。,这里，将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的方法。把额外变量,附加到问题中。可把这些变量看作是连续的（最然这些变量在最优解中取普通的整数值）。现在附加下面形式的约束条件,为证明该约束条件有预期的效果，必须证明：,（,1,）任何含子巡回的路线都不满足该约束条件；,（,2,）全部巡回都满足该约束条件。,首先证明（,1,），用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市,1,。把该子巡回记为,，则必有,这,k,个式子相加，有,：,，矛盾！,=,访问城市,i,的顺序数，取值范围为,。因此，,。下面来证明总巡回满足该约束条件。,，可取,故假设不正确，结论（,1,）得证。,下面证明（,2,），采用构造法。对于任意的总巡回,(),总巡回上的边,（,）非总巡回上的边,从而结论（,2,）得证。,这样我们把,TSP,转化成了一个混合整数线性规划问题。,显然，当城市个数较大（大于,30,）时，该混合整数线性规划问题的规模会很大，从而给求解带来很大问题。,TSP,已被证明是,NP,难问题，目前还没有发现多项式时间的算法。对小规模问题，求解这个混合整数线性规划问题的方式还是有效的。,TSP,是一个重要的组合优化问题，除了有直观的应用外，许多其它看似无联系的优化问题也可转化为,TSP,。例如：,问题,1,现需在一台机器上加工,n,个零件（如烧瓷器），这些零件可按任意先后顺序在机器上加工。我们希望加工完成所有零件的总时间尽可能少。由于加工工艺的要求，加工零件,j,时机器必须处于相应状态,S,j,（如炉温）。设起始未加工任何零件时机器处于状态,S,0,，,，且当所有零件加工完成后需恢复到,S,0,状态。已知从状态,S,i,调整到状态,S,j,(ij,),需要时间,C,ij,。零件,j,本身加工时间为,p,j,。为方便起见，引入一个虚零件,0,，其加工时间为,0,，要求状态为,S,0,，,，则,0,，,1,，,2,，,，,n,的一个圈置换,就表示对所有零件的一个加工顺序，在此置换下，完成所有加工所需要的总时间为,由于,是一个常数，故该零件的加工顺序问题变成,TSP,。,!,旅行售货员问题,;,model,:,sets,:,city/1.5/:u;,link(city,city):,dist,!,距离矩阵,;,x;,endsets,n=,size,(city);,data,:,!,距离矩阵，它并不需要是对称的,;,dist=,qrand,(1);,!,随机产生,，这里可改为你要解决的问题的数据,;,enddata,!,目标函数,;,min,=,sum,(link:dist*x);,FOR,(city(K):,!,进入城市,K;,sum,(city(I)|I#,ne,#K:x(I,K)=1;,!,离开城市,K;,sum,(city(J)|J#,ne,#K:x(K,J)=1;,);,!,保证不出现子圈,;,for,(city(I)|I,#,gt,#1:,for,(city(J)|J#gt#1#and#I#,ne,#J:,u(I)-u(J)+n,*,x(I,J,)=n-1);,);,!,限制,u,的范围以加速模型的求解，保证所加限制并不排除掉,TSP,问题的最优解,;,for,(city(I,)|I#,gt,#1:,u(I,)j,，否则就不是。,由此，我们就可方便的确定出最短路径,;,for,(roads(i,j):P(i,j,)=,if,(F(i,)#,eq,#D(i,j)+F(j),1,0),);,end,例,7.5,露天矿生产的车辆安排（,CMCM2003B,）,钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。,露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于,25%,的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多能安置一台电铲，电铲的平均装车时间为,5,分钟。,卸货地点（以下简称卸点）有卸矿石的矿石漏、,2,个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为,29.5%,1%,，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（,8,小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为,3,分钟。,所用卡车载重量为,154,吨，平均时速,28,。卡车的耗油量很大，每个班次每台车消耗近,1,吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。,每个铲位到每个卸点的道路都是专用的宽,60?,的双向车道，不会出现堵车现象，每段道路的里程都是已知的。,一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一：,1.,总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；,2.,利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。,请你就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。,某露天矿有铲位,10,个，卸点,5,个，现有铲车,7,台，卡车,20,辆。各卸点一个班次的产量要求：矿石漏,1.2,万吨、倒装场,1.3,万吨、倒装场,1.3,万吨、岩石漏,1.9,万吨、岩场,1.3,万吨。,铲位和卸点位置二维示意图如下，各铲位和各卸点之间的距离（公里）如下表：,铲位,1,铲位,2,铲位,3,铲位,4,铲位,5,铲位,6,铲位,7,铲位,8,铲位,9,铲位,10,矿石漏,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,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,各铲位矿石、岩石数量,(,万吨,),和矿石的平均铁含量如下表：,铲位,1,铲位,2,铲位,3,铲位,4,铲位,5,铲位,6,铲位,7,铲位,8,铲位,9,铲位,10,矿石量,0,.,95,1,.,05,1,.,00,1,.,05,1,.,10,1,.,25,1,.,05,1,.,30,1,.,35,1,.,25,岩石量,1,.,25,1,.,10,1,.,35,1,.,05,1,.,15,1,.,35,1,.,05,1,.,15,1,.,35,1,.,25,铁含量,30%,28%,29%,32%,31%,33%,32%,31%,33%,31%,各铲位矿石、岩石数量,(,万吨,),和矿石的平均铁含量如下表：,model,:,title,CUMCM-2003B-01;,sets,:,cai,/1.10/:,crate,cnum,cy,ck,flag,;,xie,/1.5/:,xsubject,xnum,;,link(,xie,cai,):,distance,lsubject,number,che,b,;,endsets,data,:,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 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,);,!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);,!,电铲数量约束,-added by,Xie,Jinxing,2003-09-07;,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,)*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,(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,=A7,A70),，,(C2-A7)$(C2-A7),，,100000),从“排课数据”域中输入数据的语句：,C=,OLE(c,：,rny,documents,排课数据,.,xls,，排课数据,),解答输出到“排课方案”域的语句：,OLE(crny,documents,悄,课数据,.,xls,，排课方案,),：,X,11.,说明,(1),模型中的教室总数是,5,，实际问题中往往教室总数要大得多。,例如，假设教室总数是,100,。这时，只要,5,改成,100,即可。,同时，文件排课数据,.XLS,中的两个域的范围要做相应变动。,(2,当教室总数和班级总数不相等时，可通过虚设教室,(,或班级,),实现相等。此时，虚设教室容量,(,或班级人数,),应为,0,。,例如，假设前面问题中的班级,1,不存在，可将其人数定为,0,，相应的解答。,由于班级,l,是虚设的，对应的教室,5,空出，从表中可知它是可空出的最大教室。,GENPRT,（,Markowitz,投资选择模型）,1.,背景,1952,年,3,月在美国的,金融,杂志上，,Harry,M.Markowitz,发表了题为“投资选择”的文章。文章论证了如何通过选择那些相关程度不大的投资来减少资产投资的风险。与此同时，为在风险和利润之间建立有利关系，还拟定了一个基本原则：投资多样化。换句话说，就是不要将所有的“鸡蛋”放在一个“篮子”里。,理解模型的关键：统计量投资方差。数学上，投资方差：,X,：用于第,i,项投资的投资额，若,i,不等于,j,，则,ij,是第,i,项与第,j,项的协方差；如果,i,等于,j,，则,ij,是第,i,项投资的方差。,方差：表示利润波动的平均值。方差越大，投资风险就越大。,协方差：表示一种股票利润波动与另一种股票利润波动的相关性。协方差较大，则表明一种股票利润的增加很可能会带动另一种股票利润的增加。协方差接近,0,，则意味着两种股票的利润变化彼此独立。一个负的协方差意味着一种股票利润的增加可能会导致另一种股票利润的减少。,Markowitz,模型是寻求最小投资方差的投资方案，同时使得所有期望利润总和达到一定水平。,2.,问题,假设你正在考虑向三种股票进行投资。通过历史资料，计算出了一个期望利润、利润方差、各种股票之间利润的协方差。希望通过向三种而不是一种股票投资来降低风险。计划让利润增加,12,。则，为达到这一目标并且使投资风险最小，你应该如何分配你的资金向三种股票投资？,作为一种安全上的考虑，你规定任何一项单独的投资不得超过投资总额的,75,。,3.,模型：,Markowitz,投资选择模型,GENPRT,4.,集合,定义基本集合,ASSETS,，三种股票。,利用其自乘，派生了一个密集,COVMAT,，定义协方差矩阵。,5.,属性,定义了,4,个属性。前,3,个属性,RATE,、,UB,、,V,存储数据。,RATE,：存储每一种投资的期望利润，,UB,：存储投资中用于某一项投资的上限值，,V,：存储协方差矩阵。,注意：协方差矩阵对称。只给出一半即可，为简单给出整个矩阵。,X,：决策变量。即，,X(i,),表示用于第,i,项投资的投资比例。,6.,目标函数：,使得投资风险达到最小。,用投资方差来表示投资风险。得到下面目标函数：,VARMIN=SUM(COVMAT(I,J),：,V(I,J)X(I)*X(J),；,7.,约束：,三种：,(1),必须将资金全部用于投资；,使用下面表达式可将所有资金用于投资：,FULLSUM(ASSET:X)=l,；,即，所有各项投资的比例之和必须等于,1,。如果没有这个约束，系统将试图寻求方差更低的投资方案。你可以将这个约束去掉，运行模型试试结果。,(2),不可能在某一项上投资过多；,用下面表达式保证对某项目的投资不至于太多：,FOR(ASSET,：,BND(0,，,X,，,UB),；,用,BND,函数限制变量的界限是最有效的方法。,(3),期望利润必须达到或超过目标利润率，目标利润率为,12,。,迫使投资的期望利润大于或等于目标利润：,RETSUM(ASSET,：,RATEX)=GROWTH,；,左边是期望利润率，各项投资利润率与投资比率相乘相加的结果。,8.,解答,求解模型，我们将得到下面的,MarkowitZ,投资选择模型解答：,Optimsolution,found at step,：,7,Objective value,：,0.4173749,Variable,Value,X(1)0.1548631,X(2)0.2502361,X(3)0.5949008,Row Slack Or Surplus,VAR 0.4173749,FULL 0.0000000,RET 0.2409821E-01,投资方差达到最小值,0.4174,，用于第一种股票的投资为,15.5,；第二种股票的投资为,25,；第三种股票的投资为,59.5,。,例,7.9,有,4,名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段,4,名同学的顺序是一样的）。由于,4,名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）：,秘书初试,主管复试,经理面试,同学甲,13,15,20,同学乙,10,20,18,同学丙,20,16,10,同学丁,8,10,15,4,名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨,8:00,，问他们最早何时能离开公司,?,（建立规划模型求解）,本问题是一个排列排序问题。对于阶段数不小于,3,的问题没有有效算法，也就是说对于学生数稍多一点儿（比如,20,）的情况是无法精确求解的。为此人们找到了很多近似算法。这里我们建立的规划模型可以实现该问题的精确求解，但你会看到它的变量和约束是学生数的平方。因此，当学生数稍多一点儿规划模型的规模经很大，求解会花费很长时间。记,!,三阶段面试模型,;,model,:,sets,:,students;,!,学生集三阶段面试模型,;,phases;,!,阶段集,;,sp(students,phases):t,x,;,ss(students,students,)|,endsets,data,:,students=s1.s4;,phases=p1.p3;,t=,13 15 20,10 20 18,20 16 10,8 10 15;,enddata,ns=,size,(students,);,!,学生数,;,np,=,size,(phases,);,!,阶段数,;,!,单个学生面试时间先后次序的约束,;,for,(sp(I,J,)|J#LT#,np:x(I,J)+t(I,J,)=x(I,J+1);,!,学生间的面试先后次序保持不变的约束,;,for,(ss(I,K,):,for,(phases(J,):,x(I,J)+t(I,J)-x(K,J,)=200*,y(I,K,);,x(K,J)+t(K,J)-x(I,J,)=200*(1-y(I,K);,),);,!,目标函数,;,min,=TMAX;,for,(students(I):x(I,3)+t(I,3)=TMAX);,!,把,Y,定义,0-1,变量,;,for,(ss,:,bin,(y,);,end,