数学建模：最短路问题

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

2、接矩阵返回返回定义定义有序三元组G=(V,E, )称为一个图图.1 V=,21nvvv是有穷非空集，称为顶顶点点集集， 其中的元素叫图 G 的顶顶点点.2 E 称为边边集集，其中的元素叫图 G 的边边.3 是从边集 E 到顶点集 V 中的有序或无序的元素 偶对的集合的映射，称为关关联联函函数数.例例1 设 G=(V ,E,)，其中 V=v1 ,v2 , v3 , v4， E=e1, e2 , e3, e4, e5,335414413312211)(,)(,)(,)(,)(vvevvevvevvevve.G 的图解如图.图的定义图的定义定义定义定义定义若将图 G 的每一条边 e 都对应一个实数

3、w(e)，称 w(e)为边的权权，并称图 G 为赋赋权权图图.规定用记号和分别表示图的顶点数和边数.返回返回XYxxxxyyy1234123顶点的次数顶点的次数定定义义（）在无向图中，与顶点 v 关联的边的数目（环算两次）称为 v的次次数数，记为 d(v)（）在有向图中，从顶点 v 引出的边的数目称为 v的出出度度，记为 d+(v)，从顶点 v引入的边的数目称为的入入度度，记为 d-(v)，d(v)=d+(v)+d-(v)称为 v的次数4)(4vd5)(3)(2)(444vdvdvd定理定理)(2)()(GvdGVv推论推论任何图中奇次顶点的总数必为偶数例例 在一次聚会中，认识奇数个人的人数一

4、定是偶数。返回返回子图子图定定义义设图 G=(V,E,),G1=(V1,E1,1)(1) 若 V1V，E1E,且当 eE1时，1(e)= (e),则称 G1是 G 的子子图图特别的，若 V1=V，则 G1称为 G 的生生成成子子图图(2) 设 V1V，且 V1，以 V1为顶点集、两个端点都在 V1中的图 G 的边为边集的图 G 的子图，称为 G 的由由 V1导导出出的的子子图图，记为 GV1.(3)设 E1E,且 E1,以 E1为边集,E1的端点集为顶点集的图 G 的子图,称为 G 的由由 E1导导出出的的子子图图,记为 GE1. GGv1,v4,v5Ge1,e2,e3返回返回关联矩阵关联矩阵

5、对无向图，其关联矩阵)(ijm，其中：不关联与若相关联与若jijiijevevm01M=43215432110110011000101110001vvvveeeee对有向图，其关联矩阵)(ijm，其中：不关联与若的终点是若的起点是若jijijiijevevevm011注：假设图为简单图返回返回邻接矩阵邻接矩阵对无向图，其邻接矩阵)(ijaA，其中：不相邻与若相邻与若jijiijvvvva01注：假设图为简单图A=432143210111101011011010vvvvvvvv对有向图（，） ，其邻接矩阵)(ijaA，其中：EvvEvvajijiij），若（），若（01对有向赋权图，其邻接矩阵)

