最小费用最大流问题详解

一、问题描述

在网络中求一个最大流f，使流的总输送费用最小。

伴随网络流 f 的增流网络：设 f是网络 D = ( V , A , C , F , B )的一个网络流，按照以下规则构建一个新的网络 D f = ( V , A ′ , C ′ , B ′ ) ，该网络称为伴随 f 的增流网络。

V为顶点集，A为弧集，C为容量集，F为流量集，B为费用集

负回路：在增流网络Df 中，所有的权（费用）之和小于零的回路称为负回路。

增流圈：在增流网络Df 中的负回路对应网络D中的一个圈，在这个圈中，如果方向与这个负回路方向相同的所有弧都为不饱和弧，方向与负回路方向相反的所有弧都为非零流弧，则这个圈称为增流圈。

二、求解思路

解法I：求得最大流量调整流量分布达到最小费用

利用最大流算法，将网络的流量调整到最大流

构建伴随网络流 f的增流网络 D f

针对负回路对应网络 D中的圈，若该圈是增流圈，则把增流圈方向上与负回路方向一致的所有弧的流量加上 θ，把增流圈方向上与负回路方向相反的所有弧的流量减去 θ ；若该圈不是增流圈，则转到步骤3重新寻找负回路。

解法II：满足最小费用寻找最小费用增广链达到最大流量

三、实例

增流网络实例

有如下网络D：

其对应的增流网络如下：

过程：

解法I实例

实例

首先寻找最大流，从起点出发到终点结束，将流量充满，得到最大流量图。

然后构建增流网络

构建好之后寻找负回路，可见这条负回路的最小容量为4，则 θ 取4

调整原网络，可以看到对应原网络中为增流圈，与负回路与负回路方向一致的所有弧的流量加上 θ ，把增流圈方向上与负回路方向相反的所有弧的流量减去 θ得到网络 D2

构建 D2的增流网络 Df2

寻找负回路，发现已经找不到负回路，说明网络 D2 已经是最小费用，结束算法，得到最小费用最大流，最大流为11，最小费用为： 3 × 4 + 8 × 1 + 4 × 2 + 4 × 3 + 7 × 1 + 4 × 2 = 55

解法II实例

暂略待更