最小费用最大流问题matlab程序(4页).doc

上传人:1595****071 文档编号:36999890 上传时间:2022-08-29 格式:DOC 页数:4 大小:124KB
返回 下载 相关 举报
最小费用最大流问题matlab程序(4页).doc_第1页
第1页 / 共4页
最小费用最大流问题matlab程序(4页).doc_第2页
第2页 / 共4页
点击查看更多>>
资源描述

《最小费用最大流问题matlab程序(4页).doc》由会员分享,可在线阅读,更多相关《最小费用最大流问题matlab程序(4页).doc(4页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

2、大流算法通用Matlab函数% 基于Floyd最短路算法的Ford和Fulkerson迭加算法% GreenSim团队原创作品,转载请注明% 输入参数列表%a 单位流量的费用矩阵%c 链路容量矩阵%V 最大流的预设值,可为无穷大%s 源节点%t 目的节点% 输出参数列表%f 链路流量矩阵%MinCost最小费用%MaxFlow最大流量% 第一步:初始化N=size(a,1);%节点数目f=zeros(N,N);%流量矩阵,初始时为零流MaxFlow=sum(f(s,:);%最大流量,初始时也为零flag=zeros(N,N);%真实的前向边应该被记住for i=1:N for j=1:N if

3、 i=j&c(i,j)=0 flag(i,j)=1;%前向边标记 flag(j,i)=-1;%反向边标记 end if a(i,j)=inf a(i,j)=BV; w(i,j)=BV;%为提高程序的稳健性,以一个有限大数取代无穷大 end endendif L(end)BV RE=1;%如果路径长度小于大数,说明路径存在else RE=0;end% 第二步:迭代过程while RE=1&MaxFlow=V%停止条件为达到最大流的预设值或者没有从s到t的最短路 %以下为更新网络结构 MinCost1=sum(sum(f.*a); MaxFlow1=sum(f(s,:); f1=f; TS=len

4、gth(R)-1;%路径经过的跳数 LY=zeros(1,TS);%流量裕度 for i=1:TS LY(i)=c(R(i),R(i+1); end maxLY=min(LY);%流量裕度的最小值,也即最大能够增加的流量 for i=1:TS u=R(i); v=R(i+1); if flag(u,v)=1&maxLYc(u,v)%当这条边为前向边且是非饱和边时 f(u,v)=f(u,v)+maxLY;%记录流量值 w(u,v)=a(u,v);%更新权重值 c(v,u)=c(v,u)+maxLY;%反向链路的流量裕度更新 elseif flag(u,v)=1&maxLY=c(u,v)%当这条边

5、为前向边且是饱和边时 w(u,v)=BV;%更新权重值 c(u,v)=c(u,v)-maxLY;%更新流量裕度值 w(v,u)=-a(u,v);%反向链路权重更新 elseif flag(u,v)=-1&maxLYc(u,v)%当这条边为反向边且是非饱和边时 w(v,u)=a(v,u); c(v,u)=c(v,u)+maxLY; w(u,v)=-a(v,u); elseif flag(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=s

6、um(f(s,:); MinCost2=sum(sum(f.*a); if MaxFlow2=V MaxFlow=MaxFlow2; MinCost=MinCost2; L,R=FLOYD(w,s,t); else f=f1+prop*(f-f1); MaxFlow=V; MinCost=MinCost1+prop*(MinCost2-MinCost1); return end if L(end)BV RE=1;%如果路径长度小于大数,说明路径存在 else RE=0; endendfunction L,R=FLOYD(w,s,t)n=size(w,1);D=w;path=zeros(n,n);%以下是标准floyd算法for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end end endendL=zeros(0,0);R=s;while 1 if s=t L=fliplr(L); L=0,L; return end L=L,D(s,t); R=R,path(s,t); s=path(s,t);end

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 单元课程

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