运筹学8图与网络分析.ppt

1、第八章 图与网络分析,主要内容： 8.1 图与网络的基本知识 8.2 树和最小支撑树 8.3 最短路问题 8.4 最大流问题 8.5 最小费用最大流问题 8.6 中国邮递员问题,目的要求： 1正确理解图的基本概念与基本定理，掌握用图形与矩阵表示图的方法； 2理解树与最小支撑树的概念及求最小树的算法，理解欧拉图与最优投递路线问题的解法； 3熟练掌握赋权的最短通路问题及其Dijkstra算法，会用逐次逼近法求解带有负权的最短路问题。 4理解最大流问题，掌握求最大流的标号算法。会求网络系统的最大流和最小费用最大流。,重点：图的基本概念与基本定理；树和最小支撑树；赋权的最短通路问题的求法； 网络系统的

2、最大流和最小费用最大流。,8.1 图与网络的基本知识,图论是应用非常广泛的运筹学分支，广泛应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以用图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。,回本章目录,随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人

3、员和经营管理人员的重视。,关于图的第一篇论文是瑞士数学家欧拉(E. Euler)在1736年发表的解决“哥尼斯堡” 七桥难题的论文； 德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，（见图8.1 a）当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题抽象成图8.1b所示图形的一笔画问题。,哥尼斯堡七桥问题,图 8.1 a,A,B,C,D,哥尼斯堡七桥问题可简化为以下图形,其中的四个顶点都是奇顶点,A,B,C,D,图8.1 b,即能否从

4、某一点开始不重复地一笔画出这个图形， 最终回到原点。欧拉在他的论文中证明了这是不可 能的，因为这个图形中每一个顶点都与奇数条边相 连接，不可能将它一笔画出，这就是古典图论中的 第一个著名问题。,一、图与网络的基本概念,在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。,例8.1 图8.2是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。,图8.2,例8.2 有六支球队进行足球比赛，我们分别用点v1 ，v6表示这六支球队，它们之间的比赛情况，也可以

5、用图反映出来，已知v1队战胜v2 队，v2 队战胜v3 队，v3 队战胜v5队，如此等等。这个胜负情况，可以用图8.3所示的有向图反映出来,图8.3,从以上的几个例子可以看出，我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象，用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显得并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。,综上所述，图论中的图是由点和点与点之间的线所组成的。通常，我们把点与点之间不带箭头的线叫做边，带箭头的线叫做弧

