《数学建模优秀论文-灾情巡视路线的数学模型.doc》由会员分享，可在线阅读，更多相关《数学建模优秀论文-灾情巡视路线的数学模型.doc（25页珍藏版）》请在金锄头文库上搜索。
1、灾情巡视路线的数学模型摘 要本文解决的是灾情巡视路线的设计问题。由于路线图可看成网络图因此此问题可转化为在给定的加权网络图中寻找从给定点出发行遍所有顶点至少一次再回到点使得总权（路程或时间）最小的问题。然后针对具体问题，采用一些启发式算法，建立模型进行求解。对于问题一：基于设计分三组巡视时使总路程最短且各组尽可能均衡的巡视路线的要求我们采用Dijkstra算法，通过对初始圈进行二边逐次修正,处理三组的巡视路线长度，用lingo软件求解出较优方案。定义分组的均衡度系数a检验分组均衡度，在均衡度为a=0.0751时得到分三组（路）巡视时，总路程最短且各组尽可能均衡的巡视路线见附表1。对于问题二：将
2、问题转化为图论问题，运用问题一的求解方法，得到分为四组的路线，在通过均衡度分析之后得出近似最优巡视路线。利用lingo软件求得，至少要分四组，且四组的近似最优巡视路线见附表2。对于问题三：基于问题一二中图论的方法，考虑到从点巡视H点的最短时间是所有巡视线路中用时最长的，将计算出的最长路线巡视所用的时间作为巡视路线的最短时间限定，在此限定下对路线进行设计。求得的最短时间为6.43小时，最佳巡视路线分为23组。（具体分组见附录二）对于问题四：由于组数一定， T，t和V改变，对每组内的最佳巡视路线是没有影响的，但可能会影响到各组件的均衡性，因此问题实质是讨论T，t和V对分组的影响，即在不破坏原来分组
3、均衡的条件下T，t和V允许的最大变化范围。关键词：启发式算法 Dijkstra算法 均衡度 图论 二边逐次修正1. 问题重述1.1问题背景今年夏天某县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。附录一中给出了该县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。1.2本文需解决的问题问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在2
4、4小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。问题三：在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。 2. 模型的假设与符号说明2.1模型的假设假设1：公路不考虑等级差别，不受灾情和交通情况的影响。假设2：各条公路段上的汽车行驶速度均匀。假设3：各巡视组巡视的乡（镇）、村不受行政区划分的影响。假设4：各巡视组行动统一，一个巡视组不可再分成若干小组。假设5：巡视当中在每个乡（镇）村的停留时间一
5、定，不会出现特殊情况而延误时间。2.2符号说明符号符号说明巡视小组在乡（镇）巡视的停留时间巡视小组在村巡视的停留时间汽车行驶速度为导出子图中的最佳圈。（其中=1，2，3，n.）为的权，（其中=1，2，3，n.）最大允许均衡度分组后的实际均衡度第个点距起始点的路线长度点的时间权重分组数第组巡视时要停留的乡（镇）数第组巡视时要停留的村数最短时间下限第巡视路线的长度第巡视所用的时间3. 问题分析此题研究的是某县灾情巡视路线的设计问题。问题要求设计出最佳的巡视路线，即：保证总路程最短或时间最小而且各组尽可能均衡的巡视路线。基于图论相关理论，借助于几何直观和生活体验的启发作用，便于为计算机搜索制定行之有
6、效的操作规则，接着利用图论软件包通过计算机求解出较精确的路线。再通过线路均衡性比较，对均衡性不好的线路进行微调。以此方法确定最佳巡视路线。针对问题一：基于对问题的分析，借助图论知识，将所给公路网就转化为图论中的加权网络图，因此问题就转化为一个图论问题，即在给定的加权网络图中，寻找从给定点出发，行遍所有顶点至少一次再回到点，使得总权（路程或时间）最小。此即多个推销员的最佳推销员回路问题。基于以上分析，运用图论知识和图论软件包进行求解，再利用均衡度分析对得到的分组路线进行微调，均衡度越小表示路线越均衡，微调后即可得到相对较优的分组路线。可认为这样设计的分组方法和巡回路线能使总路线近似最短。针对问题
7、二：在问题一的基础上添加了巡视组在各乡镇停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时等条件，要求在24小时内完成巡视的最少分组数以及相应的最佳巡视路线。首先，由图中数据初步计算后判断分成四组可行，再针对分组为四组的情况进行线路设计，仍将问题转化为图论问题，运用问题一的求解方法，得到分为四组的路线，在通过均衡度分析之后得出近似最优巡视路线。针对问题三：在问题二中关于T , t和V的假定下且巡视人员足够多时，要求在最短时间完成巡视的要求下所得的最佳的巡视路线，此时考虑到从点巡视H点的最短时间是所有巡视线路中用时最长的，将计算出的最长路线巡视所用的时间作为巡视路线的最
8、短时间限定，在此限定下对路线进行设计。基于问题一二中图论的方法，从一些点的路线比较少的点开始，能够使搜素容易进行，因此选择从距离点一些较远的点（如12 10 15 22等点）开始搜索，每次搜索时都要对该点的巡视时间进行判断，直到找到近似最优路线。针对问题四：在巡视组数已定(如三组）的情况下，为尽快完成巡视就要求每组完成的巡视时间尽量均衡，因为总的完成巡视时间按线路最长的完成巡视时间计算，由于组数一定， T，t和V改变，对每组内的最佳巡视路线是没有影响的，但可能会影响到各组件的均衡性，因此问题实质是讨论T，t和V对分组的影响，即在不破坏原来分组均衡的条件下T，t和V允许的最大变化范围。需要用控制
9、单一变量的方法，分别讨论T、t、V三个量中任意两个量不变时第三个量的变化范围。从而确定T，t和V的改变对最佳巡视路线的影响。4. 数据分析4.1问题一数据分析基于对该县公路图的初步分析，可以统计出该县有乡（镇）17个，村35个。（线路图见附录一）应用lingo软件求解(具体程序见附录三)得出巡视点距离县政府所在地的最短距离，如表1所示：表1：点到其余各点的最短距离PR1C2M26O10.112.9611.59.219.820.6282931AB35O22.220.822.116.311.91417.5N2520L67DO31.131.838.33927.234.522.248E9F1012O3
10、4.949.741.749.555.165.967.311GH1314J19O55.962.777.564.172.754.346.218I15161722KO52.961.169.960.353.54943.721232427Q3032O39.63944.328.42835.730.2333534O23.73627.8由此表格画出了最短路径生成图，如图1图 1由上图便于在第一问分析得到分组情况。4.2问题二数据分析问题二中给出了巡视小组在乡（镇）村的停留时间和汽车行驶速度，分别为：巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。对于要在24小
11、时内完成巡视，至少应分几组的问题，应首先求出最长路线巡视所用的时间，用停留总时间加上行走时间除以4的结果与24进行比较，以此判断最少分组能否为4组。计算如下：(17*2+35+599.8/35)/4=21.524(小时)（其中路线长度估算为599.8公里）因此最少分组可定为4组。 5 问题一的解答本文研究的是灾情巡视路线的最优设计问题，由于路线图可看成网络图，因此此问题可转化为在给定的加权网络图中寻找线路使总权（路程或时间）最小的问题。然后针对具体问题，采用一些启发式算法，建立模型。5.1模型一的建立5.1.1模型一的准备经对问题的初步分析，基于图论的相关知识，将公路网图中每个乡（镇）、村看成
12、图中的一个节点，各乡镇村之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为图论中的加权网络图，问题就转化为一个图论问题，即在给定的加权网络图中寻找从定点出发，行遍所有顶点至少一次再回到点，使得总权（路程或时间）最小。定义经过图的每个顶点正好一次的圈，称为的哈密尔顿圈，简称圈。定义 在加权图中（）权最小的哈密尔顿圈称为圈：（）经过每个顶点至少一次且权最小的闭通路称为最佳推销员回路。由定义（2）可知本问题是一个寻求最佳推销员回路的问题，最佳推销员回路的问题可以转化为最佳圈的问题，方法是由给定的图（，）构造一个以为顶点集的完备图=（，）中每条边（x y
13、）权等于顶点x与y在图中最短路径的权，即。在图论中有以下定理：定理 加权图的最佳推销员回路的权和的最佳圈的权相同。定理2 在加权完备图中求最佳圈的问题是NP完全问题。我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下：算法一 求加权图（，）的最佳推销员回路的近似算法：用图论软件包求出中任意两个顶点间的最短路，构造出完备图（，）输入图的一个初始圈；用对角线完全算法2产生一个初始圈；随机搜索出中若干个圈，例如3000个；对步所得的每个圈用二边逐次修正法2进行优化，得到近似最佳圈；在第步求出的所有圈中，找出权最小的一个，此即要找的最佳圈的近似解。（算法程序见附录）由于二边主次修正
14、法的结果与初始圈有关故本算法第步分别用三种方法，产生初始圈，以保证能得到较优的计算结果。在此问题是多个推销员的最佳推销员回路问题，即在加权图中求顶点集的划分1，将G分成n 个生成子图G， ，Vn，使得：顶点，1,2,3，n.，其中i 为导i的导出子图G中的最佳圈，w(Ci)为Ci 的权，i，j=1，2，3，n.定义3 称为该分组的实际路线均衡度，为最大允许均衡度，显然01，越小说明分组的均衡性越好，取定一个后，与满足条件3的分组，条件4表示总巡视路程最短。此问题包含两个方面：第一，对点分组；第二，在每组中寻求最佳推销员回路，即为单个推销员的最佳推销员问题，我们只能去寻求一种较合理的划分准则，对图进行初步划分后，求出各部分的最佳推销员回路的权，在进一步进行调整，使得各部分满足均衡性条件3.从点出发去其它点，要使路程较小应尽量走点到该点的最短路，故用图论软件包求出点到其余顶点的最短路，这些最短路构成一棵以为树根的树，将从点出发的树枝
