资源描述：
《1998年全国大学生数学建模竞赛题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1998年全国大学生数学建模竞赛题目B题灾情巡视路线下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。(1)若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。(2)假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。(
2、3)在上述关于T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。(4)若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。 灾情巡视路线模型摘要本文将求最佳巡视路线间题转化为图论中求最佳推销员回路（哈米尔顿回路）的问题,并用近似算法去寻求近似最优解。对赋权图中的路径分组问题定义了均衡度用以衡量分组的均衡性。对问题1和问题2先定出几个分的准则进行初步分组,并用近似算法求每一组的近似最佳推销员回路,再根据均衡度进行微调,得到较优的均衡分组和每
3、组的近似最佳推销员回路。对问题1，运用求任意两点间最短路的Floyd算法,得出总路程较短且各组尽可能均衡的路线,各组的巡视路程分别为216.4公里,191.1公里,192.3公里,总路程599.8公里。对问题2,证明了应至少分为4组,并求出了分为4组时各组的较优巡视路线,各组的巡视时间分别为22.74小时,22.59小时,21.69小时,22.54小时。对问题3,求出完成巡视的最短时间为6.43小时,并用较为合理的分组的准则,分成22个组对问题4，研究了在不影响分组的均衡条件下,T,t,V的允许变化范围,并得出了这三个变量的关系式,并由此对分三
4、个组的情况进行了具体讨论。关键词：最佳推销员回路问题哈米尔顿回路赋权图近似算法均衡度一、问题重述1998年夏天某县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各17个乡（镇）、35个村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。(1)若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。(2)假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。(3)在
5、上述关于T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。(4)若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。二、问题分析本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最分组方案和路线.将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出
6、发，行遍所有顶点至少一次再回到点O，使得总权（路程或时间）最小.本题是旅行售货员问题的延伸－多旅行售货员问题.本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.显然本问题更应属于NP完全问题.有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.三、模型假设1．汽车在路上的速度总是一定
7、，不会出现抛锚等现象；忽略天气、故障等因素的影响。2．巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；3．每个小组的汽车行驶速度完全一样；4．分组后，各小组只能走自己区内的路，不能走其他小组的路，除公共路外。四、符号说明……………………………………..任意两点，间的间距。……………………………………..各点的停留时间，即点权。………………………………………汽车行驶速度。………………………………从任意点至点的时间，则。五、模型建立与求解公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之间的公路看作图中对应节点间的
8、边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一
