《数据、模型与决策 (第二版)》第七章图及网络概述.ppt

《《数据、模型与决策 (第二版)》第七章图及网络概述.ppt》由会员分享，可在线阅读，更多相关《《数据、模型与决策 (第二版)》第七章图及网络概述.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章图及网络概述第七章 图及网络概述数据、模型与决策(第二版)学习目标了解如何用图论的观点去分析解决简单的实际问题。要求掌握图的基本概念；掌握用标号法求有向图与无向图中从一个点到另一个点的最短路；掌握可行流、可行流的流量、最大流及增广链的概念，了解求最大流的Ford-Fulkerson标号法。第七章 图及网络概述数据、模型与决策(第二版)第七章图及网络概述7.1 图的基本概念7.2 最短路问题7.3 网络最大流问题7.4 最小费用网络最大流问题第七章 图及网络概述数据、模型与决策(第二版)下图表示6个球队之间赛事关系。其中点a,b,c,d,e,f分别表示6个球队，两点的连结表示两球队之间的赛

2、事关系。因此，从图中可反映出a球队分别与b,c,d球队有赛事；b球队还与c,e球队，d球队还与e球队有赛事，而f均不与球队a,b,c,d,e有赛事。综上，这6个球队之间的关系可用图(a)来表示，也可用图(b)来反映。第七章 图及网络概述数据、模型与决策(第二版)第七章 图及网络概述数据、模型与决策(第二版)图7-2是一张石油流向的管网示意图，v1点表示石油开采地，v7点表示石油的汇集站，v2，v3，v4，v5，v6表示可供选择的石油流动加压站(中间站)，箭头表示石油流向，箭线旁的数字表示管线的长度。现在要从v1地调运石油到v7地，怎样选择管线可使路径最短？第七章 图及网络概述数据、模型与决策(

3、第二版)第七章 图及网络概述数据、模型与决策(第二版)7.1.1无向图和有向图无向图和有向图无向图：一般地，设V(v1，v2,.vp)是p个点的集合，Ee1，e2，eq是q条边的集合，其中 eivi，vjvj,vi，vi,vjV 把由V和E组成的图形称为无向图，记为G(V，E)。第七章 图及网络概述数据、模型与决策(第二版)有向图：如果一个图是由点和弧所组成，则称此图为有向图，记为D(V，A)。其中Vv1,v2,.,vp，Aa1,a2,.aq，aij=(vi,vj)(vj,vi)，vi,vjV，并称aij是以vi为始点，vj为终点的弧，i,j 的顺序是不能颠倒的，图中弧的方向用箭头标识。第七章

