运筹学第四节最大流问题ppt课件.ppt

第四节最大流问题 理解最大流问题的概念 最大流 最小割定理 掌握求最大流问题的标号算法 1 引言在许多实际的网络系统中都存在着流量和最大流问题 例如铁路运输系统中的车辆流 城市给排水系统的水流问题等等 而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题 它对于解决生产实际问题起着十分重要的作用 2 图是联结某个起始地vs和目的地vt的交通运输网 每一条弧vi旁边的权cij表示这段运输线的最大通过能力 货物从vs运送到vt 要求指定一个运输方案 使得从vs到vt的货运量最大 这个问题就是寻求网络系统的最大流问题 一 最大流有关概念连通网络G V E 有m个节点 n条弧 弧eij上的流量上界为cij 求从起始节点vs到终点vt的最大流量 3 定义20设一个赋权有向图G V E 对于G中的每一个边 弧 vi vj E 都有一个非负数cij叫做边的容量 在V中一个入次为零的点称为发点vs 一个出次为零的点称为收点vt 其它的点叫做中间点 我们把这样的图G叫做一个容量网络 记做G V E C 网络G上的流 是指定义在边 vi vj 上有流量fij 称集合f fij 为网络G上的一个流 f为可行流 4 网络上的一个流f叫做可行流 如果f满足以下条件 1 容量条件 对于每一个弧 vi vj E 有0 fij cij 2 平衡条件 对于发点vs 收点vt有 对于中间点 有 5 任意一个网络上的可行流总是存在的 例如零流w f 0 就是满足以上条件的可行流 网络系统中最大流问题就是在给定的网络上寻求一个可行流f 其流量w f 达到最大值 设流f fij 是网络G上的一个可行流 我们把G中fij cij的弧叫做饱和弧 fij0的弧为非零流弧 fij 0的弧叫做零流弧 最大流问题实际是个线性规划问题 其中发点的总流量 或收点的总流量 w叫做这个可行流的总流量 6 网络上的一个流 运输方案 每一个弧上的流量fij就是运输量 例如fs1 5 fs2 3 f13 2等等 7 定义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 8 vt 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 9 二 最大流 最小割定理定理10 设f为网络G V E C 的任一个可行流 流量为W S 是分离vsvt的任一个割集 则有W C S 定理11 最大流 最小割定理 任一个网络G V E C 从vs到vt的最大流的流量等于分离vsvt的最小割的容量 定义22 设 是网络G中连接发点 s和收点vt的一条链 定义链的方向是从 s到vt 于是链 上的边被分为两类 一类是边的方向与链的方向相同 叫做前向边 前向边的集合记做 二类是边的方向与链的方向相反 叫做后向边 后向边的集合记做 10 如果链 满足以下条件 1 在边 vi vj 上 有0 fij cij 2 在边 vi vj 上 有0 fij cij 则称 为从 s到vt可增广链 在链 vs v1 v2 v3 v4 vt 中 vs v1 v1 v2 v2 v3 v4 vt v4 v3 vt vs v1 v2 v3 v4 4 2 4 4 3 3 2 2 2 3 1 11 定理11提供了一个寻求网络系统最大流的方法 如果网络G中有一个可行流f 只要判断网络是否存在关于可行流f的增广链 如果没有增广链 那么f一定是最大流 如有增广链 那么可以按照定理中必要性 不断改进和增大可行流f的流量 最终可以得到网络G中的一个最大流 推论 网络中的一个可行流f 是最大流的充分必要条件是 不存在关于f 的增广链 在一个网络G中 最大流的流量等于分离vs和vt的最小割集的割量 12 三 标号法从网络中的一个可行流f出发 如果G中没有f 可以令f是零流 运用标号法 经过标号过程和调整过程 可以得到网络中的一个最大流 如果vt有了标号 表示存在一条关于f的增广链 如果标号过程无法进行下去 并且vt未被标号 则表示不存在关于f的增广链 这样 就得到了网络中的一个最大流和最小割集 13 1 标号过程在标号过程中 网络中的每个标号点的标号包含两部分 第一个标号表示这个标号是从那一点得到的 以便找出增广链 第二个标号是为了用来确定增广链上的调整量 标号过程开始 先给vs标号 一般地 取一个标号顶点vi 对vi所有未标号的邻接点vj按照下面条件进行处理 14 1 如果在弧 vi vj 上 fij0 那么给vj标号 vi vj 其中 vj min fji vi 重复以上步骤 如果收点Vt被标号或不再有顶点可标号为止 则标号法结束 这时的可行流就是最大流 15 2 调整过程令 但是 如果vt被标上号 表示得到一条增广链 转入下一步调整过程 3 再去掉所有的标号 对新的可行流f f ij 重新进行标号过程 直到找到网络G的最大流为止 16 例求图的网络最大流 弧旁的权数表示 cij fij 17 解 用标号法 1 标号过程 1 首先给vs标号 2 检查vs邻接点v1 v2 v3 v2点满足 vs v2 E 且fs2 2 cs2 4 v2 min 2 2 给v2以标号 vs 2 v3点满足 vs v3 E 且fs3 2 cs3 3 v3 min 1 1 给v3以标号 vs 1 vs 2 vs 1 18 3 检查v2邻接点v5 v6 v5点满足 v2 v5 E 且f25 0 c25 3 v5 min 3 2 2 给v5以标号 v2 2 vs 2 vs 1 v2 2 19 4 检查v5邻接点v1 vt v1点满足 v1 v5 E 且f15 3 c15 0 v1 min 3 2 2 给v1以标号 v5 2 vs 2 vs 1 v2 2 v5 2 20 5 检查v1邻接点v4 v4点满足 v1 v4 E 且f14 2 c14 5 v4 min 3 2 2 给v4以标号 v1 2 vs 2 vs 1 v2 2 v5 2 v1 2 21 6 检查v4邻接点vt vt点满足 v4 vt E 且f4t 2 c4t 4 vt min 2 2 2 给vt以标号 v4 2 Vt得到标号 说明已经得到一条可增广链 标号过程结束 vs 2 vs 1 v2 2 v5 2 v1 2 v4 2 22 开始调整 v4 2 23 2 调整过程从vt开始 按照标号点的第一个标号 用反向追踪的方法 找出一条从vs到vt的增广链 如图G中虚线所示 不难看出 vs v2 v1 v4 v4 vt v5 v1 取 vt 2 在 上调整f 得到 24 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 f4t 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 25 vs 2 vs 1 v2 2 v5 2 v1 2 v4 2 4 4 1 3