应用一：最短路问题课件

数学建模数学建模数学建模数学建模图论方法专题图论方法专题 最最 短短 路路 问问 题题 最短路问题最短路问题 最短路问题是最重要的优化问题之一，最短路问题是最重要的优化问题之一，最短路问题是最重要的优化问题之一，最短路问题是最重要的优化问题之一，它不仅它不仅可以直接应用于解决生产实际的许多问题可以直接应用于解决生产实际的许多问题例如各种例如各种例如各种例如各种管道的铺设、线路的安排、厂区的布局、设备的更管道的铺设、线路的安排、厂区的布局、设备的更管道的铺设、线路的安排、厂区的布局、设备的更管道的铺设、线路的安排、厂区的布局、设备的更新等等，新等等，新等等，新等等，而且经常被作为一个基本工具，用于解决而且经常被作为一个基本工具，用于解决其它优化问题如其它优化问题如运输网络的最小费用流等。运输网络的最小费用流等。运输网络的最小费用流等。运输网络的最小费用流等。（最短距离、费时最少、费用最省）（最短距离、费时最少、费用最省）（最短距离、费时最少、费用最省）（最短距离、费时最少、费用最省）v权、赋权图权、赋权图权、赋权图权、赋权图：对图对图对图对图GG的每一条的每一条的每一条的每一条边边边边e e，可赋与一个实数可赋与一个实数可赋与一个实数可赋与一个实数w w（e e）称为边称为边称为边称为边e e的权。图的权。图的权。图的权。图G G连同它边上的权称为赋权图。连同它边上的权称为赋权图。连同它边上的权称为赋权图。连同它边上的权称为赋权图。路中边权最小的称为最短路。路中边权最小的称为最短路。路中边权最小的称为最短路。路中边权最小的称为最短路。权可以表示铁路长度，通讯网络的造价，网络中表示权可以表示铁路长度，通讯网络的造价，网络中表示权可以表示铁路长度，通讯网络的造价，网络中表示权可以表示铁路长度，通讯网络的造价，网络中表示耗时等。耗时等。耗时等。耗时等。v定义定义：设设P(u,v)是加权图是加权图G中从中从u到到v的路径的路径,则该路则该路径上的边权之和称为该路径的权径上的边权之和称为该路径的权,记为记为w(P).从从u到到v的的路径中权最小者路径中权最小者 P*(u,v)称为称为u到到v的的最短路径最短路径最短路径最短路径.v最短路问题在实际工作中应用最短路问题在实际工作中应用u1、通讯网络中最可靠问题、通讯网络中最可靠问题u2、最大容量问题、最大容量问题u3、统筹方法中求关键路线、统筹方法中求关键路线u4、背包问题、背包问题u5、选址问题、选址问题u6、工件加工顺序问题、工件加工顺序问题u7、中国邮递员问题、中国邮递员问题重要性质：重要性质：重要性质：重要性质：若若v0 v1 vm 是是G中从中从v0到到vm的最短路的最短路,则对则对1km,v0v1 vk 必为必为G中从中从v0到到vk的最短路的最短路.即：最短路是一条路，且最短路的任一段也是最短路。即：最短路是一条路，且最短路的任一段也是最短路。固定起点的最短路问题固定起点的最短路问题vDijkstra算法算法 Dijkstra算法是由荷兰计算机科学家算法是由荷兰计算机科学家狄克斯特拉狄克斯特拉（Dijkstra）于于1959 年提出的。年提出的。使用范围使用范围使用范围使用范围:1)寻求从一固定顶点寻求从一固定顶点v0到其余各点的最短路径到其余各点的最短路径;2)有向图、无向图和混合图有向图、无向图和混合图;3)权非负权非负.求解思路求解思路求解思路求解思路：从始点出发，逐步从始点出发，逐步顺序地向外探寻顺序地向外探寻，每向外延伸一步都要求每向外延伸一步都要求是是最短的。最短的。最短的。最短的。Dijkstra算法算法算法步骤算法步骤S:具有永久标号的顶点集具有永久标号的顶点集;l(v):v的标记的标记,表示从起点表示从起点v0到到v的一条路的权的一条路的权;z(v):v的父顶点的父顶点,用以确定最短路径用以确定最短路径;两种标号两种标号 P 标号标号（Permanent固定固定/永久性标号）永久性标号）从始点到该标号点的最短路权从始点到该标号点的最短路权 T 标号标号（Temporary临时性标号）临时性标号）从始点到该标号点的最短路权从始点到该标号点的最短路权上界上界上界上界输入加权图的带权邻接矩阵输入加权图的带权邻接矩阵w=w(vi,vj)nxn.1)初始化：令初始化：令l(v0)=0,（给起始点给起始点v0标上固定标号标上固定标号）,v v0,l(v)=（其余各点标临时性标号其余各点标临时性标号）;S=v0;z(v)=v02)更新更新l(v),z(v)寻找不在寻找不在S中的顶点中的顶点u（与前一点相邻接）（与前一点相邻接）,使使l(u)为最小为最小.把把u加入到加入到S中中,然后对所有不在然后对所有不在S中的顶点中的顶点v,如如l(v)l(u)+w(u,v),则则更新更新l(v),z(v),即即 l(v)l(u)+w(u,v),z(v)u;3)重复步骤重复步骤2),直到所有顶点都在直到所有顶点都在S中为止中为止.例例1：用用Dijkstra算法求下图从算法求下图从v1到到v6的最短路。的最短路。v1v2v3v4v6v5352242421 解解 （1）首先给）首先给v1以以P标号，给其余所有点标号，给其余所有点T标号。标号。（2）v1的邻接点为的邻接点为v2，v3。v1v2v3v4v6v5352242421（4）例例1：用用Dijkstra算法求下图从算法求下图从v1到到v6的最短路。的最短路。v2的邻接点为的邻接点为v3，v4，v5。v1v2v3v4v6v5352242421（5）（6）反向追踪得反向追踪得v1到到v6的最短路为：的最短路为：v3的邻接点为的邻接点为v5。1,6例例2：v5v223464v3v1v41210 6 1210v8v9v72363v60,01,1,1,11,1,1,1,31,6v5v223464v3v1v41210 6 1210v8v9v72363v60,01,1,1,11,1,1,1,31,6v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,1,31,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,1,31,61,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,1,33,53,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,31,3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01,4,111,11,1,1,31,3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,11,2,61,1,31,3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,11,2,61,1,31,3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,11,2,65,121,35,93,5v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,11,2,65,121,35,9 知从知从v1到到v8 的最短路为：的最短路为：P1，8=P（v1，v3，v2，v5，v8）Dijkstra算法的算法的MATLAB实现实现w=0 1 2 inf 7 4 8 inf;1 0 2 3 inf inf 7 inf;2 2 0 1 5 inf inf inf;inf 3 1 0 3 inf inf 6;7 inf 5 3 0 3 inf 4;4 inf inf inf 3 0 2 6;8 7 inf inf inf 2 0 4;inf inf inf 6 4 6 4 0l=0 1 2 3 6 4 6 9z=1 1 1 3 4 1 6 41445642537w=0 4 1 inf inf inf;inf 0 inf 4 2 4;inf 5 0 inf 6 7;inf inf inf 0 inf inf;inf inf inf 5 0 inf;inf inf inf inf 3 0;l=0 4 1 8 6 8 6 9z=1 1 1 2 2 3 6 4任意两点间的最短路问题任意两点间的最短路问题Floyd算法算法算法算法z使用范围使用范围:1)求每对顶点的最短路径求每对顶点的最短路径;2)有向图、无向图和混合图有向图、无向图和混合图;z算法思想算法思想:直接在图的带权邻接矩阵中用插入顶点的方法依次递推直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出地构造出n个矩阵个矩阵D(1),D(2),D(v),D(v)是图的距离矩阵是图的距离矩阵,同时引入一个后继点矩阵记录两点间的最短路径同时引入一个后继点矩阵记录两点间的最短路径.z输入参数：输入参数：G的带权邻接矩阵的带权邻接矩阵W.z算法输出：距离矩阵算法输出：距离矩阵D以及路由矩阵以及路由矩阵R.（I I）求距离矩阵的方法）求距离矩阵的方法）求距离矩阵的方法）求距离矩阵的方法.（II）求路径矩阵的方法）求路径矩阵的方法.在建立距离矩阵的同时可建立路径矩阵在建立距离矩阵的同时可建立路径矩阵R（III）查找最短路路径的方法）查找最短路路径的方法.然后用同样的方法再分头查找若：然后用同样的方法再分头查找若：（IV）Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的最短路.例例3：求下图中加权图的任意两点间的距离与路径求下图中加权图的任意两点间的距离与路径.插入点插入点 v1，得：得：矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素.插入点插入点 v2，得：得：矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素.插入点插入点 v3，得：得：插入点插入点 v4，得：得：插入点插入点 v5，得：得：插入点插入点 v6，得：得：故从故从v5到到v2的最短路为的最短路为8 由由v6向向v5追溯追溯:由由v6向向v2追溯追溯:所以从到的最短路径为：所以从到的最短路径为：a=0 1 inf inf inf 2;1 0 4 inf inf 4;inf 4 0 2 inf 1;inf inf 2 0 3 3;inf inf inf 3 0 5;2 4 1 3 5 0;68523374Floyd算法的算法的MATLAB实现实现a=0 8 6 2 inf;inf 0-5-3 inf;inf inf 0 inf 4;inf inf inf 0 inf;inf 3 inf 7 0;最最 短短 路路 应用应用 设备更新问题设备更新问题设备更新问题设备更新问题例：某企业使用一种设备，在每年年初，决策者需要决定是否购例：某企业使用一种设备，在每年年初，决策者需要决定是否购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧的，需要支付一定的维修费用。现在的问置费用；若继续使用旧的，需要支付一定的维修费用。现在的问题是如何制定一个五年计划，使总的支付费用最少，表题是如何制定一个五年计划，使总的支付费用最少，表1为设备为设备在各年年初的价格，表在各年年初的价格，表2为使用不同时间的设备所需要的维修费为使用不同时间的设备所需要的维修费用。用。表表1 设备的各年价格设备的各年价格表表2 使用不同时间的维修费用使用不同时间的维修费用年年份份 一一 二二 三三 四四 五五购购 置置 费费 11 11 12 12 13使用年限使用年限 01 12 23 34 45年修理费年修理费 5 6 8 11 18解：（解：（1）分析：显然可以选择的设备更新方案是很多的。例）分析：显然可以选择的设备更新方案是很多的。例如每年都更新一台新设备，其购置费用为如每年都更新一台新设备，其购置费用为（11+11+12+12+13）万元）万元=59万元，而每年支付的维修费用万元，而每年支付的维修费用为为5万元，五年的合计为万元，五年的合计为25万元，于是五年的支付费用为万元，于是五年的支付费用为（59+25）=84万元。万元。又如可决定在第一，三，五年各购置一台，这个方案的设又如可决定在第一，三，五年各购置一台，这个方案的设备购置费用为（备购置费用为（11+12+13）=36万元，维修费用为万元，维修费用为（5+6+5+6+5）=27万元，五年总费用为万元，五年总费用为63万元。万元。如何制定计划适得总的支付费用最少呢？可以把此问题最如何制定计划适得总的支付费用最少呢？可以把此问题最化为最短路问题。化为最短路问题。（2）用点）用点v vi i 代表代表“第第i年年初购进一台新设备年年初购进一台新设备”这种状态（这种状态（v v6为第为第5年年年年底的末状态）。弧底的末状态）。弧（v vi i,v vj j）表示第表示第i年年初购进的设备一直使用到第年年初购进的设备一直使用到第j年年年年初。弧（初。弧（vi,vj）上的权数表示该期间设备所需的费用）上的权数表示该期间设备所需的费用.每条弧的权可按已知资料计算出来。如（每条弧的权可按已知资料计算出来。如（v v1，v v4）是第一年年初购进的）是第一年年初购进的一台设备（支付购置费用为本一台设备（支付购置费用为本11万元），一直使用到了第万元），一直使用到了第3年年底（支付维年年底（支付维修费用为修费用为5+6+8=19万元），故弧（万元），故弧（v v1，v v4）权重为）权重为30万元。万元。这样一来，制定一个最优更新计划的问题就等价于寻求从这样一来，制定一个最优更新计划的问题就等价于寻求从V1到到V6的最的最短路问题。短路问题。按求最短路的计算方法（按求最短路的计算方法（V1，V3，V6）及（）及（V1，V4，V6）均为最短路）均为最短路线，权重为线，权重为53万元。万元。v1v2v3v4 v5 v6161617171822304159223041233123选址问题选址问题1、中心问题、中心问题所谓中心选址问题就是在一网络中选择一点，所谓中心选址问题就是在一网络中选择一点，建立建立公用服务设施公用服务设施，为该网络中的点提供服，为该网络中的点提供服务，使得服务效率最高。比如一个区域的消务，使得服务效率最高。比如一个区域的消防站、自来水厂、学校、变电站、银行、商防站、自来水厂、学校、变电站、银行、商店等选址。为了提高服务效率，自然的想法店等选址。为了提高服务效率，自然的想法是将这些设施建立在中心地点。要求是将这些设施建立在中心地点。要求网络中网络中最远的被服务点离服务设施的距离尽可能小最远的被服务点离服务设施的距离尽可能小。设网络设网络N有个有个n点点v1,v2,vn。dij表示点表示点vi到到vj之间的距之间的距离（即最短路的长度），并记离（即最短路的长度），并记dii=0(i=1,2,n)。定义定义1:记记 ,。若。若 ,则称点则称点vk为网络为网络N的中心，的中心，I为直径。为直径。定义定义2:令令 ，若，若 ，则称，则称vk为网络为网络N的中心。的中心。例例1某城市要建立一个消防站，为该市所某城市要建立一个消防站，为该市所属的七个区服务，如图所示问应设在哪个属的七个区服务，如图所示问应设在哪个区，才能使它至最远区的路径最区，才能使它至最远区的路径最 距离矩阵第距离矩阵第i行的最大值行的最大值S(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处.例例2 教教育育部部门门打打算算在在某某新新建建城城区区建建一一所所学学校校，让让附附近近七七个个居居民民区区的的学学生生就就近近入入学学。七七个个居居民民区区之之间间的的道道路路如如下下图图所所示示，学学校校应应建建在在哪哪个个居居民民区区，才才能能使使大大家家都都方方便便？（图中距离单位：百米）。（图中距离单位：百米）。2、重心问题、重心问题例例3 例例2中中，七七个个居居民民区区的的学学生生人人数数分分别别为为：40、25、45、30、20、35、50人人，学学校校应应建建在在哪哪个个居居民民区区，才才能能使使大大家家都都方方便便？（图中距离单位：百米）。（图中距离单位：百米）。简易公路建设方案简易公路建设方案简易公路建设方案简易公路建设方案某合同战术训练基地为保障即将进行的联合军事演某合同战术训练基地为保障即将进行的联合军事演习，准备在原有的习，准备在原有的1个油库的基础上，再设立个油库的基础上，再设立7个固个固定的燃料补给点。定的燃料补给点。v1v7v6v2v8v5v3v4油库与补给点的位置如图所示，其中油库位于油库与补给点的位置如图所示，其中油库位于v1点，点，补给点位于补给点位于v2,v8点。点。经过前期的测绘工作，如果在油库和补给点之间修建经过前期的测绘工作，如果在油库和补给点之间修建简易公路，由于地形不同，每段公路花费如图，每单简易公路，由于地形不同，每段公路花费如图，每单位费用为位费用为1万元。请根据测绘结果，规划一个总造价万元。请根据测绘结果，规划一个总造价最低的建设方案。最低的建设方案。v1v7v6v2v8v5v3v425734326436174182总造价最低总造价最低各补给点到油库的各补给点到油库的花费均达到最小花费均达到最小？v1v7 6v6 4 4v2 1 1v8 9v5 6v3 2 2 v4 32243611简易公路建设方案简易公路建设方案最短运输路线问题最短运输路线问题最短运输路线问题最短运输路线问题 如图的交通网络，每条弧上的数字代表车辆在该路段行驶所需的如图的交通网络，每条弧上的数字代表车辆在该路段行驶所需的时间，有向边表示单行道，无向边表示可双向行驶。若有一批货时间，有向边表示单行道，无向边表示可双向行驶。若有一批货物要从物要从1号顶点运往号顶点运往11号顶点，问运货车应沿哪条线路行驶，才号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？能最快地到达目的地？10237411659813 35 512122 210106 61 15 58 88 87 79 99 93 32 22 27 718 9 10 11最廉价航费表的制定最廉价航费表的制定最廉价航费表的制定最廉价航费表的制定 某公司在六个城市某公司在六个城市c1,c6中有分公司，从中有分公司，从ci到到cj的直接航程票价记在下述矩阵中的的直接航程票价记在下述矩阵中的(i,j)位置上。（位置上。（表示无直接航路），请帮助该公司设计一张任意两城表示无直接航路），请帮助该公司设计一张任意两城市间的票价最便宜的路线表。市间的票价最便宜的路线表。运行输出结果：运行输出结果：D=D=0 35 45 35 25 10 0 35 45 35 25 10 35 0 15 20 30 25 35 0 15 20 30 25 45 15 0 10 20 35 45 15 0 10 20 35 35 20 10 0 10 25 35 20 10 0 10 25 25 30 20 10 0 35 25 30 20 10 0 35 10 25 35 25 35 0 10 25 35 25 35 0path=path=1 6 5 5 5 6 1 6 5 5 5 6 6 2 3 4 4 6 6 2 3 4 4 6 5 2 3 4 5 4 5 2 3 4 5 4 5 2 3 4 5 6 5 2 3 4 5 6 1 4 3 4 5 1 1 4 3 4 5 1 1 2 4 4 1 6 1 2 4 4 1 6医院选址医院选址医院选址医院选址 已知一个地区的交通网络如下：其中点代表居民小区，已知一个地区的交通网络如下：其中点代表居民小区，边表示公路，边表示公路，lij为公路距离，问区中心医院应建在哪个为公路距离，问区中心医院应建在哪个小区能使居民就诊时所走路程最短？小区能使居民就诊时所走路程最短？安排生产问题安排生产问题：现代化生产过程中，生产部门面临的突出问：现代化生产过程中，生产部门面临的突出问题之一，便是如何选取合理的生产率题之一，便是如何选取合理的生产率.生产率过高，导致产品生产率过高，导致产品大量积压，使流动资金不能及时回笼；生产率过低，产品不大量积压，使流动资金不能及时回笼；生产率过低，产品不能满足市场需要，使生产部门失去获利的机会能满足市场需要，使生产部门失去获利的机会.可见，生产部可见，生产部门在生产过程中必须时刻注意市场需求的变化，以便适时调门在生产过程中必须时刻注意市场需求的变化，以便适时调整生产率，获取最大收益整生产率，获取最大收益.某生产厂家年初要制定生产策略，已预知其产品在年初的某生产厂家年初要制定生产策略，已预知其产品在年初的需求量为需求量为a=6万单位，并以万单位，并以b=1万单位万单位/月速度递增月速度递增.若生产产品若生产产品过剩，则需付单位产品单位时间（月）的库存保管费过剩，则需付单位产品单位时间（月）的库存保管费C2=0.2元；元；若产品短缺，则单位产品单位时间的短期损失费若产品短缺，则单位产品单位时间的短期损失费C3=0.4元元.假假定生产率每调整一次带有固定的调整费定生产率每调整一次带有固定的调整费C1=1万元，问：工厂万元，问：工厂应如何制定当年的生产策略，使工厂的总损失最小？应如何制定当年的生产策略，使工厂的总损失最小？月份月份123456789101112需求量需求量（万元）（万元）67891011121314151617每月社会需求量见下表：每月社会需求量见下表：消防站选址消防站选址：某城市的开发区中要建一个消防站，该开发区某城市的开发区中要建一个消防站，该开发区的示意图如图所示，其中的示意图如图所示，其中 表示开发区中表示开发区中10个消个消防重点单位，考虑到交通路况，部分单位之间往返的距离不防重点单位，考虑到交通路况，部分单位之间往返的距离不完全相同，分析消防站选址问题。完全相同，分析消防站选址问题。.