最小费用最大流问题.pdfVIP

10.5最小费用最大流问题

10.5最小费用最大流问题

给定网络D=(V,A,C)，对任意(v,v)∈A,除

ij

了已容量c外,还给了一个单位流量的费用

ij

b(v,v)≥0(简记为b).

ijij

所谓最小费用最大流问题就是要求一个

最大流f,使流的总输送费用最小,即求f＊,使

＊

b(f)=min∑bf

f(vi,vj)∈Aijij

如何求解这个问题?

PDFcreatedwithpdfFactoryProtrialversion

1、增广链的费用

定义增广链μ的费用为bijbij.

mm

结论:若f是流量为v(f)的所有可行流中费用

最小者,而μ是关于f的所有增广链中费用最小

的增广链,则沿μ去调整f,得到的可行流f,就是

流量为v(f)的所有可行流中的最小费用流.

这样,当f是最大流时,它即为所求的最小费

用最大流.

PDFcreatedwithpdfFactoryProtrialversion

2、定义设网络D的一个可行流为f,构造其赋权

有向图,记为W(f),如下：

1)W(f)的顶点集是D的顶点集;

2)把D中的每一条弧(v,v)变成两个相反方

ij

向的弧(v,v)和(v,v).定义W(f)中弧的权为:

ijji

b,fcb,f0

wijijijijij

ij,w

fcji

,ijij,fij0

PDFcreatedwithpdfFactoryProtrialversion

注意：在网络D中求关于f的最小费用增广

链等价于在W(f)中求从v到v的最短路.

st

最小费用最大流算法：

初始化:取