灾情巡视的最短路 数学建模(2)

6.2模型一的求解

由以上模型得到调整前和经过两次调整后的结果，整理如下表：

(单位：km) 第1组 第2组 第3组 总路程 均衡度 最长路程 调整前 237.5 191.1 125.5 554.1 47.2% 237.5 第一次调整 216.5 191.1 188.7 596.3 12.8% 216.5 第二次调整 204.9 208.8 205.3 619 1.9% 208.8 得到的第二次调整后的路线及各组路程，总路程，均衡度整理如下表： (单位：km) 组路程 总路程 均衡度 最长路程 路线(用红色标记的点为停留点) 别 O-2-5-6-7-E-11-G-13-14-H-12-F-1 204.9 10-F-9-E-8-E-7-6-5-2-O 619 1.9% 208.8 O-M-N-25-20-L-19-J-18-I-15-I-12 208.8 6-17-22-K-21-23-24-27-26-P-O O-2-3-D-4-D-3-C-B-34-35-32-30-3 205.3 Q-28-Q-29-R-31-33-A-1-O

7.问题二的解答

7.1模型二的建立

由题知，有17个乡镇，35个村，巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时，所以，总停留时间为

(小时),计算得出单个组的巡视时最小H圈的路程为508.2km，为

设有x个分组，则有，得x>3.43，故取x=4，即分四组进行

巡视，

分组时遵循以下四项准则:

准则一:尽量使长的干枝和短的干枝分为一组。 准则二:尽量让各组的停留时间相同。 准则三:尽量把相邻干枝上的点分为一组。

准则四:尽量将同一干枝上的点分在一组，且能形成环路。 7.1.1确定目标函数

完成巡视的时间取决于四个组中最长的巡视时间，故目标函数为 min sj=（max（sjk））,k=1,2,32,4 7.1.2确定约束条件 sjk<24,k=1,2,3,4

7.13综上所述，得到问题二的最优化模型 min（max（sjk））,k=1,2,32,4 sjk<24,k=1,2,3,4 7.2模型二的求解

由以上模型求得调整前和调整后的结果整理如下表： 第一组 第二组 第三组 第四组 总路程 乡镇的停留点个数 调整前 村的停留点数 路程(km) 巡视所用时间(h) 乡镇的停留数 调整后 村的停留数 路程(km) 巡视所需时间（h） (km) 时间均衡度 最长时间（h） 5 8 3 10 5 8 4 9 663.6 12.30% 23.12 136.5 149.7 179.2 198.2 21.9 5 8 20.277 4 10 23.12 4 9 22.663 4 8 668.2 3.33% 22.409 136.5 154.3 179.2 198.2 21.9 22.409 22.12 21.663 所得调整后的四组路线，巡视时间等整理如下表：

