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

建模案例最佳灾情巡视路线.doc建模案例最佳灾情巡视路线
建模案例最佳灾情巡视路线
1 / 5
建模案例最佳灾情巡视路线
建模案例：最佳灾情巡视路线
这里介绍 1998 年全国大学生数学模型竞赛 B 题中的两个问题 .
一、问 题
今年夏天某县遭受水灾 .为考察灾情、 组织自救，县领导决定， 带领有关部门负责人到全县各乡（镇） 、村巡视 .巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线 .
1． 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的路线 .
2． 假定巡视人员在各乡（镇）停留时间 T=2h，在各村停留时间 t=1h，汽车行驶速度 V=35km/ 24h 内完成巡视，至少应分几组； 给出这种分组下最佳的巡视路线 .
乡镇、村的公路网示意图见图 1.
图 1
二、 假 设
1．汽车在路上的速度总是一定，不会出现抛锚等现象；
2．巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；
3．每个小组的汽车行驶速度完全一样；
4．分组后，各小组只能走自己区内的路，不能走其他小组的路（除公共路外） .
三、模 型的建立与求解
将公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇） 、村之间的公路看作图中对应节点间的边， 各条公路的长度 （或行驶时间） 看作对应边
上的权，所给公路网就转化为加权网络图， 问题就转化为在给定的加权网络图中寻找从给定点 O 出发，行遍所有顶点至少一次再回到 O 点，使得总权（路程或时间）最小，此即最佳推销员回路问题 .
在加权图 G 中求最佳推销员回路问题是 NP—完全问题，我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下：
算法一 求加权图 G（V，E）的最佳推销员回路的近似算法：
1． 用图论软件包求出 G 中任意两个顶点间的最短路，构造出完备图
G (V , E ) ， x, y E ， x, y mindG x, y ；
2． 输入图 G 的一个初始 H 圈；
3． 用对角线完全算法产生一个初始 H 圈；
4． 随机搜索出 G 中若干个 H 圈，例如 2000 个；
5． 对第 2、3、4 步所得的每个 H 圈，用二边逐次修正法进行优化，得到近
似最佳 H 圈；
6． 在第 5 步求出的所有 H 圈中，找出权最小的一个，此即要找的最佳 H
圈的近似解 .
由于二边逐次修正法的结果与初始圈有关，故本算法第 2、3、4 步分别用三种方法产生初始圈，以保证能得到较优的计算结果 .
问题一 若分为 3
组巡视，设计总路程最短且各组尽可能均衡的巡视路线 .
此问题是多个推销员的最佳推销员回路问题
.即在加权图 G 中求顶点集 V 的
划分 V1,V2 ,
,Vn ，将 G 分成 n 个生成子图 G V1
,G V2