运筹学最大流问题PPT课件

1、列出图示网络全部割边上数字为 c i j(f i j ) .9(4)sv3v4v1v27(5)2(0)9(9)10(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,

2、3) (4,t)(1,3)(3,t)15(4,t)2117181924142515割容量第1页/共12页4-3、最大流- -最小割定理定理定理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 0 (vi , v j )

3、-则称为从 v s 到 v t 的(关于 f )的可增广链 .最大流的流量等于分离 vs , vt 的最小割的容量.推论 可行流f是最大流的充要条件是不存在从vs 到 vt 的(关于f 的)可增广链.第2页/共12页4-4、求最大流的标号算法若vt得到标号, 说明存在一条可增广链, 转(第2步)调整过程. 给发点vs以标号(0, +). 选择一个已标号的顶点 vi , 对于vi ,的所有未给标号的邻(a)若边(vj ,vi )E, 且 f j i 0 , 则令j =min ( f j i , j ) , 并给 v j 以标号( - v i , j ).1. 标号过程(b)若边(vi ,vj )

4、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, 按下列规则处理: 第3页/共12页2. 调整过程 令 fi j = 去掉所有标号, 回到第1步, 对可行流 f 重新标号. f i j + t 若(vi , v j )是可增广链上的前向边 f i j - t 若(vi , v j )是可增广链上的后向边 f i j 若(vi , v j )不在可增广链上第4页/

5、共12页作 业阅读 p258 - 265p43 15, 17第5页/共12页图边集 (vs , v1), (v1 , v3), (v2 , v3), (v3 , vt), (v4 , vt)都是割集.911割集容量2v23434143222v1v4v3vtvs边集 (vs , v1), (vs , v3), (vs , v4) 第6页/共12页例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 标号(, +).检

6、查 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, 给 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. 当此网络的流达到最大时, 即获最大匹配方案.第10页/共12页例15 有5位待业者，5项工作，他们各自胜任工作情况x5y