运筹学第四节最大流问题

《运筹学第四节最大流问题》由会员分享，可在线阅读，更多相关《运筹学第四节最大流问题（28页珍藏版）》请在装配图网上搜索。

1、运筹学教程 第四节 最大流问题 理解最大流问题的概念、最大流 -最小 割定理。 掌握求最大流问题的标号算法。 运筹学教程 引言 在许多实际的网络系统中都存在着流量 和最大流问题 。 例如铁路运输系统中的车辆 流 ， 城市给排水系统的水流问题等等 。 而网 络系统流最大流问题是图与网络流理论中十 分重要的最优化问题 ， 它对于解决生产实际 问题起着十分重要的作用 。 运筹学教程 图是联结某个起始地 vs和目的地 vt的交通运输网 ， 每 一条弧 vi 旁边的权 cij表示这段运输线的最大通过能力 ， 货物从 vs运送到 vt.要求指定一个运输方案 ， 使得从 vs到 vt 的货运量最大 ， 这个

2、问题就是寻求网络系统的最大流问 题 。 一、最大流有关概念 连通网络 G(V, E) 有 m 个节点 , n条弧 , 弧 eij 上 的流量上界为 cij, 求从起始节点 vs 到终点 vt 的最大流 量。 vt v3 v2 v1 v4 vs 17 3 5 10 8 6 11 4 5 3 Cij 运筹学教程 定义 20 设一个赋权有向图 G=（ V,E） ,对于 G中的 每一个边 （ 弧 ） （ vi ,vj） E,都有一个 非负数 cij叫 做边的 容量 。 在 V 中一个入次为零的点称为发点 vs， 一个出次为零的点称为收点 vt ,其它的点叫做中间点 。 我们把这样的图 G叫做一个 容量

3、 网络 ， 记做 G=（ V， E， C） 。 网络 G上的流 ， 是指定义在边 (vi ,vj)上有流量 fij， 称集合 f=fij 为网络 G上的一个流 ， f为可行流 。 运筹学教程 网络上的一个流 f 叫做可行流 ， 如果 f 满足以下条件： （ 1） 容量条件： 对于每一个弧 （ vi ,vj） E,有 0 fij cij . （ 2） 平衡条件： i j tjis Wff 对于发点 vs,收点 vt有 对于中间点 ， 有 Evv Evv ijji ji ij ff ),( ),( 0 运筹学教程 任意一个网络上的可行流总是存在的。例如零 流 w(f)=0,就是满足以上条件的可行流

4、。 网络系统中最大流问题就是在给定的网络上寻 求一个可行流 f,其流量 w(f)达到最大值。 设流 f =fij是网络 G上的一个可行流。我们把 G 中 fij=cij的弧叫做饱和弧， fij0的弧为非零流弧， fij=0的弧叫做零流弧 . 最大流问题实际是个线性规划问题。 其中发点的总流量 （ 或收点的总流量 ） w 叫做这个可行流的总流量 。 运筹学教程 v3 v2 v1 v4 vs （ 2） （ 3） （ 2） （ 5） （ 3） （ 3） （ 6） （ 1） （ 1） （ 2） fij vt 网络上的一个流（运输方案），每一个弧上的流量 fij就是运输 量。例如 fs1=5 , fs2

5、=3 , f13=2 等等。 运筹学教程 定义 21 设一个网络 G=（ V， E， C） ， vs、 vt为发 和 收点 ， 边集 为 E的子集 ， 将 G分成 2个子图 G1,G2;其顶点集合分别 为 : ,发点 vs S,收点 vt /S ,满足 1.G=（ V， E- ） 不连通； 2. 为 的真子集 ， 而 G=（ V， E- ） 连通； 那么 为 G的割集 ， 记为 =(S, )。 割集 (S, )所有始点在 S， 终点在 的容量之和 ， 称为 (S, )的 割集容量 ， 记为 C(S, ) 。 SSVSSSS , S S S S S E E E E E E E 运筹学教程 vt

6、vs v1 v2 v3 v4 4 2 4 4 3 3 2 2 2 3 1 边集 (vs,v1),(vs,v3),(vs,v4) 边集 (vs,v1),(v1,v3),(v2,v3),(v3,vt) 为图的割集，割集容量分别为 11， 9 运筹学教程 二、最大流 -最小割定理 定理 10： 设 f为网络 G=（ V， E， C）的任一个可行流，流量 为 W, (S, )是分离 vs vt的任一个割集，则有 W C(S, ) . 定理 11： 最大流 -最小割定理 :任一个 网络 G=（ V， E， C） , 从 vs到 vt的 最大流的流量等于 分离 vs vt的最小割的容量。 定义 22： 设

7、 是网络 G中连接发点 s和收点 vt的一条链 。 定义链 的方向是从 s到 vt ， 于是链 上的边被分为两类：一类是边的 方向与链的方向相同 ， 叫做前向边 ， 前向边的集合记做 +。 二 类是边的方向与链的方向相反 ， 叫做后向边 ， 后向 边 的集合记 做 。 S S 运筹学教程 如果链 满足以下条件： 1 在边 （ vi ,vj） +上 ， 有 0fijcij。 2 在边 （ vi,vj） 上 ， 有 0fijcij,。 则称 为 从 s到 vt可增广链 。 在链 （ vs,v1,v2,v3,v4,vt)中 ， + = (vs,v1 ),(v1,v2),(v2,v3),(v4,vt)

