null第五节 最小费用流问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
第五节 最小费用流问题什么是最小费用流问题？
求解最小费用流的赋权图法
求解最小费用流的复合标号法null 在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。null 设一个网络D=（V1，A，C），对于每一个弧(vi,vj)∈A,给定一个单位流量的费用bij>=0，网络系统的最小费用最大流问题，是指要寻求一个最大流f，并且流的总费用b(f)=∑bijfij达到最小。
null在一个网络D中，当沿可行流f的一条增广链μ，以调整量θ=1改进f，得到的新可行流f’的流量，有v(f’)=v(f)+1，而此时总费用b(f’)比b(f)增加了
b(f’)-b(f)=∑bij(f’ij-fij)- ∑bij(fij-f’ij)= ∑bij-∑bij
μ+ μ- μ+ μ-
将∑bij-∑bij叫做这条增广链的费用。null 如果可行流在流量为v(f)的所有可行流中的费用最小，并且是关于f的所有增广链中的费用最小的增广链。那么沿增广链μ调整可行流f，得到的新可行流f’，也是流量为v(f’)的所有可行流中的最小费用流。
依次类推，当f’是最大流时，就是所要求的最小费用最大流。null 显然，零流f={0}是流量为0的最小费用流。一般地，寻求最小费用流，总可以从零流f={0}开始。下面的问题是：如果已知f是流量为v(f)的最小费用流，那么就要去寻找关于f的最小费用增广链。
对此，重新构造一个赋权有向图M(f)，其顶点是原网络D的顶点，而将D中的每一条弧(vi,vj)变成两个相反方向的弧（vi,vj）和(vj,vi)，并且定义M(f)中弧的权wij为：null bij,当fij
0
wij=
+∞,当fij=0
并且将权为+∞的弧从M(f)中略去。
即当 0 < fij < cij 时，成为2条方向相反，权绝对值相等的弧。否则不变。null 这样，在网络D中寻找关于f的最小费用增广链就等于价于在M(f)中寻求从vs到vt的最短路。
算法开始，取零流f(0) ={0}.一般地，如果在第K-1步得到最小费用流f(K-1),则构造图M（f(K-1)）。在图M（f(K-1)）中，寻求从vs到vt的最短路。如果存在最短路，则f(K-1)就是最小费用最大流。如果存在最短路，则在原网络D中得到相对应（一一对应）的增广链μ0 null 在增广链μ上对f(K-1)进行调整，取调整量θ=min{min((cij-f(k-1)ij),min(f(k-1)ij)}.
μ+ μ-
令
f(k-1)ij+θ，在μ+上
f(k)ij = f(k-1)ij-θ，在μ-上
其他的不变。
得到一个新的可行流f(k)，在对f(k)重复以上的步骤，直到D中找不到相对应的增广链时为止。例略null 例8.9:求图8-24 所示网络中的最小费用最大流，弧旁的权是（bij,cij）.
(bij,Cij)(1,8)vtv3v2v5v1(3,10)(2,4)(6,2)(1,7)(4,10)(2,5)null 解：
（1）取初始可行流为零流f(0)={0},构造赋权有向图M(f(0)),求出从vs到vt的最短路(vs,v2,v1,vt),如图8.25a中双箭头所示。
(1)VtV3V2VsV1(3)(2)(6)(1)(4)(2)M(f(0))null （2）在原网络D中，与这条最短路相对应的增广链为μ=（vs,v2,v1,vt）。
（3）在μ上对f(0)={0}进行调整，取θ=5，得到新可行流f(1)，如图8.25b所示。按照以上的算法，依次类推，可以得到f(1)，f(2)，f(3)，f(4)，流量分别为5，7，10，11，并且分别构造相对应的赋权有向图M(f(1)),(Mf(2)),(Mf(3)),(Mf(4))。由于在Mf(4)中已经不存在从vs到vt的最短路，因此，可行流f(4)，v(f(1))=11是最小费用最大流。null(5)vtv3v2vsv1(0)(0)(0)(5)(0)(5)图8.25bf(1),v(f(1))=5null(1)vtv3v2vsv1(3)(2)(6)(1)(4)(2,5)M(f(1))图8.25c(-1)(-1)null(5)vtv3v2vsv1(0)(0)(7)(2)(5)(0)图8.25df(2),v(f(2))=7null(1)vtv3v2vsv1(3)(2)(6)(-1)(4)(-2)(-1)(-4)M(f(2))图8.25enull(8)vtv3v2vsv1(3)(3)(0)(7)(2)(5)图8.25ff(3),v(f(3))=10null(-1)vtv3v2vsv1(3)(2)(6)(-1)(4)(-2)(-4)M(f(2))图8.25g(-2)(-3)null(8)vtv3v2vsv1(4)(4)(0)(7)(3)(4)图8.25hf(4),v(f(4))=11null(-1)vtv3v2vsv1(3)(-2)(6)(-1)(4)(2)(-4)M(f(4))图8.25i(-2)(-3)一、什么是最小费用流一、什么是最小费用流给定网络N=(V,A,c,b)和经过网络的流量v，求流在网络上的最佳分布，使总费用最小。二、求解最小费用流的赋权图法二、求解最小费用流的赋权图法增广链费用，最小费用增广链。
对于最小费用可行流，沿最小费用增广链调整流，可使流增加，并保持流费用最小。
给定初始最小费用可行流，求最小费用增广链，若存在，则沿该增广链调整网络流，直到达到给定的网络流或不存在增广链为止，后一种情况为最小费用最大流。
若给定网络流超过最大流，则不可能实现。如何求最小费用增广链？如何求最小费用增广链？生成最小费用可行流的剩余网络：
将饱和弧反向
将非饱和非零流弧加一反向弧
零流弧不变
所有正向弧的权为该弧的费用，反向弧的权为该弧费用的相反数
剩余网络又叫长度网络，本教材叫做赋权图。
最小费用增广链对应剩余网络的最短路最小费用流的实例最小费用流的实例第一次剩余网络最短路第一次剩余网络最短路第一次调整网络流第一次调整网络流第二次剩余网络最短路第二次剩余网络最短路第二次调整网络流第二次调整网络流第三次剩余网络的最短路第三次剩余网络的最短路第三次调整网络流第三次调整网络流剩余网络已不存在最短路剩余网络已不存在最短路已获最小费用最大流已获最小费用最大流最小费用最大流
若规定网络流为7，则第二次调整量应为2，而不是3。见图。
最小费用与网络流的关系是凸的，即随着流的增加，单位流的费用在增加。请见下页的图。null三、求解最小费用流的复合标号法三、求解最小费用流的复合标号法将求最短路的标号法和求最大流的标号法相结合，即在求增广链的标号后加上一个距离标号，成为一组三标号，距离标号应采用修正标号法。并采用T标号和P标号的记法。
下面以前例为例来说明符合标号的应用。第一次迭代第一次迭代第二次迭代第二次迭代第三次迭代第三次迭代最后结果最后结果提示思考提示思考最短路问题、最大流问题可以看作最小费用流的特殊情况，请
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
如何将最小费用流问题特化成最短路问题和最大流问题？
运输问题和指派问题可以用最小费用流问题建模，请将它们化为最小费用流问题。
浙公网安备 33021202002483