数学建模提高班专题六网络优化模型及案例分析资料

数学建模提高班专题六网络优化模型及案例分析资料第1页/共96页从农夫怎样过河谈起农夫过河独木桥一般过河问题的解决策略选课问题第2页/共96页农夫过河3第3页/共96页农夫过河摆渡人F狼W羊G菜C4第4页/共96页

南岸状态：

16种，其中WG,GC,WGC，从而FC,FW,F为不允许状态，FWGCFWGFWCFGCFGOCGWWC10个允许状态：农夫过河5第5页/共96页FWGCFWGFWCFGCFGOCGWWC寻求图中从顶点“FWGC”到顶点“O”的最短路径，这样的路径有几条？求出最优的渡河方案。想语言描述时未显示的关系跃然纸上农夫过河6第6页/共96页FWGCFWGFWCFGCFGOCGWWCFWGCFWGFWCFGCFGOCGWWC农夫过河7第7页/共96页独木桥8第8页/共96页一般过河问题的解决策略多少种状态状态如何转换花的时间怎么计算最后求什么9第9页/共96页选课问题学校要为一年级的研究生开设六门基础数学课：统计(S)，数值分析(N)，图论(G)，矩阵论(M)，随机过程(R)和数理方程(P)。按培养计划，注册的学生必须选修其中的一门以上，你作为教务管理人员，要设法安排一个课表，使每个学生所选的课程，在时间上不会发生冲突。10第10页/共96页选课问题11第11页/共96页选课问题为什么会出现时间上的冲突？时间冲突的本质是什么？如何表示课程在时间上冲突？如果把一门课程看成图中的顶点，那么连接两点的边表示什么？12第12页/共96页SNGRPM‡完成上述表示课程冲突关系的线图直观、清晰地表达已知信息的方式13第13页/共96页图是一种思考问题的方法图有两个基本要素--顶点和边顶点表示事物边表示两个事物之间的关系增加第三个要素--边的权值可以表示关系深浅、大小、重要等程度用图来思考问题本质是考虑事物之间的联系14第14页/共96页图是一种思考问题的方法图可以画出来v1v2v5v6v7v4v3abjkcghidfe15第15页/共96页图是一种思考问题的方法图也可以用矩阵来表示，最常用的是邻接矩阵v1v2v5v6v7v4v3abjkcghidfe16第16页/共96页邻接矩阵的优点：容易理解容易转换为具体的图便于计算机编程计算图是一种思考问题的方法17第17页/共96页最短路问题固定起点的最短路每对顶点之间的最短路选址问题第18页/共96页固定起点的最短路最短路是一条路径，且最短路的任一段也是最短路．

假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树．

因此,可采用树生长的过程来求指定顶点到其余顶点的最短路．19第19页/共96页20第20页/共96页算法步骤：21第21页/共96页

TOMATLAB(road1)22第22页/共96页23第23页/共96页

12

34

5

6

7

824第24页/共96页每对顶点之间的最短路1．求距离矩阵的方法2．求路径矩阵的方法3．查找最短路路径的方法（一）算法的基本思想（三）算法步骤25第25页/共96页算法的基本思想26第26页/共96页算法原理——求距离矩阵的方法27第27页/共96页算法原理——求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R．即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径．)(nR28第28页/共96页i

j算法原理——

查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：29第29页/共96页算法步骤30第30页/共96页

TO

MATLAB

(road2(floyd))31第31页/共96页

选址问题--中心问题

TOMATLAB

(road3(floyd))32第32页/共96页S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处.33第33页/共96页

选址问题--重心问题34第34页/共96页最小生成树问题树图最小生成树Kruskal算法Prim算法第35页/共96页赵根赵明赵亮赵丽赵雷赵虹赵雨赵霞赵云赵梅赵松树图——直观形象的表示工具类似于自然界中的树形象地表示家族36第36页/共96页树：

没有圈的连通图

树中任意两点间有唯一路径。

树的边数恰好为顶点数减1。

树图——直观形象的表示工具37第37页/共96页

城市电信局有许多业务如收费，营业，112，114等，希望在全市范围实现计算机联网服务，共享各种资源。一个主要关心的问题是：用数据通讯线把一组站点联结起来，而不允许通讯线在非站点处相交，如何连接可使通讯线的花费最小？引例：计算机网络的线路设计38第38页/共96页12345869157103引例：计算机网络的线路设计最经济的网络不应该有任何封闭的回路。39第39页/共96页引例：计算机网络的线路设计生成树或支撑树(spanningtree)：G的子图且是树，其顶点集等于G的顶点集；12345869157103如何简便地得到左图的生成树？它应有几条边？想40第40页/共96页确定应在哪些站点之间铺设通讯线路，是否可看作是在相应的加权图中构造最小费用的生成树的问题？引例：计算机网络的线路设计41第41页/共96页最小生成树最大生成树引例：计算机网络的线路设计想1)一个完全图Kn有多少不同的生成树？2)如何求其最小生成树?42第42页/共96页

