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

Mathematical Modeling Algorithms and Applications
数学建模算法与应用

图 8-3 最小费用最大流问题

解 按照最小费用流的数学规划写出相应的 LINGO 程序如下：
model：

sets：
nodes/s，1，2，3，4，t/：d；
arcs(nodes，nodes)/s 1，s 3，1 2，1 3，2 3，2 t，3 4，4 2，4 t/：c，u，f；
endsets

data：
d=14 0 0 0 0 -14； ! 最大流为 14；
c=2 8 2 5 1 6 3 4 7；
u=8 7 9 5 2 5 9 6 10；

enddata
min=@sum(arcs：c*f)；
@for(nodes(i)：@sum(arcs(i，j)：f(i，j))-@sum(arcs(j，i)：f(j，i))=d(i))；

@for(arcs：@bnd(0，f，u))；
end
求得最大流的最小费用是 205，而原最大流的费用为 210 单位，原方案并不
是最优的。

类似地，可以利用赋权邻接矩阵编程求得最小费用最大流。LINGO 程序如下：
model：
sets：

nodes/s，1，2，3，4，t/：d；
arcs(nodes，nodes)：c，u，f；
endsets

216