下载此文档

灾情巡视路线.doc


文档分类:高等教育 | 页数:约22页 举报非法文档有奖
1/22
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/22 下载此文档
文档列表 文档介绍
19 组袁光辉唐少君代悦
灾情巡视路线
摘要
本文解决的是设计最佳灾情巡视路线的问题,是经典的货郎但问题,为解决此问题,本文利用了算法prim和函数Floyd、router,对所给的公路网示意图进行分析,做出最小生成树和最短路径图,根据图论知识和图形分析。最后建立了一个最小路径的模型——最小边权模型。
对于问题一,我们确定的最佳巡视路线为
第一组
O-1-B-A-34-35-33-31-32-30-Q-28-27-24-23-N-26-P-29-R-O
第二组
O-M-25-21-K-22-17-16-I-15-14-13-J-18-J-19-20-L-6-5-2-O
第三组
O-C-3-D-4-8-E-9-F-10-F-12-H-12-G-11-D-3-2-O
对于问题二,我们得到,要在24小时内完成巡视,至少应分四组;在该分组下的最佳巡视路线为
第一组
O-C-B-34-35-32-31-32-30-Q-29-R-A-1-O
第二组
O-P-28-27-24-23-22-(17)-K-21-20-25-N-26-(P)-O
第三组
O-2-5-6-L-19-J-13-14-H-14-15-I-18-(K)-(21)-(25)-M-O
第四组
O-(2)- (5) –(6)-7-E-11-G-12-F-10-E-8-4-D-3-2-O
对于问题三,如果巡视人员足够多,,;分组为:
1
O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-O
H

2
O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-O
13\14

详情见表十
对于问题四,利用随机算法进行分析,在巡视组数为三组的情况下,在实际生活中,T和t只能在某一个范围内波动,而当其在这一范围内变化时,V的改变并不会对最佳巡视路线产生很大的影响,只是对一小部分产生影响。
关键词:最佳灾情巡视路线 prim算法 Floyd 最小生成树最小距离树
问题的重述
下图(见附录一)为某县的乡(镇)、村公路网示意图,公路边的数字为该路段的公里数。
今年夏天该县遭受水灾。为考察灾情、组织自救,县领导决定,带领有关部门负责人到全县各乡(镇)、村巡视。巡视路线指从县政府所在地出发,走遍各乡(镇)、村,又回到县政府所在地的路线。
1. 若分三组(路)巡视,试设计总路程最短且各组尽可能均衡的巡视路线。
2. 假定巡视人员在各乡(镇)停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度V=35公里/小时。要在24小时内完成巡视,至少应分几组;给出这种分组下你认为最佳的巡视路线。
3. 在上述关于T , t和V的假定下,如果巡视人员足够多,完成巡视的最短时间是多少;给出在这种最短时间完成巡视的要求下,你认为最佳的巡视路线。
4. 若巡视组数已定(如三组),要求尽快完成巡视,讨论T,t和V改变对最佳巡视路线的影响。
模型的假设与符号说明
模型的假设:
公路网络中提供的各乡村之间的路程数据是可靠的;
各乡村巡视的时间严格按照规定:各乡(镇)停留T小时,各村停留t小时;
各巡视员之间的信息是共享的,巡视员知道其他巡视员经过的乡村;
某乡镇村被巡视完之后,再次经过该乡村时,不再花时间进行巡视;
巡视员在巡视灾区的过程中不会发生意外情况,在去各乡村巡视的路上不会耽误时间,巡视车辆的运行是正常的;
在巡视的过程中严格按照提供的公路网中存在的路径行走;
符号说明:
各巡视员巡视路径的均衡度;
各巡视员巡视时间的均衡度;
公路网中定点i到顶点j所在边的路途长度;
县政府、乡(镇)、村所在地,其中;
分组的区域i的代号;
第i个巡视员所经过的路程的长度;
第i个巡视员在整个巡视的过程后中所花的总时间;
巡视员在各乡(镇)停留的时间;
巡视员在各村停留的时间;
巡视所用的汽车在公路上行驶的速度;
问题的分析
此题研究的是设计最佳的灾情巡视路线的数学建模问题。分析所给的某县的乡(镇)、村公路网示意图,将其视为图论中的无向赋权图,
其中:
要求在不同条件下的灾情巡视的最佳分组方案和连线,实际上为在给定的无向赋权图中找出使得从定点O出发,走遍各顶点,又回到O点,使得达到最小值的巡视路线。
针对问题1,若分三组巡视,设计路程最短且各组尽可能均衡的巡视路线。
首先利用中的prim算法将所给示意图中的以O为树根的最小生成树做出来。
其次,定义函数floyd和router,求出每点到O点的最短距离的路线,作出最短路径图。
对图像的

灾情巡视路线 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数22
  • 收藏数0 收藏
  • 顶次数0
  • 上传人ranfand
  • 文件大小369 KB
  • 时间2017-10-16