最小费用最大流问题详解
一、问题描述
在网络中求一个最大流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实例
暂略待更