数学建模讲座(谢金星)(精品)

,谢金星,清华大学数学科学系,2008.,数学建模讲座,CUMCM-2007B(,乘公交，看奥运,),赛题分析,谢金星,100084,北京清华大学数学科学系,Tel:010-62787812,，,Fax:010-62785847,Email:,http:/,/jxie,2007B,命题背景,奥运相关的题目：,(,时代特性,社会关注）,让运动员及时到达场馆（车辆调度，路径安排等）,应急管理（紧急疏散，应急调度等）,赛程安排（单一项目，多个项目）,成绩排名（如循环赛，体操或跳水等）,技术类，如“刘翔的运动鞋”,乘公交，看奥运：原名“自动问路机”,方沛辰（吉大），吴孟达（国防科大）提出,原拟作乙组题，似乎难度太大,命题背景,定位：公交路线选择（查询）模型与算法,如何给数据？,抽象数据实际数据？（减小规模，不给地理信息）,貌似简单，实则不然,数据处理（转换）方面有一定难度,换乘次数多时简单搜索不易（计算复杂度高）,换乘时间步行时间等需要考虑周全,标准的最短路算法（如,Dijkstra,算法）并不适用,乘公交，看奥运,公交线路选择问题的自主查询计算机系统：核心是线路选择的,模型与算法,应该从,实际情况出发,考虑，满足查询者的,各种不同需求,1:,仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的,一般,数学模型与算法,2:,同时考虑公汽与地铁线路，解决以上问题,3:,假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型,【,附录,1】,基本参数设定,相邻公汽站平均行驶时间,(,包括停站时间,),：,3,分钟,相邻地铁站平均行驶时间,(,包括停站时间,),：,2.5,分钟,公汽换乘公汽平均耗时：,5,分钟,(,其中步行时间,2,分钟,),地铁换乘地铁平均耗时：,4,分钟,(,其中步行时间,2,分钟,),地铁换乘公汽平均耗时：,7,分钟,(,其中步行时间,4,分钟,),公汽换乘地铁平均耗时：,6,分钟,(,其中步行时间,4,分钟,),公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：,0,20,站：,1,元；,21,40,站：,2,元；,40,站以上：,3,元,地铁票价：,3,元（无论地铁线路间是否换乘）,推论：换乘公汽等待分钟，换乘地铁等待分钟,【,附录,2】,公交线路及相关信息（见数据文件）,线路数据中的问题,线路数据中的异常或不明确之处，同学可根据自己的,理解,作出,假设,和处理，一般不会影响实例的计算结果,个别线路相邻站点名相同，可去掉其中一点或不作处理等,L406,未标明是环线，是否将其当作环线处理均可,L290,标明是环线，但首尾站点分别为,1477,与,1479,，可将所有线路中,1477,与,1479,统一为,1477,后计算。同学也可以按照各自认为合理的方式处理，包括不当作环线，或将,1479,改为,1477,，或在,1479,后增加,1477,，等等,如果在假设中有明确约定，则环线单向或双向发车均应认可（按单向发车作假设，计算结果可能差些）,对通过地铁换乘的理解,“假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘,(,无需支付地铁费,)”,步行：公汽站,地铁站（通道）,公汽站,换乘耗时,11min,：步行,4+4=8min;,等车,3min,第问（只考虑公汽）：可不考虑以上换乘,有同学也考虑了如上换乘，只是不坐地铁，应该也可以,此样处理时，第问和第问的难度相近,模型的目标,多目标优化问题,（至少考虑三方面）,换乘次数最少,(N),、费用最省,(M),、时间最短,(T),从该问题的实际背景来看，,加权,太合适,不少同学用层次分析法确定权,不少同学计算时间的价值（平均收入工作时间）,不同目标,组合,的模型,三个目标按优先级排序，组合成六个模型,也可将某些目标作为约束,多数队,仅,采用搜索法（,70-80%?,）,直达；一次换乘；二次换乘；,s,t,s,t,s,t,求出所有线路；评价其目标,(,容易计算,),；选优,多数队,仅,采用搜索法,总体来看，技术含量较低（基本上是枚举）,几乎没有建模，完全只有算法实现，算法也没什么创新,一般只考虑不超过两次换乘,不少文章引用参考文献作为依据，实用中似乎够用,题目难度大大降低，模型不够,一般,换乘作为了,第一目标,，或作为一个,最重要的约束,任意次换乘时算法复杂度提高，难以处理,结果不佳（如：从省时考虑，有些需次换乘）,图论模型与最短路算法,用图论做的队也不少，但往往考虑不周,弧上赋权方式交代不清,套用,Dijkstra,或,Floyd-,Warshall,算法，却不清楚其原理及适用的问题,需要建立一个带权有向图，节点表示站点，有向弧表示前一站点能够直达后一站点，弧上的权表示前一站点直达后一站点所需付出的代价,(,时间或费用,),图（网络）如何描述和表示？,基本要素：节点，有向弧（边），弧上赋权,邻接矩阵；关联矩阵（数学上处理方便，存储量较大）,链表（存储量较小，计算机上处理方便）,关联矩阵,(Incidence Matrix),表示法,在线路选择问题中，当从,i,可直达,j,时，定义弧,(,i,j,),；其上的权可为或成本,(,时间或费用,),；多重弧可只保留一条（弧上的权可取最小的成本，如时间或费用）,G,=(,V,，,A,),是一个简单有向图；,|,V,|=,n,，,|,A,|=,m,重要数学性质：,关联矩阵是全幺模矩阵,图,G,=(,V,，,A,),的邻接矩阵,C,是如下定义的：,C,是一个 的矩阵，即,邻接矩阵,(Adjacency Matrix),表示法,图,G,=(,V,，,A,),的邻接矩阵,C,是如下定义的：,C,是一个 的,0-1,矩阵，即,在线路选择问题中，当从,i,可直达,j,时，定义弧,(,i,j,),；其上的权可为或成本,(,时间或费用,),G,=(,V,，,A,),是一个简单有向图；,|,V,|=,n,，,|,A,|=,m,有向图的“传递闭包算法”,(,可用于一般二元关系,),权取,0-1,时，,C,(0),=C,可称为,直达矩阵,；,C,(1),=C*C,为,次可达矩阵,；,C,(2),=C,(1),*C,为,2,次可达矩阵,；,链表（邻接表）表示法,1,2,2,3,4,5,2,8,3,9,0,4,6,0,2,4,0,3,0,5,3,0,3,6,4,7,0,单向链表,(,指针数组,),A(1)=2,3,A(2)=4,A(3)=2,A(4)=3,5,A(5)=3,4,1,2,3,4,5,Dijkstra,算法（标号算法，,1959,）,STEP1.,如果,S=V,则,u,j,为,节点,s,到节点,j,的最短路路长,(,最短路可以通过数组,pred,所记录的信息反向追踪获得,),结束,.,否则继续,.,STEP0.(,初始化,),令,S,=,，,=,V,，；对,V,中的顶点,j(j,s),令初始距离标号,.,STEP2.,从 中找到,距离标号最小,的节点,i,，,把它从 删除，加入,S,.,对于,所有,从,i,出发的弧,若 ，则令,转,STEP1.,特点：,1.,算法求出从源点,s,到所有点的最短路长,2.,每点给一对标号,(,u,j,pred,j,),，,u,j,是从,s,到,j,的最短路长；,pred,j,是从,s,到,j,的最短路中,j,点的前一点,Example,Dijkstra,算法（标号设定算法）,适用于正费用网络：,“分层”设定标号,永久标号：,S,中的点，,u,j,是最短路长,临时标号；,其他点，,u,j,是只通过,S,中的点的最短路长,对于稠密网络，这是求解最短路问题可能达到的最小的复杂度,因为任何算法都至少必须对每条弧考虑一次,.,对于稀疏网络，利用各种形式的,堆（,Heap,）,，,其复杂度可降为,或 等,算法复杂度,O,(,n,2,+,m,),：如链表或邻接矩阵实现,找最小标号点修改标号,特点：求所有点对间最短路,基本思想：逐步逼近，迭代求解最短路方程,:,O,(,n,3,),Floyd-,Warshall,算法,（,标号修正算法,，,1962),临时标号 是不通过,k,，,k+,1,，,n,节点,(,i,j,除外,),时从节点,i,到节点,j,的最短路路长,.,Floyd-,Warshall,算法的具体实现,:O(n,3,),由于要记录所有节点之间最短路的信息,所以这里我们要用一个二维数组,P,；,可依据,P,采用“正向追踪”的方式得到最短路,.,STEP2,：,如果,k=n,结束,;,否则转,STEP1.,STEP0:,k,=0.,对于所有节点,i,和,j,:,令 ，,(,，若节点,i,和,j,之间没有弧,认为,),.,STEP1:,k=k,+1.,对于所有节点,i,和,j,:,若,令,;,否则令,.,Floyd-,Warshall,算法的,矩阵迭代法实现：,O(n,4,),令,D,为权矩阵,(,直达最短路长,),D,m,为正好经过,m,条弧从,i,到,j,的最短路长,问题,1,和,2,的一种具体建模方法,(,赋权,),在线路选择问题中，当从,i,可直达,j,时（,同为公汽或地铁站点,），定义弧,(,i,j,),；其上的权为,l,ij,表示由,i,直达,j,付出的代价，可以为时间或费用,(,不包括换乘代价；多条线路可达时只保留最小代价,),初始等车时间,2(3)min,也不包括在内，最后结果可加上,注意：,D=D,(0),不是对称矩阵,(“,直达矩阵”,),d,ij,(0),=,d,ij,问题的一种具体建模方法,i,站点是公汽站点，,j,站点为地铁站点：,（,1,）若,j,站点对应的所有换乘,(,公汽,),站点,k,，均不能从,i,直达,(,不在,i,站点所在公汽线路,L,上,),，则,d,ij,(0),=,.,（,2,）若,j,站点对应的换乘站点,(k),可从,i,站点直达,k,，则费用为,d,ij,(0),=,d,ik,(0),；对于时间则需要,加上,k,到,j,的步行时间,.,(,若有多种选择，取最小成本者即可,),i,k,j,问题的一种具体建模方法,j,站点是公汽站点，,i,站点为地铁站点：,（,1,）若从,i,站点对应的任何换乘,(,公汽,),站点,k,，均不能直达,j,站点，则,d,ij,(0),=,.,（,2,）若从,i,站点对应的换乘,(,公汽,),站点,k,，能直达,j,站点，则费用为,d,ij,(0),=,d,kj,(0),；对于时间则需要,加上,i,到,k,的步行时间,.,i,k,j,问题：最小费用或时间,定义矩阵算子“,”,如下：设,A,、,B,均为,n,阶方阵，,C=A B (,考虑,换乘代价,),当考虑费用矩阵之间的运算时，,表示在,k,的换乘时间,当考虑时间矩阵之间的运算时，,D,(k,),=D,(k-1),D,表示,k,次换乘的最低代价,(,费用或时间,),该算法大体相当于求最短路的,Floyd-,Warshall,算法，但考虑了换乘因素，可称为改进,Floyd-,Warshall,算法,类似地,通过修改,Dijkstra,算法求解也可,问题：最小费用或时间,i,j,k,表示换乘时间,i,=,j,或,k,=,i,，,j,时，,i,j,k,=0,其他情形：,若不可换乘,(,当,i,，,j,为公汽站点而,k,为地铁站点，或者,i,，,j,为地铁站点而,k,为公汽站点时,),，则,i,j,k,=0,若可换乘，则,k,这只是等待时间，因为步行时间已在,D,中考虑了,i,j,第问：已知所有站点间步行时间,多数队没有给出一般模型,而只考虑最多一次换乘,多数队的想法：假设“起点步行”，“换乘步行”，“终点步行”三种模式，限定,步行最大时间,后搜索,i,k,j,其他：最短路问题的线性规划模型,x,ij,表示弧（,i,，,j,）,是否位于,s-t,路上：当,x,ij,=1,时，表示弧（,i,，,j,）,位于,s-t,路上，当,x,ij,=0,时，表示弧（,i,，,j,）,不在,s-t,路上,.,关联矩阵是全么模矩阵，因此,0-1,变量可以松弛为