建模灾情巡视.doc

灾情巡视路线问题的研究摘要本文分析的是最佳的巡视路线问题,我们用Kruskral算法对原路线图进行处理,求得其最小生成树,并以巡视总路程、各组巡视时间和路程(时间)均衡度为目标函数建立模型,通过图论软件包、Matlab软件求解,并对结果进行均衡度检验,设计出了最佳巡视路线,而且对影响最佳巡视路线的因素进行了定量分析。针对问题一:问题一我们运用了用Kruskral算法对原路线图进行处理,求得其最小生成树,提出了分块准则,我们根据分块准则,建立了以巡视总路程和路程均衡度为目标函数的多目标标模型,并通过分析比较和路程均衡度检验,最终得出了最佳巡视路线,此时巡视总路程,路程均衡度为具体巡视路线见表三。针对问题二:我们通过分析可知在此种情况下至少需分四组巡视,并在题一得出的最小生成树的基础上,提出分块准则,建立了以个组巡视总时间和时间均衡度为目标函数的多目标模型,并通过分析比较和时间均衡度检验,得出了最佳巡视路线,此时小时,时间均衡度,具体巡视路线见图二。针对问题三:我们通过图论软件包求出了所有的点到点的最短距离,以及离最远的点为点,我们以巡视点的最短时间为各组各组巡视时间的上限,运用图论软件包和自己分析判断,最终制订了最佳巡视路线,此分组组数为23组,具体数据和巡视路线见表五。针对问题四:我们假设该问题是已经定分为三组的情形,且在乡镇停留时间为在村停留时间整数倍情况下讨论的改变对最佳巡视路线的影响。由问题一的求解结果可知,第三组巡视路线较第一组、第二组巡视路线长,所以我们只讨论在改变时对第三组巡视路线的影响进行分析以说明问题。最终得出结论:停留时间的改变对最佳巡视路线影响较大;汽车时速的改变对最佳巡视路线的确定影响较小。关键词:、村公路网络示意图,公路边的数字为该路段的公里数。今年夏天某县遭受水灾。为考察灾情、组织自救,县领导决定,带领有关部门负责人到全县各乡镇、村巡视,巡视路线指从县政府所在地出发,走遍各乡镇、村,又回到县政府所在地的路线。:若分三组(路)巡视,试设计总路程最短且各组尽可能均衡的巡视路线图问题2:假定巡视人员在各乡(镇)停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度V=35公里/小时。要在24小时内完成巡视,至少应分几组;给出这种分组下你认为最佳的巡视路线。问题3:在上述关于T,t和V的假定下,如果巡视人员足够多,完成巡视的最短时间是多少;给出在这种最短时间完成巡视的要求下,你认为最佳的巡视路线。问题4:若巡视组数已定(如三组),要求尽快完成巡视,讨论T,t和V改变对最佳巡视路线的影响。,使三组的总路程最小且各组尽可能的均衡,为此我们可以考虑建立以三组巡视路线总路程值最小和三组路程的均衡度两个目标函数的模型。首先我们可以运用Kruskral算法构造巡视图的最小生成树,然后以最小生成树的主干将生成树分成三组,分别构造出每组总路线值最小的回路,如果以上两个目标值不佳,我们还可以重新分组,进过多次调整达到较为合理的结果。,要求在二十四小时内完成巡视,我们算得完成巡视所需的总停留时间为69小时,如果按照第一问中分三组巡视,完成巡视所需的总停留时间应该不大于小时,则每辆汽车行驶的时间不能超过小时,而车行驶速度为35公里/每小时,这显然不能满足需求,为此我们考虑至少需要分四组,如果分四组,完成巡视所需的总停留时间应该不大于小时,则每辆汽车行驶的时间不能超过小时,在这种情况下,巡视的总路程的最大值为公里,,将巡视人员分为四组是可行的,然后我们分别以四组巡视的总路程、四组路程均衡度、四组完成巡视的停留时间和时间均衡度为目标函数建立模型,并重点考虑四组完成巡视的停留时间和时间均衡度为目标函数建立模型。,即巡视人员不受限制,此时完成巡视的时间由离县政府最远的乡(镇)或村决定要求完成巡视的最短时间,我们只要求离点最短距离最大的巡视点,然后算出行驶时间与在巡视点停留的时间之和即为完成巡视的最短时间,在最短巡视时间要求下,如果我们可以分足够多的组,必定能完成巡视人物,但考虑到这在现实生活中是不可能的,所以我们应该在满足条件的基础上尽量减少巡视组数,然后求出最小生成树后可以对每个结点进行遍历,借助图论软件包进行协助,这样可以求出最佳的巡视路线,,且要求在尽快完成巡视的情况下讨论的改变对最佳巡视路线的影响。由问题一的求解结果可知,第三组巡视路线较第一组、第二组巡视路线费时,故我们不妨讨论在改