[金牌原创]7.6 最小费用流

《[金牌原创]7.6 最小费用流》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、7.6最小费用流7.6.1基本概念及定理（1）流的费用定义7.12对于一个可行流f=｛fij｝来说，如果网络G=(V,A,C,W)中，对于每条弧aij∈A，都有一个单位流费用ωij，则流的费用定义为：7/19/20211管理运筹学课程组ftp://211.71.69.239（2）最小费用流定义网络G=(V,A,C,W)中，对于每一流值为V(f)的可行流f来说，都存在一个流的费用W(f)，使W(f)为最小的可行流，则称为最小费用流。最小费用流的数学定义如下：目标函数：约束条件：（1）每一条弧；（2）；（3）；（4）；其中：V(f)——目标流

2、值；Cij——能力；ωij——单位费用；Vs——发点；Vt——收点。7/19/20212管理运筹学课程组ftp://211.71.69.239（3）链的费用与最小费用增广链定义7.14已知网络G=(V,A,C,W)，f是G的可行流，μ为从vs到vt的关于f的增广链，称为链的μ的费用。若μ*是vs到vt所有增广链中费用最小的链，则称μ*为最小费用增广链。（4）最小费用流的有关定理定理7.10若f是流量为V（f）的最小费用流，μ是关于f的从vs到vt的一条最小费用增广链，则f经过μ调整流量得到新的可行流f`，f`一定是流量为V(f)+θ的可行

3、流中的最小费用流。7/19/20213管理运筹学课程组ftp://211.71.69.2397.6.2最小费用流算法及算例基本思想：从某个初始的最小费用可行流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）上

4、寻找从vs到vt的费用最小的增广链μ1，再在μ1按上述方法进行流量调整，如此反复，直到最小费用可行流的流值达到V目标为止。7/19/20214管理运筹学课程组ftp://211.71.69.239从算法思路来看，关键在于如何寻找从vs到vt的最小费用增广链，为了求最小费用我们首先想到利用最短路算法，但是路和链对弧的连接方式的要求是有差异的。为此，为了能利用最短路算法，对于网络中，已知可行流f，构造一个关于f的赋权有向网络L（f），使得在G中从vs到vt的最小费用增广链问题，等价于L（f）中求从vs到vt的最短路问题。7/19/20215管

5、理运筹学课程组ftp://211.71.69.239L（f）的构造方法如下：L（f）中的顶点是原网络中的点，而把G中的每一条弧（vi，vj）变成两个方向相反的弧（vi，vj）和（vj，vi）。定义L（f）中弧（vi，vj）和（vj，vi）的权lij和lji为：7/19/20216管理运筹学课程组ftp://211.71.69.239求流量为V目标的最小费用流的算法第一步：k=0，从一流量为（≤V目标）为最小费用初始可行流（一般取零流）开始。第二步：构造，在中求从vs到vt的费用最小的路，若没有从vs到vt的最短路，则为最大流，不存在流量为

6、V目标的最小费用流，算法结束，否则转下一步。第三步：在G中与这条最短路相应的增广链μk上，计算若θk≤V目标-，则在链μk上按最大流流量调整方法增广流量θk，得到新流，令k=k+1，转步骤2，否则当θk≥V目标-,则在链上按最大流流量调整方法增广流量V目标-，得到新流，新流就是所求的流量为V目标的费用最小的可行流。算法结束。7/19/20217管理运筹学课程组ftp://211.71.69.239例求下图所示的网络G中，求从vs到vt的目标流值为25的最小费用流，弧上括号内的数字第一个为容量，第二个为弧上单位流的费用。(17,3)(20,

7、5)(15,4)V2(18,3)(14,5)V3V1(20,8)(12,8)vsvt7/19/20218管理运筹学课程组ftp://211.71.69.239解:算法过程第一轮，k=0取={0}开始，用DijksTra算法求的中vs到vt的最短路（vs,v1,v3,vt），在网络G中相应的增广链μ0=(vs,v1,v3,vt)上用最大流算法进行流的调整。μ0+={（vs,v1）、（v1,v3），（v3,vt）}μ0-=φ得到f(1)的如图（b）所示。354V235V3V188vsvt(a)L(f(0))7/19/20219管理运筹学课程组

8、ftp://211.71.69.239第二轮，k=1作图L(f(1))如图（c）所示，由于弧上有负权，所以求最短路不能用DijksTra算法，可用逐次逼近法，最短路为(vs,v3,vt)，在G