文档介绍：2017/11/11
管理运筹学课程组 ftp://
1
最小费用流
基本概念及定理
(1)流的费用
对于一个可行流 f ={fij}来说,如果网络 G=(V,A,C,W)中,对于每条弧aij ∈ A,都有一个单位流费用ωij,则流的费用定义为:
2017/11/11
管理运筹学课程组 ftp://
2
(2)最小费用流
定义网络G=(V,A,C,W)中,对于每一流值为V(f)
的可行流 f 来说,都存在一个流的费用
W(f),使W(f)为最小的可行流,则称为最
小费用流。
最小费用流的数学定义如下:
目标函数:
约束条件:
(1)每一条弧;
(2) ;
(3) ;
(4) ;
其中:V(f)——目标流值;
Cij ——能力;
ωij——单位费用;
Vs——发点;
Vt——收点。
2017/11/11
管理运筹学课程组 ftp://
3
(3)链的费用与最小费用增广链
已知网络G=(V,A,C,W) ,f是G的可行流,μ为从
vs到vt的关于f 的增广链,称
为链的μ的费用。
若μ*是vs到vt所有增广链中费用最小的链,则称μ*为最小费用增广链。
(4)最小费用流的有关定理
若f是流量为V(f)的最小费用流,μ是关于f的从vs到vt的一条最小费用增广链,则f经过μ调整流量得到新的可行流f `, f `一定是流量为V(f) +θ的可行流中的最小费用流。
2017/11/11
管理运筹学课程组 ftp://
4
最小费用流算法及算例
基本思想:
从某个初始的最小费用可行流f(0) (一般为
零流)开始,寻找从源点vs到收点vt的关于f(0)的
最小费用增广链。在μ中按最大流的标号法的调
整方法进行调整,只是在调整量上,要比较增广
链μ0上可调整的量θ0与V目标- V(f(0))的量
值,若θ0 > V目标- V(f(0)) ,则μ0*上调整的量为V目标- V(f(0)) ,算法结束。若在链μ0上按θ0流量进行调整,得到流值为V(f(1)) 的最小费用可行流f(1) ,在f(1)上寻找从vs到vt的费用最小的增广链μ1,再在μ1按上述方法进行流量调整,如此反复,直到最小费用可行流的流值达到V目标为止。
2017/11/11
管理运筹学课程组 ftp://
5
从算法思路来看,关键在于如何寻找从vs到vt的最小费用增广链,为了求最小费用我们首先想到利用最短路算法,但是路和链对弧的连接方式的要求是有差异的。为此,为了能利用最短路算法,对于网络中,已知可行流f,构造一个关于f的赋权有向网络L(f),使得在G中从vs到vt的最小费用增广链问题,等价于L(f)中求从vs到vt的最短路问题。
2017/11/11
管理运筹学课程组 ftp://
6
L(f)的构造方法如下:L(f)中的顶点是原网络中的点,而把G中的每一条弧(vi,vj)变成两个方向相反的弧(vi,vj)和(vj,vi)。定义
L(f)中弧(vi,vj)和(vj,vi)的权lij和lji为:
2017/11/11
管理运筹学课程组 ftp://
7
求流量为V目标的最小费用流的算法
第一步:k=0,从一流量为( ≤V目标)为最小费用初始可行流(一般取零流)开始。
第二步:构造,在中求从vs到vt的费用最小的路,若没有从vs到vt的最短路,则为最大流,不存在流量为V目标的最小费用流,算法结束,否则转下一步。
第三步:在G中与这条最短路相应的增广链μk上,计算
若θk ≤V目标- ,则在链μk上按最大流流量调整方法增广流量θk ,得到新流,令k=k+1,转步骤2,
否则当θk ≥V目标- ,则在链上按最大流流量调整方法增广流量V目标- ,得到新流,新流就是所求的流量为V目标的费用最小的可行流。算法结束。
2017/11/11
管理运筹学课程组 ftp://
8
例求下图所示的网络G中,求从vs到vt的目标流值为
25的最小费用流,弧上括号内的数字第一个为容
量,第二个为弧上单位流的费用。
(17,3)
(20,5)
(15,4)
V2
(18,3)
(14,5)
V3
V1
(20,8)
(12,8)
vs
vt
2017/11/11
管理运筹学课程组 ftp://
9
解:算法过程
第一轮,k= 0