欢迎来到天天文库
浏览记录
ID:30275592
大小:359.50 KB
页数:8页
时间:2018-12-28
《灾情巡视路线地数学模型》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、实用标准文案最优灾情巡视路线摘要关键字1问题重述下图为某县的乡(镇)、村公路网示意图,公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救,县领导决定,带领有关部门负责人到全县各乡(镇)、村巡视。巡视路线指从县政府所在地出发,走遍各乡(镇)、村,又回到县政府所在地的路线。问题一:若分三组(路)巡视,试设计总路程最短且各组尽可能均衡的巡视路线。问题二:假定巡视人员在各乡(镇)停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度v=35公里/小时。要在24小时内完成巡视,至少应分几组;给出这
2、种分组下你认为最佳的巡视路线。问题三:在上述关于T,t和v的假定下,如果巡视人员足够多,完成巡视的最短时间是多少;给出在这种最短时间完成巡视的要求下,你认为最佳的巡视路线。问题四:若巡视组数已定(如三组),要求尽快完成巡视,讨论T,t和v改变对最佳巡视路线的影响。2问题假设与符号说明2.1问题假设假设一:假设在巡视过程中不考虑天气、故障等因素的影响假设二:假设路线上的公路没有被洪水冲断,可以供巡视工作使用。假设三:假设在巡视工程中,经过邻县村时,不做任何时间的耽搁。2.2符号说明赋权连通图;赋权连通图的第个子图子
3、图中的最佳回路;最佳回路的各边权之和第个乡、村到第个乡、村的距离某组从城市到城市时为1,无巡视组视为03问题分析精彩文档实用标准文案本题给出了某县的道路交通网络图,要求的是在不同条件下,灾情巡视的最佳分组方案和路线。这是一类图上的点的遍历性问题,也就是要用若干条闭链覆盖图上所有的顶点,并使某些指标达到最优。点的遍历性问题在图论中属于哈密顿问题和旅行推销员问题类似。如果巡视人员只分一组,巡视路线是指巡视人员从县政府O出发,走遍各乡(镇)、村最后又回到县政府。我们可以把该题抽象为图论的赋权连通问题,即有一赋权无向连通
4、图,且。两村之间的公路长度即为无向图的边权。寻找最佳巡视路线,即在图中找到一条包含O点的回路,它至少经过所有的顶点一次且使得总路程(总时间)最短。针对问题一:如果将巡视人员分成三组,每组考察全县的一个区域,使所有乡(镇)、村都考察到,实际上就是将图分为三个连通的子图,且每个子图都与O点相连,然后在每个子图中寻找到一条含O点的最佳回路。针对三组巡视成员,需对该县分为三个区域。我们采用Prim算法通过编程求出图的最小树形图,然后将树形图分成三个区域,最后,采用哈密顿回路法求解每个子图内的最佳巡视路线。 针对问题二:
5、完成巡视的时间应是各组巡视中最长的时间,要想提高巡视的效率则应尽量使各组的巡视时间接近,反映在图分块时应尽量均衡。4数据的分析与处理5问题一的解答5.1模型一的准备现要分三组巡视,则需要把图分成三个子图,在每个子图中寻找最佳回路。因为最小生成树中能包含图中所有的顶点,而且最小树的边权是相邻两顶点间的距离,它描述了顶点之间的相近程度,故可以采用最小生成树进行分组。本模型的主要思想是:首先采用Prim算法得到图的最小生成树,然后基于最小生成树生成一个可行的巡视路线,求得路线的最优总路程为。采用Prim算法求解最小生成
6、树步骤如下:(1)输入加权连通图的带权邻接矩阵;(2)建立初始候选边表;(3)在候选边表中选出最短边;(4)调整候选边表;精彩文档实用标准文案(5)重复(2),(3),直到含有条边。根据算法进行编程求解(具体程序见附录1),于是我们得到图的最小生成树如图1。图1现对已得到的最小生成树进行分解,以获得三个子图并使得分解结果尽量均衡。由于在最小生成树上,边权接近可以近似认为均衡即各子图包含的顶点数应接近。因此,各个子图的顶点数应尽量接近17个,且遵循以下分解原则。最小生成树分解原则:(i)分解点为O点或尽可能地接近O
7、点;(ii)分解所得的三个子图的顶点数尽可能地接近17个;(iii)尽量是分解所得的子图是连通图;(iv)尽量使子图与点O的最短路上的点在该子图内,且尽量使各子图的点在子图内部形成环路。依据以上分解原则得到的分解结果如图2。图2精彩文档实用标准文案然后,采用哈密顿回路法求解每个子图内的最佳巡视路线。寻找最佳巡视路线实际上就是在赋权图中寻找最优的哈密顿圈,包含图的每个顶点的圈陈为哈密顿圈。于是问题就可以转化为:现已知三个子图内乡、村与乡、村之间的距离,从县镇府O出发,经过子图内的所有乡、村,最后又回到点O。5.2模
8、型一的建立5.2.1确定目标函数由题中所给出的问题条件,分析出这是3个售货员寻求最佳旅行回路的问题。把县、乡、村所在地堪称借点,根据路线图可以构造一个赋权网络图,其中.根据图论中的结论,最佳售货员回路问题可转化为最佳汉密尔顿回路的问题。在图的基础上构建三个子图,于是在中寻求最佳回路的问题即在中寻找最佳回路的问题,于是决策变量定义为:;精彩文档实用标准文案其线性(整数)规划
此文档下载收益归作者所有