《数学建模最大流问题lingo求解程序ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模最大流问题lingo求解程序ppt课件.ppt（7页珍藏版）》请在三一办公上搜索。
1、最大流问题Lingo求解法,实例 现需要将城市s的石油通过管道运送到城市t，中间有4个中转站 和 , 城市与中转站的连接以及管道的容量如图所示，求从城市s到城市t的最大流.,MODEL: 1sets: 2 nodes/s,1,2,3,4,t/; 3 arcs(nodes, nodes)/ 4 s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, f; 5endsets 6data: 7 c = 8 7 5 9 9 2 5 6 10; 8enddata 9max = flow;,程序的第10到 12行表示约束(23), 第13行表示有界约束(24).,解：相应的LIN
2、GO程序为,LINGO软件的计算结果（只保留流值 f ）如下:,Global optimal solution found at iteration: 6 Objective value: 14.00000 Variable Value Reduced Cost FLOW 14.00000 0.000000 F( S, 1) 7.000000 0.000000 F( S, 2) 7.000000 0.000000 F( 1, 2) 2.000000 0.000000 F( 1, 3) 5.000000 0.000000 F( 2, 4) 9.000000 -1.000000 F( 3, 2)
3、0.000000 0.000000 F( 3, T) 5.000000 -1.000000 F( 4, 3) 0.000000 1.000000 F( 4, T) 9.000000 0.000000,因此，该网络的最大流为14，F的值对应弧上的流，如下图所示, 其中网络中的第一个数为容量，第二个数为流量.,在上面的程序中，采用稀疏集的编写方法，下面介绍的程序编写方法是利用邻接矩阵，这样可以不使用稀疏集的编写方法，更便于推广到复杂网络.,MODEL: 1sets: 2 nodes/s,1,2,3,4,t/; 3 arcs(nodes, nodes): p, c, f; 4endsets 5dat
4、a: 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; 18enddata 19max = flow; 20for(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); 23sum(nodes(i):p(1,i)*f(1,i) = flow; 24for(arcs:bnd(0, f, c); END,在本程序中，由于使用了邻接矩阵，当两点之间无弧时，定义弧容量为零，计算结果与前面程序的结果完全相同.,
