《灾情巡视路线的数学模型参考模板.doc》由会员分享，可在线阅读，更多相关《灾情巡视路线的数学模型参考模板.doc（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 / 381.问题重述今年夏天某县遭受水灾,为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。（路线相关信息见附
4、表1）本文需解决的问题：问题一：若分三组巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 问题二：假定巡视人员在各乡（镇）停留时间=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目标函数的确定 均衡度分析：我们把称为该分组的实际路程均衡度。为最大容许均衡度。显然0
9、1，越小，说明分组的均衡度越好。由问题一的分析，将乡村公路示意图抽象为一个赋权连通图，再把图分成三个子图（=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,1
11、7,22,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
12、,4）分别为该组停留的乡（镇）和村数，则各组所花费的时间为：此问题与问题一的情况类似，为得到最佳巡视路线图，就要让各组所花费的总时间最小，花费时间最多的组花费的时间也要尽可能小，于是有目标函数如下：类似于问题一，把花费时间最多的组花费的时间尽可能小作为主要判断依据，最终确定单目标函数：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,2
14、8,27,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。这些点是该组非计划之内的乡（镇）、村
15、,故该组在巡视时,可以经过这些地方，但是不停留。5.3结果的分析由上表可知，分为4组巡视时，各组巡视时间均在22小时左右，消耗最长时间的小组所消耗的时间为22.41小时24小时，满足题目条件的要求，证明分为4组进行巡视是可行的。再进行均衡度分析，分析如下：分组的时间均衡度为： 由上式可以看出，问题二分组方法的时间均衡度很好。6.问题三的解答针对问题三，建立模型三6.1模型的建立6.1.1目标函数的确定 问题一中计算出了从县城到各点的距离（见附表程序一的结果），可以知道离县城最远的乡为点，距离为77.5公里，因此单独巡视该乡所需时间为小时。故无论如何分工巡视，完成巡视至少需要6.43小时。故确定
16、以最少分组为目标的目标函数： 要在最短时间内完成巡视，即巡视时间小于等于6.43小时，有其中，分别为图中权为的点的个数。6.1.2综上所述,我们得到问题三的模型 6.2模型的求解定义最小生成树的分支上未分组的点中到O最远的点为，次最远点为，依此类推，直至离O最近的点。O点到点N的时间记为，停留时间记为。将看成第一组，再根据约束条件判断分组情况，判别方法如下：（i）若，则点应单独分在一组；若，则和分为一组。同理，可依此类推判断直至待判点不能和前面已判点分在一组。（ii）再在分支上未分组的点中找到离O最远的点，作为下一组，用上述同样的 方法判断，直至所有节点分组完。按以上求解过程，逐步求解可得以下
17、共分22组巡视方案： 表3 分为22组巡视路线 组号 分组路线花费时间路程1HO,2,5,6,7,E,9,F,12,H,12,F,9,E,7,6,5,2,O6.43155212,7O,2,5,6,7,E,9,F,12,F,9,E,7,6,5,2,O5.85134.6310,8O,2,5,6,7,E,9,F,10,F,9,E,8,E,7,6,5,2,O6.23147.84F,9O,2,5,6,7,E,9,F,9,E,7,6,5,2,O6.19110.25GO,2,5,6,7,E,11,G,11,E,7,6,5,2,O5.58125.4611,EO,2,5,6,7,E,11,E,7,6,5,2,O
18、6.19111.8714,13O,2,5,6,L,19,J,13,14,13,J,19,L,6,5,2,O6.15145.48J,19O,2,5,6,L,19,J,19,L,6,5,2,O6.10108.69L,6,5O,2,5,6,L,6,5,2,O6.2378104,D,2O,2,3,D,4,D,3,2,O5.9969.8113,C,BO,2,3,C,B,1,O6.2844.81215,20O,M,25,21,K,18,I,15,I,18,K,21,25,20,25,M,O6.37152.813IO,M,25,21,K,18,I,18,K,21,25,M,O5.49122.21418,KO
19、,M,25,21,K,18,K,21,25,M,O6.02105.81516,17O,M,25,21,K,17,16,17,K,21,25,M,O5.45120.61621,25,MO,M,25,21,25,M,O6.2679.21722,24,23O,P,26,N,23,22,23,24,23,N,26,P,O6.31115.818N,26,27O,P,26,N,26,27,26,P,O6.2277.81929,28,PO,P,28,Q,29,R,O5.6758.52030,32,QO,R,29,Q,30,32,31,R,O6.1876.221R,A,1O,R,A,1,O6.09382234
20、,35,33,31O,1,A,34,35,33,31,R,O6.4284.7 上表中，在共22组的巡视路线中，分组一栏中为巡视停留点，路线其它点均是只经过，不停留。6.3结果的分析 由以上表格，可以看出各组巡视的时间差别不大，所耗费最大时间也未超过题目要求的最小时间6.43小时，故分成22组是可行的。但我们采用的是就近归组的搜索方法，逐步优化，得到的最少需要分22组，故22组分法是否是最小数组，因论证过程较繁复，此处就不再讨论。7.问题四的解答针对问题四，建立模型四7.1模型的建立7.1.1目标函数的确定由问题四的分析知，本题要讨论参数T，t和V的改变对最佳巡视路线的影响。且要尽快完成巡视，就
21、要求花费时间最多的组花费的时间尽可能小。易知各组花费时间为：则可得到目标函数：要求在时间均衡度最小时讨论，故有约束条件：7.1.2综上所述,我们得到问题四的模型 7.2模型的求解在上述表达式中，由于T和t的作用完全相仿，所以为简化讨论起见，对于任意给定的T和t，不妨记。即这里可简记为：它是t和的的线性函数，将随着t和增大(即V的减小)而增大.于是我们容易得到以下结论：（1）若t（T）增大而V不变，为了使最大值尽可能小，就要求的最大值尽可能小.但是当T和t的关系确定后，实际上就是定值，其中m是全县的乡(镇)数17，n是全县的村数35。上述要求就成为各组停留在询问乡村的总时间尽可能均匀.用数学式子
22、表示即为:这里表示数的上整数和下整数.当然，在调整各组停留的乡村数使之达到均衡时，自然会给各组的路线及其长度带来影响.这时应当考虑进行适当调整。（2）若不变而增大.这种情况下，今起主导作用。那么，和（1）中的结论类似，我们更应使即各组的巡视路线尽可能均衡。诚然，因为不是常数，而且的均衡性会带来的增大，这对于尽快完成巡视会带来负面影响。所以对具体情况应作具体分析，比如可以考虑的前半部份对均衡性的修正，对路程较长的组尽量考虑停留较少乡村。8.模型的评价、改进及推广8.1模型的评价优点:模型有较强的理论应用性，对任意给出有各边权值的图G，都能够分为若干个子图，简化问题,便于求解；缺点：模型中只考虑了
23、路程与时间两种因素，未考虑其他影响因素，忽略了现实生活中对模型有很大影响的重要指标，如人力资源，巡视经费等。这样模型的实用性就降低了。8.2模型的改进（1）在问题二中，未论证22组是否为最小分组方法，若时间充足，应进行论证，使模型的结果更为可靠。（2）建模时可以考虑更多的因素，让模型实用性更强，比如说，如何让巡视过程中花费最小。8.3模型的推广该问题为旅行售货员问题，可以应用的范围较广，在图形数据处理及简化方面均可运用该模型均作为参考。9.参考资料1姜启源，数学建模（第三版）M，北京：高等教育出版社，20032徐权智，杨晋浩，数学建模M，北京：高等教育出版社，20043韩中庚，数学建模方法及其
24、应用M，北京：高等教育出版社，20054宋来忠，数学建模与实验M，北京：科学出版社，20055田贵超，黎明，韦雪洁.旅行商问题（TSP）的几种求解方法J.计算机仿真，2006.8（8）10.附录附录一 某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数题一程序一.县城到O到各点的距离程序及结果model: sets: cities/A35,A34,A33,A32,A31,A30,A29,A28,A27,A26,A25,A24,A23,A22,A21,A20,A19,A18,A17,A16,A15,A14,A13,A12,A11,A10,A9,A8,A7,A6,A5,A4,A3,A2,
25、A1,R,Q,P,N,M,L,K,J,I,H,G,F,E,D,C,B,A,O/:fl; roads(cities,cities)/A35,A34 A35,A33 A35,A32 A34,B A34,A A32,A33 A31,A33 A33,A A32,A31 A30,A32 A31,R A30,Q A29,R Q,A29 A29,P A27,A28 Q,A28 A28,P A27,A26 A24,A27 A26,P N,A26 A21,A25 A20,A25 N,A25 A25,M A24,A23 A24,N A22,A23 A23,A21 A23,N A17,A22 A22,K A21,A
26、20 K,A21 A19,A20 A20,L A19,L J,A19 A18,K A18,J I,A18 A16,A17 A17,K A16,I A15,A14 A15,I A14,A13 H,A14 A13,J A13,I A13,G H,A12 A12,G A12,F J,A11 G,A11 A11,E A10,F F,A9 A9,E A8,A4 A8,E A7,A6 L,A7 E,A7 A7,D A6,A5 M,A6 L,A6 A5,A2 M,A5 D,A5 A4,D A3,A2 D,A3 A3,C A2,O C,A1 B,A1 A,A1 A1,O A,R R,O P,O N,M M,O
27、 I,J C,B C,O/:w,p; endsets data: w=8.2 20.3 14.9 17.6 11.5 19 7.3 7.4 8.1 10.3 9.2 7.7 7.9 7.2 15.2 7.9 8.3 12.1 7.8 18.8 10.5 10.5 7.8 6.5 8.8 12 8.9 13.2 10 9.1 7.9 6.7 10.1 7.9 4.1 9.3 5.5 7.2 8.1 9.2 8.2 8.2 6.8 9.8 11.8 15 8.8 8.6 9.9 9.8 16.4 8.6 10.2 7.8 12.2 13.2 6.8 14.2 10.8 5.6 7.8 20.4 8
28、 7.3 14.5 7.2 15.1 9.7 9.5 11.8 8.3 11.4 11.3 12.7 4.8 8.2 7.9 9.2 11.2 5.9 10.3 6 8.8 12.9 10.1 14.2 19.8 15.8 11 11.5; enddata n=size(cities); fl(n)=0; for(cities(i)|i#lt#n:fl(i)=min(roads(i,j):w(i,j)+fl(j); for(roads(i,j):p(i,j)=if(fl(i)#eq#w(i,j)+fl(j),1,0);endFeasible solution found. Total solv
29、er iterations: 0 Variable Value N 53.00000 FL( A35) 36.00000 FL( A34) 27.80000 FL( A33) 23.70000 FL( A32) 30.20000 FL( A31) 22.10000 FL( A30) 35.70000 FL( A29) 20.80000 FL( A28) 22.20000 FL( A27) 28.40000 FL( A26) 20.60000 FL( A25) 31.80000 FL( A24) 44.30000 FL( A23) 39.00000 FL( A22) 49.00000 FL( A
30、21) 39.60000 FL( A20) 38.30000 FL( A19) 46.20000 FL( A18) 52.90000 FL( A17) 53.50000 FL( A16) 60.30000 FL( A15) 69.90000 FL( A14) 72.70000 FL( A13) 64.10000 FL( A12) 67.30000 FL( A11) 55.90000 FL( A10) 65.90000 FL( A9) 49.50000 FL( A8) 49.70000 FL( A7) 34.50000 FL( A6) 27.20000 FL( A5) 17.50000 FL(
31、A4) 34.90000 FL( A3) 14.00000 FL( A2) 9.200000 FL( A1) 6.000000 FL( R) 12.90000 FL( Q) 28.00000 FL( P) 10.10000 FL( N) 31.10000 FL( M) 19.80000 FL( L) 39.00000 FL( K) 43.70000 FL( J) 54.30000 FL( I) 61.10000 FL( H) 77.50000 FL( G) 62.70000 FL( F) 55.10000 FL( E) 41.70000 FL( D) 22.20000 FL( C) 11.50
32、000 FL( B) 11.90000 FL( A) 16.30000 FL( O) 0.000000程序二.环路一的最短路程model: sets: city/O,I,J,K,L,M,N,P,15,16,17,18,19,20,21,22,23,24,25,26,27/:u; links(city,city):dist,x; endsets data: dist=0, 61.1, 55.7, 43.7, 43.8, 19.8, 31.1, 10.1, 69.9, 60.3, 53.5, 52.9, 47.6, 38.3, 39.6, 49.0, 39.0, 44.3, 31.8, 20.6,
33、 28.4 61.1, 0, 15.8, 17.4, 31.1, 41.3, 38.1, 59.1, 8.8, 11.8, 18.6, 8.2, 23.9, 29.4, 21.5, 25.3, 30.6, 39.5, 29.3, 48.6, 56.4 55.7, 15.8, 0, 17.4, 15.3, 35.9, 32.7, 53.7, 24.6, 27.6, 27.2, 8.2, 8.1, 17.4, 21.5, 27.5, 30.6, 39.5, 23.9, 43.2, 51.0 43.7, 17.4, 17.4, 0, 17.5, 23.9, 20.7, 41.7, 26.2, 16.
34、6, 9.8, 9.2, 21.3, 12.0, 4.1, 10.1, 13.2, 22.1, 11.9, 31.2, 39.0 43.8, 31.1, 15.3, 17.5, 0, 24.0, 20.8, 41.8, 39.9, 34.1, 27.3, 23.5, 7.2, 5.5, 13.4, 27.6, 22.5, 31.4, 12.0, 31.3, 39.1 19.8, 41.3, 35.9, 23.9, 24.0, 0, 14.2, 29.9, 50.1, 40.5, 33.7, 33.1, 27.8, 18.5, 19.8, 32.1, 22.1, 27.4, 12.0, 24.7
35、, 32.5 31.1, 38.1, 32.7, 20.7, 20.8, 14.2, 0, 21.0, 46.9, 31.4, 24.6, 29.9, 24.6, 15.3, 16.6, 17.9, 7.9, 13.2, 8.8, 10.5, 18.3 10.1, 59.1, 53.7, 41.7, 41.8, 29.9, 21.0, 0, 67.9, 52.4, 45.6, 50.9, 45.6, 36.3, 37.6, 38.9, 28.9, 34.2, 29.8, 10.5, 18.3 69.9, 8.8, 24.6, 26.2, 39.9, 50.1, 46.9, 67.9, 0, 2
36、0.6, 27.4, 17.0, 32.7, 38.2, 30.3, 34.1, 39.4, 48.3, 38.1, 57.4, 65.2 60.3, 11.8, 27.6, 16.6, 34.1, 40.5, 31.4, 52.4, 20.6, 0, 6.8, 20.0, 35.7, 28.6, 20.7, 13.5, 23.5, 32.4, 28.5, 41.9, 49.7 53.5, 18.6, 27.2, 9.8, 27.3, 33.7, 24.6, 45.6, 27.4, 6.8, 0, 19.0, 31.1, 21.8, 13.9, 6.7, 16.7, 25.6, 21.7, 35.1, 42.9 52.9, 8.2, 8.2, 9.2, 23.5, 33.1, 29.9, 50.9, 17.0, 20.0, 19.0, 0,