《教案图与网络之二》PPT课件

运筹学,讲课教师：汤建影,南京航空航天大学经济与管理学院,第四章网络分析,4.1网络分析中的常用名词4.2最小生成树问题4.3最短路问题4.4最大流问题4.5最小费用流问题4.6中国邮递员问题4.7网络计划技术,第四节最大流问题,引言网络流的基本概念求解网络最大流的基本原理寻找网络最大流的标号法确定网络中最大流的方法,引言,网络中的流量，称为网络流，如公路系统中的车辆流，控制系统中的信息流，金融系统中的现金流等设产地与销地之间具有一个交通网，图中每一条弧代表从到的运输线，产品经这条弧由运到，弧旁的数字表示这条运输线的最大通过能力。现要求制定一个运输方案，使从运到的产品数量最多。,一、网络流的基本概念,流量与容量给定一个有向图D=(V,A)，在V中指定一点，称为发点(记为)，同时指定另外一点，称为收点(记为)，其余的点称为中间点。对于每一个弧，对应有一个或简写为，称为弧的容量。我们把这样的一个有向图D称为一个网络，记作,容量是弧最大允许流通量流量可看作是某时间内通过弧的物质的数量，记为，是网络流问题中的待求解变量,一、网络流的基本概念,网络流应当满足两个条件每个弧上的流量不能超过该弧的容量即容量限制条件中间点的流量为零：平衡条件定义：满足下述条件的流称为可行流(1)容量限制条件：对每一个弧(2)平衡条件：对于中间点，对于发点对于收点,一、网络流的基本概念,饱和弧与非饱和弧若给一个可行流，定义网络中（流量等于容量）成立的弧为饱和弧，的弧为非饱和弧，的弧为零流弧，的弧为非零流弧正向弧与反向弧设是网络中从始点到终点的一条链，凡与链走向一致的弧称为正向弧，逆向的称为反向弧,一、网络流的基本概念,增广链：对于一可行流，网络的一条链上的各弧满足则称该是对于该可行流的增广链增广链上的正向弧都是非饱和弧，反向弧都是非零流弧沿着增广链可以继续增加流量，增量为,当有增广链时,找出,再令,显然仍是一个可行流,与原来的可行流比较发现,网络中从st的流量增大了一个值(0).,因此,只有当网络中找不到增广链时,st的流才不可能进一步增大.,二、求解网络最大流的基本原理,数学模型,所谓求网络最大流,就是指在满足容量限制条件和中间点平衡条件下,使v(f)值达到最大.,二、求解网络最大流的基本原理,给出一初始可行流，例如。寻找增广链，若存在，则通过该增广链调整、增加网络流。若不存在增广链，则网络流不可再增加。求得最大流。定理：可行流f*为最大流的充分必要条件是当且仅当网络不存在关于f*增广链。,三、寻找网络最大流的标号法,该算法是由Ford,Fulkerson于1956年提出,故称Ford-Fulkerson标号法.算法的实质是判断网络中是否存在增广链,并将其找出来.,Ford-Fulkerson标号法,首先给发点s标号,记为,括号中第一个数字是使这个点得到标号的前一个点的代号,第二个数字表示从上一个标号点到这一标号点的流量的最大允许调整值;,找出与已标号点相邻的所有未标号点.,考虑从标号点i出发的弧(i,j),如有不给j点标号;若有则对j点标号,记为其中i表示j点的标号是从i点延伸过来的,(正向弧),考虑所有指向i的弧(h,i),如有对h点不标号,若有则对h点标号,记为(反向弧),如果某未标号点k有两个以上的相邻的标号点,为减少迭代次数,可按(1),(2)中的规则,分别计算的值,取其中最大的一个标记.,重复步骤2,可能出现两种结局:,标号过程中断,t点得不到标号,说明网络中不存在增广链,网络中给定的流就是最大流.计算结束;,t点得到标号,这时反向追踪,在网络中找到一条从s到t的由标号点和相应的弧连结而成的增广链.,修改流量:设在网络中原有的流量为f.,抹去网络图中的所有标号,重复第1到第4步,一直到在网络中找不到任何增广链,即出现第3步的结局(1)为止,这时网络中的流量为网络的最大流.,Ford-Fulkerson标号法(小节),Ford-Fulkerson标号算法，给每个节点以一对标号，第一个标号表示箭尾节点，第二个标号表示可调整量，若终点有了标号，则找到一条增广链。否则不存在增广链。调整过程：在增广链上，正向弧加上调整量，反向弧减去调整量。经过调整网络流v(f)增加一个调整量：,例4-2：第一次迭代,第二次迭代,第三次迭代：最优解,四、确定网络中最大流的方法,最大流时始节点的净流出量最大流时中介点的净流入量最小割集的容量割集割集容量最小割集最小割集最大流定理标号法求得最小割集,在下图中,括弧外的数字表示最大通过量,括弧內的数字为负载.,割集:将网络流中的发点和收点分割开,使s到t的流中断的一个弧集合.,割量:割的弧集合中各弧的容量之和,用表示,显然,一个简单的例子,例8用标号法求下面网络从s到t的最大流量,并找出该网络的最小割.,解:,先给s标号;,从s点出发的弧为,因为对暂时不标号,而,因为t点得到标号,用反向追踪法可找出从s到t的一条增广链,用红线标出;,修改增广链上的流量:其余弧上的流量不变,于是得到网络上的一个新可行流,重复上述的标号过程,转下一步;,标号中断,t点得不到标号,网络中没有增广链,该网络的可行流就是最大流,最大流量为,下面求该网络的最小割:,习题,P.266，习题4，图9-5（1）、（2）。,第六节中国邮递员问题,哥尼斯堡七桥问题与欧拉图中国邮递员问题求解中国邮递员问题的奇偶点图作业法奇偶点图作业法的改进方法,一、哥尼斯堡七桥问题与欧拉图,哥尼斯堡七桥问题欧拉图与一笔画问题,二、中国邮递员问题,1962年，管梅谷先生提出中国邮递员问题若图中无奇点，欧拉圈即为所求若图中有奇点，则奇点必为偶数，在奇点间加边（重复走），使其变为偶数而成欧拉图。中国邮递员问题是要求所加边的权之和最小。,三、求解中国邮递员问题的奇偶点图作业法,基本思想：把一个有奇点的图增加重复边后成为不含奇点的欧拉图，构造初始可行方案；寻找是否存在使重复边路长减少的改进的可行方案。,奇偶点图作业法步骤,构造初始可行方案：由于奇点个数必为偶数，因此奇点必成对出现；同时由于图是连通的，因此每一对奇点之间必存在一条链，在这条链上的各边都加上重复边而成为新图，必定是无奇点的欧拉图。寻找改进可行方案：在两奇点间检查所有链，若某链的长度小于已加重复边的长度，则在该链的每边加上重复边，去掉原重复边。重复以上步骤，直到任意两奇点间加重复边的链是最短的为止。,求解中国邮递员问题：例子,例子的初始可行解,