|
||
在实际网络问题中，不仅要考虑从
到 的流量最大，而且还要考虑可行流在网络传送过程中的费用问题，这就是网络的最小费用、最大流问题。最小费用最大流问题的一般提法：已知容量网络D=（V，A，C），每条弧（ 
, ）除了已给出容量
外，还给出了单位流量的传输费用
≥0，记作D=（V，A，C，B），其中
∈B。要在费用、容量网络D中寻找
→ 的最大流
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 ′是最大流时，它就是我们所要求的最小费用最大流。 上述命题为我们提供了寻找最小费用最大流的思路：先找一个最小费用可行流，再找出关于该可行流的最小费用增广链，沿此链调整流量，则得到一个新的流量增大了的最小费用流，然后对新的最小费用流重复上述方法，一直调整到网络的最大流出现为止，便得到了所考虑网络的最小费用最大流。 由于
≥0，所以 f =｛0｝必是流量为0的最小费用流。这样，总可以从 f =｛0｝开始算起。一般地，如果已知 f 是流量为v(f )的最小费用流，余下的问题就是如何去寻找关于
f 的最小费用增广链。 为此，构造一个有向费用网络W（ f ），它的顶点与原网络完全相同，而把原网络中的每一条弧（
,）分解成方向相反的两条弧，即（
,）和（
, ）。并按如下规则定义W（
f ）中弧的权数：
|
||
| 上述定义式的含义是：在增广链的前向弧上，当
＜
时，可以增加流量，其单位费用为
，当
=
时不能再增加流量，否则要花费高昂的代价，因此单位费用为+∞。在增广链的后向弧上，当＞0时，减少一个单位流量可节约的费用为
，当 =0时，由于无法减少流量，因此单位费用亦为+∞。 经上述处理后，在费用、容量网络中寻找关于 f 的最小费用增广链问题，就转化为在有向费用网络W（ f ）中寻找从
→ 以费用表示的最短路。因是求最短路，故
= +∞的弧可以从网络中省略。 |
||
| 具体算法步骤如下： ⑴取0流为初始最小费用可行流 
，即v(
)=0；⑵若在k-1步（k=1,2, …）得最小费用流  ,则构造关于的有向费用网络W（）;⑶在网络W（ ）中寻找从
→ 的最短路。若不存在最短路，则已是最小费用最大流，计算停止。否则转⑷；⑷在原网络图中与这条最短路相应的增广链上，对流量v( )进行调整，调整量为： 调整后得新的最小费用流  ，其流量为v()+θ。用代替返回⑵
。 |
||
例6 给定费用、容量网络图（a），弧旁数字为（
，
）试求该网络的最小费用最大流。
|
||
解： ⑴ 取0流为初始最小费用可行流
，即v(
)=0；⑵ 构造关于 的有向费用网络W（），如图（b）所示。 |
||
⑶可求得W（）的最短路为
→ →
→ ，图中以双线表示。在原网络图中与这条最短路相应的增广链｛
｝上，对流量v()进行调整，调整量θ=
min｛8，5，7｝=5，从而得新的最小费用流
，其流量v()=5，如图（c）所示。
的有向费用网络W（），如图（d）所示。
|
||
⑸可求得W（）的最短路为：
→ →
，图中以双线表示。在原网络图中与这条最短路相应的增广链｛
｝上，对流量v(f 1)进行调整，调整量θ= min｛10，7-5｝=2，从而得新的最小费用流  ，其流量：
v()=7，如图（e）所示。
|
||
⑹构造关于的有向费用网络W（），如图（f）所示。
|
||
⑺可求得W（）的最短路为：
→ →
→ ，图中以双线表示。在原网络图中与这条最短路相应的增广链｛
｝上，对流量v( )进行调整，调整量θ=
min｛8-5，10，4｝=3，从而得新的最小费用流
，其流量： v(
)=10，如图（g）所示。
|
||
（8）构造关于的有向费用网络W（），如图（h）所示。
|
||
（9）可求得W（）的最短路为：
→ →
→ →
，图中以双线表示。在原网络图中与这条最短路相应的增广链｛
｝上，对流量v()进行调整，调整量θ=
min｛10-2，10-3，4-3，5｝=1，从而得新的最小费用流  ，其流量v(
)=11，如图（i）所示。
|
||
（10）构造关于的有向费用网络W（），如图（j）所示。
|
||
由于在W（）中无法找到从
→ 的最短路，所以
就是该网络的最小费用最大流，流量v(
)=11，其分布情况如图（i）所示。它对应的总费用为：b()=4×3+1×7+1×8+2×4+2×4+3×4=55
|
||
§
5 最小费用最大流问题 
