规划在各种实际问题中的应用以和lingo求解.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,0-1规划在各种实际问题中的应用以和lingo求解,1.,游泳队员的分配问题,某游泳拟选用A、B、C、D四名游泳运动员组成一个4100m混合泳接力队，参加运动会.他们的100m自由泳、蛙泳、蝶泳、仰泳的成绩如下表.,问：A、B、C、D四名运动员各自游什么姿势，才最有可能取得好成绩？,姿势,成绩,队员,自由泳,蛙泳,蝶泳,仰泳,A,56,74,61,63,B,63,69,65,71,C,57,77,63,67,D,55,76,62,62,假设问题的决策变量,1,第,i,名运动员游第,j,种姿势,x,ij,=,0,第,i,名运动员不游第,j,种姿势,四名运动员的成绩矩阵,a,ij,=,56 74 61 63,63 69 65 71,57 77 63 67,55 76 62 62,分析,以混合泳所用总时间最小为目标，以每名运动员只游一个项目，每个项目只能由一名运动员来完成为约束，这就是标准的分派问题.,约束条件：,目标函数：,lingo,求解,model:,sets:,m/1.4/;,n/1.4/;,link(m,n):a,x;,endsets,data:,a=56,74,61,63,63,69,65,71,57,77,63,67,55,76,62,62;,enddata,objmin=sum(link(i,j):a(i,j)*x(i,j);,for(n(j):sum(m(i):x(i,j)=1;);,for(m(i):sum(n(j):x(i,j)=1;);,for(link(i,j):bin(x(i,j);x(i,j)=0;);,end,2.指派问题,设有甲、乙、丙、丁四个人，各有能力去完成,A、B、C、D、E五项科研任务中的任一项，由于四个人的能力和经验不同，所需要完成任务的时间如下表所示，由于任务数多于人数，要求考虑如下问题：,(1)任务E必须要完成，其他四项任务可任选三项完成；,(2)要求有一个人完成两项任务，其他人各完成一项任务；,(3)要求任务A可由甲或丙完成，任务C可由丙或丁完成，任务E可由甲、乙或丁完成，且规定四个人中丙或丁能够完成两项任务，其他人完成一项任务.,试确定分配方案，使得完成的总时间最少.,项目,人员,A,B,C,D,E,甲,25,29,31,42,37,乙,39,38,26,20,33,丙,34,27,28,40,32,丁,24,42,36,23,45,各人完成各项目的时间,(1)由于任务大于人数，因此增加一个完成人戊，完成多出的一个任务.,而实际上，戊所完成的任务并不是正真的任务，只是为了构造指派问题模型.所以戊完成各任务的时间就均为0(除了任务E).,戊不需要完成任务E，,x,55,对应的系数为M(很大的数，取1000)，以保证,x,55,=0,各人完成任务所需时间的如下表：,设,x,ij,表示第,i,个人完成第,j,项任务,项目,人员,A,B,C,D,E,甲,25,29,31,42,37,乙,39,38,26,20,33,丙,34,27,28,40,32,丁,24,42,36,23,45,戊,0,0,0,0,M,(1),设,x,ij,表示第,i,个人完成第,j,项任务,lingo,求解,model:,sets:,m/1.5/;,n/1.5/;,link(m,n):a,x;,endsets,data:,a=25,29,31,42,37,39,38,26,20,33,34,27,28,40,32,24,42,36,23,45,0,00,0,1000;,enddata,objmin=sum(link(i,j):a(i,j)*x(i,j);,for(n(j):sum(m(i):x(i,j)=1;);,for(m(i):sum(n(j):x(i,j)=1;);,for(link(i,j):bin(x(i,j);x(i,j)=0;);,end,即甲完成B任务，乙完成D任务，丙完成E任务，丁完成A任务总用时105分钟.,第,(2)题，按照指派模型，可添加一个虚拟完成人戊.而实际上，戊所完成任务还是由甲乙丙丁完成的.,为了保证时间最少，戊完成各项任务的时间，就取完成各任务所需时间最短人的时间.,若戊完成哪项任务，则那项任务所需时间最短人来完成.,各人完成任务所需时间的如下表：,项目,人员,A,B,C,D,E,甲,25,29,31,42,37,乙,39,38,26,20,33,丙,34,27,28,40,32,丁,24,42,36,23,45,戊,24,27,26,23,32,(2),lingo,求解,model:,sets:,m/1.5/;,n/1.5/;,link(m,n):a,x;,endsets,data:,a=25,29,31,42,37,39,38,26,20,33,34,27,28,40,32,24,42,36,23,45,24,27,26,20,32;,enddata,objmin=sum(link(i,j):a(i,j)*x(i,j);,for(n(j):sum(m(i):x(i,j)=1;);,for(m(i):sum(n(j):x(i,j)=1;);,for(link(i,j):bin(x(i,j);x(i,j)=0;);,end,即甲完成B任务，乙完成C、D两个任务，丙完成E任务，丁完成A任务总用时131分钟.,第(3)题的时间系数矩阵(注意戊的时间与第二题的不同）,项目,人员,A,B,C,D,E,甲,25,29,M,42,37,乙,M,38,M,20,33,丙,34,27,28,40,32,丁,M,42,36,23,M,戊,25,27,28,23,32,lingo,求解,model:sets:,m/1.5/;,n/1.5/;,link(m,n):a,x;,endsets,data:,a=25,29,1000,42,37,1000,38,1000,20,33,34,27,28,40,32,1000,42,36,23,1000,24,27,26,20,32;,enddata,objmin=sum(link(i,j):a(i,j)*x(i,j);,for(n(j):sum(m(i):x(i,j)=1;);,for(m(i):sum(n(j):x(i,j)=1;);,for(link(i,j):bin(x(i,j);x(i,j)=0;);,end,即甲完成A任务，乙完成E两个任务，丙完成B、C任务，丁完成D任务总用时136分钟.,3.,污水厂的选址问题,为了减少污水对环境的污染，某市拟建立一个污水处理厂，备选的厂址有三个，分别A、B、C.,相应的预算投资金额、处理能力和成本等指标如下表所示.根据环保部门的要求，污水厂建成后每年要从污水中清除8万t污染物和6万t污染物.,请建立优化模型分析在保证满足环保要求的前提下，确定在何处建厂能使得建厂投资和运行费用最小.,指标,厂址,投资金额,(万元),处理能力,(,万,t,/年,),处理能力,(元/万t),污水处理指标,(t/万t),污染物,污染物,厂址A,400,800,300,80,60,厂址B,300,500,300,50,40,厂址C,250,400,400,40,50,设,x,i,表示,i,(,i,=1,2,3)污水厂处理污水的数量(万,t,)，,y,i,(,i,=1,2,3)表示是否建立,i,污水厂.,min z=0.03,x,1,+0.03,x,2,+0.04,x,3,+400,y,1,+300,y,2,+250,y,3,80,x,1,+50,x,2,+40,x,3,80000,60,x,1,+40,x,2,+50,x,3,60000,x,1,800,y,1,x,2,500,y,2,x,3,400,y,3,x,i,0,y,i,=0或1,s.t.,lingo,求解,model:,sets:,m/1,2,3/:x,y;,endsets,objmin=300*x(1)+300*x(2)+400*x(3)+400*y(1)+300*y(2)+250*y(3);,80*x(1)+50*x(2)+40*x(3)=80000;,60*x(1)+40*x(2)+50*x(3)=60000;,x(1)=800*y(1);,x(2)=500*y(2);,x(3)=0;bin(y(i););,end,结果：,x,1,=800，,x,3,=400,y,1,=1，,y,3,=1,最少费用为690万元,即建立A污水厂，处理800万t污水；建立C污水厂，处理400万t污水.,4.服装厂生产计划安排问题,某小型服装厂可以生产,A、B、C,三种不同的服装，生产不同种类的服装需要租用不同的加工设备，设备的租金、生产成本、销售价格等指标如下表,.,如果各类服装都有足够的市场需求，该厂每月可用人工工时为,2000h,，那么该厂应如何安排生产计划可使每月的利润最大？,服装种类,设备租金,（元）,生产成本,(元/件),销售价格,(元/件),人工工时,(h/件),设备工时(h/件),设备可用工时(h),A,5000,280,400,5,3,300,B,2000,30,40,1,0.5,300,C,2000,200,300,4,2,300,三种服装的利润分别为120元、10元、100元.,设,x,i,表示生成第,i,(,i,1,2,3)种服装的数量，,y,i,表示是否生产第,i,种服装.,5,x,1,+,x,2,+4,x,3,2000,3,x,1,300,y,1,0.5,x,2,300,y,2,2,x,3,300,y,3,s.t.,lingo,求解,model:,sets:,m/1,2,3/:x,y;,endsets,objmax=100*x(1)+10*x(2)+100*x(3)-5000*y(1)-2000*y(2)-2000*y(3);,5*(1)+x(2)+4*x(3)=2000;,3*x(1)=300*y(1);,0.5*x(2)=300*y(2);,2*x(3)=0;bin(y(i););,end,