4、 图及网络概述数据、模型与决策(第二版)连通图：如果图G中任何两顶点间至少有一条链，则称G是连通图，否则为不连通。赋权图：无向图G（或有向图D）中，如果每条边(弧)都被赋予一个权数ij，则称G（或D）为赋权无向图(有向图)，记为G(V，E，W)(或D(V，A，W)。第七章 图及网络概述数据、模型与决策(第二版)7.1.2 链、路链、路链：对于无向图G(V，E)，称某顶点和边交替的序列vi1,ei1,vi2,ei2,.vi(t-1),ei(t-1),vit为连接vi1和vit的一条链，简记为vi1，vi2，vit.其中eik(eik，ei(k+1)，k1，2，t-1。路：在有向图D(V，A)中，

5、称链vi1，vi2，.，vit为一条以vi1为始点，通向终点vit的路。如果vi1=vit，则称之为回路。第七章 图及网络概述数据、模型与决策(第二版)第七章图及网络概述7.1 图的基本概念7.2 最短路问题7.3 网络最大流问题7.4 最小费用网络最大流问题第七章 图及网络概述数据、模型与决策(第二版)7.2最短路问题7.2.1 问题的提出7.2.2 Dijkstra算法（双标号法）7.2.3 最短路问题的应用7.2.4 无向图上的Dijkstra算法第七章 图及网络概述数据、模型与决策(第二版)7.2.1 问题的提出设一个简单有向图D=(V，A)，对其中指定的两个点Vs和Vt找到一条从Vs

6、到Vt的路，使得这条路上所有弧的权数的总和最小（弧的权数根据具体问题的要求可以是路程的长度，成本的花费等等），这条路被称之为从Vs到Vt的最短路，这条路上所有弧的权数的总和被称之为从Vs到Vt的距离。第七章 图及网络概述数据、模型与决策(第二版)7.2.2 Dijkstra算法（双标号法）双标号：对图中的点Vi赋予两个标号（P(Vi)，i）：第一个标号P(Vi)表示从起点Vs到Vi的最短路的长度，第二个标号i表示在Vs到Vi的最短路上Vi前面一个邻点的下标，即用来标识路径，从而可对终点到始点进行反向追踪，找到Vs到Vt的最短路。第七章 图及网络概述数据、模型与决策(第二版)Dijkstra算法

7、步骤：给起点vs标号（0，s），表示从v1到v1的距离为0，vs为起点。找出已标号的点的集合I，没标号的点的集合J，求出弧集A=（vi,vj）viI,vjJ，这个弧集是指所有从已标号的点到未标号的点的集合。若上述弧集A=，表明从所有已经赋予标号的顶点出发，不再有这样的弧，它的另一顶点尚未标号，则计算结束。对于已有标号的顶点，可求得从v1到达这个顶点的最短路，对于没有标号的顶点，则不存在从v1到达这个顶点的路。若弧集A，转下一步。对弧集A中的每一条弧(vi,vj)，计算 Tij=P(Vi)+ij 在所有的Tij中，找到其值为最小的弧，假设为（vs,vt）。需要注意的是，若上述Tij值为最小的弧有

8、多条，且这些弧的第二个顶点vj相同，则表明存在多条最优路径，因此，vj应得到多个双标号。给弧（vs,vt）的终点vt赋予双标号（P(Vt)，s）。返回步骤（2）。第七章 图及网络概述数据、模型与决策(第二版)求v1到其余各点的最短路第七章 图及网络概述数据、模型与决策(第二版)第七章 图及网络概述数据、模型与决策(第二版)7.2.3 最短路问题的应用如图，v1点表示石油开采地，v7点表示石油的汇集站，箭线旁的数字表示管线的长度，现在要从v1地调运石油到v7地，怎样选择管线可使路径最短？第七章 图及网络概述数据、模型与决策(第二版)设备更新问题。某公司在5年期内都要用到某台设备，要在今后5年的年

9、初作出购买新设备或继续使用旧设备的决策。若购新的，要支付购置费；若继续用旧的，则要支付维修费。这台设备在5年期内每年的购价和维修费用估计如表7-1所示。试制订一个5年之内的更新设备计划，使得5年内购置费和维修费总的支付费用最小。年份年份1 12 23 34 45 5年初购年初购价，万价，万元元1011111212维修费，维修费，万元万元345811第七章 图及网络概述数据、模型与决策(第二版)用点vi表示“第i年年初购进一台新设备”，我们加v6点表示第5年年底，从v1,v2,v6之间各画一条弧，弧（vi,vj）表示在第i年年初购进的设备一直使用到第j年年初，即第j-1年年底。第七章 图及网络概

10、述数据、模型与决策(第二版)我们将图中的每条弧赋予权数。对于弧（vi,vj），它的权数为从第i年年初购进设备至第j-1年年底更新设备所花费的购置费及维修费的总和，用cij来表示，第七章 图及网络概述数据、模型与决策(第二版)第七章 图及网络概述数据、模型与决策(第二版)7.2.4 无向图上的Dijkstra算法无向图中的任一条边vi,vj均可用方向相反的两条弧（vi,vj）和（vj,vi）来代替。把原来的无向图变为有向图后，即可用上述的Dijkstra算法求解。也可以直接在原来的无向图上用Dijkstra算法求解。第七章 图及网络概述数据、模型与决策(第二版)第七章图及网络概述7.1 图的基本

11、概念7.2 最短路问题7.3 网络最大流问题7.4 最小费用网络最大流问题第七章 图及网络概述数据、模型与决策(第二版)7.3 网络最大流问题7.3.1 网络最大流问题的概述7.3.2 寻找网络最大流的FordFulkerson标号法第七章 图及网络概述数据、模型与决策(第二版)7.3.1 网络最大流问题的概述在图7-8所示网络中，每条弧旁的数字即为该弧的容量cij，弧的方向就是允许流的方向。现在，要把一批货物从起点v1运到终点v7去，每条弧上通过的货物总量不能超过这条弧的容量。问：如何安排运输，使得从起点v1运到终点v6的总运量达到最大？第七章 图及网络概述数据、模型与决策(第二版)第七章

12、图及网络概述数据、模型与决策(第二版)网络：一般地，对于一个容量网络D，如果点集V中有一发点记为vs，还有一收点记为vt，其余均为中间点，且对弧集A的每条弧均赋权cij 0，则称这样的容量网络D为带收发点的容量网络，简称网络。第七章 图及网络概述数据、模型与决策(第二版)把通过弧(vi,vj)的物运量fij称为通过弧(vi,vj)的流量，所有弧上流量的集F=fij称为该网络D的一个流。第七章 图及网络概述数据、模型与决策(第二版)两个约束条件：容量约束节点流量平衡条件第七章 图及网络概述数据、模型与决策(第二版)平衡条件表示了网络中的流量必须满足守恒条件，对收发点来说：发点的总流出量=收点的总

13、流入量：对中间点v1、v2、v3、v4来说：中间点的总流入量=总流出量。对一个给定的容量网络，凡是满足以上两个条件的网络流fij都称为可行流。第七章 图及网络概述数据、模型与决策(第二版)设网络D(V，A，C)中，有一可行流f=fij，按每条弧上流量的多少，可将弧分为四种类型：饱和弧fijcij 非饱和弧fijcij 零流弧fij=0 非零流弧fij0第七章 图及网络概述数据、模型与决策(第二版)设是网络D中从vs到vt的一条链，沿此方向上的各弧可分为两类，一类是与链的方向一致的弧称为正向弧，正向弧的全体记为 ，另一类是与链的方向相反的弧，称为反向弧，反向弧的全体记为 。增广链：对于可行流f，

14、是一条从vs到vt的链，如果 中的每条弧均为非饱和弧，且 中的每条弧均为非零流弧，则称链是关于f的增广链。第七章 图及网络概述数据、模型与决策(第二版)截集：截集就是研究网络流“瓶颈”的一种工具。截量：截集中所有弧的容量之和称为该截集的截量。最小截量最大流定理：最小截量最大流定理：任一网络D中，最大流的流量等于最小截集的截量。第七章 图及网络概述数据、模型与决策(第二版)判断一个可行流是否最大流一是能否找出Vs到Vt的增广链，若能，则说明f不是最大流；否则f就是最大流。二是看v(f)是否等于最小截量。若等，则f就是最大流，否则就不是最大流。第七章 图及网络概述数据、模型与决策(第二版)7.3.

15、2 寻找网络最大流的Ford-Fulkerson标号法标号法标号法的基本思想：从一个可行流f出发，由发点vs开始，对网络D中的每个顶点进行标号，如vt得到标号，这时可用反向追踪法在网络中找出一条从s到t 的由标号点及相应的弧连接而成的增广链。若无，则f为所求的最大流；若有，则在增广链上进行调整，改变流量，得一新的可行流f，继续寻找相应于该可行流的增广链。第七章 图及网络概述数据、模型与决策(第二版)试用Ford-Fulkerson标号法求图7-11所示的网络最大流。第七章 图及网络概述数据、模型与决策(第二版)第七章图及网络概述7.1 图的基本概念7.2 最短路问题7.3 网络最大流问题7.4

16、 最小费用网络最大流问题第七章 图及网络概述数据、模型与决策(第二版)7.4 最小费用网络最大流问题7.4.1 最小费用最大流算法7.4.2 应用举例第七章 图及网络概述数据、模型与决策(第二版)7.4.1 最小费用最大流算法在给定网络D(V，A，C)中，对每条弧（vi，vj）A，除已给弧容量 外，还给出单位流量的费用 。是D中的可行流，其总费用为 。因此，把求可行流量为，且使总费用b(f)最小的问题称为最小费用流问题，其数学模型为：求使b(f)为最小且流量v(f)为最大的问题称为最小费用最大流问题。第七章 图及网络概述数据、模型与决策(第二版)基本思想：从零流（f0=0）的费用有向图D(f0

17、)开始，用求最短路的方法求出由vs到vt的最小费用链 ，并对 按上节中Ford-Fulkerson标号法的调整办法进行流量的调整，所以，新的可行流f1必是最小费用可行流。如果，则计算终止。否则，重新构造关于f的费用有向图D(f1)，继续在D(f1)上求出由vs到vt的最小费用链 ，并在 上进行流量的调整，如此下去，直到求出流量为v的可行流f为止。如果v是最大流的流量，则此最小费用流就是最小费用最大流。第七章 图及网络概述数据、模型与决策(第二版)7.4.2 应用举例已知一交通网如图7-13，要把10单位的货物从vs运到各点去，弧旁的数字（cij,bij）,cij代表每条线路的最大运输能力，bij代表通过该线路单位物资的运价。考虑：如何调运能使运费最省？第七章 图及网络概述数据、模型与决策(第二版)第七章 图及网络概述数据、模型与决策(第二版)第七章 图及网络概述数据、模型与决策(第二版)第七章 图及网络概述数据、模型与决策(第二版)第七章 图及网络概述数据、模型与决策(第二版)第七章 图及网络概述数据、模型与决策(第二版)第七章 图及网络概述数据、模型与决策(第二版)