《最大流问题学习.pptx》由会员分享，可在线阅读，更多相关《最大流问题学习.pptx（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第八章图与网络分析 图的基本概念与模型图的基本概念与模型 树图和图的最小部分树树图和图的最小部分树 最短路问题最短路问题 网络最大流问题网络最大流问题 最小费用最大流问题最小费用最大流问题 第1页/共43页网络最大流问题网络最大流问题50年代福特（Ford）、富克逊（Fulkerson）建立的“网络流理论”，是网络应用的重要组成部分。如同我们可以把一个实际的道路地图抽象成一个如同我们可以把一个实际的道路地图抽象成一个有向图有向图来计算两点之间来计算两点之间的的最短路径最短路径，我们也可以将一个，我们也可以将一个有向图有向图看作一个看作一个流网络流网络来解决另一类型的问题。来解决另一类型的问题。
2、流网络比较适合用来流网络比较适合用来模拟液体流经管道模拟液体流经管道、电流电流在电路网络中的运动、在电路网络中的运动、信息信息网络中信息的传递等等类似的过程。网络中信息的传递等等类似的过程。第2页/共43页问题的提出问题的提出在一个在一个输油管网输油管网中，有生产石油的中，有生产石油的油井油井、储存石油的、储存石油的油库油库、转运石油的中间、转运石油的中间泵站泵站，同时，还有各种口径不同的，同时，还有各种口径不同的输油管输油管。当一个输油管网给定后，单位时间内。当一个输油管网给定后，单位时间内最多可把多少石油从油井输送到油库？具体方案如何？最多可把多少石油从油井输送到油库？具体方案如何？分析：
3、就输油管网络问题，可用就输油管网络问题，可用顶点顶点表示油井、油表示油井、油库和中间泵站，用库和中间泵站，用有向边有向边表示输油管，用有向边上表示输油管，用有向边上的的权权表示单位时间沿相应的输油管可以输送石油的表示单位时间沿相应的输油管可以输送石油的最大数量（最大数量（容量容量）。）。第3页/共43页 如果我们把图看做输油管道网，如果我们把图看做输油管道网，为起点，为起点，为终点，为终点，为中转站，为中转站，边上的数表示该管道的最边上的数表示该管道的最 大输油能力大输油能力，问应该如何安排各管道输油量，才能，问应该如何安排各管道输油量，才能 使从使从 到到 的的总输油量最大总输油量最大？问题
4、的提出问题的提出管道网络中每边的最大通过能力即管道网络中每边的最大通过能力即容量容量是有限的，实际是有限的，实际流流量量也不一定等于容量，上述问题就是要讨论如何充分利用也不一定等于容量，上述问题就是要讨论如何充分利用装置的能力，以取得最好效果（流量最大），这类问题通装置的能力，以取得最好效果（流量最大），这类问题通常称为常称为最大流问题最大流问题。vsv1v3vtv2v48799562510第4页/共43页容量容量发点（源）发点（源）收点（汇）收点（汇）中间点中间点容量网络容量网络网络有向图网络有向图D=D=（V V，A A，C C）网络上流的基本概念网络上流的基本概念vsv1v3vtv2v4
5、8799562510第5页/共43页流流vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)运输问题中，每个运输方案运输问题中，每个运输方案就是一个流就是一个流可行流可行流第6页/共43页网络最大流问题网络最大流问题且满足此为一个此为一个特殊的线性规划问题特殊的线性规划问题，将会看到利用图的特点，解决这个问题的方法，将会看到利用图的特点，解决这个问题的方法要比单纯形法较为直观方便。要比单纯形法较为直观方便。第7页/共43页设设 是是网络网络D=D=（V V，A A，C C）的）的一个可一个可行流行流（v1，v2）是饱和的是饱和的2、如果0fij0，
6、该弧是该弧是非非0弧弧；（v1，v2）是非是非0弧弧3、如果、如果fijij=0，该弧是，该弧是0 0流弧流弧；弧关于流的分类弧关于流的分类f fij ij=0 0c cij ij=5=5v1v2f fij ij00c cij ij=5=5v1v2第9页/共43页链及可增广链链及可增广链链链在最大流问题中，研究的是有向网络图。但是在求最大流的方法中，则要使在最大流问题中，研究的是有向网络图。但是在求最大流的方法中，则要使用无向网络中的链。用无向网络中的链。vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)第10页/共43页非非0流弧流弧可增广链可
7、增广链vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)非饱和弧非饱和弧第11页/共43页割集和割集的容量割集和割集的容量 设有网络设有网络D=VD=V，A A，CC，点，点v vs s与点与点v vt t的是集合的是集合V V中的任意两点，若点集中的任意两点，若点集V V被剖分被剖分成两个非空集合成两个非空集合 ，使，使，记以，记以中的点为中的点为始点始点，的的A A中弧的集合记为中弧的集合记为则称这个弧的集合则称这个弧的集合是分离点是分离点v vs s与点与点v vt t的的割集割集（又称截集）。（又称截集）。中的点为中的点为终点终点割集的容
8、量割集的容量是割集中各弧的容量之和，用是割集中各弧的容量之和，用 表示。表示。割集的容量为割集的容量为9+9=189+9=18割集割集KK割集的意义割集的意义：若把某一割集的弧从网络中丢去，则：若把某一割集的弧从网络中丢去，则从从vs到到vt便不存路，即便不存路，即割集是从割集是从vs到vt的必经之道的必经之道！这里这里(v3,v2)不属于此割集不属于此割集vsv1v3vtv2v48(8)7(5)9(4)5(5)6(1)2(0)5(4)10(8)9(9)第12页/共43页考虑考虑KK的不同画法的不同画法vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10
9、(8)割集割集割集容量割集容量由于有限网络的割集只有有限多个，则截集容量的集合由于有限网络的割集只有有限多个，则截集容量的集合是有限的实数集合，令是有限的实数集合，令称割集容量为称割集容量为C0 0的割集为的割集为D D的最小割集。（的最小割集。（瓶颈瓶颈）第13页/共43页基本定理基本定理(可行流与割集的关系可行流与割集的关系)最大流-最小割定理：构造法证明构造法证明第14页/共43页这样就得到了一个这样就得到了一个寻求最大流的方法寻求最大流的方法(算法思想算法思想)：从一个从一个可行流可行流开始，寻求关于这个可行流的开始，寻求关于这个可行流的可增可增广链广链，若存在，则可以经过调整，得到一
10、个新的，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时过程，直到不存在关于该流的可增广链时就得到了最大流。就得到了最大流。沿着这条链从沿着这条链从 vs 到到 vt 输送流，还有潜力可挖，输送流，还有潜力可挖，只需按照调整方法，就可以把流量提高，调整后只需按照调整方法，就可以把流量提高，调整后的流，在各点仍满足平衡条件及容量限制条件，的流，在各点仍满足平衡条件及容量限制条件，即仍为可行流。即仍为可行流。可增广链可增广链的实际意义的实际意义第15页/共43页求解最大流的标号算法：求解最大
11、流的标号算法：第16页/共43页b)b)接着检查与相邻接的点接着检查与相邻接的点已饱和，流量不可再增。再检查已饱和，流量不可再增。再检查，可调整量为，可调整量为4-2=2，可提供量，可提供量+，取调，取调整量整量先给标号先给标号（，+）1）寻找可增广链：寻找可增广链：第17页/共43页同理，给同理，给同理，给同理，给标号标号标号标号下对已标号点（可望调整点）接着向下检查。下对已标号点（可望调整点）接着向下检查。已饱已饱和。再检查与和。再检查与相邻接且未标号的点相邻接且未标号的点给给标号标号，其中，其中表示表示的所调整量的所调整量2来自来自，且为正，且为正向流（向前流）向流（向前流）。第18页/
12、共43页调整量为调整量为给给标号为标号为第19页/共43页可令调整量为可令调整量为给给标号为标号为表示可控量，反方向流量表示可控量，反方向流量。d)检查与检查与相邻接且未标号的点相邻接且未标号的点，。而。而对对来讲是流来讲是流入，现入，现欲增加流出量，应该压缩欲增加流出量，应该压缩的流入量，只要的流入量的流入量，只要的流入量第20页/共43页f)下面检查与下面检查与相邻接且未标号的点相邻接且未标号的点，同理，调整量：，同理，调整量：给给标号为标号为g)最后，给最后，给标号标号第21页/共43页2）调整流量：从）调整流量：从到到所画出的所画出的红线红线即为即为可增广链可增广链。沿。沿该可增广链，
13、从该可增广链，从倒推，标倒推，标“”号的在实际流量上加上号的在实际流量上加上该调整量，标该调整量，标“”符号的在实际流量上减去该调整量。完符号的在实际流量上减去该调整量。完成调整过程。成调整过程。反反向向追追踪踪第22页/共43页第23页/共43页当标到当标到时，与时，与，相邻接的点相邻接的点，都不满足标号条件，都不满足标号条件，标号无法继续，且没有完成标号。此时最大流量即为所求。标号无法继续，且没有完成标号。此时最大流量即为所求。重新开始标号，寻找可增广链。重新开始标号，寻找可增广链。第24页/共43页 网络从发点到收点的各通路中，由容量决定其通过能力，网络从发点到收点的各通路中，由容量决定
14、其通过能力，最小割最小割则是这此路中的则是这此路中的咽喉部分咽喉部分，或者叫，或者叫瓶颈瓶颈，其容量最小，它决定了整个网络的最大通过能力。要提高整个，其容量最小，它决定了整个网络的最大通过能力。要提高整个网络的运输能力，必须首先改造这个咽喉部份的通过能力。网络的运输能力，必须首先改造这个咽喉部份的通过能力。最小割的意义最小割的意义第25页/共43页 如果我们把图看做输油管道网，如果我们把图看做输油管道网，为起点，为起点，为终点，为终点，为中转站，为中转站，边上的数表示该管道的最边上的数表示该管道的最 大输油能力大输油能力，问应该如何安排各管道输油量，才能，问应该如何安排各管道输油量，才能 使从
15、使从 到到 的的总输油量最大总输油量最大？解决问题解决问题vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)第26页/共43页vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)(vs,2)(-v2,2)(v1,1)(-v3,1)(v4,1)vsv1v3vtv2v48(8)7(6)9(5)9(9)5(5)6(0)2(0)5(3)10(9)(vs,1)(-v2,1)(v1,2)KKW=f*s1+f*s2=8+6=14第27页/共43页下图中，下图中，A,B,C,D,E,FA,B,C,D,E,F分别表示陆
16、地和岛屿，分别表示陆地和岛屿，表示桥梁及其表示桥梁及其编号。若河两岸分别为互为敌对的双方部队占领，问至少应切断几座桥梁编号。若河两岸分别为互为敌对的双方部队占领，问至少应切断几座桥梁（具体指出编号）才能达到阻止对方部队过河的目的。试用图论方法进行分（具体指出编号）才能达到阻止对方部队过河的目的。试用图论方法进行分析。析。14ABCDEF8911101314127123456最大流问题应用举例最大流问题应用举例第28页/共43页在图中任给可在图中任给可行流，用标号行流，用标号法寻找网络最法寻找网络最大流！大流！弧容量：两点间的桥梁数。弧容量：两点间的桥梁数。ABCDFE122211221122A
17、BCDEF8911101314127123456转化为求网络最小割转化为求网络最小割第29页/共43页 设容量网络设容量网络G G有若干发点，若干个点，有若干发点，若干个点，可以可以添加两个新点添加两个新点vs s，vt t ，用用容量为容量为 的有向边分别连结的有向边分别连结vs s 与发点，收点与与发点，收点与vt t，得到新的网络得到新的网络GG，G G 为只有一个发点，为只有一个发点，一个收点的网络，求解一个收点的网络，求解G G 的最大流问题的最大流问题即可得到即可得到G G的解。的解。多发点多收点网络的最大流问题多发点多收点网络的最大流问题最大流问题应用举例最大流问题应用举例第30
18、页/共43页设有设有5位待业者，位待业者，5项工作，他们各自能胜任工作项工作，他们各自能胜任工作的情况如图所示，要求设计一个就业方案，使尽的情况如图所示，要求设计一个就业方案，使尽量多的人能就业量多的人能就业。其中其中表示工人。表示工人。表示工作。表示工作。最大匹配问题最大匹配问题第31页/共43页图中最大匹配问题，可以转化为最大流问题求解。在图中最大匹配问题，可以转化为最大流问题求解。在图中增加两个新点图中增加两个新点分别作为发点，收点。并用分别作为发点，收点。并用有向边把它们与原图中顶点相连，令全部边上的容量有向边把它们与原图中顶点相连，令全部边上的容量均为均为1。当网络流达到最大时，如果
19、。当网络流达到最大时，如果上的流量为上的流量为1，就让就让作作工作，此即为最大匹配方案。工作，此即为最大匹配方案。第32页/共43页第一次标号。第一次标号。第一次标号。第一次标号。调整调整调整调整第33页/共43页第二次标号第二次标号第二次标号第二次标号。再调整。再调整。再调整。再调整。第34页/共43页第三次标号。第三次标号。第三次标号。第三次标号。第35页/共43页调整。调整。调整。调整。第36页/共43页第四次标号。第四次标号。第四次标号。第四次标号。第37页/共43页调整调整调整调整第38页/共43页第五次标号。第五次标号。第五次标号。第五次标号。第39页/共43页标号过程已无法再继续。流量为标号过程已无法再继续。流量为标号过程已无法再继续。流量为标号过程已无法再继续。流量为1 1的画红线。的画红线。的画红线。的画红线。第40页/共43页工人工人工人工人分别作分别作分别作分别作故最多安排四个人工作。故最多安排四个人工作。故最多安排四个人工作。故最多安排四个人工作。第41页/共43页vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)第42页/共43页感谢您的观看！第43页/共43页