《最佳灾情巡视路线模型》由会员分享，可在线阅读，更多相关《最佳灾情巡视路线模型（9页珍藏版）》请在金锄头文库上搜索。
1、word最优灾情巡视路线模型【摘要】“图论是组合数学的分支，它与其他的数学分支，如群论、矩阵论、拓扑学，数值分析有着密切的联系。在其它科学领域，如计算机科学、运筹学、电网络分析、化学物理以与社会科学等方面图论也具有越来越重要的地位，并已取得丰硕的成果。而且，图论的理论和方法在数学建模中也有重要应用。本文概述了一些常用的图论方法和算法，并通过举例灾情巡视路线说明其在数学建模中的应用。【关键词】图论灾情巡视Hamilton回路 数学模型预备知识定义1 完全图：如果图G中每一对不同的顶点恰有一条边连接，如此称此图为完全图。定义2 连通图：如果对图G=V，E的任何两个顶点u与v，G中存在一条u-v路。
2、如此称G是连通图。定义3 加权图：边上有数的图称为加权图。在加权图中，链迹、路的长度为链迹、路上的所有边的权植的和。定义4 Hamilton回路：图G中的一个回路C称为一个Hamilton回路如果C含有G的所有顶点。含有Hamilton回路的图称为Hamilton图。定义5 欧拉回路：经过图G的每条边的迹称为欧拉迹，如果这条迹是闭的，如此称这条闭迹为G的欧拉回路。一 数学建模中常用的图论方法1 迪克斯特拉算法Dijkstra在加权图中，我们经常需要找出两个指定点之间的最短路，通常称为最短路问题。解决最短路问题的方法之一就是迪克斯特拉算法。假定P：VVVVV是从V到V的最短路，如此它的子路VV一
3、定是从V到V的最短路。否如此从V出发沿路p走到V，,然后沿V到V的最短路走到V再沿路P从V到V，这样得到一条新的从V出发到V的路，其长度小于P，与P是最短路的假设矛盾。设G为所有权都为正数的加权连通简单图。G带有顶点a=V, V , V=z,权W(V, V) ,假如(V, V)不是G中的边，如此W(V, V) =for i=1 to nL(V)= L(a)=0S=(初始化标记，a的标记为0，其它结点标记为，S 为空集)当z不属于S时 begin u=不属于S的Lu最小的一个顶点S=Su对所有不属于S的顶点Vif L(u)+W(u,v)L(v) then L(v)=L(u)+L(u,v) (这样
4、就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记)End (L(z)表示从a到z的最短路的长度) 这个算法经过n-1次循环后必定完毕，计算量为1/2n-1(n-2)，因而是个有效算法。2最邻近算法最邻近算法起源于旅行推销员问题，该问题实际上是求加权完全无向图中的访问每个顶点恰好一次且返回出发点的总权数最小的闭路，又称为最优Hamilton回路。如果我们将加权图中的结点看作城市，加权看作距离，旅行推销员问题就成为找出一条最短路线，使得旅行推销员从某个城市出发，沿着这条路线遍历每个城市一次最后再回到出发的城市。2.2 算法设G=V，E是一个赋权完全图，根据实际问题作如下规定：对VG中的任何
5、三个顶点U，V和X，满足WUV+WVXWUX（1） 任选一个顶点V作起点，找一条与V关联其权最小的一条边e, e的另一个端点记为V，得一条路V V；（2） 设已选出路V VV,在VG- V，VV中取一个与V最近的相邻顶点V,得V VVV；（3） 假如i+1P(G)-1,用i代i+1返回2，否如此记C= V VV V.停止。最后得到的C就是G的一条近似Hamilton回路。改良方法设C= V VV V是G的一个Hamilton回路。假如存在i,j适合1i+1jp,并且有WVV+W(VV)W(VV)+W(VV)如此Hamilton回路为C= VVVVVVVVV它是由C删去边VV和VV添加边V V和
6、V V而得到的其权和WC=W(C)-W(VV)-W(VV)+W(VV)+W(VV)W(C)因而Hamilton回路C将是一个改良。3弗来里算法Fleury邮递员从邮局出发，沿着邮路的每条街道分送信件，最后回到邮局。在这一过程中，邮递员希望以尽可能少的行程完成投递任务。这类问题首先由我国的管梅谷先生于1962年提出，故国际上称为中国邮递员问题。用图论语言来描述：一个连通加权图GV，E，W，每一条边代表邮路中的每一条街道，每个顶点表示两条街道间的交叉点，每边的权表示街长。要找一条从邮局出发的回路，使之包含G的每一边至少一次，且该回路的权达到最小。（1） 任意取一个顶点V，令W=V；（2） 假定迹W
7、= V e VeV已经选出，那么用如下方法从EG- e,e , , e中选取e: e与V相连；除非没有别的边可选择，e不是G= e, e, , e的割边；3当2不能执行时，停止。否如此让i+1 i.,转2。二 图论方法的应用举例灾情巡视路线模型1 问题重述某县的乡村公路网示意图。今年夏天该县遭受水灾，为考察灾情，组织自救，县领导决定带领有关部门负责人到全县各乡村巡视。现要求建立数学模型解决以下问题：1假如分三路巡视，试设计各路的巡视路线，使其总路线最短且尽可能均衡；2假定巡视人员在各乡停留时间为T=2小时，在各村停留时间为t=1小时，汽车行使速度V=35千米/小时。要在24小时内完成巡视，至少
8、应分几组？给出分组下你认为最优的巡视路线。2 模型假设1所有乡、村和县政府所在地均为图中节点；2各乡、村最多被经过两次，并且只被一组巡视人员巡视一次；3交通工具只有汽车，巡视人员不采用步行或其他方式；4汽车行使速度不受天气，路况等客观因素影响，速度恒定；5巡视人员除在乡、村停留外，不做其他休息。3 模型的建立和求解3.1.1理论模型这是一个典型的旅行推销员问题,即推销员从驻地出发经所要去的城市至少一次返回原地，应如何安排旅行路线，使总的旅行距离最短。由于原图是加权连通图，图G的顶点Vi表示本县的各个乡A，B，R和村1，2，35。每两个顶点V, V间都生成一条边V, V,边的权植为这两个顶点间的
9、最短路径长度D。假如原图两顶点之间并无直接边相连，如此取这两点间按Dijkstra算法生成的最短路径。巡视人员在原图中巡视的顶点顺序按这条Hamilton回路，即为最短的巡视路线。由于图G是一完全图，图中必然存在N-1/2条Hamilton回路N为图G的顶点数，其中最短的那条就是路程最短的巡视路线。3.1.2 最邻近算法任选一个顶点V作起点，找一条与V关联其权最小的一条边e, e的另一个端点记为V得一条路C= V V；设已选出路V VV,在VG- V，V，V中取一个与V最近的相邻顶点V得V VV V；假如i+1N(G)-1,用i代i+1返回，否如此记C= V VV V.停止。最后得到的C就是G
10、的一条近似Hamilton回路。运用本算法与其改良，即可得最短的Hamilton回路为： C=O.1,B,C,3,2,5,M,6,7,D,4,8,E,9,F,10,12,H,14,13,G,11,J,19,20,25,21,K,18,I,15,16,17,22,23,24,N,26,27,28,Q,30,32,35,34,A,33,31,R,29,P,O,其总长度千米。计算过程与图见附录对于分三路巡视，我们可以将其等价地看成一路巡视人员在巡视过程中三次从县政府出发和返回。于是我们将县政府顶点O连同其相连的边一起复制两次，得到两个虚拟的顶点O、O。将O、O参加到图G中，形成新图G，再运用上述求最
11、短Hamilton回路的算法在G中找到最短Hamilton回路。于是这三条Hamilton回路分别为C=C，C= O,1, O,C= O,2, O(其中1，2为与顶点O相连的边)。总路线为千米。显然这样得到的C、C、C虽然满足总路程最短,却极不均衡，下面给出改良方案。3.3.1 划分子图要使三路尽可能均衡,应使每条巡视路线经过的顶点数目根本一样。由于地图中的乡村分布密度较均匀,因此可以将地图去掉某些边后分为面积根本一样的三个子图G、G、G,且这三个子图都应包含县政府O。由于要满足总路程最短,因此三个子图应尽量不互相覆盖。这样的G、 G、 G应成花瓣形。3.3.2 分别求解对G、 G、 G分别用
12、中算法求得最短巡视路线D、D、D,其长度分别为S(D)、S(D)、S(D)。3.3.3 调整比拟S(D),S(D),S(D).的大小,将长度较大的子图中某些顶点适当调整至长度较小的子图中，假如路径根本一样如此完毕。这样就可以得到满足一定均衡性的三条Hamilton回路,其总巡视路程S=S(D)+S(D)+S(D)。由于D、 D、 D分别是子图G、 G、 G中的最优解,故D、D、D是这种子图划分下的最优解。 D= O，2，5，6，7，E，11，G，13，14，H，12，F，10，F，9，8，4，D，3，2，O(其中F被经过两次,但只巡视一次);D=O，P，26，N，24，23，21，K，22，1
13、7，16，I，15，I，18，J，19，L，20，25，M，O (其中I被经过两次,但只巡视一次);D=O，1，C，B，34，35，32，31，33，A，R，29，Q，30，Q，28，27，26，P，O (其中Q被经过两次,但只巡视一次,26和P只是被经过,但不被巡视); S(D千米 S(D千米 S(D千米S= S(D)+ S(D)+ S(D千米图见附录3.4假定巡视人员在各乡停留时间为T=2小时，在各村停留时间为t=1小时，汽车行使速度V=35千米/小时。要在24小时内完成巡视，至少应分几组？给出分组下你认为最优的巡视路线3.4.1 人员在各乡,村的停留时间T,t转化成完全图G中边的权值的增
14、长：t=由图可知有17个乡,35个村,因此停留时间为172+351=69小时,将其转化为边的权值的增长d,如此d=3569=2415千米于是巡视总路线为千米小时要在24小时内完成巡视,如此至少需要 84.5/24 =4组3.4.2 分四组的情况下24小时内完成巡视的最优巡视路线将G划分为4个子图；的权值的增长d,如此按前面的算法逐步求解得下面一组解：图见附录L=O，C ，3，D，4，8，E，9，F，10，F，9，E，7，6，5，2，O (其中E，9，F经过两次，但只巡视一次) S千米 T小时L=O，2，5，6，7，E，11，G，12，H，14，13，J，19，L，20，25，M，O其中2，5，
15、6，7，E只被经过，不作巡视S千米 T小时L=O，M，25，21，K，18，I，15，I，16，17，22，23，24，N，26，P，O 其中I被经过两次，但只巡视一次；M、25只被经过，不作巡视S千米 T小时L=O，1，B，34，35，32，31，33，A，R，29，Q，30，Q，28，27，26，P，O 其中Q被经过两次，但只巡视一次；26、P只被经过，不作巡视S千米 T小时4 模型评价本模型将求图中最短巡视路线问题转化为求一个最短Hamilton回路的问题，这种方法有坚实的理论根底。在求多路巡视路线的最优解时,使用了划分子图的方法,在各子图实现最优,总体上也保证了均衡,方法简便,易于操作。但本模型中所使用的
