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

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

data：
d=14 0 0 0 0 -14；

c=0； u=0；
enddata
calc：
c(1，2)=2；c(1，4)=8；

c(2，3)=2；c(2，4)=5；
c(3，4)=1；c(3，6)=6；
c(4，5)=3；c(5，3)=4；c(5，6)=7；

u(1，2)=8；u(1，4)=7；
u(2，3)=9；u(2，4)=5；
u(3，4)=2；u(3，6)=5；

u(4，5)=9；u(5，3)=6；u(5，6)=10；
endcalc
min=@sum(arcs：c*f)；

@for(nodes(i)：@sum(nodes(j)：f(i，j))-@sum(nodes(j)：f(j，i))=d(i))；
@for(arcs：@bnd(0，f，u))；
end

二、求最小费用流的一种方法—迭代法

这里所介绍的求最小费用流的方法叫做迭代法。这个方法是由 Busacker 和
Gowan 在 1961 年提出。其主要步骤如下：

1. 求出从发点到收点的最小费用通路 μ(s，t)。
2. 对该通路 μ(s，t) 分配最大可能的流量

并让通路上的所有边的容量相应减少 这时，对于通路上的饱和边，其单位
流费用相应改为∞

3. 作该通路 上所有边 (i， j) 的反向边 ( j，i) 。令

217