《最佳灾情巡视路线模型.doc》由会员分享，可在线阅读，更多相关《最佳灾情巡视路线模型.doc（9页珍藏版）》请在课桌文档上搜索。
1、最优灾情巡视路线模型【摘要】“图论是组合数学的分支，它与其他的数学分支，如群论、矩阵论、拓扑学，数值分析有着密切的联系。在其它科学领域，如计算机科学、运筹学、电网络分析、化学物理以与社会科学等方面图论也具有越来越重要的地位，并已取得丰硕的成果。而且，图论的理论和方法在数学建模中也有重要应用。本文概述了一些常用的图论方法和算法，并通过举例灾情巡视路线说明其在数学建模中的应用。【关键词】图论灾情巡视Hamilton回路 数学模型预备知识定义1 完全图：如果图G中每一对不同的顶点恰有一条边连接，如此称此图为完全图。定义2 连通图：如果对图G=V，E的任何两个顶点u与v，G中存在一条u-v路。如此称G
2、是连通图。定义3 加权图：边上有数的图称为加权图。在加权图中，链迹、路的长度为链迹、路上的所有边的权植的和。定义4 Hamilton回路：图G中的一个回路C称为一个Hamilton回路如果C含有G的所有顶点。含有Hamilton回路的图称为Hamilton图。定义5 欧拉回路：经过图G的每条边的迹称为欧拉迹，如果这条迹是闭的，如此称这条闭迹为G的欧拉回路。一 数学建模中常用的图论方法1 迪克斯特拉算法Dijkstra在加权图中，我们经常需要找出两个指定点之间的最短路，通常称为最短路问题。解决最短路问题的方法之一就是迪克斯特拉算法。假定P：VVVVV是从V到V的最短路，如此它的子路VV一定是从V
3、到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) (这样就给S中
4、添加带最小标记的顶点并且更新不在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和V V而
6、得到的其权和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= V
7、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，再运用上述求最短Ham
11、ilton回路的算法在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，17，16
13、，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中边的权值的增长：t=
14、由图可知有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，6，7，
15、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回路的问题，这种方法有坚实的理论根底。在求多路巡视路线的最优解时,使用了划分子图的方法,在各子图实现最优,总体上也保证了均衡,方法简便,易于操作。但本模
16、型中所使用的求最短Hamilton回路的算法本身是个近似算法,因此结果只能是近似最优解。在经过屡次尝试之后，结果中还是有多个顶点被重复经过。与前人的研究结果见参考文献比照如下：1一路巡视本文所得总长度千米比参考文献中的千米稍短；2三路巡视均衡性较好，但总长度有所增加。见下表单位：千米第一路第二路第三路总长度参考文献本文结果3四路巡视单位：小时第一路第二路第三路第四路参考文献本文结果【参考文献】：【1】殷剑宏,吴开亚.图论与其算法,中国科学技术大学.【2】卜月华.图论与其应用,东南大学.【3】王树禾.图论,科学.【4】袁震东,洪渊林等.数学建模,华东师X大学.【5】薛毅.数学建模根底,工业大学.
17、【6】赫孝良,戴永红等.数学建模竞赛赛题简析与论文点评,某某交通大学.An Application Of Graph Theory In Mathematical ModelingKangxiaoxue【Abstract】Graph theory is a branch of bination mathematics,which contact with other branches inseparably, such as group theory, matrix theory, topology and numerical analysis.In other science fields,
18、 like puter science, electronic network analysis, physical chemistry and society scienceetc, graph theory is used more and more frequently and got many harvests. Furthermore, graph theory and its approaches also have important applications in mathematical modeling. In this paper,we introduce some me
19、thods and algorithms of graph theory., and give an example to illustrate an application of the methods or algorithms.【Key words】 Graph theory the tour of a disaster the shortest Hamilton loop mathematical model附录：1求一路巡视的运算过程1取O点为起点，比拟与点O相连的边O，1、O，C、O，2、O，M、O，P、O，R的权值，显然O，1最短，于是取C=O，1；2将1作为新起点，比拟与1相连
20、的边1，A、1，B、1，C的权值，显然1，B最短，于是C=O，1，B；3依次类推可得C=O，1，B，C，3，2，5，6，7，E，9，F，10，12，G，11，J，19，L，20，25，21，K，18，I，15，I，16，17，22，23，24，N，26，27，28，Q，29，R，A，1，O4但这样得到的路并没有包含所有顶点，遗漏了M，D，4，H，14，13，8，30，32，35，34，33，31，P，因此还需要进展调整。调整时可采用前文中提到的最邻近算法的改良方法。针对这个问题的实际况，笔者经过屡次尝试，采用的是“推而求其次的方法，即在没有经过的顶点附近，舍弃最短的边而取能够经过该点但权值稍大
21、的边.具体做法如下：5在与M点相连的点5处舍弃边5，6而取次短的5，M，再按照最邻近算法，路径就变为5，M，6，7；6在7处舍弃边7，E而取7，D，同样路径变为7，D，4，8，E，9，F，10，12；7在12处舍弃12，G而取12，H，路径变为12，H，14，13，G，11，J，19，L，20，25，21，K，18，I，15，I，16，17，22，23，24，N，26，27，28，Q，29，R，A，1，O；8在Q处舍弃(Q,29)而取(Q,30),路径变为Q,30,32,31,33,A,1,O;9在32处舍弃(32,31)而取(32,35),路径变为32,35,34,A,33,31,R,29,P,O;10将所有调整后的路径连在一起,便得到文中的最短Hamilton回路。2 三路巡视和四路巡视的方法同上，具体过程略。