10个顶点的完全图，其不同的生成树就有一亿棵。一般地，n个顶点的完全图，其不同的生成树个数为nn-2。

30个顶点的完全图就有3028个生成树，求最小生成树时用穷举法是无效的。引例：计算机网络的线路设计43第43页/共96页最小生成树与算法如果生成树*T的权)(*Tw是G的所有生成树的权中最小者，则称*T是G的最小生成树，简称为最小树，即)}({min)(*TwTwTå=，式中取遍G的所有生成树T.

定义设),(1EVT=是赋权图),(EVG=的一棵生成树，称T中全部边上的权数之和为生成树的权，记为)(Tw，即åÎ=1)()(EeewTw.

44第44页/共96页Prim算法Kruskal算法最小生成树算法及其MATLAB程序实现算法的MATLAB程序实现45第45页/共96页基本思想:

最初把图的n个顶点看作n个分离的部分树，每个树具有一个顶点，算法的每一步选择可连接两分离树的边中权最小的边连接两个部分树，合二为一,部分树逐步减少，直到只有一个部分树（n-1步之后）便得到最小生成树。Kruskal算法13245869157103时间复杂度:O(m)其中m为图的边数46第46页/共96页Kruskal算法1)选择边e1，使得w(e1)尽可能小；2)若已选定边，则从中选取，使得:i)为无圈图，ii)是满足i)的尽可能小的权，3)当第2)步不能继续执行时，则停止.

步骤定理

由Kruskal算法构作的任何生成树都是最小生成树.47第47页/共96页Kruskal算法123458391571061号子树

2号子树

3号子树给每个子树一个不同的编号48第48页/共96页初始化：j0,T,c0,k0；对所有顶点i,t(i)i.jj+1t(B(1,j))t(B(2,j))TT(B(1,j),B(2,j)),cc+B(3,j),kk+1，i0t(i)=max{t(B(1,j)),t(B(2,j))t(i)min{t(B(1,j)),t(B(2,j)),k=n-1或j=mT,c整理边权矩阵NYi=n终止NYYii+1NYNB:图的边权矩阵;T:生成树的边集;C:生成树的权;t:顶点所属子树的编号第49页/共96页Kruskal算法

例:用Kruskal算法求引例中的加权图的最小生成树。12345869157103b=[11122334;24535455;815679103];边权矩阵：50第50页/共96页b=[11122334;24535455;815679103];[B,i]=sortrows(b',3);B=B’;m=size(b,2);n=5;t=1:n;k=0;T=[];c=0;fori=1:mift(B(1,i))~=t(B(2,i))k=k+1;T=[T,B(1:2,i)];c=c+B(3,i);%修改过tmin=min(t(B(1,i)),t(B(2,i)));tmax=max(t(B(1,i)),t(B(2,i))); forj=1:n ift(j)==tmax t(j)=tmin;endendend

ifk==n-1break;endendT,c第51页/共96页程序运行结果：T=14452325c=17Kruskal算法12345617352第52页/共96页Prim算法●

基本思想：任选一个顶点v0开始，连接与v0最近的顶点v1,得子树T1，再连接与T1最近的顶点v2得子树T2，如此继续下去，直到所有顶点都用到为止。●

时间复杂度：O(n2),n为图的顶点数53第53页/共96页Prim算法54第54页/共96页提示Kruskal算法和Prim算法都蕴涵了贪婪法的思想，是贪婪法；贪婪法的基本思想：把解看成是由若干个部件构成，每一步求出解的一个部件（不是从整体或长远的角度考虑，只是局部或当前的最好选择）。求出的一个个部件组合而作为最终的解。55第55页/共96页贪婪法可被用于各种各样问题的处理。该法只是一种试探法，计算上简便有效，可提供正确解的一个近似。但一般情况下，不能保证输出的解是正确的。其正确性需要证明，这往往比较困难。已证明,求最小生成树的Kruskal算法和Prim算法都是正确的

注意56第56页/共96页

分组技术是设计制造系统的一种方法，它把生产零件的机器分组，相应地把需生产的零件分类，使零件跨组加工的情形尽量少，最理想的情况是使每个零件的加工，都在组内完成。假设有13种零件，需在9台机器上加工。在各台机器上加工的零件号在下表中给出。范例：制造系统的分组技术57第57页/共96页范例：制造系统的分组技术机器123456789加工的零件2,3,7,8,9,12,132,7,8,11,121,63,5,103,7,8,9,12,1354,104,10658第58页/共96页

设用Mi表示需由机器i加工的零件集，对任意两台机器i,j,定义相异度：范例：制造系统的分组技术建模59第59页/共96页“”：对称差，分子：在机器i但不在机器j上加工，或在机器j但不在机器i上加工的零件数。分母：或在机器i，或在机器j上加工的零件数。显然01建模1)(i,j)=0和(i,j)=1分别表示什么？2)表达了什么？想第60页/共96页构造加权图

以机器为顶点，作一个完全图，每条边(i,j)被赋予权(i,j)。原问题的转化加权图的最小生成树是由那些相异度最小的边构成的连通图，如果希望把机器分成k个组，就继续删去最小生成树上权最大的k-1条边。于是得到k个分离的子树，每棵树的顶点集就构成各机器组。建模61第61页/共96页对表1给出的数据，加权图的边权矩阵如下：[111111112222222333333444445555666778;234567893456789456789567896789789899;0.510.890.141111110.621111111110.50.870.670.750.7511111111011]

用Kruskal算法可求出最小生成树，在前面给出的Kruskal算法的MATLAB程序中，边权矩阵b的值改为此处的边权矩阵，顶点数n改为9即可。模型求解第62页/共96页T=7815123946474513c=4.4300912547863.51.5.14.87.67.750机器的分组：{3，9}，{1，2，5}，{4，6，7，8}。912547863.5.5.14.67.750第63页/共96页

你能给出对应于该机器分组的零件分类吗？机器的分组：{3，9}，{1，2，5}，{4，6，7，8}。912547863.5.5.14.67.750想模型结果64第64页/共96页

设是两点i与j之间的距离，或1（1表示连接，0表示不连接），并假设顶点1是生成树的根.则最小生成树问题的0-1规划模型65第65页/共96页最小生成树问题的0-1规划模型例（最优连线问题）我国西部的SV地区共有1个城市（标记为1）和9个乡镇（标记为2--10）组成，该地区不久将用上天然气，其中城市1含有井源.现要设计一供气系统，使得从城市1到每个乡镇（2--10）都有一条管道相连，并且铺设的管子的量尽可能的少.下表给出了城镇之间的距离.求SV地区的最优连线.66第66页/共96页最小生成树问题的0-1规划模型67第67页/共96页最小生成树问题的0-1规划模型

解：按照数学规划写出相应的LINGO程序，MODEL:1]sets:2]cities/1..10/:level;!level(i)=thelevelofcity;3]link(cities,cities):4]distance,!Thedistancematrix;5]x;!x(i,j)=1ifweuselinki,j;6]endsets

