最小生成树-数学建模-文档资料

1、123赵根赵根赵明赵明赵亮赵亮赵丽赵丽赵雷赵雷赵虹赵虹赵雨赵雨赵霞赵霞赵云赵云赵梅赵梅赵松赵松类似于自类似于自然界中的然界中的树树形象地表形象地表示家族示家族4 56123458691571037生成树或支撑树12345869157103如何简便地得到左图的生成树？它应有几条边？8确定应在哪些站点之间铺设通讯线路，是否可看作是在相应的加权图中构造最小费用的生成树的问题？9最小生成树最大生成树1011如果生成树如果生成树*T 的权的权)(*Tw是是G的所有生成树的权中最的所有生成树的权中最小者，则称小者，则称*T 是是G的的最小生成树最小生成树 ，简称为，简称为 最小树最小树，即，即)(min)

2、(*TwTwT=，式中取遍，式中取遍G的所有生成树的所有生成树T. 定义定义设设),(1EVT =是赋权图是赋权图),(EVG =的一棵生的一棵生成树，称成树，称T中全部边上的权数之和为中全部边上的权数之和为生成树的权生成树的权，记为，记为)(Tw，即，即=1)()(EeewTw. 12最小生成树算法及其MATLAB程序实现131324586915710314 1) 选择边选择边e1，使得，使得w(e1)尽可能小；尽可能小；2) 若已选定边若已选定边 ，则从，则从ieee,.,21,.,21ieeeE中选取中选取 ，使得，使得:1iei) 为无圈图，为无圈图，,.,121ieeeG ii) 是

3、满足是满足i)的尽可能小的权，的尽可能小的权，)(1iew 3) 当第当第2)步不能继续执行时，则停止步不能继续执行时，则停止. 步骤步骤定理定理 由由Kruskal算法构作的任何生成树算法构作的任何生成树,.,121*=eeeGT都是最小生成树都是最小生成树.1512345839157106B: 图的边权矩阵图的边权矩阵;T: 生成树的边集生成树的边集;C: 生成树的权生成树的权;t: 顶点所属子树的编号顶点所属子树的编号1712345869157103b=1 1 1 2 2 3 3 4; 2 4 5 3 5 4 5 5; 8 1 5 6 7 9 10 3;19123456173202122

4、2324机器机器 123456789加工加工的零的零件件2,3,7,8,9,12,132,7,8,11,121,63,5,103,7,8,9,12,1354,104,10625|MM|MM|) j , i (jiji=建模|MM|MM|) j , i (jiji=建模 1) 1) (i,j)=0(i,j)=0和和 (i,j)=1(i,j)=1分别分别表示什么？表示什么？2) 2) 表达了什么？表达了什么？27建模模型求解912547863.51.5.14.87.67.750912547863.5.5.14.67.75030 你能给出对应于该机器分组的零件分类吗？912547863.5.5.14

5、.67.750模型结果31 设是两点设是两点i与与j之间的距离，或之间的距离，或1（1表示连接，表示连接，0表示不连接），并假设顶点表示不连接），并假设顶点1是生成树的根是生成树的根.则则ijd0ijx=( , )1min ; s.t. 1,() 1,1,() ijiji jAjj Vjij Vd xxxi=根至少有一条边连接到其他边除根外，每个点只有一条边进入（各边不构成圈） 32例例 （最优连线问题）我国西部的（最优连线问题）我国西部的SV地区共有地区共有1个城市（标个城市（标记为记为1）和）和9个乡镇（标记为个乡镇（标记为2-10）组成，该地区不久将用）组成，该地区不久将用上天然气，其中

6、城市上天然气，其中城市1含有井源含有井源.现要设计一供气系统，使得现要设计一供气系统，使得从城市从城市1到每个乡镇（到每个乡镇（2-10）都有一条管道相连，并且铺设）都有一条管道相连，并且铺设的管子的量尽可能的少的管子的量尽可能的少. 下表给出了城镇之间的距离下表给出了城镇之间的距离.求求SV地区的最优连线地区的最优连线.3334 解：解： 按照数学规划写出相应的按照数学规划写出相应的LINGO程序，程序，MODEL: 1 sets: 2 cities/1.10/:level; !level(i)= the level of city; 3 link(cities, cities): 4 di

7、stance, !The distance matrix; 5 x; ! x(i,j)=1 if we use link i,j; 6 endsets 35 7data: !Distance matrix, it need not be symmetirc; 8 distance = 0 8 5 9 12 14 12 16 17 22 9 8 0 9 15 16 8 11 18 14 22 10 5 9 0 7 9 11 7 12 12 17 11 9 15 7 0 3 17 10 7 15 15 12 12 16 9 3 0 8 10 6 15 15 13 14 8 11 17 8 0 9

8、14 8 16 14 12 11 7 10 10 9 0 8 6 11 15 16 18 12 7 6 14 8 0 11 11 16 17 14 12 15 15 8 6 11 0 10 17 22 22 17 15 15 16 11 11 10 0; 18 enddata36 19n=size(cities); !The model size; 20! Minimize total distance of the links; 21min=sum(link(i,j)|i #ne# j: distance(i,j)*x(i,j); 22!There must be an arc out of

9、 city 1; 23sum(cities(i)|i #gt# 1: x(1,i)=1; 24!For city i, except the base (city 1); 25for(cities(i) | i #gt# 1 : 26! It must be entered; 27 sum(cities(j)| j #ne# i: x(j,i)=1; 28! level(j)=levle(i)+1, if we link j and i;37 29 for(cities(j)| j #gt# 1 #and# j #ne# i : 30 level(j) = level(i) + x(i,j)

10、31 - (n-2)*(1-x(i,j) + (n-3)*x(j,i); 32 ); 33! The level of city is at least 1 but no more n-1, 34 and is 1 if it links to base (city 1); 35 bnd(1,level(i),999999); 36 level(i)=n-1-(n-2)*x(1,i); 37 ); 38! Make the xs 0/1; 39for(link : bin(x); END38利用水平变量利用水平变量(level)来保证所选的边不构成圈来保证所选的边不构成圈.Global optimal solution found at iteration: 34Objective value: 60.00000 Variable Value Reduced Cost X( 1, 2) 1.000000 8.000000 X( 1, 3) 1.000000 5.000000 X( 3, 4) 1.000000 7.000000 X( 3, 7) 1.000000 7.000000 X( 4, 5) 1.000000