第五节 最小费用最大流问题1 PPT 课件一、基本概念1、什么是最小费用最大流问题？ 对每一条弧都给出单位流量费用的容量网络D=（V，A，B）（称为费用容量网络）中，求取最大流X，使输送流量的总费用 C（X）=cijxij为最小的一类优化问题。 其中，bij表示弧（vi，vj）上的容量，xij表示弧（vi，vj）上的流量，cij表示弧（vi，vj）上通过单位流量所花费的费用。2 PPT 课件2、最小费用流 对一费用容量网络，具有相同流量 f 的可行流中，总费用最小的可行流称为该费用容量网络关于流量 f 的最小费用流，简称流量为 f 的最小费用流。3 PPT 课件从上节可知，寻求最大流的方法是从某个可行流出发，找到关于这个流的一条增广链 。沿着调整f，对新的可行流试图寻求关于它的增广链，如此反复直至最大流。现在，要寻求最小费用的最大流，我们首先考察一下，当沿着一条关于可行流f的增广链 ，以=1调整f，得到新的可行流f（显然v（f）=v（f）+1）时，C（f）比C（f）增加多少( 输送流量的总费用 )？4 PPT 课件3、增广链的费用 当沿着一条关于可行流 X 的增广链（流量修正路线），
