《运筹学最大流问题.ppt》由会员分享，可在线阅读，更多相关《运筹学最大流问题.ppt（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、4最大流最大流定义定义 有向连通图有向连通图G=(V,E),G的每条边的每条边(vi,v j)称作弧称作弧上上有有c i j 称为称为边的容量边的容量,仅有一个入次为仅有一个入次为0的点的点v i 称为称为中间点中间点,这样的网络这样的网络G称为称为容量网络容量网络,常记为常记为 G=(V,E,C).对任一对任一G中的边中的边(vi,v j)有流量有流量 f i j,称为集合称为集合 f=f i j 为为网络网络G上的一个上的一个流流。称满足下列条件的流称满足下列条件的流 f 为为可行流可行流：(1)容量限制条件容量限制条件:对对G中每条边中每条边(vi,vj),有有0fij cij;jk(2
2、)平衡条件平衡条件:对中间对中间点点 v i,f i j =f k j(即中间点中间点v i 的输入量输入量与输出量输出量相等).(即从v s 点发出发出总量等于等于v t与输入输入总量相等).i对对 收收、发点发点 vi,vj,有有 f s i =f j t j一一、最大流有关概念最大流有关概念非负权非负权,发点发点(源源),一个入次为一个入次为0的点的点vi 称为称为收点收点(汇汇),其余的点称其余的点称为为定义定义容量网络容量网络G=(V,E,C),vi,v j 收收、发点发点,若有若有 边集边集E为为E的子集的子集,将将G分为两个子图分为两个子图G1,G2,其顶点集合分别记其顶点集合分
3、别记S,E为为E的真子集的真子集,而而 G(V,E-E)仍连通仍连通,G(V,E-E)不连通不连通;则称则称E为为G的的割集割集,记记 E =(S,S).S,S S=V,SS=,vi,vj 分属分属S,S,满足满足割集割集(S,S)中所有始点在中所有始点在S,终点在终点在S的边的容量之和的边的容量之和,称为称为割集容量割集容量,记为记为 C(S,S).一个流一个流f=f i j,f i j=c i j,则称流则称流 f 对边对边(vi,vj)是是饱和饱和的的.列出图示网络全部割列出图示网络全部割边上数字为边上数字为 c i j(f i j).9(4)sv3v4v1v27(5)2(0)9(9)1
4、0(8)8(8)5(5)tVVs,v1,v2,v3,v4ts,v1,v2,v4s,v1,v2,v3s,v2,v4s,v1,v3s,v1,v2s,v2s,v1sv1,v2,v3,v4,tv2,v3,v4,tv1,v3,v4,tv3,v4,tv2,v4,tv1,v3,tv4,tv3,t(s,1)(s,2)(s,2)(1,2)(s,1)(1,3)(s,1)(2,4)(s,2)(4,t)(1,3)(2,4)(4,3)(1,2)(3,2)(3,t)(2,4)(3,t)(4,3)(4,t)(1,3)(3,t)15(4,t)2117181924142515割割容量容量4-3、最大流最大流-最小割定理最小割定
5、理定理定理定理定理2(最大流最大流-最小割定理最小割定理)任一网络任一网络G中中,从从vs 到到 vt 的的定义定义设设 f 为网络为网络G=(V,E,C)的任一可行流的任一可行流,流量为流量为W,(S,S)是分离是分离 vs,vt 的任一割集的任一割集,则有则有 WC(S,S).容量网络容量网络G,若若为网络中从为网络中从 vs 到到 vt 的一条链的一条链,给给定向为从定向为从 vs 到到 vt,上的边凡与上的边凡与同向称为同向称为前向边前向边,凡凡与与反向的称为反向的称为后向边后向边，其集合分别用，其集合分别用+和和-表示表示,f 是是一个可行流一个可行流,如果满足如果满足0 f i j
6、 0 (vi,v j)-则称则称为从为从 v s 到到 v t 的的(关于关于 f)的的可增广链可增广链.最大流的流量等于分离最大流的流量等于分离 vs,vt 的最小割的容量的最小割的容量.推论推论 可行流可行流f是是最大流的充要条件是不存在从最大流的充要条件是不存在从vs 到到 vt 的的(关关于于f 的的)可增广链可增广链.4-4、求最大流的标号算法求最大流的标号算法若若vt得到标号得到标号,说明存在一条可增广链说明存在一条可增广链,转转(第第2步步)调整过调整过程程.给发点给发点vs以以标号标号(0,+).选择选择一个一个已已标号的顶点标号的顶点 vi,对于对于vi,的的所有所有未未给标
7、号的给标号的邻邻(a)若若边边(vj,vi)E,且且 f j i 0,则令则令j =min(f j i,j),并给并给 v j 以标号以标号(-v i,j).1.标号过程标号过程(b)若若边边(vi,vj)E,且且 f i j c i j 时时,令令j =min(c i j-f i j,i),并给并给 v j 以标号以标号(+v i,j).重复重复直到收点直到收点 vt 被标号或不再有顶点可标号为止被标号或不再有顶点可标号为止.若若vt未得到标号未得到标号,标号过程已无法继续标号过程已无法继续,说明说明 f 已是最大流已是最大流.接接点点 vj,按下列规则处理按下列规则处理:2.调整过程调整过
8、程 令令 fi j=去掉所有标号去掉所有标号,回到第回到第1步步,对可行流对可行流 f 重新标号重新标号.f i j +t 若若(vi,v j)是可增广链上的前向边是可增广链上的前向边 f i j -t 若若(vi,v j)是可增广链上的后向边是可增广链上的后向边 f i j 若若(vi,v j)不在可增广链上不在可增广链上作 业阅读阅读 p258-265p43 15,17图图边集边集(vs,v1),(v1,v3),(v2,v3),(v3,vt),(v4,vt)都是割集都是割集.911割集容量割集容量2v23434143222v1v4v3vtvs边集边集(vs,v1),(vs,v3),(vs,
9、v4)例例14_A图中一个网络及初始可行流图中一个网络及初始可行流,边上序数为边上序数为(c i j,f i j)v2(5,2)v1v4v3vtvsv5v6(4,2)(5,5)(3,0)(3,3)(3,3)(5,4)(2,2)(4,2)(2,2)(3,2)先先给给 vs 标号标号(,+).检查检查 vs 的邻接点的邻接点v1,v2,v3,边边(vs,v2)E,且且 f s 2 c s 2=4v2令令 =min2,+=2,同理同理 给给 v3 以标号以标号+vs,1.检查检查v2尚未标号邻接点尚未标号邻接点v5,v6,边边(v2,v6)E,且且 f25=00,v1令令 =min3,2=2,给给
10、v2 以标号以标号+vs,2.v4尚未标号与尚未标号与v1邻接邻接,v4令令 =min3,2=2,给给 v4 以标号以标号+v1,2.类似类似给给 vt 以标号以标号+v4,2.因因 vt 得以标号，得以标号，(v1,v4)E且且 f14=2|M|,则称则称M为为最大匹配最大匹配.二部图中最大匹配问题可以化为最大流问题。二部图中最大匹配问题可以化为最大流问题。在二部图中增加发点和收点在二部图中增加发点和收点,用有向边与原二部图中顶点用有向边与原二部图中顶点两条边都没有公共端点两条边都没有公共端点,则称则称M为图为图G的一个的一个匹配匹配(对集对集)相连相连,令全部边上的容量均为令全部边上的容量均为1.当此网络的流达到最大时当此网络的流达到最大时,即获最大匹配方案即获最大匹配方案.例例15 有有5位待业者，位待业者，5项工作，他们各自胜任工作情况项工作，他们各自胜任工作情况x5y1x3y2x2y3x1y4x4y5x5y1x3y2x2y3x1y4x4y5vsvt111111111111如图，要求设计一个方案，使量多的人能就业。如图，要求设计一个方案，使量多的人能就业。