复杂网络中, 单源单点的最小费用最大流算法 (MCMF) 应用广泛.
在实际网络问题中, 不仅考虑从 Vs 到 Vt 的流量最大, 还要考虑可行流在网络传送过程中的费用问题, 这就是网络的最小费用最大流问题.
最小费用最大流问题的一般提法: 已知容量网络 D=(V ,A ,C), 每条弧 (Vi,Vj) 除了已给出容量 Cij 外, 还给出单位流量的传输费用 bij≥0, 记作 D=(V, A, C, B), 其中 bij ∈B. 要在费用, 容量网络 D 中寻找 Vs→Vt 的最大流 f={fij}, 且使流的总传输费用:
b(f)=Σbijfij 最小
从上一讲可知, 最大流的求法就是在容量网络上从某个可行流出发, 设法找到一条从 Vs→Vt 的增广链, 然后沿着此增广链调整流量, 作出新的流量增大了的可行流. 在这个新的可行流基础上再寻找它的增广链. 如此反复进行, 直至再找不出增广链, 就得到了该网络的最大流.
现在要寻求最小费用的最大流, 首先考察一下, 当沿着一条关于可行流 f 的增广链 μ, 以 θ=1 调整 f 得到新的可行流 f'时, 总费用 b(f') 比 b(f) 增加多少?
因为在前向弧 μ+ 上 fij' = fij +1,
例子: 给定费用, 容量网络图(bij,cij), 试求网络的最小费用最大流.
解:
(1), 初始取 0 流量的总费用为 f(0) = 0.
(2), 由原始网络构建费用网络图(费用网络图每条线路上的权重为 bij,bij 为单位流量的费用).
(3), 通过当前费用网络图找到一个费用最少的路径, 即 vs->v3->v2->vt. 通过该路径上每条线段的容量得出该线路能通过的最大流量, 即调整量θ = min{8,5,7} = 5, 即流量为 5, 当前的最小费用为 f(1) = 5*1+5*2+5*1 = 20. 下图为流量网络图.
(4), 在 (3) 的基础上构造新的费用网络图, 构造方法为: 当线路没流量通过时, 流量方向不变, 费用为原始费用. 如 vs->v2;
当线路流量等于该线路的最大容量时, 则流量方向改变, 费用为原始费用的负数. 如 v3->v2 变为 v2->v3;
当线路流量小于该线路的最大容量时, 则增加反向流量, 费用为原始费用的负数. 如 vs->v3 新增 v3->vs;
(5), 在 (4) 中得到的费用网络图上, 找到费用最少的路径, 即 vs->v2->v1-vt, 通过该路径上每条线段的容量得出该线路能通过的最大流量, 即调整量θ = min{10,7-5} = 2, 得到的最小费用流的流量为 7, 当前的最小费用为 f(2) = 2*4+5*1+5*2+7*1 = 30.
(6), 构造可行流 f2 的费用网络图.
(7), 在 (6) 中得到的费用网络图上, 找到费用最少的路径, 即 vs->v3->v4->vt, 通过该路径上每条线段的容量得出该线路能通过的最大流量, 即调整量θ = min{8-5,10,4} = 3, 得到的最小费用流的流量为 10, 当前的最小费用为 f(3) = 2*4+8*1+5*2+7*1+3*3+3*2 = 42
(8), 构造可行流 f3 的费用网络图.
(9), 在 (8) 的费用网络图上, 找到费用最少的路径, 即 vs->v2->v3->v4->vt, 通过该路径上每条线段的容量得出该线路能通过的最大流量, 即调整量θ = min{10-2, 10-3, 4-3, 5} = 1, 得到的最小费用流的流量为 11, 当前最小费用为 f(4) = 3*4+8*1+4*2+7*1+4*3+4*2 = 55
(10), 构造可行流 f4 的费用网络图.
由于无法找到从 vs->vt 的最短路, 所以 f(4) 就是该网络的最小费用最大流.
来源: http://www.bubuko.com/infodetail-3100974.html