内容发布更新时间 : 2024/5/19 5:59:56星期一 下面是文章的全部内容请认真阅读。

题目：灾情巡视路线

学号：2012070231 姓名：施亚男 班级：12级数学教育

一．问题重述

1.1背景分析：

今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 1.2需要解决的问题：

1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。

3）在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。

4）若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。

一、 模型假设

2.1假设地面情况一切正常，不会影响汽车行驶速度； 2.2假设第二次经过的乡镇，不计算停留时间；

2.3对于同一乡镇，如果某一小组停留过，其他小组经过时不计算停留时间； 2.4假设经过邻县村不做任何停留；

2.5假设县镇府所在地灾情不派小组人员巡视。

二、 符号说明

ci 第i个小组所走路程 衡量均衡度（?越小，均衡度越好；反之，均衡度越差） 巡视一个乡（镇）所花时间T?2h 巡视一个村所花时间t?1h 汽车的行驶速度V?35km/h 第i个小组巡视所用时间 最短路径树中从O点出发到所有点距离中的最大距离 最短路径树中点j距出发点的距离(j?O,A,B?N,P,R,1,2?35) 完成所有巡视所用的最短时间 ? T t V ti Smax Sj Tmin Ts 巡视完所规定的点外的剩余时间 小组巡视乡镇的个数 小组巡视村得个数 n m

三、 问题分析

本文研究的是考察灾情最佳巡视线路设计的问题，准确合理的路线设计对灾情巡视救治起着重要作用。为很好的解决此问题，为此我们建立了网络图模型。

对于问题一，题目要求在分三组巡视的情况下，使总路程最短且各小组所走路程均衡。先考虑分区，我们将得出的最小生成树图形和最短路树图形，进行比较并找出其公共部分。分组要求尽量不破坏最短生成树和最小生成树，所以我们以公共部分为界限，将此网络图分为三组。为使每小组所走路程均衡，我们引入了均衡度?。它表示最大路程和最小路程的差值与最大路程的比值。?越小，表示均衡度越好。以总路程最短和均衡度最小作为目标函数建立多目标规划模型，利用哈密顿原理得出各组的巡回路线，并对其分析修正求得各组最优巡回路线。

对于问题二，要求在24小时内完成所有巡视。 通过第一问的结果，求得在

1609.8)?28.8h大于24小时，分三组的情况下所用的平均时间T1?(17T?35t?335所以我们先考虑分四组。我们的分组原则为：1、每子区域所分得的点近似相等；2、尽量使每一个子区域连通；3、使每一个子区域中与点O的最短路上的点在该区域内。根据以上分组原则将整个图大致划分为四个子图，同样利用哈密顿算法求得在相对均衡的情况每个小组的最短路径和所需时间。如果部分时间大于24小时，则调整分组方式；若所有时间均大于24小时再考虑多加一组。直到找到相对均衡条件下的最佳路线。

对于问题三，考虑在人员足够多的情况下，求出最短的巡视时间。假设一个小组只巡视一个点的情况下，则去巡视离O点最远的点所花时间最长。我们以巡视小组中所耗时间最长的小组所用时间作为这次整个巡视的最短时间。要使这次巡视时间最短，则要求去巡视离O点最远的点所花时间最小，由图一可知，离O点最远的点为H，所以就以巡视H所花时间作为Tmin。当此小组只巡视H时，Tmin最小。在不超过Tmin的情况下，根据其他小组的剩余时间确定沿途是否巡视其他点。其中巡视原则为：①当一组人员巡视完规定点后时，在剩余时间允许的情况下，优先考虑原巡视点附近而距离O较远的点，②最大限度使用剩余时间，主要考虑原则①。按照此原则，逐个巡视，直至巡视完所有点。

对于问题四，若巡视组数已定，则每个小组的最短路径就已确定，T、t、V改变只影响的是整个的巡视时间。要求尽快完成巡视，即巡视时间要尽可能小。