《最大流问题》PPT课件.ppt

《《最大流问题》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《最大流问题》PPT课件.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图与网络分析图与网络分析（二）最大流问题（二）最大流问题吴海佳吴海佳勤务指挥系部队管理教研室勤务指挥系部队管理教研室最大流问题是一类应用极为广泛的问题，例如在交最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流，供水网络中通运输网络中有人流、车流、货物流，供水网络中有水流，金融系统中有现金流，通信系统中有信息有水流，金融系统中有现金流，通信系统中有信息流，管道运输中的石油流，等等。流，管道运输中的石油流，等等。2020世纪世纪5050年代福特年代福特(Ford)(Ford)、富克逊、富克逊(Fulkerson)(Fulkerson)建立建立的的“网络流理论网络流理论”

2、，是网络应用的重要组成部分。，是网络应用的重要组成部分。容量网络：容量网络：容量容量：设一个：设一个赋权有向图赋权有向图D=（V,E）,在在V中指定一个中指定一个发点发点vs和一个收点和一个收点vt,其它的点叫做中间点。对于其它的点叫做中间点。对于D中中的的每一条弧每一条弧（vi,vj）E,都有一个都有一个非负数非负数cij（即每条（即每条弧的最大可能负载），叫做弧的最大可能负载），叫做弧的容量弧的容量。容量网络容量网络：对所有的弧都给出了容量的有向网络，记对所有的弧都给出了容量的有向网络，记做做D=（V，E，C）。）。一、基本概念一、基本概念容量网络案例容量网络案例有一个管道网络，使用这个网

3、络可以把石油从采地运送到其他有一个管道网络，使用这个网络可以把石油从采地运送到其他一些点，这个网络的一部分如下图所示。由于管道的直径的变一些点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（化，它的各段管道（v vi i,v,vj j）的容量）的容量c cijij也是不一样的。也是不一样的。c cijij的单位的单位为万加仑为万加仑/小时。如果使用这个网络系统从采地小时。如果使用这个网络系统从采地 v v1 1向某地向某地 v v7 7运运送石油，问每小时最多能运送多少加仑石油？送石油，问每小时最多能运送多少加仑石油？一、基本概念一、基本概念63522241263v1v2v7

4、v4v3v6v5一、基本概念一、基本概念流与可行流：流与可行流：弧上的流弧上的流：网络中加在弧上的负载量，是指定义在：网络中加在弧上的负载量，是指定义在弧集合弧集合E上的一个函数，记为上的一个函数，记为f(vi,vj)=fij 。图上的流图上的流：加在网络中各条弧上的一组负载量（即：加在网络中各条弧上的一组负载量（即定义在弧集上的一个函数），记为定义在弧集上的一个函数），记为f=f(vi,vj)=fij。零流零流：网络上所有弧上的流均为：网络上所有弧上的流均为0，则称相应的图上，则称相应的图上的流为零流。的流为零流。一、基本概念一、基本概念流与可行流：流与可行流：可行流可行流：在容量网络上，满

5、足在容量网络上，满足容量限制条件容量限制条件和和平衡条平衡条件件的的流为可行流：流为可行流：容量限制条件：对每条弧容量限制条件：对每条弧(Vi,Vj),有有0 fij Cij 平衡条件：对中间点平衡条件：对中间点Vi,有有 fij=fki 对发、收点对发、收点Vs，Vt有有 fsj=fkt=v(f)v(f)为这个可行流的流量，即发点的净输出量或收点为这个可行流的流量，即发点的净输出量或收点的净输入量。的净输入量。所谓所谓最大流问题最大流问题就是在容量网络中，寻找流量最大就是在容量网络中，寻找流量最大的可行流。的可行流。一、基本概念一、基本概念各种弧：各种弧：对于可行流对于可行流f=fij，我们

6、把网络中使，我们把网络中使fij=cij的弧称为的弧称为饱饱和弧和弧，使，使fij0的弧称为的弧称为非零流弧非零流弧一、基本概念一、基本概念容量网络、流量网络和残余网络的关系：容量网络、流量网络和残余网络的关系：容量网络容量网络=流量网络流量网络+残余网络残余网络63522241263v1v2v7v4v3v6v5容量网络容量网络一、基本概念一、基本概念63522241263v1v2v7v4v3v6v5容量网络容量网络43502021263v1v2v7v4v3v6v520022220000v1v2v7v4v3v6v5残余网络残余网络流量网络流量网络43502021263v1v2v7v4v3v6v

