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

《(精品)数学建模讲座(谢金星).ppt》由会员分享，可在线阅读，更多相关《(精品)数学建模讲座(谢金星).ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.数学建模讲座数学建模讲座CUMCM-2007B(乘公交，看奥运乘公交，看奥运)赛题分析赛题分析谢金星谢金星100084北京清华大学数学科学系北京清华大学数学科学系Tel:010-62787812，Fax:010-62785847Email: http:/ 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.2007B命题背景命题背景 奥运相关的题目：奥运相关的题目：(时代特性时代特性,社会关注）社会关注）让运动员及时到达场馆（车辆调度，路径安排等）让运动员及时到达场馆（车辆调度，路径安排等）应急管理（紧急疏散，应急调度等

2、）应急管理（紧急疏散，应急调度等）赛程安排（单一项目，多个项目）赛程安排（单一项目，多个项目）成绩排名（如循环赛，体操或跳水等）成绩排名（如循环赛，体操或跳水等）技术类，如技术类，如“刘翔的运动鞋刘翔的运动鞋”乘公交，看奥运：原名乘公交，看奥运：原名“自动问路机自动问路机”方沛辰（吉大），吴孟达（国防科大）提出方沛辰（吉大），吴孟达（国防科大）提出原拟作乙组题，似乎难度太大原拟作乙组题，似乎难度太大 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.命题背景命题背景 定位：公交路线选择（查询）模型与算法定位：公交路线选择（查询）模型与算法如何给数据？如何给数据？抽象数据实际数据？（

3、减小规模，不给地理信息）抽象数据实际数据？（减小规模，不给地理信息）貌似简单，实则不然貌似简单，实则不然数据处理（转换）方面有一定难度数据处理（转换）方面有一定难度换乘次数多时简单搜索不易（计算复杂度高）换乘次数多时简单搜索不易（计算复杂度高）换乘时间步行时间等需要考虑周全换乘时间步行时间等需要考虑周全标准的最短路算法（如标准的最短路算法（如Dijkstra算法）并不适用算法）并不适用 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.乘公交，看奥运乘公交，看奥运公交线路选择问题的自主查询计算机系统：核心是公交线路选择问题的自主查询计算机系统：核心是线路选择的线路选择的模型与算法模

4、型与算法应该从应该从实际情况出发实际情况出发考虑，满足查询者的考虑，满足查询者的各种不同各种不同需求需求1:仅考虑公汽线路，给出任意两公汽站点之间线路仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的选择问题的一般一般数学模型与算法数学模型与算法 2:同时考虑公汽与地铁线路，解决以上问题同时考虑公汽与地铁线路，解决以上问题3:假设又知道所有站点之间的步行时间，给出任意假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型两站点之间线路选择问题的数学模型 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.【附录附录1】基本参数设定基本参数设定相邻公汽站平均行驶时

5、间(包括停站时间)：3分钟相邻地铁站平均行驶时间(包括停站时间)：2.5分钟公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）推论：换乘公汽等待分钟，换乘地铁等待分钟【附录附录2】公交线路及相关信息公交线路及相关信息（见数据文件）（见数据文件）谢金星谢金星,清华大学数学科学系清华大学数

6、学科学系,2008.线路数据中的问题线路数据中的问题线路数据中的异常或不明确之处，同学可根据自己的线路数据中的异常或不明确之处，同学可根据自己的理解理解作出作出假设假设和处理，一般不会影响实例的计算结果和处理，一般不会影响实例的计算结果个别线路相邻站点名相同，可去掉其中一点或不作处理等个别线路相邻站点名相同，可去掉其中一点或不作处理等L406未标明是环线，是否将其当作环线处理均可未标明是环线，是否将其当作环线处理均可L290标明是环线，但首尾站点分别为标明是环线，但首尾站点分别为1477与与1479，可将所，可将所有线路中有线路中1477与与1479统一为统一为1477后计算。同学也可以按照各

7、后计算。同学也可以按照各自认为合理的方式处理，包括不当作环线，或将自认为合理的方式处理，包括不当作环线，或将1479改为改为1477，或在，或在1479后增加后增加1477，等等，等等如果在假设中有明确约定，则环线单向或双向发车均应认可如果在假设中有明确约定，则环线单向或双向发车均应认可（按单向发车作假设，计算结果可能差些）（按单向发车作假设，计算结果可能差些）谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.对通过地铁换乘的理解对通过地铁换乘的理解“假设同一地铁站对应的任意两个公汽站之间可以假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘通过地铁站换乘(无需支付地铁费无需

8、支付地铁费)”步行：公汽站步行：公汽站地铁站（通道）地铁站（通道）公汽站公汽站换乘耗时换乘耗时11min：步行：步行4+4=8min;等车等车3min第问（只考虑公汽）：可不考虑以上换乘第问（只考虑公汽）：可不考虑以上换乘有同学也考虑了如上换乘，只是不坐地铁，应该也可以有同学也考虑了如上换乘，只是不坐地铁，应该也可以此样处理时，第问和第问的难度相近此样处理时，第问和第问的难度相近 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.模型的目标模型的目标多目标优化问题多目标优化问题（至少考虑三方面）（至少考虑三方面）换乘次数最少换乘次数最少(N)、费用最省、费用最省(M)、时间最短、时

9、间最短(T)从该问题的实际背景来看，从该问题的实际背景来看，加权加权太合适太合适 不少同学用层次分析法确定权不少同学用层次分析法确定权不少同学计算时间的价值（平均收入工作时间）不少同学计算时间的价值（平均收入工作时间）不同目标不同目标组合组合的模型的模型三个目标按优先级排序，组合成六个模型三个目标按优先级排序，组合成六个模型也可将某些目标作为约束也可将某些目标作为约束 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.多数队多数队仅仅采用搜索法（采用搜索法（70-80%?）直达；直达；一次换乘；一次换乘；二次换乘；二次换乘；ststs t求出所有线路；评价其目标求出所有线路；评价其

10、目标(容易计算容易计算)；选优；选优 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.多数队多数队仅仅采用搜索法采用搜索法总体来看，技术含量较低（基本上是枚举）总体来看，技术含量较低（基本上是枚举）几乎没有建模，完全只有算法实现，算法也没什么创新几乎没有建模，完全只有算法实现，算法也没什么创新一般只考虑不超过两次换乘一般只考虑不超过两次换乘不少文章引用参考文献作为依据，实用中似乎够用不少文章引用参考文献作为依据，实用中似乎够用 题目难度大大降低，模型不够题目难度大大降低，模型不够一般一般换乘作为了换乘作为了第一目标第一目标，或作为一个，或作为一个最重要的约束最重要的约束任意次换乘

11、时算法复杂度提高，难以处理任意次换乘时算法复杂度提高，难以处理结果不佳（如：从省时考虑，有些需次换乘）结果不佳（如：从省时考虑，有些需次换乘）谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.图论模型与最短路算法图论模型与最短路算法用图论做的队也不少，但往往考虑不周用图论做的队也不少，但往往考虑不周弧上赋权方式交代不清弧上赋权方式交代不清套用套用Dijkstra或或Floyd-Warshall算法，却不清楚其原理及算法，却不清楚其原理及适用的问题适用的问题需要建立一个带权有向图，节点表示站点，有向弧需要建立一个带权有向图，节点表示站点，有向弧表示前一站点能够直达后一站点，弧上的权表

12、示前表示前一站点能够直达后一站点，弧上的权表示前一站点直达后一站点所需付出的代价一站点直达后一站点所需付出的代价(时间或费用时间或费用)图（网络）如何描述和表示？图（网络）如何描述和表示？基本要素：节点，有向弧（边），弧上赋权基本要素：节点，有向弧（边），弧上赋权邻接矩阵；关联矩阵（数学上处理方便，存储量较大）邻接矩阵；关联矩阵（数学上处理方便，存储量较大）链表（存储量较小，计算机上处理方便）链表（存储量较小，计算机上处理方便）谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.关联矩阵关联矩阵(Incidence Matrix)表示法表示法在线路选择问题中，当从在线路选择问题中，当

13、从i i可直达可直达j j时，定义弧时，定义弧(i,ji,j)；其上的权可为或成本；其上的权可为或成本(时间或费用时间或费用)；多重弧可只保留一条（弧上的权可取最小的成多重弧可只保留一条（弧上的权可取最小的成本，如时间或费用）本，如时间或费用）G=(V，A)是一个简单有向图；是一个简单有向图；|V|=n，|A|=m 重要数学性质：重要数学性质：关联矩阵是全幺模矩阵关联矩阵是全幺模矩阵图图G=(V，A)的的邻邻接接矩矩阵阵C是是如如下下定定义义的的：C是是一一个个 的矩阵，即的矩阵，即 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.邻接矩阵邻接矩阵(Adjacency Matri

14、x)表示法表示法图图G=(V，A)的的邻邻接接矩矩阵阵C是是如如下下定定义义的的：C是是一一个个 的的0-1矩阵，即矩阵，即在线路选择问题中，当从在线路选择问题中，当从i i可直达可直达j j时，定义弧时，定义弧(i,ji,j)；其上的权可为或成本；其上的权可为或成本(时间或费用时间或费用)G=(V，A)是一个简单有向图；是一个简单有向图；|V|=n，|A|=m 有向图的有向图的“传递闭包算法传递闭包算法”(可用于一般二元关可用于一般二元关系系)权取权取0-10-1时，时，C C(0)(0)=C=C可称为可称为直达矩阵直达矩阵；C C(1)(1)=C*C=C*C 为为次可达矩阵次可达矩阵；C

15、C(2)(2)=C=C(1)(1)*C*C 为为2次可达矩阵次可达矩阵；谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.链表（邻接表）表示法链表（邻接表）表示法 122345283904602403053036470单向链表(指针数组)A(1)=2,3A(2)=4A(3)=2A(4)=3,5A(5)=3,412345 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.DijkstraDijkstra算法（标号算法，算法（标号算法，19591959）STEP1.如果S=V,则uj为节点s到节点j的最短路路长(最短路可以通过数组pred所记录的信息反向追踪获得),结束.否

16、则继续.STEP0.(初始化)令S=，=V，；对V 中的顶点j(j s)令初始距离标号 .STEP2.从 中找到距离标号最小距离标号最小的节点i，把它从 删除，加入S.对于所有所有从i出发的弧 ,若 ，则令 转STEP1.特点：特点：1.算法求出从源点算法求出从源点s到所有点的最短路长到所有点的最短路长 2.每每点点给给一一对对标标号号(uj,predj)，uj是是从从s到到j的最短路长；的最短路长；predj是从是从s到到j的最短路中的最短路中j点的前一点点的前一点 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.Example 谢金星谢金星,清华大学数学科学系清华大学数学科学

17、系,2008.DijkstraDijkstra算法（标号设定算法）算法（标号设定算法）适用于正费用网络：适用于正费用网络：“分层分层”设定标号设定标号永久标号：永久标号：S中的点，中的点，uj是最短路长是最短路长临时标号；临时标号；其他点，其他点，uj是只通过是只通过S中的点的最短路长中的点的最短路长对对于于稠稠密密网网络络，这这是是求求解解最最短短路路问问题题可可能能达达到到的的最最小小的的复复杂杂度度,因为任何算法都至少必须对每条弧考虑一次因为任何算法都至少必须对每条弧考虑一次.对于稀疏网络，利用各种形式的对于稀疏网络，利用各种形式的堆（堆（HeapHeap），其复杂度可降为其复杂度可降为

18、 或或 等等算法复杂度算法复杂度O(n2+m)：如链表或邻接矩阵实现：如链表或邻接矩阵实现找最小标号点修改标号找最小标号点修改标号 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.特点：求所有点对间最短路特点：求所有点对间最短路基本思想：逐步逼近，迭代求解最短路方程基本思想：逐步逼近，迭代求解最短路方程:O(n3)Floyd-Warshall算法算法（标号修正算法标号修正算法，1962)1962)临临时时标标号号 是是不不通通过过k，k+1，,n 节节点点(i,j 除除外外)时时从从节节点点i到节点到节点j的最短路路长的最短路路长.谢金星谢金星,清华大学数学科学系清华大学数学科学