68第68页/共96页最小生成树问题的0-1规划模型

7]data:!Distancematrix,itneednotbesymmetirc;8]distance=08591214121617229]809151681118142210]5907911712121711]91570317107151512]12169308106151513]14811178091481614]12117101090861115]161812761480111116]1714121515861101017]2222171515161111100;18]enddata69第69页/共96页最小生成树问题的0-1规划模型

19]n=@size(cities);!Themodelsize;20]!Minimizetotaldistanceofthelinks;21]min=@sum(link(i,j)|i#ne#j:distance(i,j)*x(i,j));22]!Theremustbeanarcoutofcity1;23]@sum(cities(i)|i#gt#1:x(1,i))>=1;24]!Forcityi,exceptthebase(city1);25]@for(cities(i)|i#gt#1:26]!Itmustbeentered;27]@sum(cities(j)|j#ne#i:x(j,i))=1;28]!level(j)=levle(i)+1,ifwelinkjandi;70第70页/共96页最小生成树问题的0-1规划模型29]@for(cities(j)|j#gt#1#and#j#ne#i:30]level(j)>=level(i)+x(i,j)31]-(n-2)*(1-x(i,j))+(n-3)*x(j,i);32]);33]!Thelevelofcityisatleast1butnomoren-1,34]andis1ifitlinkstobase(city1);35]@bnd(1,level(i),999999);36]level(i)<=n-1-(n-2)*x(1,i);37]);38]!Makethex's0/1;39]@for(link:@bin(x));END71第71页/共96页最小生成树问题的0-1规划模型利用水平变量(level)来保证所选的边不构成圈.Globaloptimalsolutionfoundatiteration:34Objectivevalue:60.00000VariableValueReducedCostX(1,2)1.0000008.000000X(1,3)1.0000005.000000X(3,4)1.0000007.000000X(3,7)1.0000007.000000X(4,5)1.0000003.000000X(5,8)1.0000006.000000X(7,9)1.0000006.000000X(9,6)1.0000008.000000X(9,10)1.00000010.0000072第72页/共96页最小生成树问题的0-1规划模型连接这10个城镇的最小距离为60公里，其连接情况如下.SV地区的