7、5一、基本概念一、基本概念增广路：增广路：从残余网络中找到一条从起点到终点的链路，该链路从残余网络中找到一条从起点到终点的链路，该链路就是增广路；就是增广路；增广路的最大流量取决于组成该链路的各弧的最小容增广路的最大流量取决于组成该链路的各弧的最小容量。量。43502021263v1v2v7v4v3v6v5残余网络残余网络增广路增广路222二、最大流问题二、最大流问题寻找最大流的思路：寻找最大流的思路：定理：定理：可行流可行流f是最大流，是最大流，当且仅当当且仅当不存在从起点到终点不存在从起点到终点的关于的关于f的可增广链。的可增广链。1v1v2v4v31111二、最大流问题二、最大流问题寻找

8、最大流的思路：寻找最大流的思路：初始时，流量网络的流量为初始时，流量网络的流量为0，残余网络，残余网络=容量网络；容量网络；不断从残余网络中寻找增广路，将增广路的最大流量不断从残余网络中寻找增广路，将增广路的最大流量赋予流量网络；赋予流量网络；直至残余网络中找不到增广路，流量网络的流量最大直至残余网络中找不到增广路，流量网络的流量最大1v1v2v4v31111二、最大流问题二、最大流问题寻找最大流的思路：寻找最大流的思路：初始时，流量网络的流量为初始时，流量网络的流量为0，残余网络，残余网络=容量网络；容量网络；不断从残余网络中寻找增广路，将增广路的最大流量不断从残余网络中寻找增广路，将增广路

9、的最大流量赋予流量网络；赋予流量网络；直至残余网络中找不到增广路，流量网络的流量最大直至残余网络中找不到增广路，流量网络的流量最大1v1v2v4v31111找到找到v1-v2-v3-v4这条增广路，最这条增广路，最大流量为大流量为1；二、最大流问题二、最大流问题寻找最大流的思路：寻找最大流的思路：初始时，流量网络的流量为初始时，流量网络的流量为0，残余网络，残余网络=容量网络；容量网络；不断从残余网络中寻找增广路，将增广路的最大流量不断从残余网络中寻找增广路，将增广路的最大流量赋予流量网络；赋予流量网络；直至残余网络中找不到增广路，流量网络的流量最大直至残余网络中找不到增广路，流量网络的流量最

10、大0v1v2v4v30101找到找到v1-v2-v3-v4这条增广路，最这条增广路，最大流量为大流量为1；将该增广路最大流量赋予流量网络，将该增广路最大流量赋予流量网络，得到新的残余网络；得到新的残余网络；二、最大流问题二、最大流问题寻找最大流的思路：寻找最大流的思路：初始时，流量网络的流量为初始时，流量网络的流量为0，残余网络，残余网络=容量网络；容量网络；不断从残余网络中寻找增广路，将增广路的最大流量不断从残余网络中寻找增广路，将增广路的最大流量赋予流量网络；赋予流量网络；直至残余网络中找不到增广路，流量网络的流量最大直至残余网络中找不到增广路，流量网络的流量最大0v1v2v4v30101

11、找到找到v1-v2-v3-v4这条增广路，最这条增广路，最大流量为大流量为1；将该增广路最大流量赋予流量网络，将该增广路最大流量赋予流量网络，得到新的残余网络；得到新的残余网络；残余网络中找不到增广路了。残余网络中找不到增广路了。二、最大流问题二、最大流问题问题出在哪里？问题出在哪里？0v1v2v4v30101找到找到v1-v2-v3-v4这条增广路，最这条增广路，最大流量为大流量为1；将该增广路最大流量赋予流量网络，将该增广路最大流量赋予流量网络，得到新的残余网络；得到新的残余网络；残余网络中找不到增广路了。残余网络中找不到增广路了。0v1v2v4v31000在从在从v1-v2时，下一步有两

12、种选择，时，下一步有两种选择，需要回溯穷举所有路径，算法效率将需要回溯穷举所有路径，算法效率将很低。很低。二、最大流问题二、最大流问题反向容量方法反向容量方法通过标记反向容量，给算法留有后悔的余地；通过标记反向容量，给算法留有后悔的余地；1v1v2v4v311111/0v1v2v4v31/01/01/01/0二、最大流问题二、最大流问题反向容量方法反向容量方法在寻找到一条增广路的最大流量后，将残余网络中该在寻找到一条增广路的最大流量后，将残余网络中该增广路各弧的正向容量减去该最大流量，同时在反向增广路各弧的正向容量减去该最大流量，同时在反向容量中添加该最大流量。容量中添加该最大流量。1/0v1

