Page 225 - 数学建模算法与应用

第八章 图与网络模型及方法应用

圈。则对于任何顶点 v ，C － v 是在 G － v 中的 Hamilton 轨，因而也是 G － v
的生成树。由此推知：若 T 是 G－v 中的最优树，同时 e 和 f 是和 v 关联的两条边，
并使得 w(e) ＋ w( f ) 尽可能小，则 w(T) ＋ w(e) ＋ w( f ) 将是 w(C) 的一个上界。

第七节 最小费用流问题及其算法的应用

一、最小费用流

上面我们介绍了一个网络上最短路以及最大流的算法，但是还没有考虑到网
络上流的费用问题，在许多实际问题中，费用的因素很重要。例如，在运输问题
中，人们总是希望在完成运输任务的同时，寻求一个使总的运输费用最小的运输

方案。这就是下面要介绍的最小费用流问题。在运输网络 中，设
是定义在 A 上的非负函数，它表示通过弧 (i， j) 单位流的费用。所谓最小费用
流问题就是从发点到收点怎样以最小费用输送一已知量为 v( f ) 的总流量。
最小费用流问题可以用如下的线性规划问题描述：

显然，如果 v( f )= 最大流 则本问题就是最小费用最大流问题。如
果
则本问题无解。
例 （最小费用最大流问题）（续上例 ）由于输油管道的长短不一或地质等
原因，使每条管道上运输费用也不相同，因此，除考虑输油管道的最大流外，还
需要考虑输油管道输送最大流的最小费用。图 8-3 所示是带有运费的网络，其中

第 1 个数字是网络的容量，第 2 个数字是网络的单位运费。

215