8、, = (v4 ,v3). vt vs v1 v2 v3 v4 4 2 4 4 3 3 2 2 2 3 1 运筹学教程 定理 11提供了一个寻求网络系统最大流的方法。如果网络 G 中有一个可行流 f，只要判断网络是否存在关于可行流 f 的增广链 。如果没有增广链，那么 f一定是最大流。如有 增广链，那么可以按照定理中必要性，不断改进和增大可 行流 f 的流量，最终可以得到网络 G中的一个最大流。 推论： 网络中的一个可行流 f*是最大流的充分必要条件 是，不存在关于 f*的增广链。 在一个网络 G中，最大流的流量等于分离 vs 和 vt 的最小割 集的割量。 运筹学教程 三 、 标号法 从网络

9、中的一个可行流 f 出发 （ 如果 G中没有 f， 可以令 f 是零流 ） ， 运用标号法 ， 经过标号过程和 调整过程 ， 可以得到网络中的一个最大流 。 如果 vt有了标号 ， 表示存在一条关于 f 的增广链 。 如果标号过程无法进行下去 ， 并且 vt未被标号 ， 则 表示不存在关于 f 的增广链 。 这样 ， 就得到了网络 中的一个最大流和最小割集 。 运筹学教程 1 标号过程 在标号过程中 ， 网络中的每个标号点的标号包 含两部分：第一个标号表示这个标号是从那一点得 到的 ， 以便找出增广链；第二个标号是为了用来确 定增广链上的调整量 。 标号过程开始 ， 先给 vs 标号 （ ，

10、+） ， 一般 地 ， 取一个标号顶点 vi， 对 vi所有 未标号的邻接点 vj 按照下面条件进行处理： 运筹学教程 （ 1） 如果在弧 （ vi ,vj） 上 ， fij 0,那么给 vj标号 （ -vi , (vj) ） .其中 (vj)=minfji , (vi) 。 重复以上步骤 ， 如果收点 Vt被标号或不再有顶点 可标号为止 ， 则标号法结束 。 这时的可行流就是最 大流 。 运筹学教程 2.调整过程 令 但是，如果 vt 被标上号，表示得到一条增广 链 ，转入下一步调整过程。 不在可增广链),(, ),(, ),(, jiji jitji jitji ji vvf vvf vv

11、f f 3.再去掉所有的标号，对新的可行流 f =f ij,重新 进行标号过程，直到找到网络 G的最大流为止。 运筹学教程 vs v2 v5 v t v4 v1 v6 v3 (5,5) (3,2) (3,3) (4,2) (5,4) (3,3) (2,2) (5,2) (4,2) (2,2) 例 求图的网络最大流，弧旁的权 数表示（ cij , fij） 。 运筹学教程 vs v2 v5 vt v4 v1 v6 v3 (5,5) (3,2) (3,3) (4,2) (5,4) (3,3) (2,2) (5,2) (4,2) (2,2) 解： 用标号法。 1.标号过程。 （ 1） 首先给 vs标

12、号（ ， +） （ 2） 检查 vs邻接点 v1,v2,v3: v2点 满足（ vs,v2) E,且 fs2=2cs2=4, v2=min2,+ =2,给 v2以 标号 (+ vs,2); v3点 满足（ vs,v3) E,且 fs3=2cs3=3, v3=min1,+ =1,给 v3以 标号 (+vs,1); ( ， +) (+ vs,2) (+ vs,1) 运筹学教程 （ 3） 检查 v2邻接点 v5,v6: v5点 满足 （ v2,v5) E,且 f25=0c15=0, v1=min3,2=2,给 v1以 标号 (- v5,2); vs v2 v5 vt v4 v1 v6 v3 (5,5

13、) (3,2) (3,3) (4,2) (5,4) (3,3) (2,2) (5,2) (4,2) (2,2) ( ， +) (+ vs,2) (+ vs,1) (+ v2,2) (- v5,2) 运筹学教程 （ 5） 检查 v1邻接点 v4: v4点 满足（ v1,v4) E,且 f14=2c14=5, v4=min3,2=2,给 v4以 标号 (+ v1,2); vs v2 v5 vt v4 v1 v6 v3 (5,5) (3,2) (3,3) (4,2) (5,4) (3,3) (2,2) (5,2) (4,2) (2,2) ( ， +) (+ vs,2) (+ vs,1) (+ v2,

14、2) (- v5,2) (+ v1,2) 运筹学教程 （ 6） 检查 v4邻接点 vt: vt点 满足（ v4,vt) E,且 f4t=2c4t=4, vt=min2,2=2,给 vt以标号 (+ v4,2); Vt得到标号，说明已经得到一条可增广链，标号过程结束。 vs v2 v5 vt v4 v1 v6 v3 (5,5) (3,2) (3,3) (4,2) (5,4) (3,3) (2,2) (5,2) (4,2) (2,2) ( ， +) (+ vs,2) (+ vs,1) (+ v2,2) (- v5,2) (+ v1,2) (+ v4,2) 运筹学教程 开始调整 vs v2 v5 v