13、v2v4v31/01/01/01/00/1v1v2v4v30/11/00/11/0二、最大流问题二、最大流问题反向容量方法反向容量方法当某条弧的反向容量大于零，则增广路可包含该弧的当某条弧的反向容量大于零，则增广路可包含该弧的反向弧。反向弧。寻找该增广路的最大流量，将该增广路中的正向弧中寻找该增广路的最大流量，将该增广路中的正向弧中正向容量减去该流量，同时反向容量加上该流量；将正向容量减去该流量，同时反向容量加上该流量；将该增广路中的反向弧中，反向容量减去该流量，同时该增广路中的反向弧中，反向容量减去该流量，同时正向容量加上该流量。正向容量加上该流量。0/1v1v2v4v30/11/00/11

14、/00/1v1v2v4v31/00/10/10/1二、最大流问题二、最大流问题反向容量方法反向容量方法直至找不到增广路为止。直至找不到增广路为止。0/1v1v2v4v31/00/10/10/1军事案例（军用输油管道网设计）：军事案例（军用输油管道网设计）：二、最大流问题二、最大流问题63522241263v1v2v7v4v3v6v5军事案例（军用输油管道网设计）：军事案例（军用输油管道网设计）：二、最大流问题二、最大流问题6/03/05/02/02/02/04/01/02/06/03/0v1v2v7v4v3v6v5军事案例（军用输油管道网设计）：军事案例（军用输油管道网设计）：二、最大流问题二

15、、最大流问题3/30/32/32/02/02/04/01/02/06/03/0v1v2v7v4v3v6v5军事案例（军用输油管道网设计）：军事案例（军用输油管道网设计）：二、最大流问题二、最大流问题1/50/30/50/20/22/04/01/02/06/03/0v1v2v7v4v3v6v5军事案例（军用输油管道网设计）：军事案例（军用输油管道网设计）：二、最大流问题二、最大流问题1/50/30/50/20/20/22/21/02/04/21/2v1v2v7v4v3v6v5军事案例（军用输油管道网设计）：军事案例（军用输油管道网设计）：二、最大流问题二、最大流问题1/50/30/50/20/2

16、0/21/30/12/03/31/2v1v2v7v4v3v6v5军事案例（军用输油管道网设计）：军事案例（军用输油管道网设计）：二、最大流问题二、最大流问题1/50/30/50/20/20/21/30/10/21/51/2v1v2v7v4v3v6v5军事案例（军用输油管道网设计）：军事案例（军用输油管道网设计）：二、最大流问题二、最大流问题1/50/30/50/20/20/21/30/10/21/51/2v1v2v7v4v3v6v5最大流量为？最大流量为？四、求最大流问题的实战四、求最大流问题的实战例例1：求下图所示网络中的最大流，弧旁数为求下图所示网络中的最大流，弧旁数为(3,3)v2v1v

17、4v6vsvtv3(3,0)(5,5)(3,2)(5,4)(5,2)(2,2)(4,2)(3,3)v5(2,2)(4,2)四、求最大流问题的实战四、求最大流问题的实战例例1：求下图所示网络中的最大流，弧旁数为求下图所示网络中的最大流，弧旁数为(3,3)v2v1v4v6vsvtv3(3,0)(5,5)(3,2)(5,4)(5,2)(2,2)(4,2)(3,3)v5(2,2)(4,2)0/3v2v1v4v6vsvtv33/00/51/21/43/20/22/20/3v50/22/2四、求最大流问题的实战四、求最大流问题的实战例例2：求如图所示的网络的最大流。求如图所示的网络的最大流。(5,5)vsv1vtv2v3 (6,4)(3,2)v4 (2,2)(5,4)(6,6)(8,6)(4,4)(2,0)(3,3)(2,0)(3,3)v5四、求最大流问题的实战四、求最大流问题的实战例例3：求下图所示网络中的最大流。求下图所示网络中的最大流。6vsv1vtv2v3 10 6v4 5 1 7 69 3 5四、求最大流问题的实战四、求最大流问题的实战例例4：求下图所示网络中的最大流。求下图所示网络中的最大流。63522241263v1v2v7v4v3v6v5