数学建模期末大作业

《数学建模期末大作业》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数学建模期末大作业论文题目：A题美好的一天组长：何曦（2014112739）组员：李颖（2014112747）张楚良（2014112740）班级：交通工程三班指导老师：陈崇双美好的一天摘要关键字：Dijkstra算法多目标规划有向赋权图MATLABSPSS1问题的重述Hello！大家好，我是没头脑,住在西南宇宙大学巨偏远的新校区（节点22）。明天我一个外地同学来找我玩，TA叫不高兴，是个镁铝帅锅，期待ing。我想陪TA在城里转转，当然是去些不怎么花钱的地方啦~~。目前想到的有林湾步行街(节点76)、郫郫公园（节点91），大川博物院（节点72）。交通嘛，

2、只坐公交车好了,反正公交比较发达，你能想出来的路线都有车啊。另外，进城顺便办两件事，去老校区财务处一趟（节点50），还要去新东方（节点34）找我们宿舍老三，他抽奖中了两张电影票，我要霸占过来明晚吃了饭跟TA一起看。电影院嘛，TASHIWODE电影院（节点54）不错，比较便宜哈。我攒了很久的钱，订了明晚开心面馆（节点63）的烛光晚餐，额哈哈，为了TA，破费一下也是可以的哈。哦，对了，老三说了，他明天一整天都上课，只有中午休息的时候能接见我给我票。我主要是想请教一下各位大神：1）明天我应该怎么安排路线才能够让花在坐车上的时间最少？2）考虑到可能堵车啊，TA比

3、较没耐心啊，因为TA叫不高兴嘛。尤其是堵车啊，等车啊，这种事，万一影响了气氛就悲剧了。我感觉路口越密的地方越容易堵，如果考虑这个，又应该怎么安排路线呢？3）我们城比较挫啊，连地图也没有，Z老师搞地图测绘的，他有地图，跟他要他不给，只给了我一个破表格（见附件，一个文件有两页啊），说“你自己画吧”。帮我画一张地图吧，最好能标明我们要去的那几个地方和比较省时的路线啊，拜托了~2问题的分析2.1对问题一的分析问题一要求安排路线使得坐车花费的时间最少。对于问题一，假设公交车的速度维持不变，要使花费的时间最少，则将问题转化为对最短路径的求解。求解最短路径使用Dijk

4、stra算法很容易进行求解，在运用MATLAB编程，得到最优的一条路径，则这条路径所对应的时间即为最少用时。2.2对问题二的分析问题二要求在考虑堵车的情况下，路口越密越容易发生拥堵，安排路线是乘车时间最短。18对于问题二，在问题的基础上增加了附加因素，即公交车的速度会因道路的密集程度而发生改变，从而问题一建立的基本Dijkstra算法对于问题二就不再适用了，因此对问题一的基本Dijkstra算法进行改进，并结合蚁群算法的机理与特点，运用MATLAB求解出最短路径，保证了花费时间的最少性。2.3对问题三的分析问题三要求根据提供的附件，画出一张地图，标明要去

5、的那几个地方和比较省时的路线。对于问题三，在问题一和问题二的基础上，根据求解的结果，运用SPSS软件画出地图。3模型假设1、问题一开动中的公交车速度为一恒定值2、问题一公交车不会遇到拥堵情况3、不计公交车启动与制动时间4、不计公交车在站台的停留时间5、节点之间均为直线距离4符号说明符号含义公交车行驶速度0-1变量路口i和j连接道路长度与公交车行驶速度的比值i路口与j路口间道路长度T最短时间18i,j,r节点经过每个节点的概率5模型的建立与求解5.1问题一模型的建立与求解公交车速度是恒定的，要使坐车时间最短，故使两点之间的路程最短。根据题目，要去7个地点，

6、且均乘坐公交车。5.1.1最短路径基本概念用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题-即已知起始结点，求最短路径的问题。确定终点的最短路径问题-与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有

7、路径方向反转的确定起点的问题。确定起点终点的最短路径问题-即已知起点和终点，求两结点之间的最短路径。18全局最短路径问题-求图中所有的最短路径5.1.2Dijkstra算法描述构造赋权图G=(V,E,W)。其中，定点集V={v1,...,vn}，这里v1，...，vn表示各个地点；E为边的集合，邻接矩阵，这里表示顶点和之间直通的距离，若顶点和之间无连接，。问题就是求赋权图G中指定的两个顶点，间的具有最小权的路。这条路叫做，间的最短路，它的权叫做，间的距离，亦记作。迪克斯特拉算法的基本思想是按距从近到远为顺序，依次求得到G的各项点的最短路和距离，直至(或直

8、至G的所有顶点)，算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下