数学建模最大流问题lingo求解程序

图论建模最大流问题Lingo求解法图论建模实例现需要将城市s的石油通过管道运送到城市t，中间有4个中转站和,城市与中转站的连接以及管道的容量如图所示，求从城市s到城市t的最大流.123,,vvv4v图论建模MODEL:1]sets:2]nodes/s,1,2,3,4,t/;3]arcs(nodes,nodes)/4]s,1s,21,21,32,43,23,t4,34,t/:c,f;5]endsets6]data:7]c=8759925610;8]enddata9]max=flow;程序的第10]到12]行表示约束(23),第13]行表示有界约束(24).解：相应的LINGO程序为图论建模LINGO软件的计算结果（只保留流值f）如下:Globaloptimalsolutionfoundatiteration:6Objectivevalue:14.00000VariableValueReducedCostFLOW14.000000.000000F(S,1)7.0000000.000000F(S,2)7.0000000.000000F(1,2)2.0000000.000000F(1,3)5.0000000.000000F(2,4)9.000000-1.000000F(3,2)0.0000000.000000F(3,T)5.000000-1.000000F(4,3)0.0000001.000000F(4,T)9.0000000.000000图论建模因此，该网络的最大流为14，F的值对应弧上的流，如下图所示,其中网络中的第一个数为容量，第二个数为流量.在上面的程序中，采用稀疏集的编写方法，下面介绍的程序编写方法是利用邻接矩阵，这样可以不使用稀疏集的编写方法，更便于推广到复杂网络.图论建模MODEL:1]sets:2]nodes/s,1,2,3,4,t/;3]arcs(nodes,nodes):p,c,f;4]endsets5]data:6]p=0110007]0011008]0000109]00100110]00010111]000000;图论建模12]c=08700013]00590014]00009015]00200516]000601017]000000;18]enddata19]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在本程序中，由于使用了邻接矩阵，当两点之间无弧时，定义弧容量为零，计算结果与前面程序的结果完全相同.