南昌大学数学建模参赛论文--校园最短游览路线.doc

校园最短游览路线 摘要:本文建立了一个游览路线最优化模型.将游览路线问题转化为最佳推销员问题,并用算法去寻求最优解.通过对校园景点图的分析,我们首先把全校路线分为二部分,将图分为二个子图建立了数学模型.将基础实验大楼至医学院这一块分为A区,剩余那块为B区，结果就是这两个的合成.我们采用了一种近似算法的思路，利用Matlab数学软件编程和最小生成树两种方法求出第一部分的最短路径,第二部分的最短路径，两条路径相连接起来,于是我们得到了游览路线的最短路径.本文模型一中我们分别对理、工、文、医四种报考专业的同学根据自己的报考专业制定了四条不同的游览路线, 同时在模型二中给出了所有点都去的最优路线.并通过程序统计出总的路径条数。 关键词：最短路线；H圈；游览路线；二边逐次修正法 一 问题的提出 南昌大学校园开放日时，会有许多学生及其家长要求参观新校园.为此校方要在本校高年级学生中招募一批导游，负责接待并陪同考生及其家长乘坐校园游览车（电动平板车）参观游览.路线是从新校园正大门出发，最后返回到出发地. 假设你就是其中的一名导游，为了向所有参观者展现南昌大学的全部风貌和亮点，同时满足参观者了解南昌大学的不同要求，请你制定一份详细的校园游览计划，计划中应包括参观者下车参观的主楼、景点或场地. 具体要求是，根据图一的数据及考生的理、工、文、医四种报考专业，建立数学模型，分别设计4条不同的具体游览路线，使每条游览路线的总路程最短. 校园景点图 二 模型的假设 1.两景点除图中给出路径外没有其他的路. 2.游览车在路上不会出现抛锚等现象. 3.游览车在路上的速度总是一定. 4.同一性质景点只参观一次. 三 模型的分析 这是个求游览路线最短的问题,我们可以将关于游览最短路线问题转化为图的最短问题 A区 B区  于是原问题可分解为两个问题: 1.A中由正门出发经过所有点回到正门. 2.B中由基础实验大楼出发经过所有点回到基础实验大楼. (一)模型一求解 在加权图G中求最佳推销员回路是NP-完全问题,我们采用两种近似算法求出该问题的近似最优解,来代替最优解(见文献[4]). 求加权图G（V，E）的最佳推销员回路的算法一： 1.用图论软件包求出G中任意两个顶点间的最短路，构造出完备图，， ； 2.随机产生中若干个H圈，例如20000个 3.所得的每个H圈，用二边逐次修正法进行优化，得到近似最佳H圈； 算法中的完备图是由A区或B区的完备图经过图论软件得到,再通过matlab编程处理得来的. (程序见附录). 图中浏览路线的走法为： 对于A区，从基础实验大楼出发，B区从正门出发，沿着路线走，遇到分支则打一个转回到圈.例如下图中理科B区路线为:28,29,5,11,16,15,14,13,14,17,18,19,20,19,21,22,23,25,24,9,8,7,2,1,2,7,26,3,4,29,28.也可反过来，其他的以此类推. 理科类A、B区游览路线  工科类A、B区游览路线 文科类A、B区游览路线 医学类A、B区游览路线 于是得到相应的游览计划为: 理科类：正门-办公楼-正气广场-外经楼-教学楼-校医院-体育场-体育馆-体育场-游泳馆-运动场B-本科生公寓C区-学生食堂C-本科生公寓C区-商业街-学工楼-学生食堂B-建工楼-机电楼-信工楼-材料楼-理科生命大楼-计算机实验中心-基础实验大楼-天健园-工程实验楼-昌海楼-国际学术交流中心-第二教学大楼-白求恩广场-医学实验大楼区-青年教师宿舍区-运动场-研究生公寓区-本科生公寓区-天健园-基础实验大楼-计算机中心-理科生命大楼-保安楼-图书馆-中心广场-办公楼-正门 工科类：正门-办公楼-正气广场-人文楼-法学楼-教学楼-校医院-体育场-体育馆-体育场-游泳馆-运动场B-本科生公寓C区-商业街-学工楼-学生食堂B-建工楼-机电楼-信工楼-材料楼-环境楼-材料楼-理科生命大楼-计算机实验中心-基础实验大楼-天健园-工程实验楼-昌海楼-国际学术交流中心-第二教学大楼-白求恩广场-医学实验大楼区-青年教师宿舍区-运动场-研究生公寓区-本科生公寓区-天健园-基础实验大楼-计算机中心-理科生命大楼-保安楼-图书馆-中心广场-办公楼-正门 文科类:：正门-办公楼-正气广场-外经楼-艺术楼-体育馆-体育场-校医院-体育场-游泳馆-运动场B-本科生公寓C区-商业街-学工楼-学生食堂B-教学楼-法学楼-人文楼-信工楼-材料楼-理科生命大楼-计算机实验中心-基础实验大楼-天健园-工程实验楼-昌海楼-国际学术交流中心-第二教学大楼-白求恩广场-医学实验大楼区-青年教师宿舍区-运动场-研究生公寓区