第8讲最短路问题.ppt课件

1、数学建模与数学实验数学建模与数学实验 最短路问题最短路问题实验目的实验目的实验内容实验内容2会用会用MATLAB软件求最短路软件求最短路1了解最短路的算法及其运用了解最短路的算法及其运用1图图 论论 的的 基基 本本 概概 念念2最最 短短 路路 问问 题题 及及 其其 算算 法法3最最 短短 路路 的的 应应 用用4建模案例：最优截断切割问题建模案例：最优截断切割问题5实验作业实验作业图图 论论 的的 基基 本本 概概 念念一、一、 图图 的的 概概 念念1图的定义图的定义2顶点的次数顶点的次数 3子图二、二、 图图 的的 矩矩 阵阵 表表 示示1 关联矩阵关联矩阵2 邻接矩阵邻接矩阵前往前

2、往定义定义有序三元组G=(V,E, )称为一个图,假设：图的定义图的定义定义定义定义定义规定用记号和分别表示图的顶点数和边数.前往前往顶点的次数顶点的次数4()4dv5)(3)(2)(444vdvdvd定定理理)(2)()(GvdGVv推推论论任何图中奇次顶点的总数必为偶数例例 在一次聚会中，认识奇数个人的人数一定是偶数在一次聚会中，认识奇数个人的人数一定是偶数.前往前往子图子图前往前往关联矩阵关联矩阵注：假设图为简单图前往前往邻接矩阵邻接矩阵注：假设图为简单图无向赋权图的邻接矩阵可类似定义前往前往最最 短短 路路 问问 题题 及及 其其 算算 法法一、一、 基基 本本 概概 念念二、固二、固

3、 定定 起起 点点 的的 最最 短短 路路三、每三、每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路前往前往基基 本本 概概 念念通路44112544141vevevevevWvv道路4332264521141vevevevevevTvv路径4521141vevevPvv定定义义（）任意两点均有路径的图称为连连通通图图（）起点与终点重合的路径称为圈圈（）连通而无圈的图称为树树前往前往固固 定定 起起 点点 的的 最最 短短 路路最短路是一条途径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，那么从u0到其他顶点的最短路将构成一棵以u0为根的树 因此, 可采用树生长的过

4、程来求指定顶点到其他顶点的最短路算法步骤：算法步骤：（4） 若S ，转 2，否则，停止.（2）更新l v( )、z v ( )： vSVS,若l v( )l uW u v( )( , ) 则令l v( )=l uW u v( )( , ),z v ( )= u TO MATLAB(road1) 1 2 34 5 6 7 8前往前往uuuuuuuu每每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路(二二)算算法法原原理理1求间隔矩阵的方法求间隔矩阵的方法2求途径矩阵的方法求途径矩阵的方法3查找最短路途径的方法查找最短路途径的方法一一算法的根本思想算法的根本思想三三算法步骤算法步骤前往前往

5、算法的根本思想算法的根本思想前往前往算法原理算法原理 求间隔矩阵的方法求间隔矩阵的方法前往前往算法原理算法原理 求途径矩阵的方法求途径矩阵的方法)()0()0(ijrR, jrij)0(每求得一个 D(k)时，按下列方式产生相应的新的 R(k)否则若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立间隔矩阵的同时可建立途径矩阵R 即当k被插入任何两点间的最短途径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的途径)(D)(R前往前往)(Rvi j算法原理算法原理 查找最短路途径的方法查找最短路途径的方法若1)(prij，则点 p1是点 i 到

6、点 j 的最短路的中间点.pkp2p1p3q1q2qm那么由点i到j的最短路的途径为：jqqqpppimk,21, 12前往前往算法步骤算法步骤Floyd算算法法：求任意两点间的最短路(2) 更新 d(i,j), r(i,j)对所有 i,j，若 d(i,k)+d(k,j)d(i,j)，则 d(i,j)d(i,k)+d(k,j), r(i,j)k(3) 若 k=，停止否则 kk+1，转（） 例例 求下图中加权图的任意两点间的距离与路径 TOMATLAB(road2(floyd)5333434331543243332344441,0646960243420256420793570RD951d，故从

7、v5到v1的最短路为51r所以从 v5到 v1的最短路径为：1435.前往前往最最 短短 路路 的的 应应 用用一、一、 可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题二、二、 选选 址址 问问 题题1 中心问题中心问题2 重心问题重心问题前往前往可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题 例例 1 设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的.若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用.现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少. 已知该种设备在每年年初的价格为

8、：第一年第二年第三年第四年第五年1111121213 使用不同时间设备所需维修费为：使用年限0112233445维修费5681118（3）问题转化为顶点Xb1到Xrk6( )的最短路问题.五年的最优购置费为 kbrkd XX1 2 3 4 516, , , ,( )min (,)其中 d(Xb1,Xrk6( )为顶点Xb1到Xrk6( )的最短路的权.前往前往 选址问题-中心问题则kv就是要求的建立消防站的地点此点称为图的中中心心点点 TO MATLAB(road3(floyd)05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730571065

9、 .42502545 .24720375 .5710530DS(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5S(v3)=6,故应将消防站设在v3处. 前往前往 选址问题-重心问题前往前往实验作业实验作业 消费战略问题：现代化消费过程中，消费部门面临的突出问题之一，便是如何选取合理的消费率.消费率过高，导致产品大量积压，使流动资金不能及时回笼；消费率过低，产品不能满足市场需求，使消费部门失去获利的时机.可见，消费部门在消费过程中必需时辰留意市场需求的变化，以便适时调整消费率，获取最大收益. 某消费厂家年初要制定消费战略，已预知其产品在年初的需求量为a=