最大流的网络,可看作为辅送一般货物的运输网络,此时,最大流问题仅表明运输网络运输货物的能力,
但没有考虑运送货物的费用。在实际问题中,运送同样数量货物的运输方案可能有多个,因此从中找一个
输出费用最小的的方案是一个很重要的问题,这就是最小代价流所要讨论的内容。
最小费用最大流问题的模型E
给定网络 ,,,,,,每一弧属于 上,除了已给容量
外,还给了一个单位流
量的费用 简记为
。所谓最小费用最大流问题就是要求一个最大流 ,使得流的总输送费用
取最小值。
用对偶法解最小费用最大流问题E
定义:已知网络 ,,,,,, 是 上的一个可行流, 为 到 关于流 的可增广路
径,称
(
)
(
)
为路径 的费用。
若 是从 到 所有可增广路径中费用最小的路径,则称 为最小费用可增广路径。
定理:若 是流量为 的最小费用流, 是关于 的从 到 的一条最小费用可增广路径,则 经过
调整流量 得到新的可行流 记为 ,一定是流量为 的可行流中的最小费用流。
对偶法的基本思路
取 !"#
$ 寻找从 到 的一条最小费用可增广路径 。
若不存在 ,则 为 中的最小费用最大流,算法结束。
若存在 ,则用求最大流的方法将 调整成 ,使 ,并将 赋值给 ,转②。
%迭代法求最小费用可增广路径
在前一节中,我们已经知道了最大流的求法。在最小费用最大流的求解中,每次要找一条最小费用的增
广路径,这也是与最大流求法唯一不同之处。于是,对于求最小费用最大流问题余下的问题是怎样寻求关
于 的最小费用增广路径 。为此,我们构造一个赋权有向图 &,它的顶点是原网络 中的顶点,而把
中每一条弧,变成两个相反方向的弧,和,。定义 中的弧的权如下:
如果
'
,则 &
;如果
,则 &
((
如果
)",则 &
;如果
,则 &
((
于是在网络 中找关于 的最小费用增广路径就等价于在赋权有向图 &中,寻求从 到 的最短路径。
求最短路有三种经典算法,它们分别是 *+,- 算法、./(01 算法和迭代算法(,1 算法)。由于在本问
题中,赋权有向图 &中存在负权,故我们只能用后两种方法求最短路,其中对于本问题最高效的算法是
迭代算法。为了程序的实现方便,我们只要对原网络做适当的调整。将原网络中的每条弧,变成两
条相反的弧:
前向弧,其容量
和费用
不变,流量为
;
后向弧,其容量 " 和费用
,流量为
。
事实上,对于原网络的数据结构中,这些单元已存在,在用标号法求最大流时是闲置的。这样我们就不
必产生关于流 的有向图 &。同时对判断的流量可否改时,可以统一为判断是否“
'
2。因为对
于后向弧,,若 3)",则
'"
。
例 2:求输送量最大且费用最小的运输方案?
如下图是一公路网, 是仓库所在地(物资的起点),4 是某一工地(物资的终点)每条弧旁的两个数
字分别表示某一时间内通过该段路的最多吨数和每吨物资通过该段路的费用。
评论1