7 综合举例.ppt

《7 综合举例.ppt》由会员分享，可在线阅读，更多相关《7 综合举例.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、例例7.17.1 求解非线性方程组代码：model:x2+y2=2;2*x2+x+y2+y=4;end结果：Feasiblesolutionfoundatiteration:0VariableValueX0.454336Y1.3392477 综合举例综合举例 一条装配线含有一系列的工作站，在最终产品的加工过程中每个工作站执行一种或几种特定的任务。装配线周期是指所有工作站完成分配给它们各自的任务所化费时间中的最大值。平衡装配线的目标是为每个工作站分配加工任务，尽可能使每个工作站执行相同数量的任务，其最终标准是装配线周期最短。不适当的平衡装配线将会产生瓶颈有较少任务的工作站将被迫等待其前面分配了较

2、多任务的工作站。问题会因为众多任务间存在优先关系而变得更复杂，任务的分配必须服从这种优先关系。这个模型的目标是最小化装配线周期。有2类约束：要保证每件任务只能也必须分配至一个工作站来加工；要保证满足任务间的所有优先关系。例 有11件任务（AK）分配到4个工作站（14），任务的优先次序如下图。每件任务所花费的时间如下表。例7.27.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，

3、等等）;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个工作站完成;ENDSETSDATA:!任务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):SU

4、M(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任务ABCDEFGHIJK时间4511950151212121289有一个推销员

5、，从城市1出发，要遍访城市2，3，n各一次，最后返回城市1。已知从城市i到j的旅费为Cij，问他应按怎样的次序访问这些城市，使得总旅费最少？可以用多种方法把TSP表示成整数规划模型。这里介绍的一种建立模型的方法，是把该问题的每个解（不一定是最优的）看作是一次“巡回”。在下述意义下，引入一些0-1整数变量：例例7.3 7.3 旅行售旅行售货员问题货员问题（又称（又称货货郎担郎担问题问题，Traveling Salesman ProblemTraveling Salesman Problem）其目标只是使 为最小。这里有两个明显的必须满足的条件：访问城市i后必须要有一个即将访问的确切城市；访问城市

6、j前必须要有一个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。123456到此得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于TSP来说并不充分，仅仅是必要条件。例如：以上两个条件都满足，但它显然不是TSP的解，它存在两个子巡回。这里，将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的方法。把额外变量附加到问题中。可把这些变量看作是连续的（最然这些变量在最优解中取普通的整数值）。现在附加下面形式的约束条件为证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线都不满足该约束条件；（2）全部巡回都满足该约束条件。首先证明（1），用反证法。假设还存在

7、子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回记为，则必有这k个式子相加，有：，矛盾！=访问城市i的顺序数，取值范围为。因此，。下面来证明总巡回满足该约束条件。，可取故假设不正确，结论（1）得证。下面证明（2），采用构造法。对于任意的总巡回()总巡回上的边（）非总巡回上的边从而结论（2）得证。这样我们把TSP转化成了一个混合整数线性规划问题。显然，当城市个数较大（大于30）时，该混合整数线性规划问题的规模会很大，从而给求解带来很大问题。TSP已被证明是NP难问题，目前还没有发现多项式时间的算法。对小规模问题，求解这个混合整数线性规划问题的方式还是有效的。TSP

8、是一个重要的组合优化问题，除了有直观的应用外，许多其它看似无联系的优化问题也可转化为TSP。例如：问题问题1 1 现需在一台机器上加工n个零件（如烧瓷器），这些零件可按任意先后顺序在机器上加工。我们希望加工完成所有零件的总时间尽可能少。由于加工工艺的要求，加工零件j时机器必须处于相应状态Sj（如炉温）。设起始未加工任何零件时机器处于状态S0，且当所有零件加工完成后需恢复到S0状态。已知从状态Si调整到状态Sj(ij)需要时间Cij。零件j本身加工时间为pj。为方便起见，引入一个虚零件0，其加工时间为0，要求状态为S0，则0，1，2，n的一个圈置换就表示对所有零件的一个加工顺序，在此置换下，完成

9、所有加工所需要的总时间为由于是一个常数，故该零件的加工顺序问题变成TSP。!旅行售货员问题;model:sets:city/1.5/:u;link(city,city):dist,!距离矩阵;x;endsetsn=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;);!保证不出现子

10、圈;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 7.5 露天露天矿矿生生产产的的车辆车辆安排（安排（CMCM2003BCMCM2003B）钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多

11、现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多能安置一台电铲，电铲的平均装车时间为5分钟。卸货地点（以下简称卸点）有卸矿石的矿石漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山

12、的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5%1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3分钟。所用卡车载重量为154吨，平均时速28。卡车的耗油量很大，每个班次每台车消耗近1吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。每个铲位到每个卸点的道路都是专用的宽60?的双向车道，不会出

13、现堵车现象，每段道路的里程都是已知的。一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一：1.总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。请你就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面的实例，给出具

14、体的生产计划、相应的总运量及岩石和矿石产量。某露天矿有铲位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.265.194.214.002.952.742.461.900.641.27倒装场1.900.991.901.131.272.251.482.043.093.51岩场5.895.615.614.563.513.652.462.461.060.

15、57岩石漏0.641.761.271.832.742.604.213.725.056.10倒装场4.423.863.723.162.252.810.781.621.270.50各铲位矿石、岩石数量(万吨)和矿石的平均铁含量如下表：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石量0.951.051.001.051.101.251.051.301.351.25岩石量1.251.101.351.051.151.351.051.151.351.25铁含量30%28%29%32%31%33%32%31%33%31%各铲位矿石、岩石数量(万吨)和矿石的平均铁含量如下表：model:ti

16、tleCUMCM-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.65

17、2.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)+xn