组别 1 2 3 4 路线(用红色标记的点为停留点) O-1-A-33-31-R-29-Q-30-32-35-34-B-C-O O-M-25-21-K-17-16-17-22-23-24-N-26-27-28-P-O O-M-25-20-L-19-J-18-I-15-14-13-G-11-E-7-6-5-2-O O-2-3-D-4-8-E-9-F-12-H-12-F-10-F-9-E-7-6-5-2-O 路程停留时行驶时巡视时（km) 间（h） 间（h） 间(h） 136.5 154.3 179.2 198.2 18 18 17 16 3.90 21.9 4.41 22.41 5.12 22.12 5.66 21.66 8.问题三的解答

8.1从O点巡视H点的最短时间是所有最短时间中最长的，其距离为77.5km，算

出时间为小时，因此，T=2h，t=1h，V=35km/h时，若巡视

人员足够多，完成巡视的最短时间为6.43小时。

在最短时间的限制下，完成巡视的最佳路线应满足以下条件： （1）每个组巡视的总时间不能超过最短时间

小时，

（2）所有的点都必须访问到，不能漏点， （3）所需巡视组数要尽量小。 在寻求最优路线时，从距离O点较远的点开始搜索比较容易，因为到这些点的路线比较少。

具体方法如下：

第一步：依据最小生成树算出从O点到每一点的最短距离。

第二步：找出其中最大的一个，算出从O点到最短路巡视所需时间ti，并求 第三步：若

。

，则这一组只能访问这一点；若

，则在余下的点中找出

距离O点最远的点，根据条件看这一组能否巡视这一点。 第四步：若能巡视则算出

，转到第三步。

，

第五步：若不能，则依次判断次远点、第三远点···满足总巡视时间不超过 就让这组巡视这一点，直到

，然后再从第二步开始。

通过以上方法找到最优解是23组，如下表：

8.2模型三的求解 路线(用红色标记的点为停留点) 时间 第1组 第2组 第3组 第4组 第5组 第6组 第7组 第8组 第9组 第10组 第10组 第12组 第13组 第14组 第15组 第16组 第17组 第18组 第19组 第20组 第21组 第22组 第23组 O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-0 O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-0 O-M-25-21-K-18-I-15-I-18-K-17-16-17-K-21-25-M-0 O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O O-2-5-6-7-E-9-F-10-F-9-E-8-E-7-6-5-2-O O-2-5-6-7-E-11-G-11-E-7-6-5-2-O O-M-25-21-K-18-I-18-K-21-25-M-O O-2-5-6-7-E-11-E-7-6-5-2-O O-2-5-6-L-E-9-F-9-E-7-6-5-2-O O-2-5-6-L-19-J-19-L-6-5-2-O O-M-25-21-K-17-16-17-K-21-25-M-O O-M-25-21-K-18-K-21-25-20-25-M-O O-P-26-N-23-22-23-N-24-N-26-P-O O-2-5-6-7-E-8-E-7-6-5-2-3-D-4-D-3-2-O O-2-5-6-L-6-5-2-O-M-O O-1-A-34-35-34-A-33-A-1-O O-R-29-Q-30-Q-29-R-O O-M-25-M-O-P-26-N-26-P-O O-R-31-32-31-R-O O-P-26-27-26-P-28-P-O O-2-3-D-3-2-O-C-O O-1-A-1-B-1-O O-2-3-2-5-2-O-M-O-P-26-N-23-N-26-P-O 9.问题四的解答

6小时26分 6小时9分 6小时19分 5小时51分 6小时13分 5小时35分 5小时29分 6小时12分 6小时9分 6小时6分 6小时3分 6小时13分 5小时12分 6小时0分 6小时17分 5小时29分 6小时2分 6小时3分 5小时44分 5小时40分 5小时25分 6小时9分 5小时51分 9.1模型四的建立

根据题意，假设巡视组数定为四组，以问题二中的分组方案为例，固定T，t和V中的两个量，改变其中一个量，求巡视时间与该变量间的关系，通过MATLAB求解得到如下巡视时间随三个变量的变化而变化的图(程序见附录一):

图中三个红色的点位于一条直线上，分别代表T=2小时，t=1小时，V=35千米/小时时，对应问题二的巡视时间22.409h，即为问题二的解。 显然，由下图得出以下结论：

(1)当固定t、V时，巡视时间随T的增大而增大

(2)当固定T、V时，巡视时间随t的增大而增大，且随t增大得比随T增大地 快

(3)当固定T、t时，巡视时间随V的增大而减小

更进一步分析，可看出，当V低于20km/h后，巡视时间急剧增加，当V高于50km/h后，再增加对减小巡视时间作用很小，故从效率和安全两个角度综合考虑，汽车速度V应不低于20km/h，应不高于50km/h

11.模型的模型的评价、改进及推广

11.1模型评价

模型优点：

(1)用均衡度量化分组的均衡性。

(2)综合多种算法的思想进行求解，使所得模型在灾情巡视方面有科学的指

导意义。

模型缺点：第三问用经验来调整的，如果可以通过编程求解则更好。 11.2模型改进

由于实际情况中，各个乡（镇）、村的受灾情况不同，故应根据受灾的严重程度来分配巡视时的停留时间，可先将每个巡视点的受灾程度量化，建立T，t关于受灾程度的函数，然后分组巡视，求最佳巡视路线。 11.3模型推广

所建模型还可用于公安执勤人员的最优巡回路线、流水作业、生产线的顺序问题以及老师任课班级负荷分配等问题。

12.参考文献

[1] 赵静,但琦,数学建模与数学实验,北京:高等教育出版社,2008.

[2] 薛定宇，陈阳泉，高等应用数学问题的MATLAB求解，北京：清华大学

出版社，2008.

13.附录

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库灾情巡视的最短路 数学建模(2)在线全文阅读。