《灾情巡视路线的数学模型参考模板》由会员分享，可在线阅读，更多相关《灾情巡视路线的数学模型参考模板（38页珍藏版）》请在金锄头文库上搜索。
1、灾情巡视路线的数学模型摘要 本文是解决灾情巡视路线最佳安排方案的问题。某县领导将带人下乡巡视灾情，打算从县城出发，视察所有乡、村后返回县城。为确定安排巡视路线，本文将此安排问题转化为旅行售货员问题，建立了四个最优化模型解决问题。对于问题一,建立了双目标最优化模型。首先将问题一转化为三个售货员的最佳旅行售货员问题，得到以总路程最短和路程均衡度最小的目标函数，采用最短路径的算法，并用MATLAB软件编程计算，得到最优树图，然后按每块近似有相等总路程的标准将最优树分成三块，最后根据最小环路定理，得到三组巡视路程分别为208.8、205.3和210.5，三组巡视的总路程达到624.6，路程均衡度为,具
2、体巡视路线安排见表1。对于问题二，建立了单目标最优化模型。首先根据条件计算可确定至少要分4组巡视，于是可将问题转化为四个售货员的最佳旅行售货员问题，采用算法求出巡视路线的最小生成树。再根据求最优哈密顿圈的方法，运用LINGO软件编程计算，求出了各组的最佳巡视路线。各组巡视的路程分别为、184、136.5、186.4，时间分别为22.41、22.26、21.90、21.33,时间均衡度为4.82%，具体巡视路线安排见表2。对于问题三, 建立了以最少分组数为目标函数的单目标最优化模型。运用问题一中最短路径的Dijkstra算法，运用LINGO软件编程计算,得到从县城到各点的最短距离，再经过计算可得
3、到本问的最短巡视时间为6.43小时。最后采用就近归组的搜索方法，逐步优化，最终得到最少需要分22组进行巡视，具体的巡视方案见表3。对于问题四，建立了单目标优化模型，并且对变量进行讨论。在分析乡（镇）停留时间，村庄停留时间和汽车行驶速度的改变对最佳巡视路线的影响时，我们通过控制变量的变化，初步的得出了当与变化时和变化时对最佳巡视路线的影响。关键词 最优化模型 旅行售货员问题 最优哈密顿圈 / 1.问题重述今年夏天某县遭受水灾,为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。（路线相关信息见附表1）
4、本文需解决的问题：问题一：若分三组巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 问题二：假定巡视人员在各乡（镇）停留时间=2小时，在各村停留时间=1小时，汽车行驶速度=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 问题三：在上述关于, 和的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论，和改变对最佳巡视路线的影响。2.模型假设与符号说明2.1模型的假设假设1：巡视人员足够多，汽车足够多；假设2：每组视察路线的路况相同，并
5、且各汽车的平均速度相等；假设3：每个乡（镇）、村均只视察一次，第二次经过时不作停留；假设4：各巡视小组只在各自计划的乡（镇）、村停留，非计划之内的乡（镇）、村可以经过，但是不停留。假设5：在乡镇的停留时间与在村的停留时间成正比例关系。2.2符号说明赋权连通图赋权连通图的第个子图子图中的最佳回路边的边权点的点权的各边权之和的各点权之和巡视中在每个乡镇停留时间巡视中在每个村的停留时间汽车行驶速度各乡(镇)、村所在地县政府所在地对应示意图中的公路乡（镇）、村的总个数第组停留的乡（镇）数第组停留的村数3.问题分析本文是领导视察受灾县,并求最佳巡视路线的数学建模问题，题中已给出该县公路的网络图，要求在不
6、同的题目要求下，得到灾情巡视的最佳分组方案和路线。若将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员的问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O，使得总权（路程或时间）最小. 本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又可使边上的权之和达到最小的闭链（闭迹）,即最佳旅行售货员问题。针对问题一, 要求分三组（路）巡视，得到总路程最短且各组尽可能均衡的巡视路线，可转化为三个售货员的最佳旅行售货员
7、问题。先用MATLAB软件编程计算得到加权网络图的最小生成树，按每块近似有相等总路程的标准将最小生成树分成三块，每一块都转化为一个最佳旅行售货员问题。再确定总路程最短且满足各组尽可能均衡的路线的目标函数，最后对目标函数适当改进，得到最终的双目标最优化模型。针对问题二，由于T=2小时，t=1小时，V=35公里/小时,需访问的乡镇共有17个，村共有35个。计算出在乡(镇)及村的总停留时间为小时，要在24小时内完成巡回，若不考虑行走时间，有:69/k24(k为分的组数). 得k最小为4，所以至少要分4组。于是将题目转化为四个售货员的最佳旅行售货员问题，再用与问题一类似的方法运用MATLAB软件编程计
8、算求解，即可得到问题二的结果。针对问题三, 从起始点O出发，中途不作任何停留，直接沿最小生成树路线巡视到距O最远的点，并仅在此点停留，再返回，得到最短巡视时间。为避免人力浪费，且满足条件，以分组最少的巡视方法为单目标函数建立模型求解。针对问题四，实际上是一个变量讨论问题。在分析乡（镇）停留时间T，村庄停留时间t和汽车行驶速度V的改变对最佳巡视路线的影响时，我们通过控制不同变量的变化，初步的得出了当T与t变化时和V变化时对最佳巡视路线的影响。4.问题一的解答针对问题一，建立模型一4.1模型的建立4.1.1目标函数的确定 均衡度分析：我们把称为该分组的实际路程均衡度。为最大容许均衡度。显然01，越
9、小，说明分组的均衡度越好。由问题一的分析，将乡村公路示意图抽象为一个赋权连通图，再把图分成三个子图（=1,2,3）,在每个子图中寻找最佳回路（=1,2,3），为回路的各边权之和。要使总路程最短且各组有尽可能均衡的巡视路线，确定的目标函数应该为： 易知，上式两个目标函数相互矛盾，不可能同时达到。然而，要使总路程最短，可以尽量让每个子图的边权之和最小，又边权为，n为每个子图中乡（镇）、村的总数，则有：4.1.2综上所述,我们得到问题一的模型 4.2模型的求解与分析 根据最短路径的原理，用MATLAB软件编程计算得到图的最优树，如下图所示： 图一由于在最优树上,各边权接近,要使最优树分解时, 分解结
10、果尽量均衡，则各子图包含的顶点就应尽量接近(35+17)/3=17个，由此得到最优树的分解原则如下：（1）分解点为O点或尽可能接近O点；（2）分解所得的三个子图包含的顶点数尽可能接近17个；（3）尽量使分解所得的子图为连通图；（4）尽量使子图与O的最短路上的点在该子圈内，尽量使各子图内部形成环路。根据以上原则，得到分解后的结果图如下图所示： 图二通过增环、扩环、换枝等方法，对子图内部进行适当调整优化，寻找出最佳巡视回路，运用LINGO软件编程计算得到结果如下表： 表1 分三组巡视的路线 单位（公里）小组路线路程之和总路程一O,M,N,25,20,L,19,J,18,I,15,I,16,17,2
11、2,K,21,23,24,27,26,P,O208.8624.6二O,1,A,33,31,R,29,Q,28,Q,30,32,35,34,B,C,3,D,4,D,3,2,O205.3三O,2,5,6,7,E,8,E,11,G,13,14,H,12,F,10,9,E,5,2,O210.5根据上表数据，得到分组路程均衡度为. 本题的分组路程均衡度为，说明本题分组路程均衡性很好，满足题目要求的均衡路线，但是总路程稍长，达到了624.6公里。5.问题二的解答针对问题二，建立模型二5.1模型的建立5.1.1目标函数的确定 由问题二的分析知，要满足条件，最少要分成4组进行灾情巡视。若，（=1,2,3,4）
12、分别为该组停留的乡（镇）和村数，则各组所花费的时间为：此问题与问题一的情况类似，为得到最佳巡视路线图，就要让各组所花费的总时间最小，花费时间最多的组花费的时间也要尽可能小，于是有目标函数如下：类似于问题一，把花费时间最多的组花费的时间尽可能小作为主要判断依据，最终确定单目标函数：5.1.2确定约束条件要使总路程最短，应尽量让每个子图的边权之和最小，又边权为，则有：对有以下四个约束条件（1）每个点只有一条边出去，即（2）每个点只有一条边进去，即（3）除起点和终点外，各边不构成圈5.1.3综上所述,我们得到问题二的模型5.2模型的求解 根据算法原理，用MATLAB编程计算得到最小生成树（程序见附录
13、），结果如下图所示： 图三此最小生成树分解方法类似于问题一，为得到最佳巡视路线图，乡村数的均衡性和各组时间的均衡性是分组的主要依据，故有平均每个子图中点权和为(172+35)/4=17,得到分成四组时的最小生成树分解原则如下：（1）分解点为O或尽量接近O； （2）分解后的各子图尽量为连通图；（3）生成的子图容易形成圈或接近圈；（4）使各子图中的点权和尽量接近17；根据以上原则，得到分解后的结果图如下图所示： 图四通过增环、扩环、换枝等方法，对子图内部进行适当调整优化，寻找出最佳巡视回路，运用LINGO软件编程计算得到结果如下表：表2 分4组巡视的路线小组路线路程之和时间总路程一O,P,28,2
14、7,26,N,24,23,22,17,16,17,K,21,25,M,O154.322.41661.2二O,2,5,6,L,19,J,13,14,H,14,15,I,18,K,21,20,25,M,O18422.26三O,C,B,34,35,32,30,Q,29,R,31,33,A,R,31,33,A,1,O136.521.90四O,C,3，D,4,8,E,11,G,12,F,10,F,9,E,7,6,5,2，O186.421.33由上表可发现，第二组和第一组有重叠点：K，21，25，M;第四组和第二组有重叠点：2，5，6；第四组和第三组有重叠点：C。这些点是该组非计划之内的乡（镇）、村,故该组在巡视时,可以经过这些地方，但是不停留。5.3结果的分析由上表可知，分为4组巡视时，各组巡视时间均在22小时左右，消耗最长时间的小组所消耗的时间为22.41小时24小时，满足题目条件的要求，证明分为4组进行巡视是可行的。再进行均衡度分析，分析如下：分组的时间均衡度为： 由上式可以看出，问题二分组方法的时间均衡度很好。6.问题三的解答针对问题三，建立模型三6.1模型的建立6.1.1目标函数的确定 问题一中计算出了从县城到各点的距离（见附表程
