建模案例：最佳灾情巡视路线.pdf

《建模案例：最佳灾情巡视路线.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、建模案例建模案例：建模案例：：：最佳灾情巡视路线最佳灾情巡视路线最佳灾情巡视路线最佳灾情巡视路线这里介绍1998年全国大学生数学模型竞赛B题中的两个问题.一一一、一、、、问问问问题题题今年夏天某县遭受水灾.为考察灾情为考察灾情、为考察灾情、、、组织自救组织自救组织自救，组织自救，，，县领导决定县领导决定县领导决定，县领导决定，，，带领有关部门带领有关部门负责人到全县各乡负责人到全县各乡（负责人到全县各乡（（（镇镇镇镇）、）、）、村巡视）、村巡视.巡视路线指从县政府所在地出发巡视路线指从县政府所在地出

2、发，巡视路线指从县政府所在地出发，，，走遍各乡走遍各乡（（（镇（镇镇镇）、）、）、村）、村村村，，，，又回到县政府所在地的路线又回到县政府所在地的路线.1．．．若分三组若分三组（若分三组（（（路路路路））））巡视巡视巡视，巡视，，，试设计总路程最短且各组尽可能均衡的路线试设计总路程最短且各组尽可能均衡的路线.2．．．假定巡视人员在各乡假定巡视人员在各乡（假定巡视人员在各乡（（（镇镇镇镇））））停留时间停留时间T=2小时小时，小时，，，在各村停留时间在各村停留时间t=1小小小时时时，时，，，汽车行驶速

3、度汽车行驶速度V=35公里/小时.要在24小时内完成巡视小时内完成巡视，小时内完成巡视，，，至少应分几组至少应分几组至少应分几组；至少应分几组；；；给给给给出这种分组下最出这种分组下最佳的巡视路线出这种分组下最佳的巡视路线.乡镇乡镇、乡镇、、、村的公路网示意图见图村的公路网示意图见图11-9.图图图11-9二二二、二、、、假假假设设设1．．．汽车在路上的速度总是一定．汽车在路上的速度总是一定汽车在路上的速度总是一定，汽车在路上的速度总是一定，，，不会出现抛锚等现象不会出现抛锚等现象不会出现抛锚等现象

4、；不会出现抛锚等现象；；；2．．．巡视当中．巡视当中巡视当中，巡视当中，，，在每个乡镇在每个乡镇在每个乡镇、在每个乡镇、、、村的停留时间一定村的停留时间一定村的停留时间一定，村的停留时间一定，，，不会出现特殊情况而延误时间不会出现特殊情况而延误时间不会出现特殊情况而延误时间；不会出现特殊情况而延误时间；；；3．．．每个小组的汽车行驶速度完全一样．每个小组的汽车行驶速度完全一样每个小组的汽车行驶速度完全一样；每个小组的汽车行驶速度完全一样；；；4．．．分组后．分组后分组后，分组后，，，各小组只能走自己

5、区内的路各小组只能走自己区内的路各小组只能走自己区内的路，各小组只能走自己区内的路，，，不能走其他小组的路不能走其他小组的路不能走其他小组的路，不能走其他小组的路，，，除公共路外除公共路外.三三三、三、、、模模模模型型型的的的建建建立立立与与与求求求解解解将公路网图中将公路网图中，将公路网图中，，，每个乡每个乡每个乡（每个乡（（（镇镇镇镇））））或村看作图中的一个节点或村看作图中的一个节点或村看作图中的一个节点，或村看作图中的一个节点，，，各乡各乡各乡（各乡（（（镇镇镇镇）、）、）、村之）、村之间的

6、公路看作图中间的公路看作图中对应节点间的边间的公路看作图中对应节点间的边对应节点间的边，对应节点间的边，，，各条公路的长度各条公路的长度各条公路的长度（各条公路的长度（（（或行驶时间或行驶时间或行驶时间）或行驶时间）））看作对应边看作对应边上的权上的权，上的权，，，所给公路网就转化为加权网络图所给公路网就转化为加权网络图所给公路网就转化为加权网络图，所给公路网就转化为加权网络图，，，问题就转化为在给定的加权网络图中问题就转化为在给定的加权网络图中寻找从给定点O出发出发，出发，，，行遍所有顶点至少一次

7、再回到行遍所有顶点至少一次再回到O点点点，点，，，使得总权使得总权使得总权（使得总权（（（路程或路程或时间时间）时间）））最小最小最小，最小，，，此即最佳推销员回路问题此即最佳推销员回路问题.在加权图G中求最佳推销员回路问题是NP———完全问题—完全问题完全问题，完全问题，，，我们采用一种近似我们采用一种近似算法求出该问题的一个近似最优解算法求出该问题的一个近似最优解，算法求出该问题的一个近似最优解，，，来代替最优解来代替最优解来代替最优解，来代替最优解，，，算法如下算法如下算法如下：算法如下：：：

8、算法一求加权图G（V，E）的最佳推销员回路的近似算法：1．．．用图论软件包求出G中任意两个顶点间的最短路中任意两个顶点间的最短路，中任意两个顶点间的最短路，，，构造出完备图构造出完备图G¢(V,E¢)，，，"(x,y)ÎE¢，，，w(x,y)=MindG(x,y)；；；2．．．输入图G¢的一个初始H圈圈圈；圈；；；3．．．用对角线完全算法用对角线完全算法（用对角线完全算法（（（见见见见[23]）））产生一个初始）产生一个初始H圈圈圈；圈；；；4．．．随机搜索出G¢中若