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

1、例7.1 求解非线性方程组,代码：model:x2+y2=2;2*x2+x+y2+y=4;end,7 综合举例,一条装配线含有一系列的工作站，在最终产品的加工过程中每个工作站执行一种或几种特定的任务。装配线周期是指所有工作站完成分配给它们各自的任务所化费时间中的最大值。平衡装配线的目标是为每个工作站分配加工任务，尽可能使每个工作站执行相同数量的任务，其最终标准是装配线周期最短。不适当的平衡装配线将会产生瓶颈有较少任务的工作站将被迫等待其前面分配了较多任务的工作站。问题会因为众多任务间存在优先关系而变得更复杂，任务的分配必须服从这种优先关系。这个模型的目标是最小化装配线周期。有2类约束：要保证每

2、件任务只能也必须分配至一个工作站来加工；要保证满足任务间的所有优先关系。例 有11件任务（AK）分配到4个工作站（14），任务的优先次序如下图。每件任务所花费的时间如下表。,例7.2 装配线平衡模型,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

3、;!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):SUM(STATION(K):X(I,K)=1);!对于每一个存在优先关系的作业对来说，前者对应的工作站I必须小于后 者对应的工作站J，即满足约束;FOR(PRED(I,J):SUM(STATION(K):K*X(J,K)

4、-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,有一个推销员，从城市1出发，要遍访城市2，3，n各一次，最后返回城市1。已知从城市i到j的旅费为Cij，问他应按怎样的次序访问这些城市，使得总旅费最少？,可以用多种方法把TSP表示成整数规划模型。这里介绍的一种建立模型的方法，是把该问题的每个解（不一定是最优的）看作是一次“巡回”。在下述意义下，

5、引入一些0-1整数变量：,例7.3 旅行售货员问题（又称货郎担问题，Traveling Salesman Problem）,其目标只是使 为最小。,这里有两个明显的必须满足的条件：访问城市i后必须要有一个即将访问的确切城市；访问城市j前必须要有一个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。,到此得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于TSP来说并不充分，仅仅是必要条件。例如：,以上两个条件都满足，但它显然不是TSP的解，它存在两个子巡回。,这里，将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的方法。把额外变量,附加到问题中。可把这些变量看作

6、是连续的（最然这些变量在最优解中取普通的整数值）。现在附加下面形式的约束条件,为证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线都不满足该约束条件；（2）全部巡回都满足该约束条件。首先证明（1），用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回记为,，则必有,这k个式子相加，有：,，矛盾！,=访问城市i的顺序数，取值范围为,。因此，,。下面来证明总巡回满足该约束条件。,，可取,故假设不正确，结论（1）得证。,下面证明（2），采用构造法。对于任意的总巡回,()总巡回上的边,（）非总巡回上的边,从而结论（2）得证。这样我们把TSP转

7、化成了一个混合整数线性规划问题。,显然，当城市个数较大（大于30）时，该混合整数线性规划问题的规模会很大，从而给求解带来很大问题。TSP已被证明是NP难问题，目前还没有发现多项式时间的算法。对小规模问题，求解这个混合整数线性规划问题的方式还是有效的。TSP是一个重要的组合优化问题，除了有直观的应用外，许多其它看似无联系的优化问题也可转化为TSP。例如：问题1 现需在一台机器上加工n个零件（如烧瓷器），这些零件可按任意先后顺序在机器上加工。我们希望加工完成所有零件的总时间尽可能少。由于加工工艺的要求，加工零件j时机器必须处于相应状态Sj（如炉温）。设起始未加工任何零件时机器处于状态S0，且当所有

8、零件加工完成后需恢复到S0状态。已知从状态Si调整到状态Sj(ij)需要时间Cij。零件j本身加工时间为pj。为方便起见，引入一个虚零件0，其加工时间为0，要求状态为S0，则0，1，2，n的一个圈置换就表示对所有零件的一个加工顺序，在此置换下，完成所有加工所需要的总时间为,由于,是一个常数，故该零件的加工顺序问题变成TSP。,!旅行售货员问题;model:sets:city/1.5/:u;link(city,city):dist,!距离矩阵;x;endsets n=size(city);data:!距离矩阵，它并不需要是对称的;dist=qrand(1);!随机产生，这里可改为你要解决的问题的

9、数据;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)=n-2);!定义X为01变量;for(link:bin(x);end

10、,给定N个点pi(i=1,2,N)组成集合pi。cij表示任一点pi到另一点pj的距离，并作如下规定：若pi到pj没有弧联结，cij=+，cii=0(i=1,2,N)。现指定一个终点pN，求从pi点出发到pN的最短路线。用动态规划方法做：点pi表示状态，决策集合是除pi以外点，选定一个点pj以后，得到cij并转入新状态效益pj，当状态是pN时，过程停止。这是一个不定期多阶段决策过程。定义f(i)：由点pi出发至终点pN最短路程，由最优化原理得：,函数方程，用LINGO可以方便的解决。,例7.4 最短路问题,!最短路问题;model:data:n=10;enddatasets:cities/1.

11、n/:F;!10个城市;roads(cities,cities)/1,2 1,3 2,4 2,5 2,6 3,4 3,5 3,6 4,7 4,8 5,7 5,8 5,9 6,8 6,9 7,10 8,10 9,10/:D,P;endsetsdata:D=6 5 3 6 9 7 5 11 9 1 8 7 5 4 10 5 7 9;enddata F(n)=0;for(cities(i)|i#lt#n:F(i)=min(roads(i,j):D(i,j)+F(j););!显然，如果P(i,j)=1,则点i到点n的最短路径的第一步是i-j，否则就不是。由此，我们就可方便的确定出最短路径;for(ro

12、ads(i,j):P(i,j)=if(F(i)#eq#D(i,j)+F(j),1,0);end,例7.5 露天矿生产的车辆安排（CMCM2003B）钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的

13、。每个铲位至多能安置一台电铲，电铲的平均装车时间为5分钟。卸货地点（以下简称卸点）有卸矿石的矿石漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5%1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3分钟。所用卡车载重量为154吨，平均时速28。卡车的耗油量很大，每个班次每台车消耗近1吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火

14、一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。每个铲位到每个卸点的道路都是专用的宽60?的双向车道，不会出现堵车现象，每段道路的里程都是已知的。一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一：1.总运量（吨公里）最小，同时出

15、动最少的卡车，从而运输成本最小；2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。请你就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。某露天矿有铲位10个，卸点5个，现有铲车7台，卡车20辆。各卸点一个班次的产量要求：矿石漏1.2万吨、倒装场1.3万吨、倒装场1.3万吨、岩石漏1.9万吨、岩场1.3万吨。铲位和卸点位置二维示意图如下，各铲位和各卸点之间的距离（公里）如下表：,各铲位矿石、岩石数量(万吨)和矿石的平均铁含量如下表：,各铲位矿石、岩石数量(万吨)和矿石的平均铁含

16、量如下表：,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;endsetsdata: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

17、.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=su

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

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

20、: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;su

21、m(cai(j):flag(j)=7;,!卸点能力约束;for(xie(i):xnum(i)=xsubject(i)*10000/154);!铁含量约束;sum(cai(j):number(1,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);!整数约

22、束;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全部顶点的树为图G的生成树。生成树上各边的权之和称为该生成树的权。连通图G的权最小的生成树称为图G的最小生成树。许多实际问题都可以归结为最小生成树。如,如何修筑一些公路把若干个城镇连接起来；如何架设

23、通讯网络将若干个地区连接起来；如何修筑水渠将水源和若干块待灌溉的土地连接起来等等。为说明问题,以下面的问题作为范例。范例：假设某电话公司计划在六个村庄架设电话线，各村庄之间的距离如图所示。试求出使电话线总长度最小的架线方案。为了便于计算机求解，特作如下规定：（1）节点V1表示树根；（2）两个节点之间没有线路时，规定两节点之间距离为M（较大的值）MST的整数规划模型如下：,例7.6 最小生成树（Minimal Spanning Tree，MST）问题,这是个给n个人分配n项工作以获得某个最高总效果的问题。第i个人完成第j项工作需要平均时间cij。要求给每个人分配一项工作，并要求分配完这些工作，以

24、使完成全部任务的总时间为最小。该问题可表示如下：,例7.7 分配问题（指派问题，Assignment Problem）,显然，此问题可看作是运输问题的特殊情况。可将此问题看作具有n个源和n个汇的问题，每个源有1单位的可获量，而每个汇有1单位的需要量。从表面看，这问题要求用整数规划以保证xij能取0或1。然而，幸运的是，此问题是运输问题的特例，因此即使不限制xij取0或1，最优解也将取0或1。如果把婚姻看作分配问题，丹茨证明，整数性质证明一夫一妻会带来最美满幸福的生活！显然，分配问题可以作为线性规划问题来求解，尽管模型可能很大。例如，给100人分配100项工作将使所得的模型具有10000个变量。

25、这时，如采用专门算法效果会更好。时间复杂度为O(n2)的匈牙利算法便是好选择，这是由Kuhu（1955）提出的。,model:!7个工人，7个工作的分配问题;sets:workers/w1.w7/;jobs/j1.j7/;links(workers,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:

26、cost=6 2 6 7 4 2 5 4 9 5 3 8 5 8 5 2 1 9 7 4 3 7 6 7 3 9 2 7 2 3 9 5 7 2 6 5 5 2 2 8 11 4 9 2 3 12 4 5 10;enddataend,1.背景 排课问题是将n个班级快速、合理地安排在n个教室里上课。在现实生活中，这是一个普遍存在的问题。表面上看，这个问题似乎很简单，其实也不尽然。教室有大有小，班级也有大有小。当班级总数和教室总数很大时，要想快速、合理、高效地排课也是很困难的。针对这一问题，提出了排课规则，定义了排课“费用”，结合Excel，给出了排课问题的数学模型。利用它，可快速、合理、高效地完

27、成排课任务。2.问题假设 5个班级安排到5个教室里上课，班级人数和教室容量如下。,例7.8 排课模型 PKMX,试求出一个可行、合理、高效的排课方案。,3.排课规则及排课“费用”三个规则：排课规则1：班级人数小于等于教室容量。排课规则2：如果教室总数大于班级总数，要尽可能空出大教室。排课规则3：离差(离差=教室容量一班级人数)和相同情况下，选择离差平方和最小的排课方案。满足上面三个规则的排课方案就是可行、合理、高效的排课方案。为说明排课规则3，请看下面两个排课方案：方案1：班级B1一教室A1，班级B2一教室A2方案2：班级Bl一教室A2，班级B2一教室A1两个方案的离差和都是30。方案1使每个

28、教室都留有一定空间，增加少量学生听课不会有问题方案2中教室A1满员，不能增加任何人。方案1比较合理。两个方案的离差平方和分别是500和900。按照排课规则3，我们就会选择方案1。,4.定义排课“费用”：定义假设第i个班级人数为ai；第j个教室容量为bi(i,j=1,2,3,4,5)。Cij表示第i个班级指定到第i个教室上课的“费用”。则注意：实际问题中，常常会出现班级总数小于教室总数情况。此时可虚设几个班级，令其人数为零，使班级总数等于教室总数。根据以上规则和定义，原问题就成了求解“费用”最小的指派问题。5.模型：排课模型PKMX,6.集合定义了两个基本集合A、B。A表示教室，B表示班级。用A

29、、B产生派生集合AB。7.变量在AB上定义了两个属性C、X。C存放排课“费用”，X是决策变量。若x(ij)=1，则第i个班级指派到第j个教室上课；若x(ij)=0，则第i个班级不指派到第j个教室上课。8.目标求出“费用”最小的排课方案，可用下式描述：min=sum(AB(i,j)：C(i,j)*X(i,j)9.约束：3种。第一种：For(A(i)：sum(B(j)：X(i,j)=1)它限制一个班级只能到一个教室上课。第二种：for(B(j)：sum(A(i)：X(i,j)=1)它限制一个教室只能安排一个班级上课。第三种：.for(A(i)：for(B(j)：BIN(X(i,j)它限制x只取01

30、两个值。,10.数据与解答数据来自文件排课数据.xls，解答也输出到此文件中。排课数据.xls中定义了两个域：“排课数据”域，范围：Sheetl!$c$4：$G$8；“排课方案”域，范围：Sheetl!$C$15：$G$19。“排课数据”域中每个单元的数据是按定义1计算的，具有相类似的计算格式。如：C7=IF(AND(C2=A7,A70)，(C2-A7)$(C2-A7)，100000)从“排课数据”域中输入数据的语句：C=OLE(c：rny documents排课数据.xls，排课数据)解答输出到“排课方案”域的语句：OLE(crny documents悄课数据.xls，排课方案)：X,11.

31、说明(1)模型中的教室总数是5，实际问题中往往教室总数要大得多。例如，假设教室总数是100。这时，只要5改成100即可。同时，文件排课数据.XLS中的两个域的范围要做相应变动。(2当教室总数和班级总数不相等时，可通过虚设教室(或班级)实现相等。此时，虚设教室容量(或班级人数)应为0。例如，假设前面问题中的班级1不存在，可将其人数定为0，相应的解答。由于班级l是虚设的，对应的教室5空出，从表中可知它是可空出的最大教室。,GENPRT（Markowitz投资选择模型）1.背景1952年3月在美国的金融杂志上，Harry M.Markowitz发表了题为“投资选择”的文章。文章论证了如何通过选择那些

32、相关程度不大的投资来减少资产投资的风险。与此同时，为在风险和利润之间建立有利关系，还拟定了一个基本原则：投资多样化。换句话说，就是不要将所有的“鸡蛋”放在一个“篮子”里。理解模型的关键：统计量投资方差。数学上，投资方差：X：用于第i项投资的投资额，若i不等于j，则ij是第i项与第j项的协方差；如果i等于j，则ij是第i项投资的方差。方差：表示利润波动的平均值。方差越大，投资风险就越大。协方差：表示一种股票利润波动与另一种股票利润波动的相关性。协方差较大，则表明一种股票利润的增加很可能会带动另一种股票利润的增加。协方差接近0，则意味着两种股票的利润变化彼此独立。一个负的协方差意味着一种股票利润的

33、增加可能会导致另一种股票利润的减少。Markowitz模型是寻求最小投资方差的投资方案，同时使得所有期望利润总和达到一定水平。,2.问题假设你正在考虑向三种股票进行投资。通过历史资料，计算出了一个期望利润、利润方差、各种股票之间利润的协方差。希望通过向三种而不是一种股票投资来降低风险。计划让利润增加12。则，为达到这一目标并且使投资风险最小，你应该如何分配你的资金向三种股票投资？作为一种安全上的考虑，你规定任何一项单独的投资不得超过投资总额的75。3.模型：Markowitz投资选择模型 GENPRT4.集合定义基本集合ASSETS，三种股票。利用其自乘，派生了一个密集COVMAT，定义协方差矩阵。5.属性定义了4个属性。前3个属性RATE、UB、V存储数据。RATE：存储每一种投资的期望利润，UB：存储投资中用于某一项投资的上限值，V：存储协方差矩阵。注意：协方差矩阵对称。只给出一半即可