总费用b(f)比b(f)增加多少？ .在前向弧上f=+1,在后向弧上f后1， bW)bW)=∑b0f)+∑b,ff)] ->bi >bu 即沿着关于可行流∫的增广链，增加一个单位运量时，所增加的总 费用是上所有前向弧的费用之和减去所有后向弧的费用和。 我们称此费用为该增广链的费用。 可以证明：若f是流量为()的所有可行流中费用最小者/而u 是关于f的所有增广链中费用最小的增广链，那么沿着法调整f, 得到的可行流f'就是流量为f)的所有可行流中的最小费用流。这 样，当f'是最大流时，它就是我们所要求的最小费用最木流。 上述命题为我们提供了寻找最小费用最大流的思路：先我个 最小费用可行流，再找出关于该可行流的最小费用增广链，沿此链 调整流量，则得到一个新的流量增大了的最小费用流，然后对新的 最小费用流重复上述方法，一直调整到网络的最大流出现为止，使 得到了所考虑网络的最小费用最大流。总费用b(f′)比b(f )增加多少？ ∵在前向弧μ＋上 f ij′= f ij+1，在后向弧μ -上 f ij′= f ij-1， ∴ b(f′)-b(f )=[∑bij（f ij ′- f ij）+∑bij（f ij ′- f ij）] = ∑bij -∑bij 即沿着关于可行流 f 的增广链μ，增加一个单位运量时，所增加的总 费用是μ上所有前向弧的费用之和减去所有后向弧的费用之和。 我们称此费用为该增广链μ的费用。 可以证明：若 f 是流量为v(f )的所有可行流中费用最小者，而μ 是关于f 的所有增广链中费用最小的增广链，那么沿着μ去调整 f ， 得到的可行流f ′就是流量为v(f ′)的所有可行流中的最小费用流。这 样，当 f ′是最大流时，它就是我们所要求的最小费用最大流。 上述命题为我们提供了寻找最小费用最大流的思路：先找一个 最小费用可行流，再找出关于该可行流的最小费用增广链，沿此链 调整流量，则得到一个新的流量增大了的最小费用流，然后对新的 最小费用流重复上述方法，一直调整到网络的最大流出现为止，便 得到了所考虑网络的最小费用最大流。 μ＋ μ - μ＋ μ -