matlab、lingo程序代码20-最大流问题

最大流问题例17用Ford-Fulkerson算法计算如图6网络中的最大流，每条弧上的两个数字分别表示容量和当前流量。图6最大流问题解编写程序如下：clc,clearu(1,2)=1;u(1,3)=1;u(1,4)=2;u(2,3)=1;u(2,5)=2;u(3,5)=1;u(4,3)=3;u(4,5)=3;f(1,2)=1;f(1,3)=0;f(1,4)=1;f(2,3)=0;f(2,5)=1;f(3,5)=1;f(4,3)=1;f(4,5)=0;n=length(u);list=[];maxf(n)=1;whilemaxf(n)0maxf=zeros(1,n);pred=zeros(1,n);list=1;record=list;maxf(1)=inf;%list是未检查邻接点的标号点，record是已标号点while(~isempty(list))&(maxf(n)==0)flag=list(1);list(1)=[];label1=find(u(flag,:)-f(flag,:));label1=setdiff(label1,record);list=union(list,label1);pred(label1)=flag;maxf(label1)=min(maxf(flag),u(flag,label1)...-f(flag,label1));record=union(record,label1);label2=find(f(:,flag));label2=label2';label2=setdiff(label2,record);list=union(list,label2);pred(label2)=-flag;maxf(label2)=min(maxf(flag),f(label2,flag));record=union(record,label2);endifmaxf(n)0v2=n;v1=pred(v2);whilev2~=1ifv10f(v1,v2)=f(v1,v2)+maxf(n);elsev1=abs(v1);f(v2,v1)=f(v2,v1)-maxf(n);endv2=v1;v1=pred(v2);endendendf最大流问题例18现需要将城市s的石油通过管道运送到城市t，中间有4个中转站321,,vvv和4v，城市与中转站的连接以及管道的容量如图7所示，求从城市s到城市t的最大流。图7最大流问题解使用最大流的数学规划表达式，编写LINGO程序如下：model:sets:nodes/s,1,2,3,4,t/;arcs(nodes,nodes)/s1,s3,12,13,23,2t,34,42,4t/:c,f;endsetsdata:c=8795259610;enddatan=@size(nodes);!顶点的个数;max=flow;@for(nodes(i)|i#ne#1#and#i#ne#n:@sum(arcs(i,j):f(i,j))=@sum(arcs(j,i):f(j,i)));@sum(arcs(i,j)|i#eq#1:f(i,j))=flow;@sum(arcs(i,j)|j#eq#n:f(i,j))=flow;@for(arcs:@bnd(0,f,c));end在上面的程序中，采用了稀疏集的编写方法。下面介绍的程序编写方法是利用赋权邻接矩阵，这样可以不使用稀疏集的编写方法，更便于推广到复杂网络。model:sets:nodes/s,1,2,3,4,t/;arcs(nodes,nodes):c,f;endsetsdata:c=0;@text('fdata.txt')=f;enddatacalc:c(1,2)=8;c(1,4)=7;c(2,3)=9;c(2,4)=5;c(3,4)=2;c(3,6)=5;c(4,5)=9;c(5,3)=6;c(5,6)=10;endcalcn=@size(nodes);!顶点的个数;max=flow;@for(nodes(i)|i#ne#1#and#i#ne#n:@sum(nodes(j):f(i,j))=@sum(nodes(j):f(j,i)));@sum(nodes(i):f(1,i))=flow;@sum(nodes(i):f(i,n))=flow;@for(arcs:@bnd(0,f,c));end