数学建模赛题分析建模方法.ppt

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

矩阵迭代法实现：O(n4)令D为权矩阵(直达最短路长)Dm为正好经过m条弧从i到j的最短路长第38页,共57页，星期六，2024年，5月问题1和2的一种具体建模方法(赋权)在线路选择问题中，当从i可直达j时（同为公汽或地铁站点），定义弧(i,j)；其上的权为lij表示由i直达j付出的代价，可以为时间或费用(不包括换乘代价；多条线路可达时只保留最小代价)初始等车时间2(3)min也不包括在内，最后结果可加上注意：D=D(0)不是对称矩阵(“直达矩阵”)dij(0)=dij第39页,共57页，星期六，2024年，5月问题１－２的一种具体建模方法i站点是公汽站点，j站点为地铁站点：（1）若j站点对应的所有换乘(公汽)站点k，均不能从i直达(不在i站点所在公汽线路L上)，则dij(0)=∞.（2）若j站点对应的换乘站点(k),可从i站点直达k，则费用为dij(0)=dik(0)；对于时间则需要加上k到j的步行时间.(若有多种选择，取最小成本者即可)ikj第40页,共57页，星期六，2024年，5月问题１－２的一种具体建模方法j站点是公汽站点，i站点为地铁站点：（1）若从i站点对应的任何换乘(公汽)站点k，均不能直达j站点，则dij(0)=∞.（2）若从i站点对应的换乘(公汽)站点k，能直达j站点，则费用为dij(0)=dkj(0)；对于时间则需要加上i到k的步行时间.ikj第41页,共57页，星期六，2024年，5月问题１－２：最小费用或时间定义矩阵算子“⊙”如下：设A、B均为n阶方阵，C=A⊙B(考虑换乘代价)当考虑费用矩阵之间的运算时，表示在k的换乘时间当考虑时间矩阵之间的运算时，＝０D(k)=D(k-1)⊙D表示k次换乘的最低代价(费用或时间)该算法大体相当于求最短路的Floyd-Warshall算法，但考虑了换乘因素，可称为改进Floyd-Warshall算法类似地,通过修改Dijkstra算法求解也可第42页,共57页，星期六，2024年，5月问题１－２：最小费用或时间δi,j,k表示换乘时间i=j或k=i，j时，δi,j,k=0其他情形：若不可换乘(当i，j为公汽站点而k为地铁站点，或者i，j为地铁站点而k为公汽站点时)，则δi,j,k=0若可换乘，则k这只是等待时间，因为步行时间已在D中考虑了ij第43页,共57页，星期六，2024年，5月第３问：已知所有站点间步行时间多数队没有给出一般模型,而只考虑最多一次换乘多数队的想法：假设“起点步行”，“换乘步行”，“终点步行”三种模式，限定步行最大时间后有哪些信誉好的足球投注网站ikj第44页,共57页，星期六，2024年，5月其他：最短路问题的线性规划模型xij表示弧（i，j）是否位于s-t路上：当xij=1时，表示弧（i，j）位于s-t路上，当xij=0时，表示弧（i，j）不在s-t路上.关联矩阵是全么模矩阵，因此0-1变量可以松弛为区间[0,1]中的实数不含负圈，变量直接松弛为所有非负实数思考：为什么xij可以不限定为{0，1}(0-1规划)?第45页,共57页，星期六，2024年，5月