最小费用最大流问题xfj.pptVIP

10-5 最小费用最大流问题 一、基本概念 1、什么是最小费用最大流问题？ 对每一条弧都给出单位流量费用的容量网络D=(V, A, C) (称为费用容量网络)中，求取最大流f，使输送流量的总费用 b(f) =∑bijfij 为最小的一类优化问题。 其中，cij表示弧(vi, vj)上的容量，bij表示弧(vi, vj)上通过单位流量所花费的费用，fij表示弧(vi, vj)上的流量。 vi vj (cij,bij,fij) 2、最小费用流 对于一个费用容量网络，具有相同流量 v(f) 的可行流中，总费用b(f)最小的可行流称为该费用容量网络关于流量 v(f) 的最小费用流，简称流量为 v(f) 的最小费用流。 3、增广链的费用 当沿着一条关于可行流 f 的增广链（流量修正路线）μ，以修正量ε=1进行调整，得到新的可行流 ，则称 为增广链μ的费用。 ②增广链μ的费用定义为：以单位调整量调整可行流时所付出的费用； ③当修正量ε=1时， 此时， ① 的流量v( ) = v(f)+1； 二、求解最小费用最大流问题的对偶法 1、求解途径： （1）始终保持网络中的可行流是最小费用 流，然后不断调整，使流量逐步增大， 最终成为最小费用的最大流； （2）始终保持可行流是最大流，通过不断 调整使费用逐步减小，最终成为最大流 量的最小费用流。 主要学习按思路(1)的求解方法始终保持网络中的可行流是最小费用流，然后不断调整，使流量逐步增大，最终成为最小费用的最大流。 v(f) b(f) (1) (2) 应该如何实现“始终保持网络中的可行流是最小费用流” 呢？ 2、算法原理 （1）定理 若f 是流量为v(f)的最小费用流，μ是关于 f 的所有增广链中费用最小的增广链，那么沿着μ去调整 f 得到的新的可行流 就是流量为 的最小费用流。 （2）实现思路 基于第一种求解途径，根据上述定理，从流量为v(f) 的最小费用流f 开始，只要找到其上的最小费用增广链，在该链上调整流量，就得到增加流量后的最小费用流。循环往复就可以求出最小费用最大流。 实施中的关键——寻找最小费用增广链 具体方法：构造增广费用网络图，借助最短路算法寻找最小费用增广链。 增广费用网络图的构造方法 将流量网络中的每一条弧（vi,vj）都看作一对方向相反的弧，并定义弧的权数如下： vi vj (cij,fij) wij = bij 若fij cij +∞ 若fij=cij wji = -bij 若fij0 +∞ 若fij=0 对于零流弧(fij=0),在其对应位置构造与其方向相同且权数为bij的弧； wij = bij 若fij cij +∞ 若fij=cij wji = -bij 若fij0 +∞ 若fij=0 对于非饱和且非零流弧( cijfij0)，在其对应位置构造与其方向相同且边权为bij的弧，以及与其方向相反且边权为-bij的弧。 处理完所有的弧，即形成增广费用网络图。 对于饱和弧(fij=cij)，在其对应位置构造与其方向相反且权数为-bij的弧； 零流弧上(fij=0) ，保持原弧不变，将单位费用作为权数，即wij= bij: Vi Vj bij Vi Vj -bij 饱和弧上(fij=cij)：去掉原有弧，添加以单位费用的负数作为权数后向弧（虚线弧）： 非饱和且非零流弧上( cijfij0) ，原有弧以单位费用作权数，并添加以单位费用的负数作为权数后向弧（虚线弧）： Vi Vj bij -bij 3、整个过程的求解步骤： 第一步---取初始可行流为零流 ，它必为流量=0的最小费用流。 第二步 --- 对该可行流f(0)构造增广费用网络图W(f(0))，用最短路算法求出从发点到收点的最短路。(寻找f(0)的最小费用增广链) 若不存在最短路，则该可行流即为最小费用最大流，停止迭代；否则，转下一步。 第三步--- 将最短路还原成流量网络图（cij,fij）中的最小费用增广链μ，在μ上对可行流f(0)进行调整(采用最大流问题中的增广链流量调整方法)，得到新的可行流图。返回第二步，将f(0)替换为新的可行流即可。 4、举例：以下图为例，求最小费用最大流，弧旁的数字为(cij,bij)。 vs vt v2 v3 v1 (10,4) (7,1) (8,1) (10,3) (4,2) (5,2) (2,6) 解：（1）以零流弧为初始可行流f(0