图论模型的LINGO算法.ppt

图7-6给出的有一个源和一个汇的网络. 网络 中每一条边 有一个容量 , 除此之外, 对边 还有一个通过边的流(Flow), 记为 . 显然, 边 上的流量 不会超过该边上的容量 , 即 因此，该网络的最大流为14，F的值对应弧上的流，如图7-7所示, 其中网络中的第一个数为容量，第二个数为流量. 在上面的程序中，采用稀疏集的编写方法，下面介绍的程序编写方法是利用邻接矩阵，这样可以不使用稀疏集的编写方法，更便于推广到复杂网络. MODEL: 1]sets: 2] nodes/s,1,2,3,4,t/; 3] arcs(nodes, nodes): p, c, f; 4]endsets 5]data: 6] p = 0 1 1 0 0 0 7] 0 0 1 1 0 0 8] 0 0 0 0 1 0 9] 0 0 1 0 0 1 10] 0 0 0 1 0 1 11] 0 0 0 0 0 0; 12] c = 0 8 7 0 0 0 13] 0 0 5 9 0 0 14] 0 0 0 0 9 0 15] 0 0 2 0 0 5 16] 0 0 0 6 0 10 17] 0 0 0 0 0 0; 18]enddata 19]max = flow; 20]@for(nodes(i) | i #ne# 1 #and# i #ne# @size(nodes): 21] @sum(nodes(j): p(i,j)*f(i,j)) 22] = @sum(nodes(j): p(j,i)*f(j,i))); 23]@sum(nodes(i):p(1,i)*f(1,i)) = flow; 24]@for(arcs:@bnd(0, f, c)); END 在上述程序中，由于使用了邻接矩阵，当两点之间无弧时，定义弧容量为零.计算结果与前面程序的结果完全相同，这里就不再列出了. § 7.2.3 最小费用最大流问题 例7.13（最小费用最大流问题）（续例7.11）由于输油管道的长短不一，或地质等原因，使每条管道上运输费用也不相同，因此，除考虑输油管道的最大流外，还需要考虑输油管道输送最大流的最小费用，图7-8所示是带有运费的网络，其中第1个数字是网络的容量，第2个数字是网络的单位运费. 例7.13所提出的问题就是最小费用最大流问题(Minimum-cost maximum flow)，即考虑网络在最大流情况下的最小费用.例7.12虽然给出了例7.11最大流一组方案，但它是不是关于费用的最优方案呢？这还需要进一步讨论. 1. 最小费用流的数学表达式 min s.t. 其中 当 为网络的最大流进，数学规划 表 示的就是最小费用最大流问题. 2. 最小费用流的求解过程 例7.14（继例7.13）用LINGO软件求解例7.13. 解： 按照最小费用流的数学规划写出相应的LINGO程序，程序名： exam0714.lg4. MODEL: 1]sets: 2] nodes/s,1,2,3,4,t/:d; 3] arcs(nodes, nodes)/ 4] s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, u, f; 5]endsets 6]data: 7] d = 14 0 0 0 0 -14; 8] c = 2 8 5 2 3 1 6 4 7; 9] u = 8 7 5 9 9 2 5 6 10; 10]enddata 11]min=@sum(arcs:c*f); 12]@for(nodes(i) | i #n