0-1规划在各种实际问题中的应用以及lingo求解.ppt

0-1规划,如果整数规划问题中的所有变量仅限于取0或1两个值，则称此问题为0-1整数规划，简称0-1规划，其变量为0-1变量.,1.游泳队员的分配问题,某游泳拟选用A、B、C、D四名游泳运动员组成一个4100m混合泳接力队，参加运动会.他们的100m自由泳、蛙泳、蝶泳、仰泳的成绩如下表. 问：A、B、C、D四名运动员各自游什么姿势，才最有可能取得好成绩？,假设问题的决策变量 1 , 第i名运动员游第j种姿势 xij= 0 , 第i名运动员不游第j种姿势,分析,以混合泳所用总时间最小为目标，以每名运动员只游一个项目，每个项目只能由一名运动员来完成为约束，这就是标准的分派问题.,约束条件：,目标函数：,lingo求解,model: sets: m/14/; n/14/; 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可由甲、乙或丁完成，且规定四个人中丙或丁能够完成两项任务，其他人完成一项任务. 试确定分配方案，使得完成的总时间最少.,各人完成各项目的时间,(1)由于任务大于人数，因此增加一个完成人戊，完成多出的一个任务. 而实际上，戊所完成的任务并不是正真的任务，只是为了构造指派问题模型.所以戊完成各任务的时间就均为0(除了任务E). 戊不需要完成任务E，x55对应的系数为M(很大的数，取1000)，以保证x55=0 各人完成任务所需时间的如下表：,设xij表示第i个人完成第j项任务,(1),设xij表示第i个人完成第j项任务,lingo求解,model: sets: m/15/; n/15/; 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,0,0,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)题，按照指派模型，可添加一个虚拟完成人戊.而实际上，戊所完成任务还是由甲乙丙丁完成的. 为了保证时间最少，戊完成各项任务的时间，就取完成各任务所需时间最短人的时间. 若戊完成哪项任务，则那项任务所需时间最短人来完成. 各人完成任务所需时间的如下表：,(2),lingo求解,model: sets: m/15/; n/15/; 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)题的时间系数矩阵(注意戊的时间与第二题的不同）,lingo求解,model: sets: m/15/; n/15/; 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污染物. 请建立优化模型分析在保证满足环保要求的前提下，确定在何处建厂能使得建厂投资和运行费用最小.,设xi表示i(i=1,2,3)污水厂处理污水的数量(万t)，yi (i=1,2,3)表示是否建立i污水厂.,min z=0.03x1+0.03x2+0.04x3+400y1+300y2+250y3,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)=0;bin(y(i);); end,结果： x1=800，x3=400, y1=1，y3=1 最少费用为690万元 即建立A污水厂，处理800万t污水；建立C污水厂，处理400万t污水.,4.服装厂生产计划安排问题,某小型服装厂可以生产A、B、C三种不同的服装，生产不同种类的服装需要租用不同的加工设备，设备的租金、生产成本、销售价格等指标如下表. 如果各类服装都有足够的市场需求，该厂每月可用人工工时为2000h，那么该厂应如何安排生产计划可使每月的利润最大？,三种服装的利润分别为120元、10元、100元. 设xi表示生成第i(i=1,2,3)种服装的数量，yi表示是否生