15、 t v4 v1 v6 v3 (5,5) (3,2) (3,3) (4,2) (5,4) (3,3) (2,2) (5,2) (4,2) (2,2) ( ， +) (+ vs,2) (+ vs,1) (+ v2,2) (- v5,2) (+ v1,2) (+ v4,2) 运筹学教程 2.调整过程 从 vt开始 ， 按照标号点的第一个标号 ， 用反向追踪 的方法 ， 找出一条从 vs到 vt的增广链 ， 如图 G中虚 线所示 。 不难看出 ,+=(vs ,v2), (v1 ,v4),(v4 ,vt), =(v5 ,v1) ,取 = vt = 2 ， 在 上调整 f ， 得到 f * = f4t

16、+ vt =2+2=4 在 +上 f14 + vt =2+2=4 在 +上 f25 + vt =0+2=2 在 +上 fs2 + vt =2+2=4 在 +上 f15 vt =3 2=1 在 -上 其它的不变 vs v2 v5 vt v4 v1 v6 v3 (5,5) (3,2) (3,1) (4,4) (5,4) (3,3) (2,2) (5,4) (4,4) (2,2) （ ， +） （ +vs ， 1） (3,2) 重新开始标号，寻找可增广链，当标到 V3，与 VS,V3相连的 V1,V2,V6不满足标号条件，标号无法进行， vt得不到标号。 流量： w=fs1+ fs2+ fs3= f

17、4t+ f5t+ f6t=11 得到一个最小割，标点号集合： S=vs,v3 非标点号集合： /S=v1,v2， v4,v5 ， v6,vt 此时割集（ s,/s） =(vs,v1),(vs,v2),(v3,v6), 割集容量 C(s,/s)=Cs1+ Cs2+ C36=5+4+2=11 运筹学教程 vs v2 v5 v t v4 v1 v6 v3 (5,5) (3,2) (3,3) (4,2) (5,4) (3,3) (2,2) (5,2) (4,2) (2,2) ( ， +) (+ vs,2) (+ vs,1) (+ v2,2) (- v5,2) (+ v 1,2) (+ v4,2) 4) 4) 1) (3,0) 2) 4) 第一条可增广链： vs-v2,v5,v1,v4,vt,调整量为： 2 流量： f=11 无可增广链 最大流 =14 割集 =(vs,v1),(vs,v2),(v3,v6) 运筹学教程 求最大流的标号算法可以解决多发点多 收点网络的最大流问题 X1 X2 X3 xm Y1 Y2 Y3 yn vs vt + + 运筹学教程 小结 1、最大流问题的概念、最大流 -最小割 定理。 2、求最大流问题的标号算法。 作业 8.10,8.14