19、系,2008.Floyd-Warshall算法的具体实现算法的具体实现:O(n3)由由于于要要记记录录所所有有节节点点之之间间最最短短路路的的信信息息,所所以以这这里里我我们们要要用用一一个个二维数组二维数组P；可依据可依据P,采用采用“正向追踪正向追踪”的方式得到最短路的方式得到最短路.STEP2：如果如果k=n,结束结束;否则转否则转STEP1.STEP0:k=0.对于所有节点对于所有节点i和和j:令令 ，,(，若节点，若节点i和和j之间没有弧之间没有弧,认为认为 ).STEP1:k=k+1.对于所有节点对于所有节点i和和j:若若 ,令令 ,;否则令否则令 ,.谢金星谢金星,清华大学数学科

20、学系清华大学数学科学系,2008.Floyd-Warshall算法的算法的矩阵迭代法实现：矩阵迭代法实现：O(n4)令令D为权矩阵为权矩阵(直达最短路长直达最短路长)Dm为正好经过为正好经过m条弧从条弧从i到到j的最短路长的最短路长 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.问题问题1和和2的一种具体建模方法的一种具体建模方法(赋权赋权)在线路选择问题中，当从在线路选择问题中，当从i i可直达可直达j j时（时（同为公同为公汽或地铁站点汽或地铁站点），定义弧），定义弧(i,ji,j)；其上的权为；其上的权为lij表示由表示由i直达直达j付出的代价，可以为时间或费用付出的代价

