matlab、lingo程序代码26-最小费用流

最小费用最大流问题例19（最小费用最大流问题）（续例18）由于输油管道的长短不一或地质等原因，使每条管道上运输费用也不相同，因此，除考虑输油管道的最大流外，还需要考虑输油管道输送最大流的最小费用。图8所示是带有运费的网络，其中第1个数字是网络的容量，第2个数字是网络的单位运费。图8最小费用最大流问题解按照最小费用流的数学规划写出相应的LINGO程序如下：model:sets:nodes/s,1,2,3,4,t/:d;arcs(nodes,nodes)/s1,s3,12,13,23,2t,34,42,4t/:c,u,f;endsetsdata:d=140000-14;!最大流为14;c=282516347;u=8795259610;enddatamin=@sum(arcs:c*f);@for(nodes(i):@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=d(i));@for(arcs:@bnd(0,f,u));end求得最大流的最小费用是205，而原最大流的费用为210单位，原方案并不是最优的。类似地，可以利用赋权邻接矩阵编程求得最小费用最大流。LINGO程序如下：model:sets:nodes/s,1,2,3,4,t/:d;arcs(nodes,nodes):c,u,f;endsetsdata:d=140000-14;c=0;u=0;enddatacalc:c(1,2)=2;c(1,4)=8;c(2,3)=2;c(2,4)=5;c(3,4)=1;c(3,6)=6;c(4,5)=3;c(5,3)=4;c(5,6)=7;u(1,2)=8;u(1,4)=7;u(2,3)=9;u(2,4)=5;u(3,4)=2;u(3,6)=5;u(4,5)=9;u(5,3)=6;u(5,6)=10;endcalcmin=@sum(arcs:c*f);@for(nodes(i):@sum(nodes(j):f(i,j))-@sum(nodes(j):f(j,i))=d(i));@for(arcs:@bnd(0,f,u));end求最小费用流的一种方法—迭代法下面我们编写了最小费用最大流函数mincostmaxflow，其中调用了利用Floyd算法求最短路的函数floydpath。求解例19具体程序如下（下面的全部程序放在一个文件中）：functionmainexample19clear;clc;globalMnumc=zeros(6);u=zeros(6);c(1,2)=2;c(1,4)=8;c(2,3)=2;c(2,4)=5;c(3,4)=1;c(3,6)=6;c(4,5)=3;c(5,3)=4;c(5,6)=7;u(1,2)=8;u(1,4)=7;u(2,3)=9;u(2,4)=5;u(3,4)=2;u(3,6)=5;u(4,5)=9;u(5,3)=6;u(5,6)=10;num=size(u,1);M=sum(sum(u))*num^2;[f,val]=mincostmaxflow(u,c)%求最短路径函数functionpath=floydpath(w);globalMnumw=w+((w==0)-eye(num))*M;p=zeros(num);fork=1:numfori=1:numforj=1:numifw(i,j)w(i,k)+w(k,j)w(i,j)=w(i,k)+w(k,j);p(i,j)=k;endendendendifw(1,num)==Mpath=[];elsepath=zeros(num);s=1;t=num;m=p(s,t);while~isempty(m)ifm(1)s=[s,m(1)];t=[t,t(1)];t(1)=m(1);m(1)=[];m=[p(s(1),t(1)),m,p(s(end),t(end))];elsepath(s(1),t(1))=1;s(1)=[];m(1)=[];t(1)=[];endendend%最小费用最大流函数function[flow,val]=mincostmaxflow(rongliang,cost,flowvalue);%第一个参数：容量矩阵；第二个参数：费用矩阵；%前两个参数必须在不通路处置零%第三个参数：指定容量值（可以不写，表示求最小费用最大流）%返回值flow为可行流矩阵,val为最小费用值globalMflow=zeros(size(rongliang));allflow=sum(flow(1,:));ifnargin3flowvalue=M;endwhileallflowflowvaluew=(flowrongliang).*cost-((flow0).*cost)';path=floydpath(w);%调用floydpath函数ifisempty(path)val=sum(sum(flow.*cost));return;endtheta=min(min(path.*(rongliang-flow)+(path.*(rongliang-flow)==0).*M));theta=min([min(path'.*flow+(path'.*flow==0).*M),theta]);flow=flow+(rongliang0).*(path-path').*theta;allflow=sum(flow(1,:));endval=sum(sum(flow.*cost));