6、(ijaA，其中：EvvjiwEvvwajiijjiijij),(0,),(若若为其权且若无向赋权图的邻接矩阵可类似定义A=4321432105375083802720vvvvvvvv返回返回最最 短短 路路 问问 题题 及及 其其 算算 法法一、一、 基基 本本 概概 念念二、固二、固 定定 起起 点点 的的 最最 短短 路路三、每三、每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路返回返回基基 本本 概概 念念通路44112544141vevevevevWvv道路4332264521141vevevevevevTvv路径4521141vevevPvv定义定义（）任意两点均有路径的图

7、称为连通图连通图（）起点与终点重合的路径称为圈圈（）连通而无圈的图称为树树定定义义（）设 P(u,v)是赋权图 G 中从 u 到 v的路径， 则称)()()(PEeewPw为路径 P 的权权(2) 在赋权图 G 中，从顶点 u 到顶点 v的具有最小权的路 ),(*vuP，称为 u 到 v的最最短短路路返回返回固固 定定 起起 点点 的的 最最 短短 路路最短路是一条路径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路Dijkstra 算法算法：求 G 中从顶点 u0到其

8、余顶点的最短路设 G 为赋权有向图或无向图，G 边上的权均非负对每个顶点，定义两个标记（l v( )，z v( )） ，其中: l v( )：表从顶点 u0到 v 的一条路的权 z v( )：v 的父亲点，用以确定最短路的路线算法的过程就是在每一步改进这两个标记，使最终l v( )为从顶点u0到 v 的最短路的权S：具有永久标号的顶点集输入: G 的带权邻接矩阵),(vuw算法步骤：算法步骤：（2）更新l v( )、z v( )： vSVS,若l v( )l uW u v( )( , ) 则令l v( )=l uW u v( )( , ),z v( )= u例例 求下图从顶点 u1到其余顶点的

9、最短路先写出带权邻接矩阵： 03064093021509701608120W因 G 是无向图，故 W是对称阵u1u2u3u4u5u6u7u8返回返回每每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路(二二)算算法法原原理理1、求距离矩阵的方法、求距离矩阵的方法2、求路径矩阵的方法、求路径矩阵的方法3、查找最短路路径的方法、查找最短路路径的方法（一）算法的基本思想（一）算法的基本思想（三）算法步骤（三）算法步骤返回返回算法的基本思想算法的基本思想返回返回算法原理算法原理 求距离矩阵的方法求距离矩阵的方法把带权邻接矩阵 W 作为距离矩阵的初值，即 D(0)=)()0(ijd=W（）D(1)

10、= )() 1 (ijd，其中)0(1)0() 1 (,miniijijddd)0(1jd)1(ijd是从 vi到 vj的只允许以 v1作为中间点的路径中最短路的长度（2）D(2)= )()2(ijd，其中) 1 (2) 1 ()2(,miniijijddd)1 (2 jd )2(ijd是从 vi到 vj的只允许以 v1 、 v2作为中间点的路径中最短路的长度（）D()=)()(ijd，其中)1()1()(,miniijijddd)1( jd)(ijd是从 vi到 vj的只允许以 v1、v2、v作为中间点的路径中最短路的长度即是从 vi到 vj中间可插入任何顶点的路径中最短路的长，因此D()即

11、是距离矩阵返回返回算法原理算法原理 求路径矩阵的方法求路径矩阵的方法R=)(ijr, rij的含义是从 vi到 vj的最短路要经过点号为 rij的点)()0()0(ijrR, jrij)0(每求得一个 D(k)时，按下列方式产生相应的新的 R(k)否则若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立距离矩阵的同时可建立路径矩阵R 即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ， 可由 来查找任何点对之间最短路的路径( )D( )R( )R返回返回ij算法原理算法原理 查找最短路路径的方法查找最短路路径的方法若1)(prij，则点 p1是

12、点 i 到点 j 的最短路的中间点.然后用同样的方法再分头查找若：（） 向点 i 追朔得：2)(1prip,3)(2prip,kipprk)(（） 向点 j 追朔得：1)(1qrjp,2)(1qrjq,jrjqm)(pkp2p1p3q1q2qm则由点i到j的最短路的路径为：jqqqpppimk,21, 12返回返回算法步骤算法步骤Floyd 算法：算法：求任意两点间的最短路D(i,j)：i 到 j 的距离R(i,j)：i 到 j 之间的插入点输入: 带权邻接矩阵 w(i,j)（） 赋初值：对所有 i,j, d(i,j)w(i,j), r(i,j)j, k1(2) 更新 d(i,j), r(i,

13、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，转（） 例例 求下图中加权图的任意两点间的距离与路径5333434331543243332344441,0646960243420256420793570RD951d，故从 v5到 v1的最短路为51r由 v4向 v5追朔：3, 35354rr;由 v4向 v1追朔：141r所以从 v5到 v1的最短路径为：1435.返回返回最最 短短 路路 的的 应应 用用一、一、 可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题二

14、、二、 选选 址址 问问 题题1、 中心问题中心问题2、 重心问题重心问题返回返回可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题 例例 1 设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的.若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用.现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少. 已知该种设备在每年年初的价格为：第一年第二年第三年第四年第五年1111121213 使用不同时间设备所需维修费为：使用年限0112233445维修费5681118构造加权有向图 G1(V,E)（1）顶点集 VXib

15、 , i=1,2,3,4,5Xirk( ), i=2,3,4,5,6; k=1,2,i-1,每个顶点代表年初的一种决策，其中顶点Xib代表第 i 年初购置新设备的决策，顶点Xirk( )代表第 i 年初修理用过 k 年的旧设备的决策也可构造加权有向图 G2(V,E).（2）弧集 E=(,)V Vij，i=1,2,3,4,5; ij6,弧(,)V Vij表第 i 年初购进一台设备一直使用到第 j 年初的决策，其权 W(,)V Vij表由这一决策在第 i 年初到第 j 年初的总费用，如W(,)V V14=11+5+6+8=30.（3）问题转化为求V1到V6的最短路问题，求得两条最短路为VVV146

16、，VVV136，权为 53，与图 G1(V,E)的解相同返回返回（2） 计算在各点iv设立服务设施的最大服务距离)(ivS max)(1ijjidvS , 2 , 1i 选址问题选址问题-中心问题中心问题例例 2某城市要建立一个消防站，为该市所属的七个区服务，如图所示问应设在那个区，才能使它至最远区的路径最短（1）用 Floyd 算法求出距离矩阵 D=)(ijd（3）求出顶点kv，使)(min)(1iikvSvS则kv就是要求的建立消防站的地点此点称为图的中心点中心点05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .4250

17、2545 .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处。 返回返回 选址问题选址问题-重心问题重心问题例例 3某矿区有七个矿点，如图所示已知各矿点每天的产矿量)(jvq（标在图的各顶点上） 现要从这七个矿点选一个来建造矿厂 问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运力（千吨公里）最小（1）求距离阵 D=)(ijd（2） 计算各顶点作为选矿厂的总运力)(ivm ijjjidvqvm)()(1 , 2 , 1i（3） 求kv使)(min)(1iikvmvm，则kv就是选矿厂应设之矿点此点称为图 G 的重心重心或中位点中位点返回返回实验作业实验作业 生产策略问题生产策略问题：现代化生产过程中，生产部门面临的突出问题之一，便是如何选取合理的生产率