最小费用最大流问题matlab程序.doc

《最小费用最大流问题matlab程序.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、下面的最小费用最大流算法采用的是“基于Floyd最短路算法的Ford和Fulkerson迭加算法”，其基本思路为：把各条弧上单位流量的费用看成某种长度，用Floyd求最短路的方法确定一条自V1至Vn的最短路；再将这条最短路作为可扩充路，用求解最大流问题的方法将其上的流量增至最大可能值；而这条最短路上的流量增加后，其上各条弧的单位流量的费用要重新确定，如此多次迭代，最终得到最小费用最大流。本源码由GreenSim团队原创，转载请注明function[f,MinCost,MaxFlow]=MinimumCostFlow(a,c,V,s

2、,t)%%MinimumCostFlow.m%  最小费用最大流算法通用Matlab函数%%基于Floyd最短路算法的Ford和Fulkerson迭加算法%GreenSim团队原创作品，转载请注明%%输入参数列表%  a      单位流量的费用矩阵%  c      链路容量矩阵%  V      最大流的预设值，可为无穷大%  s      源节点%  t      目的节点%%输出参数列表%  f      链路流量矩阵%  MinCost  最小费用%  MaxFlow  最大流量%%第一步：初始化N=size(a,1);

3、%节点数目f=zeros(N,N);%流量矩阵，初始时为零流MaxFlow=sum(f(s,:));%最大流量，初始时也为零flag=zeros(N,N);%真实的前向边应该被记住fori=1:N  forj=1:N      ifi~=j&&c(i,j)~=0        flag(i,j)=1;%前向边标记        flag(j,i)=-1;%反向边标记      end      ifa(i,j)==inf        a(i,j)=BV;        w(i,j)=BV;%为提高程序的稳健性，以一个有限大数取代

4、无穷大      end  endendifL(end)

5、(R(i),R(i+1));  end  maxLY=min(LY);%流量裕度的最小值，也即最大能够增加的流量  fori=1:TS      u=R(i);      v=R(i+1);      ifflag(u,v)==1&&maxLY

6、==1&&maxLY==c(u,v)%当这条边为前向边且是饱和边时        w(u,v)=BV;%更新权重值        c(u,v)=c(u,v)-maxLY;%更新流量裕度值        w(v,u)=-a(u,v);%反向链路权重更新      elseifflag(u,v)==-1&&maxLY

7、g(u,v)==-1&&maxLY==c(u,v)%当这条边为反向边且是饱和边时        w(v,u)=a(v,u);        c(u,v)=c(u,v)-maxLY;        w(u,v)=BV;      else      end  end  MaxFlow2=sum(f(s,:));  MinCost2=sum(sum(f.*a));  ifMaxFlow2<=V      MaxFlow=MaxFlow2;      MinCost=MinCost2;      [L,R]=FLOYD(w,s,t); 

8、 else      f=f1+prop*(f-f1);      MaxFlow=V;      MinCost=MinCost1+prop*(MinCost2-MinCost1);      return  end  ifL(end)