与图有关的优化问题

1、优化模型优化模型 -与图有关的优化与图有关的优化一、图的基本知识一、图的基本知识 一个图是由点集一个图是由点集V=vV=vi i 和和V V中元素的无序对的一个中元素的无序对的一个集合集合E=eE=ek k 所构成的二元组，记为所构成的二元组，记为G=(V,E)G=(V,E)，V V中元素中元素v vi i叫做顶点，叫做顶点，|V|V|称为图的顶点数。称为图的顶点数。E E中的元素中的元素e ek k叫做边。叫做边。v1v2v3v4e1e2e3e4e5e6图图1 1 无向图无向图G=(V,E)G=(V,E)V=vV=v1 1,v,v2 2,v,v3 3,v,v4 4 E=eE=e1 1,e,e

2、2 2,e,e3 3,e,e4 4,e,e5 5,e,e6 6 其中：其中：e1=(v1,v1) e2=(v1,v2) e1=(v1,v1) e2=(v1,v2) e3=(v1,v3) e4=(v2,v3)e3=(v1,v3) e4=(v2,v3)e5=(v2,v3) e6=(v3,v4)e5=(v2,v3) e6=(v3,v4)边集边集图图2 2 有向图有向图v1v2v3v4G=(V,E)G=(V,E)V=vV=v1 1,v,v2 2,v,v3 3,v,v4 4 E=eE=e1 1,e,e2 2,e,e3 3,e,e4 4 其中：其中：e1=(v1,v3) e1=(v1,v3) e2=(v1

3、,v4) e2=(v1,v4) e3=(v2,v3) e3=(v2,v3) e4=(v2,v4)e4=(v2,v4)e1e2e3e4弧集弧集 无向图或有向图都用来表示事物之间的关系，在无向图或有向图都用来表示事物之间的关系，在优化中，不严格按照图论知识去研究问题，而是遇到优化中，不严格按照图论知识去研究问题，而是遇到问题根据问题解释边和点的意义。问题根据问题解释边和点的意义。v1v2v3v4e1e2e3e4e5e6图图1 1 无向图无向图链和圈链和圈 在无项图在无项图G=(V,E)中，若中，若G的的某些点和边的交替序列可以拍成某些点和边的交替序列可以拍成）kkkiiiiiiivevevev,.

