§5最小费用最大流 在实际网络问题中，不仅要考虑从v到v,的流量最大，而且还 要考虑可行流在网络传送过程中的费用问题，这就是网络的最小费 用、最大流问题。 最小费用最大流问题的一般提法：已知容量网络D=(V,A,①) 每条弧(，V)除了已给出容量c:外，还给出了单位流量的传输费 用b≥0，记作D=(V,A,C,B),其中b∈B。要在费用、容量 网络D中寻找V,→，的最大流f={f}，且使流的总传输费用： b(f)=∑bf最小。 从上一讲可知，最大流的求法就是在容量网络上从某个可行流 出发，设法找到一条从，→？，的增广链，然后沿着此增广链调整流 量，作出新的流量增大了的可行流。在这个新的可行流基础再 找它的增广链。如此反复进行，直至再找不出增广链时，就得到了 该网络的最大流。 现在要寻求最小费用的最大流，我们首先考察一下，当沿着 条关于可行流f的增广链，以01调整f得到新的可行流f时， §5 最小费用最大流 ❖ 在实际网络问题中，不仅要考虑从vs 到vt 的流量最大，而且还 要考虑可行流在网络传送过程中的费用问题，这就是网络的最小费 用、最大流问题。 ❖最小费用最大流问题的一般提法：已知容量网络D=（V，A，C）， 每条弧（vi ,vj）除了已给出容量cij 外，还给出了单位流量的传输费 用bij ≥0，记作D=（V，A，C，B），其中 bij ∈B。要在费用、容量 网络D中寻找 vs →vt 的最大流 f =｛f ij｝，且使流的总传输费用： b(f )= ∑bij f ij 最小。 ❖ 从上一讲可知，最大流的求法就是在容量网络上从某个可行流 出发，设法找到一条从vs →vt 的增广链，然后沿着此增广链调整流 量，作出新的流量增大了的可行流。在这个新的可行流基础上再寻 找它的增广链。如此反复进行，直至再找不出增广链时，就得到了 该网络的最大流。 ❖ 现在要寻求最小费用的最大流，我们首先考察一下，当沿着一 条关于可行流 f 的增广链μ，以θ=1调整 f 得到新的可行流 f′时