您好,欢迎访问三七文档
1西安邮电大学暑期大学生数学建模培训作业三小组人员:左虎博夏朝阳康敏2013年08月07日2摘要针对问题一,我们先采用直观分析法进行试探,再结合最小生成树法分析求解并得到更优解。若分三组巡视,最小生成树法求解各组的巡视路程分别为214.7km、198.9km、227.6km,总路程为641.2km,路程均衡度为12%。然后结合最小生成树原理和哈密顿回路法,重新设计分组路线,并结合地理位置和最优单旅行商路线对第二种方法进行略微的修改,得倒的各组的巡视路程分别为200.7km、196.5km、206km,总路程为603.2km,路程均衡度为4.61%。此结果下的总路程相对较短,而均衡度偏高。基于对问题一结果的分析,发现分三组的情况下,不能满足题目要求。因此我们我们通过理论证明得到最少得分四组进行巡视。通过将G图分为4个子图,并运用哈密顿回路法找出各个组的最佳巡视路线。然后,计算出各组最佳巡视路线的总长度及汽车行驶所需时间,同时算出各组的停留时间,从而得到各组完成巡视的最佳时间。同样以巡视路程最短和时间均衡度最小为目标函数,各巡视时间小于24小时作为约束条件建立多目标规划模型。采用Lingo软件进行编程求解(程序见附录3)得到4个组的最优巡视路线,并计算出各组巡视的总时间。对于问题三,在巡视人员足够多的情况下,巡视距离O点最远的点所用的时间为最短时间,最短时间约为6.43小时。根据最短路径树,从远到近,依次巡视各村镇,在所用时间不大于最短时间的前提下,各组尽可能多的巡视几个村镇,进行分组确立巡视点,并对已巡视过的点进行逐个剔除。结合Matlab编程得到的最短距离矩阵和人工记录分析,得出分组情况及巡视路线(见附表),对于问题四,在组数固定时,则各组的最短路径就已确定,在最佳路径不变的情况下,t、T、V改变影响的只是整个巡视时间。我们利用matlab编程画图得到问题二中个别分组的路径的T、t、V与巡视时间的关系曲线。通过观察曲线发现:①停留时间t与巡视时间呈线性关系,无论t取何值,对巡视时间影响都较大;②当速度V较小时,V的变化对巡视时间的影响较大;当速度V足够大时,V的变化对巡视时间的几乎无影响。在t变化和V较大幅度减小时,都需适当调整分组,甚至重新分组。关键词:哈密顿改良圈,最小生成树,MATLAB,prim算法3目录1.问题重述………………………………..12.模型假设与符号说明…………………...23.问题分析……………………………..34.模型建立与求解………………………...45.模型评价………………………………186.参考文献………………………………197.附录…………………………………….201一、问题重述1.1问题背景2008年夏天某县遭受水灾.为考察灾情、组织自救,县领导决定,带领有关部门负责人到全县各乡(镇)、村巡视.巡视路线指从县政府所在地出发,走遍各乡(镇)、村,又回到县政府所在地的路线。1.2问题内容1.若分三组(路)巡视,试设计总路程最短且各组尽可能均衡的路线。2.假定巡视人员在各乡(镇)停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度V=35公里/小时.要在24小时内完成巡视,至少应分几组;给出这种分组下你认为最佳的巡视路线。3.在上述关于T、t和V的假定下,如果巡视人员足够多,完成巡视的最短时间是多少:给出在这种最短时间完成巡视的要求下,你认为最佳的巡视路线。4.若巡视组数已定(如三组),要求尽快完成巡视,讨论T,t和V改变对最佳巡视路线的影响。2二、模型假设与符号说明2.1模型假设1.公路不考虑等级差别,也不受灾情或交通情况的影响;2.各条公路段上汽车行驶的速度可以认为是均匀的;3.巡视人员在各乡(镇)、村停留的时间一定,不会出现特殊情况而延误时间;4.各巡视组巡视的乡(镇)、村不受行政区划的影响,即某乡(镇)与隶属于它的村不一定要分在同一组内;5.忽略不计巡视人员上、下车所用的时间;6.当巡视比较偏僻的乡村时,汽车从县镇府出发直至到达终点,中途不会停留,仅在终点站停留T(或t)小时,然后按原路返回,到达沿途各站接回巡视人员。2.2符号说明k:巡视人员的分组数;(,)GVE:赋权连通图;iG:赋权连通图的第i个子图(1,2,)i,k;iL:子图iG中的最佳回路;ic:最佳回路iL的各边权之和;ih:最佳回路iL的巡视时间;ijw:第i个乡、村到第j个乡、村的距离(j1,2,53)i,,;T:巡视员在各乡(镇)的停留时间;t:巡视人员在各村停留的时间;V:汽车行驶的速度,单位公里/小时。3三、问题分析首先,本题所求的是分组巡视的最佳路线,应与多旅行商问题类似。1)最佳旅行商问题可转化为最佳哈密尔顿回路的问题。在一般图中,最佳旅行线路未必为最佳哈密尔顿回路,首先哈密尔顿回路未必存在,其次就算哈密尔顿回路存在,也未必是最佳旅行线路。所以需要转化。转化方法是,在图G的基础上构造一个完全图G′,点集仍为N,每条边(i,j)的权w(i,j)为点i与j在G中最短路的长。于是,在G中寻求最佳旅行商回路的问题即为在G′中寻求最佳H-回路的问题。2)多旅行商问题可转化为单旅行商问题。3)在均衡性的要求下,上面的转化方法可能会得到比较差的结果。因此,这个问题应该先分组,再用单旅行商问题的方法求解。1.问题一的分析1)分组方法和依据地理位置、最小生成树、最短路生成树、最优单旅行商路线2)均衡性的度量a=(max(Ci)-min(Ci))/max(Ci)3)调整策略及依据各路线的长度、相邻点的数量、两组点间的距离2.问题二的分析1)确定最少组数停留时间:17*2+35*1=692)停留时间与路程的转化3)解法类似第一问,顶点数、转移点3.问题三的分析1)首先应确定最短时间2)分组依照最小距离树和由远及近原则4.问题四的分析对于问题四,也可以结合问题二(在分四组去巡视的前提下),要求尽快完成巡视,分析村、乡镇停留时间及汽车行驶速度对巡视路线的影响。鉴于均衡度系数较低与寻访点个数相差不大,我们可以利用matlab编程画图得到问题二中个别分组的路径的T、t、V与巡视时间的关系曲线。通过曲线走势直观分析,得出结论。4四、模型建立与求解4.1问题一模型的建立及求解:4.1.1模型一的建立与求解(直观分析法):根据题中所给的乡(镇)、村示意图对地理位置进行粗略的划组分析。很显然,由于县政府位置偏向东面,则若分成三组巡视,县城远离的一边分为两块的可能性比邻近县城的一边大得多,这样就可以得到手工给出的三组巡视路线图见表1:表1:三组巡视路线的详细情况对比图为了衡量分组的合理性,于是我们定义分组的路程均衡度公式:123123123max,,min,,max,,ccccccccc;显然01,值越小,说明分组的均衡性越好。由此我们可以得到采用直观分析法时的均衡度%67.121。4.1.2模型二的建立与求解(基于最小生成树法)现要分三组巡视,则需要把图G分成三个子图(1,2,3)iGi,在每个小组名称路线总路线长度路线的总长度IO—1—B—34—35—33—A—R—31—32—30—Q—28—27—24—N—26—P—29—R—O214.7641.2IIO—P—26—N—23—22—17—16—I—15—14—13—J—18—K—21—25—20—L—6—M—O198.9IIIO—C—3—D—4—8—E—F—10—F—12—H—12—G—11—J—19—L—7—6—5—2—O227.65子图iG中寻找最佳回路(1,2,3)iLi。因为最小生成树中能包含图G中所有的顶点E,而且最小树的边权是相邻两顶点间的距离,它描述了顶点之间的相近程度,故可以采用最小生成树进行分组。本模型的主要思想是:首先采用Prim算法得到G图的最小生成树,然后基于最小生成树生成一个可行的巡视路线,求得路线的最优总路程为。采用Prim算法求解最小生成树步骤如下:(1)输入加权连通图G的带权邻接矩阵((,))nnAaij;(2)建立初始候选边表,BT;(3)在候选边表中选出最短边(,),(,)uvTTuv;(4)调整候选边表B;(5)重复(2),(3),直到T含有1n条边。根据Prim算法进行编程求解(具体程序见附录1),于是我们得到G图的最小生成树如图1。图1现对已得到的最小生成树进行分解,以获得三个子图iG并使得分解结果尽6量均衡。由于在最小生成树上,边权接近可以近似认为均衡即各子图包含的顶点数应接近。因此,各个子图的顶点数应尽量接近17个,且遵循以下分解原则。最小生成树分解原则:(1)分解点为O点或尽可能地接近O点;(2)分解所得的三个子图Gi的顶点数尽可能地接近17个;(3)尽量是分解所得的子图是连通图;(4)尽量使子图Gi与点O的最短路上的点在该子图内,且尽量使各子图的点在子图内部形成环路。依据以上分解原则得到的分解结果如图2。图2然后,采用哈密顿回路法求解每个子图内的最佳巡视路线。寻找最佳巡视路线实际上就是在赋权图中寻找最优的哈密顿圈,包含图G的每个顶点的圈称为哈密顿圈。于是问题就可以转化为:现已知三个子图内乡、村与乡、村之间的距离,从县镇府O出发,经过子图内的所有乡、村,最后又回到点O。将划分好后的点通过MATLAB进行哈密尔顿改良圈处理,我们可以得到三个分组的哈密尔顿改良圈的连接方式。再进过我们的初步拟合和处理,我们得到了表2。7表2:哈密尔顿回路法得到的三组路线由此,可以计算出对模型二初步改进后的分组的均衡度为:%82.72从上述图表中不难看出,第二组走的路程稍长,而第一组与第三组走的路程过短,其间差值较大,故为了使分组的均衡性更好,我们需在基于最小生成树的原则之上对原来的分组进行适当的调整。为了缩小第二组与其他两组间的路程差,首先,我们将第二组的K点附近的路线进行修改,使之延K,22,17,16,I,15,14,再在J点处过一趟18处;然后将H点划到第三组,并将E点到4相连,过4后走D,3,C回到O点,如此可以有效地减少了第二组的路程,稍微地减少了第一组和第三组的路程;最后,采用Hamilton圈法分别求解三个子图内的最佳回路(表3)。表3:最终改进路线图的分组情况注:加有底纹的表示只经过此点但不停留。由此,可以计算出对模型二最终改进后的分组的均衡度为:%61.43。名称路线总路线长度路线的总长度IO—1—B—A—34—35—32—31—R—29—Q—30—Q—28—27—26—N—23—24—27—26—P—O205635.8IIO—M—25—20—L—19—J—13—14—H—14—15—I—18—K—17—16—17—22—K—21—25—M—O222.4IIIO—2—5—6—7—E—11—G—12—F—10—F—9—E—8—E—7—D—4—D—3—C—O208.4小组名称路线总路线长度路线的总长度IO—1—B—A—34—35—32—31—33—A—R—29—Q—30—Q—28—27—24—23—N—26—P—O200.7603.2IIO—M—25—21—K—22—17—16—I—15—14—13—J—18—J—19—L—20—25—M—O196.5IIIO—C—3—D—4—8—E—9—F—10—F—12—H—12—G—11—E—7—6—5—2—O2068综上所述,对比模型一和改进后模型二的结果可知,若分成三组巡视,虽然改进后模型二的巡视总路程比模型一的短,而且,改进后模型二分组的均衡性比模型一要好很多。此外,模型二的结果是经过严谨科学的计算得到的,具有较高的可信度,相比之下,模型一的结果是人根据地理位置粗略划分得到地,具有随机性,可信度较低。经上述分析可知,若分成三组巡视,则应该采用改进后模型二的巡视路线,见图3。图394.2问题二的模型建立及求解:此问添加了巡视组在各乡(镇)停留的时间2T小时,在各村停留的时间1t小时以及汽车的行驶速度35v公里/小时的条件后,要求在24小时内完成巡视的最少分组数以及相应的最佳巡视路线。此时需访问的乡(镇)共有17个,村共有
本文标题:灾情巡视路线模型
链接地址:https://www.777doc.com/doc-4419663 .html