最小费用最大流问题

墨蓝 2021-12-15 09:29 396阅读 0赞

复杂网络中，单源单点的最小费用最大流算法(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)=Σbij fij 最小

从上一讲可知，最大流的求法就是在容量网络上从某个可行流出发，设法找到一条从 Vs→Vt 的增广链，然后沿着此增广链调整流量，作出新的流量增大了的可行流。在这个新的可行流基础上再寻找它的增广链。如此反复进行，直至再找不出增广链，就得到了该网络的最大流。

例子：给定费用、容量网络图(bij，cij)，试求网络的最小费用最大流。

![1235684-20190623004602638-1890337432.png][]

解：

（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。下图为流量网络图。

![1235684-20190623010700103-1076229341.png][]

（4）、在（3）的基础上构造新的费用网络图，构造方法为：当线路没流量通过时，流量方向不变，费用为原始费用。如vs->v2；

当线路流量等于该线路的最大容量时，则流量方向改变，费用为原始费用的负数。如v3->v2变为v2->v3；

当线路流量小于该线路的最大容量时，则增加反向流量，费用为原始费用的负数。如vs->v3新增v3->vs；

![1235684-20190623013406219-2048295175.png][]

（5）、在（4）中得到的费用网络图上，找到费用最少的路径，即vs->v2->vt，通过该路径上每条线段的容量得出该线路能通过的最大流量，即调整量θ = min\{10,7-5\} = 2，得到的最小费用流的流量为7，当前的最小费用为 f(2) = 2\*4+5\*1+5\*2+7\*1 = 30。

![1235684-20190623013603957-460510864.png][]

（6）、构造可行流 f2的费用网络图。

![1235684-20190623020140871-949295519.png][]

（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

![1235684-20190623021323151-287134669.png][]

（8）、构造可行流 f3 的费用网络图。

![1235684-20190623021522519-1730455107.png][]

（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

![1235684-20190623021919078-316366348.png][]

（10）、构造可行流 f4 的费用网络图。

![1235684-20190623022527235-347385938.png][]

由于无法找到从 vs->vt 的最短路，所以 f(4) 就是该网络的最小费用最大流。

转载于:https://www.cnblogs.com/keye/p/11059148.html

[1235684-20190623004602638-1890337432.png]: /images/20211214/c71b47fa0e594cb7b548a955f17c18f5.png
[1235684-20190623010700103-1076229341.png]: /images/20211214/58e305e59f1d429dacd11cb6b19bc1e0.png
[1235684-20190623013406219-2048295175.png]: /images/20211214/51b69543e97f4787a2ab14be377ccfd7.png
[1235684-20190623013603957-460510864.png]: /images/20211214/11853320d3e346f5858167308d14b0d2.png
[1235684-20190623020140871-949295519.png]: /images/20211214/b6e8d5a0d5f2404ab677d1a3dca083d8.png
[1235684-20190623021323151-287134669.png]: /images/20211214/8c003e7f9c884cd487f5acc6f6af1bb1.png
[1235684-20190623021522519-1730455107.png]: /images/20211214/fe8ff0beacd24aef91e5b06f11c2386a.png
[1235684-20190623021919078-316366348.png]: /images/20211214/d415af276f8a41a784c65b619c7b833f.png
[1235684-20190623022527235-347385938.png]: /images/20211214/12689cce4f9743cfa353cb2a010fefb7.png