4、,(12110的形式，且的形式，且ktvvetttiii,.,2 , 1),(1则称这个点边序列为连接则称这个点边序列为连接kiivv ,0的一条链，链长为的一条链，链长为k。例如例如，在图，在图1中，链中，链),(34221vevev就是连接就是连接v1,v3的一条链，的一条链，),(35221vevev也是连接也是连接v1,v3的另一条链。的另一条链。 在给定的链中，如果起点在给定的链中，如果起点和终点相同，则称这条链和终点相同，则称这条链圈圈。例如，在图例如，在图1中，中，v1v2v3v4e1e2e3e4e5e6图图1 1 无向图无向图),(1335221vevevev就是圈。就是圈。

5、在有向图中，类似链的定在有向图中，类似链的定义称为义称为道路道路，类似圈的定义称，类似圈的定义称为为回路回路。二、图的矩阵表示二、图的矩阵表示赋权图赋权图 给定一个图给定一个图G(V,E)G(V,E)，如果对于，如果对于(v(vi i,v,vj j)E)E，赋予一，赋予一个实数个实数w(vw(vi i,v,vj j) )，则称，则称w(vw(vi i,v,vj j) )为边为边(v(vi i,v,vj j) )的权，的权，G G连同连同边上的权称为赋权图。（一般来说，权的意义根据问题边上的权称为赋权图。（一般来说，权的意义根据问题不同，解释不同不同，解释不同：（：（1 1）距离；（）距离；（2

6、 2）费用；（）费用；（3 3）时间；）时间；（4 4）容量；（）容量；（4 4）流量等。图）流量等。图3 3就是一个赋权图。就是一个赋权图。图图3 赋权图赋权图v1v2v3v4v5768394245权矩阵权矩阵 给定赋权图，给定赋权图，G=(V,E)，|V|=n,其边其边(vi,vj)上有权上有权wij,构造构造矩阵矩阵A=(aij)nxn，其中：，其中：EvvEvvwajijiijij),( ,0),( ,图图3 赋权图赋权图v1v2v3v4v5768394245例如，图例如，图3的权矩阵为的权矩阵为0650760844580320430974290A邻接矩阵邻接矩阵 在给定图在给定图G=

7、(V,E)，|V|=n，购造一个矩阵购造一个矩阵A=(aij)nxn，其中：，其中：E),( , 0),( , 1jijiijvvEvva图图3 赋权图赋权图v1v2v3v4v5768394245则称矩阵则称矩阵A为图为图G的的邻接矩阵邻接矩阵。图。图3的邻接矩阵为的邻接矩阵为0110110111110110110111110A 如果图是无向图，如果图是无向图，则邻接矩阵对称，如果则邻接矩阵对称，如果是有向图，邻接矩阵不是有向图，邻接矩阵不一定对称。一定对称。例例1 1 有两个工厂有两个工厂A A1 1,A,A2 2，产量分别等于，产量分别等于9 9，8 8个单位；个单位；四个顾客四个顾客B

8、B1 1,B,B2 2,B,B3 3,B,B4 4，其需求量分别为，其需求量分别为3 3，5 5，4 4，5 5；三个仓库三个仓库M M1 1,M,M2 2,M,M3 3，三个仓库的最大库存量分别为，三个仓库的最大库存量分别为7,6,77,6,7，货物必须从工厂先运往仓库配送到顾客手中。，货物必须从工厂先运往仓库配送到顾客手中。从工厂到仓库，从仓库到顾客的运费单价如下表，求从工厂到仓库，从仓库到顾客的运费单价如下表，求总运费最少的运输方案。总运费最少的运输方案。仓库仓库工厂或顾客工厂或顾客A1 A2 B1 B2 B3 B4M1 1 3 5 7 - 5 M2 2 1 9 6 7 4 M3 - 2

9、 - 6 7 -注：表中注：表中”-”-”表示没有道路连接。表示没有道路连接。 问题分析问题分析 凡是遇到有中转的运输问题，尽可能先画凡是遇到有中转的运输问题，尽可能先画出图来表示产地、中转、销地直接的（道路）连接关系出图来表示产地、中转、销地直接的（道路）连接关系的有向图。的有向图。A1A2M1M2B1M3B2B4B3两个工厂、三个中转、四个顾客的转运问题两个工厂、三个中转、四个顾客的转运问题 变量设置变量设置 aiai：表示第：表示第i i个工厂的产量个工厂的产量,i=1,2;,i=1,2;bjbj：表示第：表示第j j个顾客的需求量个顾客的需求量,j=1,2,3,4;,j=1,2,3,4

10、;mk: mk: 表示第表示第k k个中转的仓库上限个中转的仓库上限,k=1,2,3;,k=1,2,3;XikXik：表示从工厂：表示从工厂i i运到仓库运到仓库k k的运输量；的运输量；YkjYkj：表示从仓库：表示从仓库k k运到顾客运到顾客j j的运输量；的运输量；C1ikC1ik：表示从工厂：表示从工厂i i运到仓库运到仓库k k的单位运费；的单位运费；C2kjC2kj：表示从仓库：表示从仓库k k运到顾客运到顾客j j的单位运费；的单位运费； 建立模型建立模型 总运费最小：总运费最小：31k41jkjkj21i31kikiky2cxc1 min工厂约束：工厂约束：2 , 1i ,ax

11、i31kik中转仓库的约束：中转仓库的约束：3 , 2 , 1k,yx41jkj21iik顾客约束：顾客约束：4 , 3 , 2 , 1j ,byj31kkj特殊道路的要求：特殊道路的要求：, 0yyyx34133113变量约束：变量约束：4 , 3 , 2 , 1j; 3 , 2 , 1k; 2 , 1i , 0y,xkjik数学模型数学模型31k41jkjkj21i31kikiky2cxc1 min2 , 1i ,axi31kik3 , 2 , 1k,yx41jkj21iik4 , 3 , 2 , 1j ,byj31kkj, 0yyyx341331134 , 3 , 2 , 1j; 3 ,

12、 2 , 1k; 2 , 1i , 0y,xkjiks.t.三、最短路径问题三、最短路径问题例例2 2 如下图所示，用点表示城市，现有如下图所示，用点表示城市，现有A,BA,B1 1,B,B2 2，C C1 1,C,C2 2,C,C3 3,D,D共共7 7个城市，点与点之间的连线表示城市之个城市，点与点之间的连线表示城市之间有道路相连，连线旁的数字表示道路的长度。现在间有道路相连，连线旁的数字表示道路的长度。现在计划从城市计划从城市A A到城市到城市D D铺设一条天然气管道，请你设计铺设一条天然气管道，请你设计出最小价格的管道铺设方案。出最小价格的管道铺设方案。AB1B2C1C2C3D7 7个

13、城市间的连接图个城市间的连接图24331231134 变量设置变量设置 n n 表示图的顶点数，假设顶点编号是表示图的顶点数，假设顶点编号是1,2,n;1,2,n;x xijij=1=1，表示弧，表示弧(i,j)(i,j)位于位于1 1到到n n的路上；否则的路上；否则x xijij=0;=0;E) j , i (ijijxwminwij 点点i到到j的距离，即权；的距离，即权；问题分析问题分析设设(k0,e1,k1,km-1,en,kn)为连接为连接1到到n的路径。将的路径。将这条路径上边的权（距离）相加（权和），权和最小这条路径上边的权（距离）相加（权和），权和最小的路径就是最短路径，即目

14、标函数为的路径就是最短路径，即目标函数为模型假设模型假设（）铺设成本与路径长度成正比；（）铺设成本与路径长度成正比；关于关于x xijij的约束：的约束：对于顶点对于顶点1 1的约束的约束, 1xn1jj1对于顶点对于顶点n n的约束的约束, 1xn1iin总要从总要从1 1开始！开始！总要回到总要回到n n！对于既不是对于既不是1 1，又不是，又不是n n的中间点的中间点k k，有，有n, 1k,xxn1jkjn1iik对于中间点对于中间点k k，左边只有一条边进入，右边只有一，左边只有一条边进入，右边只有一条边出发。条边出发。变量约束：变量约束：.E) j, i (,1 ,0 xij数学模

15、型数学模型E) j , i (ijijxwmin, 1xn1jj1, 1xn1iinn, 1k,xxn1jkjn1iik.E) j, i (,1 ,0 xijs.t.AB1B2C1C2C3D24331231134模型计算模型计算（系数格式输入法）（系数格式输入法）sets:sets:dian/a b1 b2 c1 c2 c3 d/:;dian/a b1 b2 c1 c2 c3 d/:;link(dian,dian)/a,b1 a,b2 b1,c1 b1,c2 b1,c3 link(dian,dian)/a,b1 a,b2 b1,c1 b1,c2 b1,c3 b2,c1 b2,c2 b2,c3

16、c1,d c2,d c3,d/:x,w;b2,c1 b2,c2 b2,c3 c1,d c2,d c3,d/:x,w;endsetsendsetsdata:data:w=2 4 3 3 1 2 3 1 1 3 4;w=2 4 3 3 1 2 3 1 1 3 4;enddataenddata(注意：边的顺序和权的顺序一致！注意：边的顺序和权的顺序一致！)min=sum(link:w*x);for(link:bin(x);n=size(dian);sum(link(i,j)|i#eq#1:x(i,j)=1;sum(link(j,i)|i#eq#n:x(j,i)=1;for(dian(k)|k#ne#

17、1#and#k#ne#n: sum(link(i,k):x(i,k)=sum(link(k,i):x(k,i);计算结果的读取：计算结果的读取：Variable Value Reduced Cos N 7.000000 0.000000 X( A, B1) 1.000000 2.000000X( B1, C1) 1.000000 3.000000 X( C1, D) 1.000000 1.000000即最短路径为：即最短路径为：。function D1=Floydf(D)m,n=size(D);for k=2:n+1 for k1=1:n for k2=1:n if k1=k2 D1(k1,k

18、2)=0; else D1(k1,k2)=min(D(k1,k2),D(k1,k-1)+D(k-1,k2); end end end D=D1;end 下面是求图中任意两点间最短距离的下面是求图中任意两点间最短距离的matlab程序，其中程序，其中D为为图的距离矩阵，图的距离矩阵，D1返回任意两点之间的最短距离。返回任意两点之间的最短距离。例例3 设备更新问题设备更新问题 张先生打算购买一辆新轿车，轿车的售价张先生打算购买一辆新轿车，轿车的售价1212万人万人民币，轿车购买后，每年的各种保险、养护费等如表民币，轿车购买后，每年的各种保险、养护费等如表1.1.如果如果5 5年内，张先生将轿车售出

19、，并购买新车，年内，张先生将轿车售出，并购买新车，5 5年内的年内的二手车销售价格如表二手车销售价格如表2 2。请帮助张先生设计一种购买轿。请帮助张先生设计一种购买轿车方案，使车方案，使5 5年内用车的总费用最少。年内用车的总费用最少。表表1 轿车的维护费用轿车的维护费用车龄车龄/年年 0 1 2 3 4费用费用/万元万元 2 4 5 9 12表表2 二手车的售价二手车的售价车龄车龄/年年 1 2 3 4 5费用费用/万元万元 7 6 2 1 0模型假设模型假设（1）张先生任何一年年初都可以卖掉旧车买新车；）张先生任何一年年初都可以卖掉旧车买新车；（2）只是计算当前）只是计算当前5年内的费用。

20、年内的费用。模型设置模型设置C Cij ij 表示第表示第i i年开始到第年开始到第j-1j-1年结束年结束( (第第j j年年初年年初) )的购的购车总消费，即车总消费，即 Cij= Cij=在第在第i i年开始到第年开始到第j-1j-1年的结束的轿车维护费年的结束的轿车维护费用用+ +第第i i年开始购买新车的够买费年开始购买新车的够买费- -在第在第j-1j-1年年末卖出年年末卖出二手车的销售收入二手车的销售收入其中，其中，i=1,2,3,4,j=2,3,4,5,6.i=1,2,3,4,j=2,3,4,5,6. 问题分析问题分析 (凡是设备更新问题，均可以化为最短路径问题凡是设备更新问题

21、，均可以化为最短路径问题) 由于跨越由于跨越5 5年，用年，用6 6个点表示每个年的起始。用个点表示每个年的起始。用任意两点的连线表示从起点到终点所包含的年的花任意两点的连线表示从起点到终点所包含的年的花费，这样就构成了汽车消费费用网络图，如下图费，这样就构成了汽车消费费用网络图，如下图123456c12c13c14c15c16c23c24c25c26c34c35c36c45c46c56C12=12+2-7=7,c13=12+2+4-6=12,C12=12+2-7=7,c13=12+2+4-6=12,c14=12+2+4+5-2=21,C15=12+2+4+5+9-1=31,c14=12+2+

22、4+5-2=21,C15=12+2+4+5+9-1=31,C16=12+2+4+5+9+12-0=44,C16=12+2+4+5+9+12-0=44,C23=7,c24=12,C25=21,C26=31,C23=7,c24=12,C25=21,C26=31,C34=7,c35=12,c36=21,C34=7,c35=12,c36=21,C45=7,c46=12,C45=7,c46=12,同理，有同理，有C56=7,C56=7,1234567777712121212212121313144 数学模型数学模型 EjixniniixxtsxijEijjjiEjijijEjiij),(,1 ,0, 1

23、,0, 11, 1.Cmin6),(16),(1),(ij模型计算模型计算sets:dian/1.6/:;link(dian,dian)/1,2 1,3 1,4 1,5 1,6 2,3 2,4 2,5 2,6 3,4 3,5 3,6 4,5 4,6 5,6/:c,x;endsetsdata:c=7 12 21 31 44 7 12 21 31 7 12 21 7 12 7;enddatamin=sum(link:c*x);n=size(dian);sum(link(i,j)|i#eq#1:x(i,j)=1;sum(link(i,j)|j#eq#n:x(i,j)=1;for(dian(i)|i#

24、ne#1#and#i#ne#n:sum(link(i,j):x(i,j)=sum(link(j,i):x(j,i);for(link(i,j):bin(x(i,j);计算结果计算结果 Global optimal solution found. Objective value: 31.00000 Objective bound: 31.00000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost X( 1, 3) 1.000000 1

25、2.00000 X( 3, 4) 1.000000 7.000000 X( 4, 6) 1.000000 12.00000 即先用两年，再换车用一年，再换车用两年。最即先用两年，再换车用一年，再换车用两年。最小费用为小费用为31万。万。四、最大流问题四、最大流问题例例4 4 现在需要将城市现在需要将城市s s的石油通过管道运送到城市的石油通过管道运送到城市t t，中间有中间有4 4个中转站个中转站v v1 1,v,v2 2,v,v3 3,v,v4 4, ,城市与中转站的连接及城市与中转站的连接及管道容量如图所示，求从城市管道容量如图所示，求从城市s s到城市到城市t t的最大流。的最大流。st

26、v1v2v3v48752995610流量网络图流量网络图这种研究容量的图，一般称为网络。这种研究容量的图，一般称为网络。模型假设模型假设（1）石油从）石油从s点出发，经过连接点出发，经过连接s和和t的任何链形成的的任何链形成的管道都可以运输到管道都可以运输到t；（2）管道的实际流量不超过管道设计的最大容量。）管道的实际流量不超过管道设计的最大容量。符号设置符号设置f(u,v) f(u,v) 边边(u,v)(u,v)管道的流量，管道的流量，Ev)(u,建立模型建立模型从发点从发点s s出发的流量是整个网络图的流量，即出发的流量是整个网络图的流量，即Et)(v,v)(s,t)f(v,v)f(s,m

27、axEf每条边上的流量，都不能超过容量，即每条边上的流量，都不能超过容量，即,E)v,u(),v,u(c)v,u(f对于中间的点对于中间的点u u，流入的流量等于流出的流量，即，流入的流量等于流出的流量，即VvVv)u,v(fv)f(u,ts,uV,u数学模型数学模型Et)(v,v)(s,t)f(v,v)f(s,maxEff,E)v,u(),v,u(c)v,u(fVvVv)u,v(fv)f(u,ts,uV,us.t.模型计算模型计算sets:nodes/1.6/:;hu(nodes,nodes)/1,2 1,3 2,3 2,4 3,5 4,3 4,6 5,4 5,6/:f,c;endsetsd

28、ata:c=8 7 9 5 9 2 5 6 10;enddatamax=flow;flow=sum(hu(i,j)|i#eq#1:f(i,j);for(hu(i,j):bnd(0,f,c);for(nodes(i)|i#ne#1#and#i#ne#6:sum(hu(i,j):f(i,j)=sum(hu(j,i):f(j,i);计算结果计算结果 Global optimal solution found. Objective value: 14.00000 Variable Value Reduced Cost FLOW 14.00000 0.000000 F( 1, 2) 7.000000 0

29、.000000 F( 1, 3) 7.000000 0.000000 F( 2, 3) 2.000000 0.000000 F( 2, 4) 5.000000 -1.000000 F( 3, 5) 9.000000 -1.000000 F( 4, 6) 5.000000 0.000000 F( 5, 6) 9.000000 0.000000结果分析结果分析stv1)v2v3v4(8,7)(7,7)(5,2)(2,0)(9,5)(9,9)(5,5)(6，0)(10,9)将求解的每条管道的流量写在图上，进一步分析将求解的每条管道的流量写在图上，进一步分析 由每条边的由每条边的(c,f)(c,f)值

30、可以看出，只要值可以看出，只要(v(v2 2,v,v4 4) )边扩边扩容一个单位，整个网络流量就会扩大一个单位！瓶颈容一个单位，整个网络流量就会扩大一个单位！瓶颈所在！所在！这种模型专门研究车流量、信息流量、金融这种模型专门研究车流量、信息流量、金融流量、货物流量、汛期河水流量等问题，用以寻找瓶流量、货物流量、汛期河水流量等问题，用以寻找瓶颈所在，以供改造网络！颈所在，以供改造网络！五、最小费用最大流五、最小费用最大流例例6 6 由于输油管道长短不一或者地质等原因，使得每条由于输油管道长短不一或者地质等原因，使得每条管道上运费也不同，因此除了要考虑输油管道的最大流管道上运费也不同，因此除了要

31、考虑输油管道的最大流外，还需要考虑输油管道输送最大流的费用。如图所示外，还需要考虑输油管道输送最大流的费用。如图所示是带有单位运费的网络，其中第一个数字是网络的容量，是带有单位运费的网络，其中第一个数字是网络的容量，第二个数字就是网络的单位费用。第二个数字就是网络的单位费用。stv1v2v3v4(8,2)(7,8)(5,5)(2,1)(9,2)(9,3)(5,6)(6,4)(10,7)最小费用最大流问题最小费用最大流问题 变量设置变量设置 f fijij表示弧表示弧(i,j)(i,j)上的流量上的流量; ;c cijij为弧为弧(i,j)(i,j)上的单位运费，上的单位运费，u uijij为弧

32、为弧(i,j)(i,j)上的容量上的容量; ;Fv Fv 为网络的实际流量为网络的实际流量. .建立模型建立模型E) j , i (ijijfcmin ,ff s.t.vE) j , s (Vjsj,ffvE) t , i (Viitt , sj ,ffE) i , j (VijiE) j , i (Viijijij0fu ,(i, j)E模型计算模型计算dian/s,v1,v2,v3,v4,t/:;hu(dian,dian)/s,v1 s,v2 v1,v2 v1,v3 v2,v4 v3,v2 v3,t v4,v3 v4,t/:c,f,u;endsetsmin=sum(hu(i,j):c(i,

33、j)*f(i,j);sum(hu(i,j)|i#eq#1:f(i,j)=14;n=size(dian);sum(hu(i,j)|j#eq#n:f(i,j)=14;for(dian(i)|i#ne#1#and#i#ne#n:sum(hu(i,j):f(i,j)=sum(hu(j,i):f(j,i);for(hu(i,j):bnd(0,f,u);data:u=8,7,5,9,9,2,5,6,10;c=2,8,5,2,3,1,6,4,7;enddata计算结果计算结果 Global optimal solution found. Objective value: 205.0000 Variable

34、Value Reduced Cost F( S, V1) 8.000000 -1.000000 F( S, V2) 6.000000 0.000000 F( V1, V2) 1.000000 0.000000 F( V1, V3) 7.000000 0.000000 F( V2, V4) 9.000000 0.000000 F( V3, V2) 2.000000 -2.000000 F( V3, T) 5.000000 -7.000000 F( V4, T) 9.000000 0.000000 最小费用为最小费用为205205，流量分布如右图所示，流量分布如右图所示(u,f)(u,f)，其，其

35、中中u u为容量，为容量，f f为流量。为流量。stv1v2v3v4(8,8)(7,6)(5,1)(2,2)(9,7)(9,9)(5,5)(6,0)(10,9) 此模型求的就是网络流量为此模型求的就是网络流量为fvfv时的最小费用，当时的最小费用，当fvfv为最大流量时，所求费用就是最小费用最大流。为最大流量时，所求费用就是最小费用最大流。六、最小生成树问题（最优连线问题）六、最小生成树问题（最优连线问题）例例6 6 我国西部某地区有一个城市（记为我国西部某地区有一个城市（记为1 1）和）和9 9个乡镇个乡镇（记为（记为210210）。该地区不久将用上天然气，其中城市）。该地区不久将用上天然气

36、，其中城市1 1含有井源，现在要设计一个天然气供气系统，使得从含有井源，现在要设计一个天然气供气系统，使得从城市城市1 1到每个乡镇到每个乡镇( (210210) )都有一条管道相连，并且铺设都有一条管道相连，并且铺设管道尽量少，下图给出了该地区地理位置图，表给出了管道尽量少，下图给出了该地区地理位置图，表给出了乡镇之间的距离。乡镇之间的距离。12745869103城镇地理位置图城镇地理位置图2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 8 5 9 12 14 12 16 17 22 9 15 17 8 11 18 14 22 7 9 11 7 12 12 173 1

37、7 10 7 15 188 10 6 15 159 14 8 168 6 1111 1110各城镇之间的距离各城镇之间的距离模型假设模型假设 （1 1）所谓树，就是连通（任意两点有路径相连）的）所谓树，就是连通（任意两点有路径相连）的无圈（回路）的图（可以查一般图论教材或者运筹学无圈（回路）的图（可以查一般图论教材或者运筹学图论部分内容）。对照你看到的野外的任何一棵树的图论部分内容）。对照你看到的野外的任何一棵树的结构对照理解）结构对照理解）符号设置符号设置d dijij：两点：两点i i和和j j之间的距离（成本，费用等）；之间的距离（成本，费用等）；X Xijij: =1: =1表示表示i

38、 i与与j j连接，连接，=0=0表示表示i i与与j j不连接。不连接。（2 2） 并假设定点并假设定点1 1为树的根。为树的根。数学模型数学模型ijijxdminVi , 1i , 1x, 1xs.t.VjijVj1j（至少有一条边从顶（至少有一条边从顶点点1 1连接到其它点）连接到其它点）（除顶点（根（除顶点（根1 1）外，其余）外，其余各点只有一条边进入）各点只有一条边进入）（各边不形成圈）（各边不形成圈）模型求解模型求解sets:dian/1.10/:level; !level(i)表示点表示点i的水平，用来防止生产圈的水平，用来防止生产圈;link(dian,dian):d,x;e

39、ndsetsdata:d=0 8 5 9 12 14 12 16 17 22 8 0 9 15 16 8 11 18 14 22 5 9 0 7 9 11 7 12 12 17 9 15 7 0 3 17 10 7 15 15 12 16 9 3 0 8 10 6 15 15 14 8 11 17 8 0 9 14 8 16 12 11 7 10 10 9 0 8 6 11 16 18 12 7 6 14 8 0 11 11 17 14 12 15 15 8 6 11 0 10 22 22 17 15 15 16 11 11 10 0;enddatan=size(dian);min=sum(l

40、ink(i,j)|i#ne#j:d(i,j)*x(i,j);sum(dian(j)|j#gt#1:x(1,j)1;for(dian(i)|i#gt#1:sum(dian(j)|j#ne#i:x(j,i)=1);for(dian(i)|i#gt#1:for(dian(j)|j#ne#i#and#j#gt#1:level(j)level(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i);for(dian(i)|i#gt#1:level(i)level(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i);for(dian(i):level(i)-

41、1+(n-2)*x(i,1);for(link:bin(x);计算结果表达如下图计算结果表达如下图 Global optimal solution found at iteration: 8002 Objective value: 73.00000X( 1, 2) X( 2, 6) X( 1, 2) X( 2, 6) X( 3, 1) X( 4, 8)X( 3, 1) X( 4, 8)X( 5, 4) X( 6, 5) X( 5, 4) X( 6, 5) X( 7, 3) X( 8, 10)X( 7, 3) X( 8, 10)X( 9, 7) X( 10, 9)X( 9, 7) X( 10,

42、9)12745869103八、工程工期问题八、工程工期问题 PERT(program evaluation and review technique，计划评审法）和，计划评审法）和CPM(critial path method,关键路线法关键路线法)是网络计划的重要组成部分，在是网络计划的重要组成部分，在国外称为国外称为PERT/CPM，在国内称为统筹方法，在国内称为统筹方法（scheduling method）。）。案例案例 某人想泡茶喝，必须得做如下作业（工作）才能某人想泡茶喝，必须得做如下作业（工作）才能实现：拿茶叶（实现：拿茶叶（1分钟），洗茶壶（分钟），洗茶壶（3分钟），向茶壶分钟）

43、，向茶壶加水（加水（1分钟），烧开水（分钟），烧开水（10分钟），洗茶杯（分钟），洗茶杯（2分分钟），泡茶叶（钟），泡茶叶（2分钟），那么此人最短多少分钟后才分钟），那么此人最短多少分钟后才能喝到泡好的茶水？能喝到泡好的茶水？计划网络图的概念计划网络图的概念（1）作业（工作）、事件）作业（工作）、事件：称任何消耗时间和资源的：称任何消耗时间和资源的行动为行动为作业作业，称作业的开始或结束为，称作业的开始或结束为事件事件，事件本身不，事件本身不消耗时间和资源。工作一般用消耗时间和资源。工作一般用带字母的箭线带字母的箭线来表示，事来表示，事件一般用件一般用带数字的圈带数字的圈来表示。来表示。 在泡

44、茶的案例中，用字母表示各个工作，并把各在泡茶的案例中，用字母表示各个工作，并把各个工作的相互关系整理成下表个工作的相互关系整理成下表作业作业 时间（时间（min）说明说明作业作业时间时间（min）说明说明A1拿茶叶拿茶叶D10烧水烧水B3洗茶壶洗茶壶E2洗茶杯洗茶杯C1加水加水F2泡茶叶泡茶叶（2）理清各个作业的前行后继关系（前后顺序）理清各个作业的前行后继关系（前后顺序） 工作工作i必须在工作必须在工作j完成后才能开始，称工作完成后才能开始，称工作j为工作为工作i的紧的紧前工作，或者工作前工作，或者工作i为工作为工作j的紧后工作。的紧后工作。作业作业时间（时间（min）说明说明作业作业时间时间（min）说明说明A1拿茶叶拿茶叶D10烧水烧水B3洗茶壶洗茶壶E2洗茶杯洗茶杯C1加水加水F2泡茶叶泡茶叶 上面泡茶的案例中，各个作业的紧前作业如下表（上面泡茶的案例中，各个作业的紧前作业如下表（- 表示前表示前面没有作业）面没有作业）作业作业时间（时间（min）紧前作业紧前作业作业作业时间时间（min）紧前作业紧前作业A1-D10CB3-E2-C1BF2A,D,E （3）绘制网络计划图）绘制网络计划图 根据各个工序的前行后继关系，绘制网络图，要根据各个工序的前行后