初等数学方法建模
§8 最小费用流及其求法
8.1 最小费用流
上面我们介绍了一个网络上最短路以及最大流的算法，但是还没有考虑到网络上流的费用问题，在许多实际问题中，费用的因素很重要。例如，在运输问题中，人们总是希望在完成运输任务的同时，寻求一个使总的运输费用最小的运输方案。这就是下面要介绍的最小费用流问题。
在运输网络N?(s,t,V,A,U)中，设cij是定义在A上的非负函数，它表示通过弧(i,j)单位流的费用。所谓最小费用流问题就是从发点到收点怎样以最小费用输送一已知量为v(f)的总流量。
最小费用流问题可以用如下的线性规划问题描述：
min(i,j)?A?cijijf
?v(f),i?s?fji???v(f),i?t ，
?0,i?s,t?s.t.
ijj:(i,j)?A?f?j:(j,i)?A? 0?fij?uij,?(i,j)?A.
显然，如果v(f)?最大流v(fmax)，则本问题就是最小费用最大流问题。如果v(f)?v(fmax)，则本问题无解。
8.2 求最小费用流的一种方法—迭代法
这里所介绍的求最小费用流的方法叫做迭代法。这个方法是由Busacker和Gowan在1961年提出的。其主要步骤如下：
(i)求出从发点到收点的最小费用通路?(s,t)。 (ii)对该通路?(s,t)分配最大可能的流量：
f?min{uij}
(i,j)??(s,t)并让通路上的所有边的容量相应减少f。这时，对于通路上的饱和边，其单位流费用相应改为?。
(iii)作该通路?(s,t)上所有边(i,j)的反向边(j,i)。令
uji?f，cji??cij
(iv)在这样构成的新网络中，重复上述步骤(i)，(ii)，(iii)，直到从发点到收点的全部流量等于v(f)为止（或者再也找不到从s到t的最小费用道路）。
41