数学建模期末大课后复习.doc

数学建模期末大作业论文题目：A题 美好的一天 组长：何曦（2014112739） 组员：李颖（2014112747） 张楚良（2014112740） 班级：交通工程三班 指导老师：陈崇双美好的一天摘要关键字：Dijkstra算法 多目标规划 有向赋权图 MATLAB SPSS1 问题的重述Hello！大家好，我是没头脑,住在西南宇宙大学巨偏远的新校区（节点22）。明天我一个外地同学来找我玩，TA叫不高兴，是个镁铝帅锅，期待ing。我想陪TA在城里转转，当然是去些不怎么花钱的地方啦。目前想到的有林湾步行街(节点76)、郫郫公园（节点91），大川博物院（节点72）。交通嘛，只坐公交车好了,反正公交比较发达，你能想出来的路线都有车啊。另外，进城顺便办两件事，去老校区财务处一趟（节点50），还要去新东方（节点34）找我们宿舍老三，他抽奖中了两张电影票，我要霸占过来明晚吃了饭跟TA一起看。电影院嘛，TASHIWODE电影院（节点54）不错，比较便宜哈。我攒了很久的钱，订了明晚开心面馆（节点63）的烛光晚餐，额哈哈，为了TA，破费一下也是可以的哈。哦，对了，老三说了，他明天一整天都上课，只有中午休息的时候能接见我给我票。我主要是想请教一下各位大神：1）明天我应该怎么安排路线才能够让花在坐车上的时间最少？2）考虑到可能堵车啊，TA比较没耐心啊，因为TA叫不高兴嘛。尤其是堵车啊，等车啊，这种事，万一影响了气氛就悲剧了。我感觉路口越密的地方越容易堵，如果考虑这个，又应该怎么安排路线呢？3）我们城比较挫啊，连地图也没有，Z老师搞地图测绘的，他有地图，跟他要他不给，只给了我一个破表格（见附件，一个文件有两页啊），说“你自己画吧”。帮我画一张地图吧，最好能标明我们要去的那几个地方和比较省时的路线啊，拜托了2 问题的分析2.1 对问题一的分析 问题一要求安排路线使得坐车花费的时间最少。 对于问题一，假设公交车的速度维持不变，要使花费的时间最少，则将问题转化为对最短路径的求解。求解最短路径使用Dijkstra算法很容易进行求解，在运用MATLAB编程，得到最优的一条路径，则这条路径所对应的时间即为最少用时。2.2 对问题二的分析 问题二要求在考虑堵车的情况下，路口越密越容易发生拥堵，安排路线是乘车时间最短。 对于问题二，在问题的基础上增加了附加因素，即公交车的速度会因道路的密集程度而发生改变，从而问题一建立的基本Dijkstra算法对于问题二就不再适用了，因此对问题一的基本Dijkstra算法进行改进，并结合蚁群算法的机理与特点，运用MATLAB求解出最短路径，保证了花费时间的最少性。2.3 对问题三的分析 问题三要求根据提供的附件，画出一张地图，标明要去的那几个地方和比较省时的路线。 对于问题三，在问题一和问题二的基础上，根据求解的结果，运用SPSS软件画出地图。3 模型假设1、 问题一开动中的公交车速度为一恒定值2、 问题一公交车不会遇到拥堵情况3、 不计公交车启动与制动时间4、 不计公交车在站台的停留时间5、 节点之间均为直线距离 4符号说明符号含义公交车行驶速度0-1变量 路口i和j连接道路长度与公交车行驶速度的比值 i路口与j路口间道路长度T 最短时间i,j,r节点经过每个节点的概率5模型的建立与求解 5.1 问题一模型的建立与求解 公交车速度是恒定的，要使坐车时间最短，故使两点之间的路程最短。根据题目，要去7个地点，且均乘坐公交车。5.1.1 最短路径基本概念 用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括：确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。全局最短路径问题 - 求图中所有的最短路径5.1.2 Dijkstra算法描述 构造赋权图G=(V,E,W)。其中，定点集V=v1,.,vn，这里v1，.，vn表示各个地点；E为边的集合，邻接矩阵 ，这里表示顶点和之间直通的距离，若顶点和之间无连接，。问题就是求赋权图G中指定的两个顶点，间的具有最小权的路。这条路叫做，间的最短路，它的权叫做，间的距离，亦记作。迪克斯特拉算法的基本思想是按距从近到远为顺序，依次求得到G的各项点的最短路和距离，直至(或直至G的所有顶点)，算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。（1）。（2） 代替，这里表示顶点u和v之间边的权值。计算，把达到这个最小值的一个顶点记为，令。（3）若，则停止；若，则用i+1代替i，转（2）。5.1.3 有向赋权图的定义（1） 邻接矩阵的建立 将该道路视为一个有向权图，其领接矩阵可定义为： 其中，表示该有向权图，其领接矩阵元素为0-1决策变量，定义为： （2） 权值（时间）矩阵的建立 同样，根据题目时间最短的要求，本文将时间作为该有向赋权图中第i各节点和第j个节点之间弧的权值，即： 其中，时间矩阵元素是路口i和j连接道路长度与公交车行驶速度的比值，即： 其中，-公交车行驶速度，规定为40km/h， -i路口与j路口间道路长度，通过两个路口坐标和确定，即： 当i、j路口不连通时，规定等于+。5.1.4 基于最短理论的模型建立 1、目标分析 根据5.1.3中建立的有向赋权图，其中0-1决策变量表示弧（i,j）是否在起点与终点的路上，在定义了为边i到j的权的有向网络图后，可看出从出发点到终点有多条线路选择，但必有一条为时间最少的，因而可将这条时间最短的路径找出。 因而，根据所建立的网络领接矩阵和时间权值矩阵可以得到到达某一路口的时间的数学模型为： 从时间考虑，既要满足单个路径时间最短，所以目标函数应为： 2、约束分析 （1）最短路起点约束 由于G为有向图，则其中顶点分为“起点”、“中间点”、“终点”三类，对于起点只有出的边而无入的边，对于中间点既有入的边也有出的边，对于中只有入的边而无出的边。 对有向图而言，若求顶点r1到r2的最短路径，以 表示进第j顶点的边，以 表示出第j顶点的边，则r1到r2的三类约束可表示为： （2）0-1决策变量约束 由于0-1决策变量 为有向道路网路图的领接矩阵元素，即表示i、j两路口是否连通，所以对其作下列约束： 3、模型确定 综上目标和约束分析，可得从起始点到目的地的优化模型如下： 5.1.5 基于Dijkstra算法的“搜索算法”求解 该模型求解得到的是从起始点新校区（节点22）到目的地TASHIWODE电影院（节点54）的乘坐公交车的最短时间。所以将这7个最短时间相加即得整个过程的最短时间。 对于这个单目标规划模型，由于数据量较大且计算步骤繁琐，利用Lingo优化软件求解困难，因此本文结合Dijkstra算法通过Mtalab编程进行遍历搜索求解。算大步骤如下： Step1：取一路口节点j； Step2：利用Dijkstra算法求解最短时间； Step3：将 Step2中7个最短时间相加，并记录对应的路径和两端点； Step4：若求解未通过，转Step1，否则，转Step5； Step5：输出Step3的记录，根据断点确定最短时间。 根据以上算法，利用Matalb软件编程（见附录）求解得到两个指定顶点间的最短距离，具体的线路安排如下：22（新校区）、21、14、10、15、16、38、40、43、72（大川博物院）、73、18、91（郫郫公园）、90、83、80、79、78、76（林湾步行街）、62、57、50（老校区财务处）、51、8、34（新东方）、46、55、63（开心面馆）、54（TASHIWODE电影院）。5.2 问题二模型的建立与求解 路口越密，越容易发生拥堵情况，因而公交车的行驶速度越慢。因此要建立在不同路段公交车行驶速度与路口密度的模型，从而找出最佳路线使全程乘车时间最短。5.2.1 蚁群算法 （1）蚁群算法的基本原理 与其它模拟进化算法一样，蚁群算法通过多个可行解组成的种群不断进化，并以最大概率逼近甚至达到问题的最优解。该过程包括两个基本阶段:适应阶段和协作阶段。在适应阶段，各个可行解根据积累的信息不断调整自身的结构;在协作阶段，可行解之间通过信息交流，以期产生性能更好的解。蚁群成功地搜索一轮所形成的是一组可行解，然后一记录其中的最优解。此外，蚂蚁所遗留下的信息素也将按一定程度挥发后保留到以后的各轮搜索中，从而对后面的蚂蚁在路径选择时产生影响。这些特性使得蚁群算法体现出明显的自组织机制，即在没有外界作用的条件下，使蚁群从无序状态演化到有序状态。前面的蚂蚁遗留下的信息素能够在一定程度上指导后面的蚂蚁，这称为“利用(exploitation)。另一方面，为了能够找到新的最优解，算法引入了随机概率来确保路径选择的多样性，这称为“探索(exploration)。算法初始时，首先将具体的组合优化问题表述成规范的格式，然后利用信息素和启发信息决定蚂蚁的行为是进行“探索”还是“利用”，同时按照相应的信息素更新策略对路径的信息素进行增量构建，随后从整体角度规划出蚁群活动的行为方向，周而复始，即可求出组合优化问题的最优解。 （2）基本蚁群算法描述 在求解不同性质的问题时，蚁群算法的模型也有所不同。但主要思路都是事先生成具有一定蚂蚁数量的蚁群，每只蚂蚁负责通过路径搜索建立一个可行解或可行解的一部分。算法开始时，将蚂蚁放置在若干个随机选取的初始结点上，每只蚂蚁从初始结点出发，根据路径上信息素浓度和启发信息以某种概率策略选择下一个要移动到的结点，直到建立起一个可行解。每只蚂蚁根据所找到的解的优劣程度，在所经过的路径上释放与解的质量成正比的信息素。之后，每只蚂蚁又开始新的搜索过程，直到蚁群找到全局最优解。5.2.2改进的Dijkstra算法 根据5.1优化原则和优化的描述，可以从减少算法遍历的临时结点来优化，基于此，提出了以下的想法，采用椭圆限制搜索区域，减少遍历的临时结点数;利用两点间直线最短的原理，以当前节点的邻接点与当前点和终点连线夹角最大作为贪婪搜索策略。在算法中每经过一个节点，只选取该节点和起始点的关联边与该节点与终止节点连线夹角最大的一条边，不仅考虑了路段具有方向性特征，在选取局部最优解时也在一定程度上考虑了全局的最优性，同时，进行起止点直线左右两边各一个满足前述夹角最大的节点的搜寻即搜索一棵二叉树，这样，就大大提高了最短路径解的精确性。5.2.2 模型的建立 根据以上改进的Dijkstra算法，综合考虑时间，公交车行驶速度，交通道路密度的约束，可以建立多目标规划模型。如下所示： 5.2.3模型的求解 基于Dijkstra算法的“全局逐步搜索算法”进行求解，算法步骤如下： Step1：利用Dijkstra算法生成两点间的最短时间矩阵； Step2：针对每一道路节点，建立对应每个节点的包含点集合； Step3：对7个节点处理，对重叠部分采用就近原则，分配给相应的节点； Step4：建立 矩阵，行列分别代表91个道路节点，若从j路口到i路口， Step5：计算出最优路径，及其对应的最短时间。 根据以上基于Dijkstra算法的逐步搜索算法，本文利用Matlab编程（见附录）进行了求解，结果如下：22（老校区）、21、14、16、35、46、49、50（老校区财务处）、5、34（新东方）、35、39、40、17、72（大川博物院）、74、18、91（郫郫公园）、90、83、80、77、76（林湾步行街）、63（开心面馆）、54（TASHIWODE电影院）。5.3 问题三模型的建立与求解在问题三中，即利用问题一和问题二所得的结果，运用SPSS软件，标出需要到的地点，以及把这些点用箭头连接起来，表示经过这些节点的先后顺序。使用SPSS得出的相关性检测如图1所示图1使用MATLAB软件利用SPSS的数据得出问题一的结果如图2所示图2得出问题二的结果如图3所示 图36模型评价与改进6.1模型的评价6.1.1模型的优点（1） 针对多个问题，本文建立单目标优化和多目标优化，模型简单且清楚易懂。（2） 本文巧妙地运用了Dijkstra算法，及其改进算法，融合了蚁群算法思想，结合MATLAB、SPSS等软件，建立相应的理想及修正模型。同时在建立模型的过程中，充分考虑了简化模型的原则，使得求解更加简便。（3） 本文在完成了问题一后，在原有基础上对Dijkstra算法进行了巧妙地改进，使得问题二的求解变得更加简单。6.1.2模型的缺点（1）在建模之初做了一些假设，使得条件更便于建模，但对一部分实际存在的因素的忽略也造成了模型较为理想化的结果，在实际运用中会产生一定误差。（1）由于在求解模型过程中，所需处理的数据量很大，利用一般的优化软件进行优化求解会导致耗时过多，过程繁琐，同时受硬件内存限制，所建立的模型不能用于实际求解，因此需要现编写算法进行求解，这也是本文模型的一个缺点。6.2模型的改进（1） 在模型的分析与建立的过程中 ，忽略了一些因素，在模型的改进中，将忽略的因素加以考虑。（2） 在问题二可考虑使用Floyd算法。7参考文献1司守奎、孙玺菁，数学建模算法与应用，北京：国防工业出版社，2011。2李家杰，郑义，影响城市道路通行能力因素分析J,道路交通，3:19-21,2006.3姜启源、谢金、叶俊，数学模型（第三版），北京：高等教育出版社，2003。4韩中庚，数学建模方法及其应用，北京：高等教育出版社，2005.6。5张志涌、杨祖樱等，MATLAB教程，北京：北京航空航天大学出版社，2006。8附录附录：clc,clearfid=fopen(txt1.txt,r);n1=4;n2=4;a=;for i=1:n1tmp=str2num(fgetl(fid);a=a;tmp; endfor i=1:n1str1=char(b,int2str(i),=;);str2=char(b,int2str(i),=b,int2str(i),;tmp;);eval(str1);for j=1:n2tmp=str2num(fgetl(fid);eval(str2); endendri=0,0,0.58,0.90,1.12,1.24,1.32,1.41,1.45;x,y=eig(a);lamda=max(diag(y);num=find(diag(y)=lamda);w0=x(:,num)/sum(x(:,num);cr0=(lamda-n1)/(n1-1)/ri(n1)for i=1:n1x,y=eig(eval(char(b,int2str(i);lamda=max(diag(y);num=find(diag(y)=lamda);w1(:,i)=x(:,num)/sum(x(:,num);cr1(i)=(lamda-n2)/(n2-1)/ri(n2);附录：（4）F_JIDtjl.mfunction F_JIDtjl(R)%定义函数m,n=size(R);%获得矩阵的行列数if(m=n|m=0)return;endfor(i=1:n)R(i,i)=1;for(j=i+1:n)if(R(i,j)1)R(i,j)=1;endR(i,j)=round(10000*R(i,j)/10000;R(j,i)=R(i,j);endendjs0=0;while(1)R1=Max_Min(R,R);js0=js0+1;if(R1=R)break;elseR=R1;endendlmd(1)=1;k=1;for(i=1:n)for(j=i+1:n)pd=1;for(x=1:k)if(R(i,j)=lmd(x)pd=0;break;end;endif(pd)k=k+1;lmd(k)=R(i,j);endend;endfor(i=1:k-1)for(j=i+1:k)if(lmd(i)=lmd(x)js=js+1;Sz(js)=j;end;endflsz(x)=flsz(x)+1;endendendfor(i=1:k-1)for(j=i+1:k)if(flsz(j)=flsz(i)flsz(j)=0;end;end;endfl=0;for(i=1:k)if(flsz(i)fl=fl+1;lmd(fl)=lmd(i);end;endfor(i=1:n)xhsz(i)=i;endfor(x=1:fl)js=0;flsz(x)=0;for(i=1:n)pd=1;for(y=1:js)if(Sz(y)=i)pd=0;break;end;endif(pd)if(js=0)y=0;endfor(j=1:n)if(R(i,j)=lmd(x)js=js+1;Sz(js)=j;end;endflsz(x)=flsz(x)+1;Sz0(flsz(x)=js-y;endendjs0=0;for(i=1:flsz(x)for(j=1:Sz0(i)Sz1(j)=Sz(js0+j);endfor(j=1:n)for(y=1:Sz0(i)if(xhsz(j)=Sz1(y)js0=js0+1;Sz(js0)=xhsz(j);end;end;endendfor(i=1:n)xhsz(i)=Sz(i);endendfor(x=1:fl)js=0;flsz(x)=0;for(i=1:n)pd=1;for(y=1:js)if(Sz(y)=i)pd=0;break;end;endif(pd)if(js=0)y=0;endfor(j=1:n)if(R(i,j)=lmd(x)js=js+1;Sz(js)=j;end;endflsz(x)=flsz(x)+1;Sz0(flsz(x)=js-y;endendjs0=1;for(i=1:flsz(x)y=1;for(j=1:flsz(x)if(Sz(y)=xhsz(js0)flqksz(x,i)=Sz0(j);js0=js0+Sz0(j);break;endy=y+Sz0(j);endendendF_dtjltx=figure(name,动态聚类图,color,w);axis(off);Kd=30;Gd=40;y=fl*Gd+Gd;lx=80;text(24,y+Gd/2,&);for(i=1:n)text(lx-5+i*Kd-0.4*Kd*(xhsz(i)9),y+Gd/2,int2str(xhsz(i);line(lx+i*Kd,lx+i*Kd,y,y-Gd);linesz(i)=lx+i*Kd;endtext(lx*1.5+i*Kd,y+Gd/2,分数类);y=y-Gd;for(x=1:fl)text(8,y-Gd/2,num2str(lmd(x);js0=1;js1=0;if(x=1)for(i=1:flsz(x)js1=flqksz(x,i)-1;if(js1)line(linesz(js0),linesz(js0+js1),y,y);endline(linesz(js0+js1)+linesz(js0)/2,(linesz(js0+js1)+linesz(js0)/2,y,y-Gd);linesz(i)=(linesz(js0+js1)+linesz(js0)/2;js0=js0+js1+1;endelse for(i=1:flsz(x)js1=js1+flqksz(x,i);js2=0;pd=0;for(j=1:flsz(x-1)js2=js2+flqksz(x-1,j);if(js2=js1)pd=1;break;endendif(j=js0)line(linesz(js0),linesz(j),y,y);endline(linesz(js0)+linesz(j)/2,(linesz(js0)+linesz(j)/2,y,y-Gd);linesz(i)=(linesz(js0)+linesz(j)/2;js0=j+1;end;endtext(2*lx+n*Kd,y-Gd/3,int2str(flsz(x);y=y-Gd;End