18、um(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,

19、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

20、(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);!电铲数量约束-addedbyXieJinxing,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)+numbe

21、r(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;!关于车辆的

22、具体分配;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建立相应的整数规划模型是一种新的尝试。这对于处理非标准的MST问题非常方便。我们主要参考了文7。在图论中，称无圈的连通图为树。在一个连通图G中，称包含图G全部顶点的树

23、为图G的生成树。生成树上各边的权之和称为该生成树的权。连通图G的权最小的生成树称为图G的最小生成树。许多实际问题都可以归结为最小生成树。如,如何修筑一些公路把若干个城镇连接起来；如何架设通讯网络将若干个地区连接起来；如何修筑水渠将水源和若干块待灌溉的土地连接起来等等。为说明问题,以下面的问题作为范例。范例：假设某电话公司计划在六个村庄架设电话线，各村庄之间的距离如图所示。试求出使电话线总长度最小的架线方案。为了便于计算机求解，特作如下规定：（1）节点V1表示树根；（2）两个节点之间没有线路时，规定两节点之间距离为M（较大的值）MST的整数规划模型如下：例例7.6 7.6 最小生成最小生成树树（

24、Minimal Spanning TreeMinimal Spanning Tree，MSTMST）问题问题V1V2V3V4V5V61122233345这是个给n个人分配n项工作以获得某个最高总效果的问题。第i个人完成第j项工作需要平均时间cij。要求给每个人分配一项工作，并要求分配完这些工作，以使完成全部任务的总时间为最小。该问题可表示如下：例例7.7 7.7 分配分配问题问题（指派（指派问题问题，Assignment ProblemAssignment Problem）显然，此问题可看作是运输问题的特殊情况。可将此问题看作具有n个源和n个汇的问题，每个源有1单位的可获量，而每个汇有1单位的

25、需要量。从表面看，这问题要求用整数规划以保证xij能取0或1。然而，幸运的是，此问题是运输问题的特例，因此即使不限制xij取0或1，最优解也将取0或1。如果把婚姻看作分配问题，丹茨证明，整数性质证明一夫一妻会带来最美满幸福的生活！显然，分配问题可以作为线性规划问题来求解，尽管模型可能很大。例如，给100人分配100项工作将使所得的模型具有10000个变量。这时，如采用专门算法效果会更好。时间复杂度为O(n2)的匈牙利算法便是好选择，这是由Kuhu（1955）提出的。model:!7个工人，7个工作的分配问题;sets:workers/w1.w7/;jobs/j1.j7/;links(worke

26、rs,jobs):cost,volume;endsets!目标函数;min=sum(links:cost*volume);!每个工人只能有一份工作;for(workers(I):sum(jobs(J):volume(I,J)=1;);!每份工作只能有一个工人;for(jobs(J):sum(workers(I):volume(I,J)=1;);data:cost=6267425495385852197437673927239572655228114923124510;enddataend指派问题的一种推广。可以把指派问题看作线性规划问题，故较易求解，而二次分配问题是纯整数规划问题，往往很难求解

27、。与分配问题一样，二次分配问题也与两个目标集合S、T有关。S和T含有相同数目的元素，以便达到某一目标。这里两种必须满足的条件：必须把S的每个元素确切地分配给T的一个元素；T的每个元素只能接受S的一个元素。可引入0-1变量：用和分配问题相同的约束条件给出以上两个条件：例例7.8 7.8 二次分配二次分配问题问题（Quadratic Assignment ProblemQuadratic Assignment Problem）但是本问题的目标比分配问题的更加复杂。我们得到的价格系数cijkl，其解释是：在i（S的一个元素）分配给j（T的一个元素）的同时把k（S的一个元素）分配给l（T的一个元素）所

28、应承担的费用。显然，只有当xij=1且xkl=1，即其乘积xijkl=1时，才承担这种费用。于是本目标变成一个0-1变量的二次表达式：最常见是系数cijkl从其它系数tik和djl的乘积推出来的情况：Cijkl=tikdjl为弄清这个相当复杂的模型，研究下面两个应用有好处。首先认为S是一个n个工厂的集合，T是一个n个城市的集合。本问题就是要在每一城市中设置一个工厂，并要使工厂之间总的通讯费用最小。通讯费用取决于（1）每对工厂之间通讯的次数；（2）每对工厂所在两个城市之间的距离。显然，有些工厂很少与别的工厂通讯，虽相距甚远而费用却不大。另一方面，有些工厂可能需要大量通讯。通讯费取决于距离的远近。

29、在此应用中，表示tik工厂i和工厂k之间的通讯次数（以适当的单位计量）；djl为城市j和城市j之间每单位的通讯费用（显然这与j和之间的距离有关）。若工厂i和k分别设在城市j和l，显然这两家间的通讯费由Cijkl=tikdjl来确定。因而总费用可用上述目标函数来表示。例例7.97.9 有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）：秘书初试主管复试经理面试同学甲131520

30、同学乙102018同学丙201610同学丁810154名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8:00，问他们最早何时能离开公司?（建立规划模型求解）本问题是一个排列排序问题。对于阶段数不小于3的问题没有有效算法，也就是说对于学生数稍多一点儿（比如20）的情况是无法精确求解的。为此人们找到了很多近似算法。这里我们建立的规划模型可以实现该问题的精确求解，但你会看到它的变量和约束是学生数的平方。因此，当学生数稍多一点儿规划模型的规模经很大，求解会花费很长时间。记!三阶段面试模型;model:sets:students;!学生集三阶段面试模型;phases;!阶段集;sp(stu

31、dents,phases):t,x;ss(students,students)|&1#LT#&2:y;endsetsdata:students=s1.s4;phases=p1.p3;t=13152010201820161081015;enddatans=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