21、，可以为时间或费用(不包不包括换乘代价；多条线路可达时只保留最小代价括换乘代价；多条线路可达时只保留最小代价)初始等车时间初始等车时间2(3)min也不包括在内，最后结果可加上也不包括在内，最后结果可加上注意：注意：D=D(0)不是对称矩阵不是对称矩阵(“直达矩阵直达矩阵”)dij(0)=dij 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.问题的一种具体建模方法问题的一种具体建模方法i站点是公汽站点，站点是公汽站点，j站点为地铁站点：站点为地铁站点：（1）若若j站站点点对对应应的的所所有有换换乘乘(公公汽汽)站站点点k，均均不不能能从从i直直达达(不不在在i站站点点所所在在公

22、公汽汽线线路路L上上)，则则dij(0)=.（2）若若j站站点点对对应应的的换换乘乘站站点点(k),可可从从i站站点点直直达达k，则则费费用用为为dij(0)=dik(0)；对对于于时时间间则则需需要要加加上上k到到j的步行的步行时间时间.(若有多种选择，取最小成本者即可若有多种选择，取最小成本者即可)ikj 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.问题的一种具体建模方法问题的一种具体建模方法j站点是公汽站点，站点是公汽站点，i站点为地铁站点：站点为地铁站点：（1）若若从从i站站点点对对应应的的任任何何换换乘乘(公公汽汽)站站点点k，均均不不能能直直达达j站点，则站点，则

