第五节 最小费用最大流问题       (1) (2) (3) (4) (5)
    在实际网络问题中，不仅要考虑从到的流量最大，而且还要考虑可行流在网络传送过程中的费用问题，这就是网络的最小费用、最大流问题。
    最小费用最大流问题的一般提法：已知容量网络D=（V，A，C），每条弧（ ,）除了已给出容量外，还给出了单位流量的传输费用 ≥0，记作D=（V，A，C，B），其中 ∈B。要在费用、容量网络D中寻找→的最大流 f =｛｝，且使流的总传输费用：
    b(f)= ∑ 最小。
    从上一讲可知，最大流的求法就是在容量网络上从某个可行流出发，设法找到一条从→的增广链，然后沿着此增广链调整流量，作出新的流量增大了的可行流。在这个新的可行流基础上再寻找它的增广链。如此反复进行，直至再找不出增广链时，就得到了该网络的最大流。
    现在要寻求最小费用的最大流，我们首先考察一下，当沿着一条关于可行流 f 的增广链μ，以θ=1调整 f 得到新的可行流 f′时，总费用b(f′)比b(f )增加多少？
    ∵在前向弧μ＋上 ′= +1，在后向弧μ-上 ′= -1，
    ∴ b(f′)-b(f )=[∑（′- ）+∑（′- ）]= ∑ -∑
    即沿着关于可行流 f 的增广链μ，增加一个单位运量时，所增加的总费用是μ上所有前向弧的费用之和减去所有后向弧的费用之和。 我们称此费用为该增广链μ的费用。
    可以证明：若 f 是流量为v(f )的所有可行流中费用最小者，而μ是关于f 的所有增广链中费用最小的增广链，那么沿着μ去调整 f ， 得到的可行流f ′就是流量为v(f ′)的所有可行流中的最小费用流。这样，当 f ′是最大流时，它就是我们所要求的最小费用最大流。
    上述命题为我们提供了寻找最小费用最大流的思路：先找一个最小费用可行流，再找出关于该可行流的最小费用增广链，沿此链调整流量，则得到一个新的流量增大了的最小费用流，然后对新的最小费用流重复上述方法，一直调整到网络的最大流出现为止，便得到了所考虑网络的最小费用最大流。