6、。 如果一个图是由点和边所构成的，称为无向图，记作G=(V，E)，其中V表示图G 中的点集合，E表示图G中的边集合。连接点vi , vjV 的边记作vi , vj，或者vj , vi。 如果一个图是由点和弧所构成的，那么称为它为有向图，记作D=(V, A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi 指向vj 的弧，记作(vi , vj)。,例如.图8.4是一个无向图G=（V，E）， 其中V=v1 , v2 , v3 , v4 E=v1 , v2,v2 ,v1,v2 ,v3, v3 ,v4,v1 ,v4, v2 ,v4, v3 ,v3,图8.4,图8.5 是一个有向图D

7、=（V，A） 其中V=v1 ,v2 ,v3 ,v4 ,v5 ,v6 ,v7 A=(v1,v2),(v1,v3),(v3 ,v2)(v3 ,v4),(v2 ,v4),(v4 ,v5), (v4 ,v6),(v5 ,v3),(v5 ,v4), (v5 ,v6),(v6 ,v7),图8.5,下面介绍一些常用的名词： 一个无向图G或有向图D中的点数,记作P(G)或P(D),简记作P,边数或者弧数,记作q(G)或者q(D),简记作q 。 如果边vi ,vjE ,那么称vi , vj 是边的端点，或者vi ,vj是相邻的。如果一个图G中，一条边的两个端点是相同的,那么称为这条边是环，如图8.4中的边v3

8、,v3是环。如果两个端点之间有两条以上的边，那么称为它们为多重边，如图8.4中的边v1 ,v2 ,v2 ,v1。一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。,以点v为端点的边的个数称为点v的度，记作d(v),如图84中d(v1)=3， d(v2 )=4,d(v3 )=4,d(v4 )=3。 度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。 端点的度 d(v)：点 v 作为端点的边的个数 奇点：d(v)=奇数；,偶点：d(v) = 偶数； 悬挂点：d(v)=1； 悬挂边：与悬挂点连接的边； 孤立点：d(v)=0

9、； 空图：E = ，无边图,V=v1 , v2 , v3 , v4 , v5 ,v6 , v7 ,d(v1)=3 ; d(v2)=5 ;,d(v3)=4 ; d(v4)=4 ;,d(v5)=1 ; d(v6)=3;,d(v7)=0,其中 v5 为悬挂点， v7 为孤立点。,定理8.1 所有顶点度数之和等于所有边数的2倍。 证明：因为在计算各个点的度时，每条边被它的两个端点个用了一次。,定理8.2 在任一图中，奇点的个数必为偶数。 证明：设 V1，V2 分别是图G中奇点和偶点的 集合，由定理8.1 ，有,因为 是偶数， 也是偶数，因此,也必是偶数，从而V1 中的点数是偶数。,二、图的连通性 链：

10、由两两相邻的点及其相关联的边构成的点边序列。 如:v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,vn-1 , en ， vn ; v0 ，vn分别为链的起点和终点 。记作（ v0 ,v1 , v2， ,v3 , , vn-1 , vn ） 简单链：链中所含的边均不相同； 初等链：链中所含的点均不相同, 也称通路；,圈：若 v0 vn 则称该链为开链，否则称 为闭链或回路或圈；,简单圈：如果在一个圈中所含的边均不相同初等圈：除起点和终点外链中所含的点均 不相同的圈； 连通图：图中任意两点之间均 至少有一条通路，否则 称为不连通图。,初等链: (v1 , v2 , v3 , v6 , v7

11、 , v5 ),初等圈： (v1 , v2 , v3 , v5 , v4 , v1 ),简单圈： (v4 , v1 , v2 , v3 , v5 , v7 , v6 ,v3 , v4 ),简单链：(v1 , v2 , v3 , v4 ,v5 , v3 ),以后除特别声明，均指初等链和初等圈。,连通图,子图定义：如果 V2 V1 , E2 E1 称 G2 是 G1 的子图； 真子图：如果 V2 V1 , E2 E1 称 G2 是 G1 的真子图； 部分图：如果 V2 = V1 , E2 E1 称 G2 是 G1 的部分图或支撑子图； 导出子图： 如果V2 V1, E2=vi,vjvi,vjV2,

12、称 G2 是 G1 中由V2 导出的导出子图。,设 G1= V1 , E1 ,G2= V2 ,E2 ,G1,G2真子图,G3子图部分图,G4导出子图,G5生成树,G6G5余树,有向图：关联边有方向 弧：有向图的边 a=(u ,v),起点u ,终点v； 路：若有从 u 到 v 不考虑方向的链,且 各方向一致,则称之为从u到v 的路； 初等路: 各顶点都不相同的路； 初等回路:u = v 的初等路; 连通图： 若不考虑方向 是无向连通图; 强连通图：任两点有路;,三、图的矩阵表示,图的图形表示法在较为简单的情况下由于比较直观，所以有一定的优越性，但对于比较复杂的图这种表示方法就不太方便了。故目前一

13、般多用矩阵方法表示图。由于这种方法表示简单，使用方便，目前应用较为普遍。更重要的是，它把图的问题变成为数学计算问题，因而对图的研究可借助于计算机来实现。图的矩阵表示法有权矩阵、邻接矩阵、关联矩阵、回路矩阵等，这里仅介绍其中的两种。,定义：对于网络（赋权图）G=（V，E），其中边 有权 ，构造矩阵 ，其中： 称矩阵A为网络G的权矩阵。,定义 设图G=（V，E）中顶点的个数为n，构造一个矩阵 ，其中： 称矩阵A为网络G的邻接矩阵。,例 如图所示，其权矩阵为：,邻接矩阵为： 因为G是无向图，所以邻接矩阵是对称的。,8.2 树和最小支撑树,一、树的概念和性质 在各种各样的图中，有一类图是十分简单又非常

14、具有应用价值的图，这就是树。 例8.3 已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。,回本章目录,如果用六个点v1v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。表示任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图8.8是一个不含圈的连通图，代表了一个电话线网。,图8.8,v6,v3,v4,v2,v5,v1,定义8.1 一个无圈的连通图叫做树。 下面介绍树的一些重要性质： 定理8.3

15、 设图G=（V，E）是一个树，P(G) 2 (P(G)为无向图点数)，图G中至少有两个悬挂点。 定理8.4 图G=（V，E）是一个树的充要条件是G 不含圈，并且有且仅有P-1条边。 定理8.5 图G=（V，E）是一个树的充要条件是G是连通图，并且有且仅有 p1 条边。 定理8.6 图G是一个树的充分必要条件是任意两个顶点之间有且仅有一条链。,从以上定理，不难得出以下结论： （1）从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。 （2）在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。,二.支撑树,定义8.2 设图K=( V , EI )

16、是图G=(V , E )的,一支撑子图，如果图K=(V,EI) 是一个树,那么称K 是G 的一个支撑树。 例如,图8.10b 是图8.10a 的一个支撑树,图8.10,显然,如果图K=(V,EI)是图G=(V,E)的一个支撑树,那么K 的边数是p(G)-1，G中不属于支撑树K 的边数是q(G)-p(G)+1。 定理8.7 一个图G有支撑树的充要条件是G 是连通图。 证明：充分性: 设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个支撑树。若G含圈，则任取G的,一个圈，从该圈中任意去掉一条边，得到图G的一支撑子图G1。若G1不含圈，则G1是G的一个支撑树。若G1仍然含圈，则任

17、取G1的一个圈，再从圈中任意去掉一条边，得到图G的一支撑子图G2。依此类推，可以得到图G的一个支撑子图GK，且不含圈，从而GK是一个支撑树。,定理8.7充分性的证明，提供了一个寻找连通图支撑树的方法叫做“破圈法”。就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个支撑树。 例8.4 用破圈法求出图8-11的一个支撑树。,图8-11,取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3 。在剩下的图中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4 。再从圈（v3,v4 v5,v3）中去掉边e6 。再从圈(v1,v2,v5,v4,v3,v1

18、）中去掉边e7， 这样，剩下的图不含圈，于是得到一个 支撑树，如图8.12所示。,图8.12,三.最小支撑树问题 定义8.3 如果图G=（V，E），对于G中的每一条边vi ,vj，相应地有一个数Wij ，那么称这样的图G为赋权图，Wij称为边vi ,vj的权。这里所指的权，是具有广义的数量值。根据实际研究问题的不同，可以具有不同的含义。例如长度，费用、流量等等。 赋权图在图论及实际应用方面有着重要的地位，被广泛应用于现代科学管理和工程技术等领域，最小支撑树问题就是赋权图的最优化问题之一。,设G=（V，E）是一个连通图，G的每一条vi ,vj对应一个非负的权Wij。 定义8.4 如果图T=（V，

19、EI）是图G的一个支撑树，那么称EI上所有边的权的和为支撑树T的权，记作S(T)。 如果图G的支撑树T*的权S(T*)，在G 的所有支撑树T中的权最小，即S(T*)=minTS(T)，那么称T*是G的最小支撑树。,如前所述，在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，一个问题的解决可以归结为最小支撑树问题。 再如，城市间交通线的建造等，都可以归结为这一类问题。,下面介绍寻求最小支撑树的方法-破圈法。 在给定的连通图中任取一个圈，去掉权最大的一条边，如果有两条以上权最大的边，则任意,去掉一条。在剩下的图中，重复以上步骤，直到得到一个不含圈的连通图为止，这个图便是最小支撑树。

20、 例8.5 某六个城市之间的道路网如图8.13a 所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。,图8.13a,图8.13b,解：这个问题的解决就是要求所示赋权图8.13a中的最小支撑树。用破圈法求解。任取一个圈，例如（ v1 ,v2 ,v3 ,v1 ），去掉这个圈中权最大的边v1 ,v3。再取一个圈（ v3 , v5 , v2 ,v3），去掉边v2 , v5。再取一个圈（ v3 , v5 ,v4 , v2 ,v3），去掉边v3 ,v5。再取一个圈（v5 ,v6 ,v4 ,v5），这个圈中，有两条权最大的边v5 ,v6和v4 ,v6。任意去掉其中的一条，例如v5

21、, v6。这时得到一个,不含圈的图，如图8.13b 所示，即是最小支撑树。 关于破圈法正确性的证明略去。,例 用破圈法求出下图中的最小支撑树,破圈法和生长法两个方法：,（1）在网络图中寻找一个圈。若不存在圈，则已经得到最小支短树或网络不存在最小支撑树；,（2）去掉该圈中权数最大的边；,反复重复 两步，直到最小支撑树。,1.破圈法,从网络图中任意节点开始寻找与该节点关联的权数最小的边，得到另一节点后，再从这个新节点开始寻找与该节点关联的权数最小的另一边。注意寻找过程中，节点不得重复，即在找最小权数边时不考虑已选过的边,反复进行，直到得到最小支撑树或证明网络不存在最小支撑树。,2.成长法(避圈法)

22、,例 用成长法求出下图中的最小支撑树（最短 树）,一、引言 最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。,8. 3最短路问题,回本章目录,例86 如图8.14所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交通网到达v8，要寻求是总路程最短的线路。,图8.14,1,从v1到v8 的路线是很多的。比如从v1出发，经过v2 , v5到达v8 或者从v1出发，经过v4 ，v6 ，v7 到达v8 等等。但不同

23、的路线，经过的总长度是不同的。例如，按照第一个线路，总长度是6+1+6=13单位，按照第二个路线，总长度是1+10+2+4=17单位。 从这个例子中，可以给出一般意义下的最短路问题。设一个赋权有向图D=（V，A），,对于每一个弧a =（vi ,vj），相应地有一个权wij。vs ,vt是D中的两个顶点，P 是D中从vs到vt 的任意一条路，定义路的权是P 中所有弧的权的和，记作S(p)。最短路问题就是要在所有从vs到vt的路P中，寻找一个权最小的路P0 ，亦即S(P0)=minS(p)。P0 叫做从vs到vt的最短路。P0的权S(P0) 叫做从vs到vt 的距离，记作d（vs，vt）。由于D是

24、有向图，很明显d（vs，vt）与d（vt，vs）一般不相等。,求解最短路的方法很多，该问题完全可以看成一个网络问题，可以利用后面的最小费用流算法可以求解，也可以用前面介绍的动态规划方法求解。但计算效率最高的还是图论的方法。下面介绍几种算法。,二.狄克斯屈拉(Dijkstra)算法 下面介绍在一个赋权有向图中寻求最短路的方法Dijkstra算法，它是在1959年提出来的。目前公认，在所有的权wij 0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。,Dijkstra算法的基本思想是从vs出发，逐步向外寻找最短路。在运算过程中，与每

25、个点对应，记录一个数，叫做一个点的标号。它或者表示从vs到该点的最短路权(叫做P 标号, permanet label），或者表示从vs 到该点最短路权的上界（叫做T 标号, tentative label ）。算法的每一步是去修改T标号，把某一个具有T 标号的点改变为具有P 标号的点，使图D中具有P 标号的顶点多一个。这样，至多经过n-1 步，就可求出从vs 到各点vj 及终点vt最短路。,算法步骤：,给始点vs以P标号 ，这表示从vs到 vs的最短距离为0，其余节点均给T标号， 。 2. 设节点vi为刚得到P标号的点，考虑点vj，其中 ，且vj为T标号。对vj的T标号进行如下修改：,3.比

26、较所有具有T标号的节点，把最小者改为P标号，即： 当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。,例一、 用Dijkstra算法求下图从v1到v6的最短路。,解 （1）首先给v1以P标号，给其余所有点T标号。,（2）,（3）,（4）,（5）,（6）,（7）,（8）,（9）,（10）,反向追踪得v1到v6的最短路为：,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求从1到8的最短路径,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,

27、w1=0,min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1 X=1,4, p4=1,p4=1,p1=0,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2 X=1,2,4, p2=2,p1=0,p4=1,p2=2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,min c13,c23,c25,c47=min 0+3,2+6,2+5,

28、1+2=min 3,8,7,3=3 X=1,2,4,6, p6=3,p2=2,p4=1,p1=0,p6=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 X=1,2,4,6,7, p7=3,p2=2,p4=1,p1=0,p6=3,p7=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min c23,c25,c75,c78=min 2+6,2+5,3

29、+3,3+8=min 8,7,6,11=6 X=1,2,4,5,6,7, p5=6,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8 X=1,2,3,4,5,6,7, p3=8,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,

30、4,6,7,min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10 X=1,2,3,4,5,6,7,8, p8=10,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,8,1到8的最短路径为1，4，7，5，8，长度为10。,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,求从V1 到 V8 的最短路线。,由此看到，此方法不仅求出了从V1 到 V8 的最短路长，同时也求出

31、了从V1 到 任意一点 的最短路长。将从V1 到 任一点的最短路权标在图上，即可求出从V1 到 任一点的最短路线。本例中V1 到 V8 的最短路线是： v1 v2 v5 v6 v8,例8.6,三、逐次逼近法,前面已经说过，Dijkstra算法只能计算非负权的情况，本算法可用于网络中带有负权的边时，求某指定点到网络中任意点的最短距离。,算法的基本思路与步骤：首先设任一点vi到任一点vj都有一条弧。如果在图G中， ，则添加弧 ，并令 。显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v

32、1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程：,利用如下的递推公式： 开始时，令 即用v1到vj的直接距离做初始解。 从第二步起，使用递推公式： 求 ，当进行到第 t 步，若出现 则停止计算， 即为v1到各点的最短路长。,例二、,求图中v1到 各点的最短路,可以看出，当t =4时，有： ，因此，表中的最后一列，就是从v1到v1，v2 .，v8的最短路权(表中没有数字的空格表示+) 。为了求出从v1到各个点的最短路，一般采用反向追踪的方法：,如果已知P1j,那么寻求一个点vk,使得P1k+Lkj=P1j,然后记录下(vk , vj).再看P1k,寻求一个点vi，使得P1i+

33、Lik=P1k，依次类推，一直到达v1为止。这样，从v1到vj的最短路是（v1 , ，vi，vk，vj）。 在本例中，由表可知，P18=6。由于P16+L68=(-1)+7，记录下v6。由于P13+L36=P16,记录下v3。由于P11+L13=P13,于是，从v1到v8的最短路是(v1，v3，v6，v8)。,对于递推公式中的 的实际意义为：从v1到vj 点，最多含有K-1中间点的最短路权，所以在含有n个点的图中，如果不含有总权小于零的回路，求从v1到任一点的最短路权，用上述算法最多经过n-1次迭代必定收敛。如果图中含有总权小于零的回路，则可能某些最短路权没有下界。,（0，0）,（ v3 ，-

34、5）,（ v1 ，-2）,（ v3 ，-7）,（ v2 ，-3）,（ v4 ，-5）,（ v3 ，-1）,（ v6 ，6）,例三、求：5年内，哪些年初购置新设备，使5年内的总费用最小。 解：（1）分析：可行的购置方案（更新计划）是很多的， 如： 1） 每年购置一台新的，则对应的费用为： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年购置新的，一直用到第五年年底，则总费用为： 11+5+6+8+11+18 = 59 显然不同的方案对应不同的费用。,（2）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。 求解步骤： 1）画赋权有向图： 设 Vi 表示

35、第i年初，(Vi ,Vj )表示第i 年初购买新设备用到第j年初（j-1年底），而Wi j 表示相应费用，则5年的一个更新计划相当于从V1 到V6的一条路。 2）求解 （标号法）,W12 =11+5=16 W13 =11+5+6=22 W14 =11+5+6+8=30 W15 =11+5+6+8+11=41 W16 =11+5+6+8+11+18=59,W23 =11+5=16 W24 =11+5+6=22 W25 =11+5+6+8=30 W26 =11+5+6+8+11=41,W45 =12+5=17 W46 =12+5+6=23 W56 =13+5=18,W34 =12+5=17 W35

36、 =12+5+6=23 W36 =12+5+6+8=31,例四、 某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。,28,v1,v2,v3,v4,v5,v6,23,25,26,29,30,42,60,85,32,44,62,33,45,30,8.4 最大流问题,在许多实际的网络系统中都

37、存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。,回本章目录,图8.19是联结某个起始地vs和目的地vt的交通运输网，每一条弧vi 旁边的权cij表示这段运输线的最大通过能力，货物经过交通岗从vs运送到vt.要求指定一个运输方案，使得从vs到vt的货运量最大，这个问题就是寻求网络系统的最大流问题。,问题描述 连通网络 G(V, A) 有 m 个节点, n条弧, 弧 eij 上的流量上界为 cij, 求从起始节点 vs 到终点 vt 的最大流量。,图8.19,二

38、 基本概念 定义8.5 设一个赋权有向图D=（V,A）,在V 中指定一个发点vs和一个收点vt ,其它的点叫做中间点。对于D中的每一个弧（vi ,vj）A,都有一个权叫做弧的容量。我们把这样的图D叫做一个网络系统，简称网络，记做D=（V，A，C）。 网络D上的流，是指定义在弧集合A上的一个函数f=f(vi ,vj)=fij f(vi ,vj)=fij叫做弧(vi ,vj)上的流量。,例如图8.19就是一个网络。每一个弧旁边的权就是对应的容量（最大通过能力）cij . 图8.20表示的就是这个网络上的一个流（运输方案），每一个弧上的流量fij就是运输量。例如fs1=5 , fs2=3 , f13

39、=2 等等。 对于实际的网络系统上的流，有几个显著的特点：(1)发点的总流出量和收点的总流入量必相等。(2)每一个中间点的流入量与流出量的代数和等于零。(3)每一个弧上的流量,不能超过它的最大通过能力（即容量） 于是有：,图8.20,定义8.6 网络上的一个流f 叫做可行流，如果f 满足以下条件 （1）容量条件：对于每一个弧（vi ,vj）A,有 0 fij cij . （2）平衡条件：,对于发点vs,有,对于收点vt,有,对于中间点，有,任意一个网络上的可行流总是存在的。例如零流v(f)=0,就是满足以上条件的可行流。 网络系统中最大流问题就是在给定的网络上寻求一个可行流f,其流量v(f)达

40、到最大值。 设流f =fij是网络D上的一个可行流。我们把D中fij=cij的弧叫做饱和弧，fijcij的弧叫,其中发点的总流量（或收点的总流量） v ( f ) 叫做这个可行流的流量。,做非饱和弧，fij0的弧为非零流弧，fij=0的弧 叫做零流弧 .,在图8.20中，(v4 ,v3)是饱和弧，其他的弧是非饱和弧，并且都是非零流弧。 设是网络D中连接发点s和收点vt的一条链。定义链的方向是从s到 vt ，于是链上的弧被分为两类：一类是弧的方向与链的方向相同，叫做前向弧，前向弧的集合记做+。二类是弧的方向与链的方向相反，叫做后向弧，,后向弧的集合记做。 例如在图8.19中，在链（vs,v1,v

41、2,v3,v4,vt)中，+ = (vs,v1 ),(v1,v2),(v2,v3),(v4,vt), = (v4 ,v3).,增广链：如果链满足以下条件： 1在弧（vi ,vj）+上，有0fijcij,即+中的每一条弧是非饱和弧。 2在弧（vi,vj）上，有0fijcij,即中的每一条弧是非零流弧。,例如在图8.20中，链=（vs,v1,v2,v3,v4,vt）就是一条增广链。,定义8.8 设一个网络D=（V，A，C）。如果点集V 被分为两个非空集合v1和 ，发点vsv1,收点vt ,那么将弧集（v1 ， ）叫做是分离vs和vt的截集。,如右图，取 ， 截集 截集容量 由于V的分解方法不同，所

42、以截集就不相同，对应的截集的容量也不相同，其中容量最小的称为最小截集。,定义8.9 设一个截集（V1 , ）.将截集（V1 , ）中所有的弧的容量的和叫做截集的容量，记做 s( V1 , ) , 亦即,下面的事实是显然的：一个网络D中，任何一个可行流 f 的流量v (f ) 都小于或等于这个网络中任何一个截集(V1 , )的容量。并且，如果,网络上的一个可行流 f * 和网络中的一个截集（V1*, ）， 满足条件v*(f* )=c (V1* , ) ,那么f * 一定是D上的最大流，而 （V1*, ）一定是D的所有的截集中容量最小的一个（即最小截集）,定理8.8 网络中的一个可行流f*是最大流

43、的充分必要条件是，不存在关于f*的增广链。 定理8.9 在一个网络D中，最大流的流量等于分离vs 和vt 的最小截集的容量。,定理8.8为我们提供了一个寻求网络系统最大流的方法。亦即，如果网络D中有一个可行流 f，只要判断网络是否存在关于可行流 f 的增广链 。如果没有增广链，那么f一定是最大流。如有增广链，那么可以按照定理 8.9中必要性，不断改进和增大可行流 f 的流量，最终可以得到网络中的一个最大流。,三标号法 从网络中的一个可行流f 出发（如果D中没有 f，可以令f 是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。 下面用给顶点标号的方法来定义V1*.在标号过

44、程中，有标号的顶点是V1*中的点，没有标号的点不是V1*中的点。如果vt有了标号，表示存在一条关于f 的增广链。如果标号过程无法进行下去，并且vt未被标号，则表示不存在关于f 的增广链。这样，就得到了网络中的一个最大流和最小截集。,1 标号过程 标号过程开始，先给vs 标号（0，+）。 取一个已标号的点vi，对于vi一切未标号的邻接点vj 按下列规则处理： （1）如果在弧（vi ,vj）上，fijcij,那么给vj 标号（vi ,l(vj) ）.其中 l(vj) = minl(vi),cij fij.,（2）如果在弧（vj ,vi）上，fji 0,那么给vj标号（-vi , l(vj)）.其中

45、l (vj)=min l(vi), fji . 重复以上步骤，直到vt 被标号或标号过程无法进行下去，则标号法结束。这时的可行流就是最大流。,2.调整过程 设是一条从vs到vt的可增广链,的前向边和后向边分别用+和-表示。取调整量 =l(vt)，即为vt的第二个标号。,但是，如果vt 被标上号，表示得到一条增广链，转入下一步调整过程。,其它不变,令 再去掉所有的标号，对新的可行流f =f ij,重新进行标号过程，直到找到网络D的最大流为止。,例8.8 求图8.21的网络最大流，弧旁的权 数表示（cij , fij）。,图8 20 例8 8网络图,解：用标号法。 1.标号过程。 （1）首先给vs

46、标号（0，+） （2）看vs : 在弧(vs ,v2)上,fs2=cs3=3 , 不 具备标号条件。在弧(vs ,v1)上,fs1=1 0 ,故给 v2标号（-v1 , l(v2)）,其中 l(v2)=minl(v1) , f21 = min 4 , 1 = 1.,图8 21 例8 8网络图,(0,+),(vs , 4),(v1 , 1),(v2 , 1),(-v2 , 1),(v3 , 1),（4）看v2:在弧（v2 ,v4）上，f24 =3 0 ,故给v3标号（-v2，l(v3) , 其中 l (l(v3 )= minl(v2) , f32 = min1 , 1 =1。 （5）在v3 ,v

47、4中任意选一个，比如v3 ,在弧（v3 , vt）上，f3t =1 c3t =2,故给vt标号(v3 ,l(vt),其中l(vt)=minl(v3),(c3t-f3t)=min1,1=1.因为vt被标上号，根据标号法，转入调整过程。,2.调整过程 从vt开始，按照标号点的第一个标号，用反向追踪的方法，找出一条从vs到vt的增广链，如图822中双箭线所示。不难看出,+=(vs ,v1),(v3 ,vt), =(v2 ,v1) , (v3 ,v2), 取=1，在上调整f ，得到,图8 22 例8 8网络图,(5 , 2),(1 , 0),(1 , 0),(2 , 2),(cij , fij),调整

48、后的可行流f *，如图8.22所示，再对这个可行流从新进行标号过程，寻找增广链。 首先给vs标号（0，+），看vs,给v1标号（vs ,3）。看v1,在弧（v1 ,v3）上，f13=c13,弧（v2 ,v1）上，f21=0,均不符合条件。因此标号过程无法进行下去，不存在从vS到vt的增广链，算法结束。,这时，网络中的可行流f * 即是最大流，最大流的流量v(f*)= fs1+fs2=5.同时，也找出D的最小截集（V1， ），其中V1是标号的集合， 是未标号的集合。,(0 , +),(vs , 3),图823 例8 8网络图,例89 求图8 24所示网络的最大流,图 824 例89网络图,解：给

49、定初始可行流为全零流，即 f （0） = 0,给vs 标号（0，+），检查 vs ： 给 v1 标号 (vs ,4) , 给 v2 标号(vs , 3) , 给 v3 标号(vs , 10) ,(0 , +),(vs , 4),(vs , 3),(vs , 10),检查 v1 ：给 v4 标号(v1 , 1) ，检查完毕；,(v1 , 1),检查 v2 ：给 v5 标号(v2 , 3) ，检查完毕；,(v2 , 3),检查 v5 ：给 vt 标号(v5 , 3) ，检查完毕；,(v5 , 3),因为终点 vt 已标号，故找出一条从vs到vt的增广链： vs v2 v5 vt . 取 = 3,(

50、vs , 4),(v1 , 3),(vs , 10),(v1 , 1),(v2 , 2),(0 , +),(v5 , 2),(vs , 2),(v3 , 3),(vs , 10),(v2 , 3),(v3, 4),(0 , +),(v4 , 3),(0 , +),(vs , 2),(vs , 10),(v3, 4),(v5, 2),(v5, 3),(0 , +),(vs , 2),(vs , 4),(v1 , 1),(v1 , 1),(v4 , 1),(0 , +),(vs , 4),(vs , 1),(v3 , 1),(v5 , 1),(v4 , 1),(0 , +),(vs , 1),(v

51、s , 3),(v1 , 1),(v2 , 1),(v4 , 1),(0 , +),(vs , 3),首先给vs标号（0，+），看vs,给v3标号（vs ,3）。看v3,在弧（v3 ,v2）上，f32=c32,弧（v3 ,v5）上，f35= c35,均不符合条件。因此标号过程无法进行下去，不存在从vS到vt的增广链，算法结束。最大流量 f * = 14 。,8.5 最小费用最大流问题,在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类

52、问题。,回本章目录,我们首先考察，在一个网络D中，当沿可行流 f 的一条增广链，以调整量=1改进f ，得到的新可行流f 的流量，有 v(f )=,设一个网络D=（V，A，C），对于每一个弧(vi ,vj )A ,给定一个单位流量的费用bij 0 ，网络系统的最小费用最大流问题，是指要寻求一个最大流 f ，并且流的总费用 达到最小。,=v(f )+1，而此时总费用b(f )比b(f)增加了,结论：如果可行流 f 在流量为v(f )的所有可行流中的费用最小，并且 是关于f 的所有增广链中的费用最小的增广链，那么沿增广链,我们将 叫做这条增广链的费用。,调整可行流f，得到的新可行流f ，也是流量为v

53、(f)的所有可行流中的最小费用流。依次类推，当 f 是最大流时，就是所要求的最小费用最大流。,显然，零流f =0是流量为0的最小费用流。一般地，寻求最小费用流，总可以从零流f =0开始。下面的问题是：如果已知f 是流量为v(f)的最小费用流，那么就要去寻找关于f 的最小费用增广链。,对此，重新构造一个赋权有向图 M( f )，其顶点是原网络D的顶点，而将D中的每一条弧 ( vi , vj )变成两个相反方向的弧（vi , vj）和(vj , vi)，并且定义M ( f )中弧的权wij为：,并且将权为+的弧从 M( f ) 中略去。,这样，在网络D中寻找关于f 的最小费用增广链就等于价于在M(

54、f )中寻求从vs 到vt 的最短路。 算法开始，取零流f (0) =0.一般地，如果在第K-1步得到最小费用流f (K-1),则构造图M(f (k-1)。 在图M(f (k-1)中，寻求从vs到vt的最短路。如果存在最短路，则f (k-1)就是最小费用最大流。如果存在最短路，则在原网络D中得到相对应（一一对应）的增广链0,在增广链上对f (k1)进行调整，取调整量,令：,得到一个新的可行流f(k)，在对f(k)重复以上的步骤，直到D中找不到相对应的增广链时为止。,例8.9 求图8-24 所示网络中的最小费用最大流，弧旁的权是（bij , cij）.,图 8-24,解：（1）取初始可行流为零流f (0)=0,构造赋权有向图M(f(0),求出从vs到vt的最短路(vs ,v2 ,v1 ,vt),如图8.25a 中双箭头所示。,图 8.25 a,（2）在原网络D中，与这条最短路相对应的增广链为=（vs ,v2 ,v1 ,vt ）。 （3）在