用Lingo求解整数规划模型.ppt

温州大学城市学院,温州大学城市学院,实验二 用,Lingo,求解规划模型,变量定界函数,:,bin(x):,限制,x,为,0,或,1.,gin(x):,限制,x,为整数,.,例,1,用,Lingo,软件求解,0-1,规划问题,max=2*x1+5*x2+3*x3+4*x4;,-4*x1+x2+x3+x4=0;,-2*x1+4*x2+2*x3+4*x4=1;,x1+x2-x3+x4=1;,bin(x1);bin(x2);bin(x3);bin(x4);,Lingo,程序,:,一、用,Lingo,求解规划问题,例,2,用,Lingo,软件求解整数规划问题,min=2*x1+5*x2+3*x3;,4*x1-x2+x3=0;,-2*x1+4*x2-2*x3=2;,x1-x2+x3=2;,gin(x1);gin(x2);gin(x3);,Lingo,程序,:,例,3,用,Lingo,软件求解非线性规划问题,min=(x1-1)2+(x2-2)2;,x2-x1=1;,x1+x2=2;,Lingo,程序,:,注意,:,Lingo,默认变量的取值从,0,到,正无穷大,变量定界函数可以改变默认状态,.,free(x):,取消对变量,x,的限制,(,即,x,可取任意实数值,),例,4,求函数 的最小值,.,解,:,编写,Lingo,程序如下,:,min=(x+2)2+(y-2)2;,free(x)例,4,求函数 的最小值,.,求得结果,:x=-2,y=2,二、,Lingo,循环编程语句,(1),集合的定义,包括如下参数,:,1),集合的名称,.,命名规则,:,以,字母开头,后面是,字母,或,下划线,.,字母不区分大小写,.,2),集合包含的元素,(,可选,).,3),集合中元素的所有属性,(,可选,).,例,4,Math,English,total,sets:,endsets,students,John,Jill,Rose,Mike,sets:,students,/,John,Jill,Rose,Mike,/:,Math,English,total,;,endsets,(2),数据赋值,例,4,data:,enddata,data:,Math=80,85,90,70;,English=75,80,72,60;,enddata,格式,:,(1),集合的定义,例,4,sets:,students,/,John,Jill,Rose,Mike,/:,Math,English,total;,endsets,(3),集合的,循环函数,集合的,循环函数,可以使所有的元素重复完成一些操作,.,函数,函数功能,for,形成集合,所有元素,需满足的约束条件,sum,计算集合中元素所在表达式的,和,min,计算集合中元素所在表达式的,最小值,max,计算集合中元素所在表达式的,最大值,maxM=max(students(i):Math);,maxE=max(students(i):English);,averageM=sum(students(i):Math)/4;,for(students(i):total(i)=Math(i)+English(i);,例,4,!,数学的最高分,;,!,英语的最高分,;,!,数学的平均分,;,!,每个学生数学与英语分数之和,.,(4),衍生集合的定义,.,包括如下参数,:,1),衍生集合的名称,.,3),衍生集合包含的元素,(,可选,).,4),集合中元素的所有属性,(,可选,).,例,5,link,2),衍生集合的父集合名称,.,sets:,ren,/A,B,C,D/:rent;,job,/1.5/:jobt;,link,(ren,job):,time,;,endsets,ren,job,time,注,:,若没有指明元素列表,LINGO,将用父集合元素的所有组合作为衍生集合的元素,.,(A,1),(A,2),(A,3),(A,4)(A,5),(B,1),(B,2),(B,3),(B,4)(B,5),(C,1),(C,2),(C,3),(C,4)(C,5),(D,1),(D,2),(D,3),(D,4)(D,5),(5)Lingo,内部的数学函数及其返回值,abs(x):,返回,x,的绝对值,sin(x):,返回,x,的正弦值,cos(x):,返回,x,的余弦值,tan(x):,返回,x,的正切值,log(x):,返回,x,的自然对数值,exp(x):,返回,e,x,的值,sqr(x):,返回,x,的平方值,.,该函数可以用表达式,x2,代替,sqrt(x):,返回,x,的正的平方根,.,可以用表达式,x(1/2),代替,三、,Lingo,循环编程举例,例,5,现有五名工人甲,乙,丙,丁,戊,完成五项工作,A,B,C,D,E,所需时间列表如下,工作,时间,(,小时,),工人,A,B,C,D,E,甲,1,0.5,2,1.75,4,乙,2,1,3,1.5,3.5,丙,1.75,1.5,2.5,1,3,丁,2.5,2,1.5,0.5,4,戊,1,1.5,2,2,3,(2),求每份工作最短的用时,.,(1),求每个人的最短工作时间,;,问题,:,三、,Lingo,循环编程举例,例,5,sets:,ren/A,B,C,D,E/:rent;,job/1.5/:jobt;,link,(ren,job):,time,;,endsets,data:,time,=1,0.5,2,1.75,4,2,1,3,1.5,3.5,1.75,1.5,2.5,1,3,2.5,2,1.5,0.5,4,1,1.5,2,2,3;,enddata,S=,sum,(link(i,j):time(i,j);,for,(ren(i):rent=,min,(job(j):time(i,j);,for,(job(j):jobt=,min,(ren(i):time(i,j);,!,定义集合,;,!,数据赋值,;,!,所有工作时间求和,;,!,求每个人的最短工作时间,;,!,求每份工作最短的用时,;,三、,Lingo,循环编程举例,例,5,用,Lingo,循环编程语句求解线性规划模型,三、,Lingo,循环编程举例,sets:,bliang/1,2/:x,a;,yshu/1,2,3/:b;,xshu(yshu,bliang):c;,endsets,data:,a=72,64;,b=50,480,100;,c=1,1,12,8,3,0;,enddata,max=,sum,(bliang(i):a(i)*x(i);,for,(yshu(j):,sum,(bliang(i):x(i)*c(j,i)=b(j);,!,定义集合,;,!,数据赋值,;,!,目标函数,;,!,约束条件,;,例,5,用,Lingo,循环编程语句求解线性规划模型,例,6,：人员选拔问题,3,5,7,1.92,队员号码,身高,/m,1,位置,1.88,1.85,1.80,中锋,前锋,前锋,后卫,4,6,8,1.90,队员号码,身高,/m,2,位置,1.86,1.83,1.78,中锋,前锋,后卫,后卫,同时,要求出场阵容必须满足以下条件,:,中锋只能有一个上场,;(2),至少有一名后卫,;,(3),如果,1,号,队员和,4,号,队员都上场,则,6,号,队员不能上场,;,(4),2,号,队员和,6,号,队员必须至少保留一个不出场,.,如何确定符合要求的出场阵容,?,上机作业题,1,、建立数学模型，,2,、用,lingo,循环语句编写程序,.,要求：,上机作业题,某城市的巡逻大队要求每天的各个时间段都有一定数量的警员值班,以便随时处理突发事件,每人连续工作,6h,中间不休息,.,如表所示是一天,8,个班次,所需值班警员的人数情况统计,:,现在在不考虑时间段中警员上班和下班的情况下,巡逻大队至少需要多少警员才能满足值班需要,?,人员安排问题,班次,时间段,人数,班次,时间段人数,1,6:00,9:00,70,5,18:00,21:00,80,2,9:00,12:00,80,6,21:00,24:00,100,3,12:00,15:00,65,7,24:00,3:00,120,4,15:00,18:00,90,8,3:00,6:00,90,设第,i,个班次开始上班的警员数为,x,i,.,目标函数,:,约束条件,:,上机作业题,分配问题,某游泳队拟选用甲,乙,丙,丁 四名游泳运动员组成一个,4100 m,混合泳接力队,参加今年的锦标赛,.,他们的,100 m,自由泳,蛙泳,蝶泳,仰泳的成绩如表所示,乙,丙,丁,56,成绩,自由泳,/s,甲,63,57,55,74,蛙泳,/s,69,77,76,61,蝶泳,/s,65,63,62,63,仰泳,/s,71,67,62,甲,乙,丙,丁 四名队员各自游什么姿势,才最有可能取得好成绩,?,约束条件,