实用数学方法：解决最小费用最大流问题

在上一节中，利用Ford-Fulkerson算法设计运输方案时，我们考虑的仅仅是流量，但是在实际的网络应用中，除了需要考虑流量外，还需要考虑运输的费用问题。尤其要两者兼顾，于是就出现了最小费用最大流问题。这就要求我们在保证网络最大流的情况下，找到总的运输费用最小的运输方案。

给定网络D =〈V ,A, C〉，每一条有向弧(i,j)上的权，除了已给容量Cij外，还给了一个单位流量的费用bij=b (i ,j)≥0。所谓最小费用最大流问题，是求一个从源点到汇点的最大流f，且使费用b( f)=∑bi j fij 最小。

解决最小费用最大流问题的算法是由Busacker-Gowan提出的，其基本思想是先找到一个最小费用可行流，再找出关于该可行流的最小费用增广路径，沿此路径调整流量，则得到一个新的流量增大了的最小费用流，然后对新的最小费用流重复上述方法，一直调整到出现网络最大流为止，便得到了所考虑的最小费用最大流。

算法基本过程：

第一步：求出从源点到汇点的最小费用通路。

第二步：对该通路分配最大可能的流量：令f′=min{C (i ,j )}，通路上所有边的容量相应减少f′。这时，对于通路上的饱和边，其单位流费用相应改为∞。

第三步：该通路上每一条弧变成方向相反的两条弧(i, j ),(j ,i)，令Cji=f ′,dji=-dij。

第四步：在构成的新网络中，重复上述步骤，直到找不到从s到t的最小费用通路为止。

例1 如图3.5.1所示的是石油公司运输管道网络，使用这个网络可以把石油从采地① 输送到销售地⑧，由于输送距离长短不一，每段管道除了有不同的容量Cij限制外，还有不同的单位流量费用bij，所以，网络中每条弧的权为（Ci j,bij)，如果使用这个网络从采地①到销售地⑧输送石油，问怎样才能输送最多的石油并使输送费用最小？(www.xing528.com)

图3.5.1　石油公司运输管道网络

解 应用算法编写MATLAB程序如下：

用C表示容量矩阵，b表示单位流量费用矩阵，f表示最小费用最大流矩阵，wf表示最大流量，zwf表示最小费用

求得最大流的最小费用为164。