23、dij(0)=.（2）若若从从i站站点点对对应应的的换换乘乘(公公汽汽)站站点点k，能能直直达达j站站点点，则则费用为费用为dij(0)=dkj(0)；对于时间则需要；对于时间则需要加上加上i到到k的步行的步行时间时间.ikj 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.问题：最小费用或时间问题：最小费用或时间 定义矩阵算子定义矩阵算子“”如下：设如下：设A、B均为均为n阶方阵，阶方阵，C=A B (考虑考虑换乘代价换乘代价)当考当考虑费虑费用矩用矩阵阵之之间间的运算的运算时时，表示在表示在k的换乘时间的换乘时间 当考当考虑时间虑时间矩矩阵阵之之间间的运算的运算时时，D(k)

24、=D(k-1)D 表示表示k次换乘的最低代价次换乘的最低代价(费用或时间费用或时间)该算法大体相当于求最短路的该算法大体相当于求最短路的Floyd-Warshall算法，算法，但考虑了换乘因素，可称为改进但考虑了换乘因素，可称为改进Floyd-Warshall算法算法 类似地类似地,通过修改通过修改Dijkstra算法求解也可算法求解也可 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.问题：最小费用或时间问题：最小费用或时间i,j,ki,j,k表示换乘时间表示换乘时间 i=j 或或k=i，j时，时，i,j,ki,j,k=0其他情形：其他情形：若不可换乘若不可换乘(当当i，j为公

25、汽站点而为公汽站点而k为地铁站点，或为地铁站点，或者者i，j为地铁站点而为地铁站点而k为公汽站点时为公汽站点时)，则，则 i,j,ki,j,k=0若可换乘，则若可换乘，则k这只是等待时间，因为步这只是等待时间，因为步行时间已在行时间已在D中考虑了中考虑了ij 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.第问：已知所有站点间步行时间第问：已知所有站点间步行时间多数队没有给出一般模型多数队没有给出一般模型,而只考虑最多一次换乘而只考虑最多一次换乘多数队的想法：假设多数队的想法：假设“起点步行起点步行”，“换乘步行换乘步行”，“终点步行终点步行”三种模式，限定三种模式，限定步行最大

