lingo讲解课件数学建模讲座2007B题tsinghua幻灯片.pptVIP

Example Dijkstra算法（标号设定算法） 适用于正费用网络：“分层”设定标号 永久标号：S中的点，uj是最短路长 临时标号；其他点， uj是只通过S中的点的最短路长 对于稠密网络，这是求解最短路问题可能达到的最小的复杂度,因为任何算法都至少必须对每条弧考虑一次. 对于稀疏网络，利用各种形式的堆（Heap），其复杂度可降为 或 等 算法复杂度O( n2+m)：如链表或邻接矩阵实现 找最小标号点　　　修改标号 　特点：求所有点对间最短路 　基本思想：逐步逼近，迭代求解最短路方程: O(n3) Floyd-Warshall算法 （标号修正算法，1962) 临时标号 是不通过k，k+1，…,n 节点(i,j 除外)时从节点i到节点j的最短路路长. Floyd-Warshall算法的具体实现: O(n3) 由于要记录所有节点之间最短路的信息, 所以这里我们要用一个二维数组P； 可依据P, 采用“正向追踪”的方式得到最短路. STEP2：如果k=n, 结束; 否则转STEP1. STEP0: k=0. 对于所有节点i和j: 令 ， , ( ，若节点i和j之间没有弧, 认为 ) . STEP1: k=k+1. 对于所有节点i和j: 若 , 令 , ; 否则令 , . Floyd-Warshall算法的矩阵迭代法实现：O(n4) 令D为权矩阵(直达最短路长) Dm为正好经过m条弧从i到j的最短路长 问题1和2的一种具体建模方法(赋权) 在线路选择问题中，当从i可直达j时（同为公汽或地铁站点），定义弧(i,j)；其上的权为 lij表示由i直达j付出的代价，可以为时间或费用 (不包括换乘代价；多条线路可达时只保留最小代价) 初始等车时间2(3)min也不包括在内，最后结果可加上 注意：D=D(0)不是对称矩阵(“直达矩阵”) dij(0)=dij 问题１－２的一种具体建模方法 i站点是公汽站点，j站点为地铁站点： （1）若j站点对应的所有换乘(公汽)站点k，均不能从i直达(不在i站点所在公汽线路L上)，则dij(0) =∞. （2）若j站点对应的换乘站点(k), 可从i站点直达k，则费用为dij(0) = dik(0)；对于时间则需要加上k到j的步行时间. (若有多种选择，取最小成本者即可) i k j 问题１－２的一种具体建模方法 j站点是公汽站点，i站点为地铁站点： （1）若从i站点对应的任何换乘(公汽)站点k，均不能直达j站点，则dij(0) =∞. （2）若从i站点对应的换乘(公汽)站点k，能直达j站点， 则费用为dij(0) = dkj(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 其他：最短路问题的线性规划模型 xij表示弧（i，j）是否位于s-t路上：当xij =1时，表示弧（i，j）位于s-t路上，当xij =0时，表示弧（i，j）不在s-t路上. 关联矩阵是全么模矩阵，因此0-1变量可以松弛