最大流问题

最大流问题 例 现需要将城市 s的石油通过管道运送到城市 t，中间 有 4个中转站v v ，城市与中转站的连接以及 管道的额定容量如下图所示，求从城市 s到城市 t的 最大流. 1 2 3, , ,v v4 定义：设G V 为有向图，如果在V中有两个不同 的顶点集S和T，而在边集上定义一个非负权值c， 则称G为一个网络（Network）.称 中的顶点为源 （Source），T中的顶点为汇（Sink）,既非源又非汇 的顶点称为中间顶点，称c为G的容量函数，容量函 数在边 上的值称为边 的容量，记为c u 或 者c a . ( , )E ( , )a u v S a ( , )v ( ) 网络G中每一条边( , 有一个容量c u , 除此之外, 对边( , 还有一个通过边的流(Flow), 记为 . )u v ( , )v )u v ( , )f u v 显然, 边 上的流量 不会超过该边上的额 定容量 , 即 ( , )u v ( , )c u v ( , )f u v (1) 0 ( , ) ( ,f u v c u v  ) 对于所有中间顶点u , 流入的总量应等于流出的 总量, 即: ( , ) ( , ) v V v V f u v f v u     (2) 一个网络G的流量值(Value of flow) 定义为从源 流出的总流量, 即 ( )V f S ( ) ( , ) v V V f f s v   (3) 由（2）和（3）可以看出： ( ) ( , ) v V V f f v t   (4) 结合（2）（3）（4）有 ( ), , ( , ) ( , ) 0, , , , ( ), . 当 当 当v V v V V f u s f u v f v u u V v s v t V f u t          (5) 满足（5）的网络G为守恒的。 如果流满足（1）（5），则称此流为可行的。 最大流问题的数学形式 ( , ) ( , ) max ; , , s.t. 0, , , , , 0 ,( , ) . f f ij ji j V j V i j E j i E f ij ij v v i s f f i s t v i t f c i j E             LINGO程序求解 model: sets: points/s,v1,v2,v3,v4,t/; edge(points,points) /s,v1 s,v2 v1,v2 v1,v3 v2,v4 v3,v2 v3,t v4,v3 v4,t/:c,f; endsets data: c=8 7 5 9 9 2 5 6 10; enddata max=vf; @for(points(i)|i#ne#@index(s) #and# i#ne#@index(t): @sum(edge(i,j):f(i,j))-@sum(edge(j, i):f(j,i))=0; ); @sum(edge(i,j)|i#eq#@index(s):f(i,j)) =vf; @sum(edge(j,i)|i#eq#@index(t):f(j,i)) =vf; @for(edge(i,j):@bnd(0,f(i,j),c(i,j))) ; end 结果 注：解可能不唯一 上述问题的另解，如下图