26、时间步行最大时间后搜索后搜索ikj 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.其他：最短路问题的线性规划模型其他：最短路问题的线性规划模型xij表示弧（表示弧（i，j）是否位于是否位于s-t路上：当路上：当xij=1时，表示弧（时，表示弧（i，j）位于位于s-t路上，当路上，当xij=0时，表示弧（时，表示弧（i，j）不在不在s-t路上路上.关联矩阵是全么模矩阵，因此关联矩阵是全么模矩阵，因此0-10-1变量可以松弛为变量可以松弛为区间区间0,10,1中的实数中的实数 不含负圈不含负圈，变量直接松弛为所有非负实数，变量直接松弛为所有非负实数思考：为什么思考：为什么xij 可

27、以不限定为可以不限定为0，1(0-1规划规划)?谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.最短路问题的线性规划模型最短路问题的线性规划模型线性规划模型，应该可以计算到比较大规模的问题线性规划模型，应该可以计算到比较大规模的问题有些队写出了上述模型，但并未用该模型求解有些队写出了上述模型，但并未用该模型求解可能需要强大的优化软件，数据输入工作量也较大可能需要强大的优化软件，数据输入工作量也较大换乘代价不易考虑（网络上的权不易定义，或不具换乘代价不易考虑（网络上的权不易定义，或不具可加性）可加性）有些同学提到有些同学提到动态规划动态规划,但要么与这里介绍的最短但要么与这里介绍的

28、最短路算法等价路算法等价,要么处理有误要么处理有误,或只是搜索法的变种或只是搜索法的变种 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.有些队讨论有些队讨论“交通阻抗交通阻抗”:“:“文不对题文不对题”道路阻抗在交通流分配中可以通过道路阻抗在交通流分配中可以通过路阻函数路阻函数来描述来描述所谓路阻函数是指路段行驶时间与路段交通负荷，交所谓路阻函数是指路段行驶时间与路段交通负荷，交叉口延误与交叉口负荷之间的关系叉口延误与交叉口负荷之间的关系在具体分配过程中，由路段行驶时间及交叉口延误共在具体分配过程中，由路段行驶时间及交叉口延误共同组成出行交通阻抗同组成出行交通阻抗交通网络上的路

29、阻，应包含反映交通时间、交通安全、交通网络上的路阻，应包含反映交通时间、交通安全、交通成本、舒适程度、便捷性和准时性等等许多因素交通成本、舒适程度、便捷性和准时性等等许多因素 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.同学论文中存在的主要问题同学论文中存在的主要问题2.目标不当，或不完整目标不当，或不完整 3.换乘时间处理不当换乘时间处理不当-尤其地铁站与公汽站之间，以及尤其地铁站与公汽站之间，以及-通过地铁通道换乘的公汽站之间通过地铁通道换乘的公汽站之间1.几乎没有模型，只有算法（一般是搜索法）几乎没有模型，只有算法（一般是搜索法）4.算法使用不当，或滥用算法使用不当，或

30、滥用5.对第问，很少认真进行讨论和建模对第问，很少认真进行讨论和建模6.全文表达不清，思路混乱全文表达不清，思路混乱 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.小结：小结：CUMCM评阅标准评阅标准模型完整明确模型完整明确模型模型/算法创新算法创新软件使用恰当软件使用恰当假设的合理性，建模的创造性，假设的合理性，建模的创造性，结果的正确性，表述的清晰性。结果的正确性，表述的清晰性。深入思考深入思考/分析分析表达规范严谨表达规范严谨严禁作弊抄袭严禁作弊抄袭 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.部分资料下载说明1.清华大学清华大学大学数学实验大学数学实验、数学模型数学模型等课等课程课件：程课件：http:/ （密码：清华大学）（密码：清华大学）2.LINGO程序、课件下载地址：程序、课件下载地址：http:/ 湖南培训班课件下载地址：湖南培训班课件下载地址：http:/ (密码：清华大学密码：清华大学)谢金星谢金星,清华大学数学科学系清华大学数学科学系,2008.Thats all.Any Questions?Thank you for your attendance!最后，祝大家在数学建模活动中取得优异成绩！谢金星,清华大学数学科学系,2008.