实验三使用matlab求解最小费用最大流算问题

《实验三使用matlab求解最小费用最大流算问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、北京联合大学实验报告项目名称：运筹学专题实验报告学院：自动化专业：物流工程班级：1201B学号：2012100358081姓名：管水城成绩：2015年5月6日实验三:使用matlab求解最小费用最大流算问题一、实验目的：(1)使学生在程序设计方面得到进一步的训练;，学习Matlab语言进行程序设计求解最大流最小费用问题。二、实验用仪器设备、器材或软件环境计算机,MatlabR2006a三、算法步骤、计算框图、计算程序等1•最小费用最大流问题的概念。在网络D(V,A)中,对应每条弧(vi,vj)IA,规定其容量限制为cij(cijO),单位流量通过弧(vi,vj)的费用为di

2、j(dij),求从发点到收点的最大流f,使得流量的总费用d(f)为最小，即mind(f)=E(vi,vj)1A2.求解原理。若f是流值为W的所有可行流屮费用最小者，而P是关于f的所有可扩充链中费用最小的可扩充链，沿P以E调整f得到可行流fc,则fc是流值为(W+E)的可行流中的最小费用流。根据这个结论，如果已知f是流值为W的最小费用流，则关键是要求出关于f的最小费用的可扩充链•为此，需要在原网络D的基础上构造一个新的赋权有向图E(f),使其顶点与D的顶点相同，且将D屮每条弧(vi,vj)均变成两个方向相反的弧(vi,vj)和(vj,vi)1新图E(f)中各弧的权值与f中弧

3、的权值有密切关系，图E(f)中各弧的权值定义为：新图E(f)中不考虑原网络D中各个弧的容量cij.为了使E(f)能比较清楚，一般将长度为］的弧从图E(f)屮略去.由可扩充链费用的概念及图E(f)小权的定义可知，在网络D中寻求关于可行流f的最小费用可扩充链，等价于在图E(f)中寻求从发点到收点的最短路•因图E(f)中有负权,所以求E(f)中的最短路需用Floyd算法。1.最小费用流算法的框图描述。图一1.计算最小费用最大流MATLAB源代码，文件名为mp_mc.mfunction[Mm,me,Mmr]=mp_mc(a,c)A二a;%各路径最大承载流量矩阵C=c;%各路径花费矩阵

4、Mm=0;%初始可彳亍流设为零mc=0;%最小花费变量mcr=0;mrd=0;n二0;whilemrd"=inf%—直叠代到以花费为权值找不到最短路径fori二1:(size(mcr",1)-1)ifa(mcr(i),mcr(i+1))==infta=A(mcr(i+1),mcr(i))-a(mcr(i+1),mcr(i));elseta=a(mcr(i),mcr(i+1));endn=min(ta,n);%将最短路径上的最小允许流量捉取岀来endfori二1:(size(mcr?,1)-1)ifa(mcr(i),mcr(i+1))—infa(mcr(i+1),mcr(i))

5、=a(mcr(i+1),mcr(i))+n;elsea(mcr(i),mcr(i+1))=a(mcr(i),mcr(i+1))-n;endendMm=Mm+n;%将每次叠代后增加的流量累加，叠代完成时就得到最大流量fori二1:size(a,1)forj=l:size(a，,1)ifi〜二j&a(i,j)〜二infifa(i,j)二二A(i,j)%零流弧c(j,i)=inf;c(i,j)=C(i,j);elseifa(i,j)==0%饱合弧c(i,j)=inf;c(j,i)二C(j,i);elseifa(i,j)"=0%非饱合弧c(j,i)=C(j,i);c(i,j)=C(i

6、,j);endendendend[mcr,mrd]=floydjnr(c)%进彳亍叠代，得到以花费为权值的最短路径矩阵(mcr)和数值(mrd)n二inf;end%下面是计算最小花费的数值fori=l:size(A,1)forj二1:size(A',1)ifA(i,j)==infA(i,j)=0;endifa(i,j)二二infa(i,j)=0;endendendMmr=A-a;%将剩余空闲的流量减掉就得到了路径上的实际流量，行列交点处的非零数值就是两点间路径的实际流量fori=l:sizc(Mmr,1)forj=l:size(Mmr，,1)ifMmr(i,j)、=0mc=m

7、c+Mmr(i,j)*C(i,j);%最小花费为累加各条路径实际流量与其单位流量花费的乘积endendend利用福得算法计算最短路径MATLAB源代码，文件名为floydjwr.mfunction[mr,mrd]=floyd_mr(a)n=size(a,1);[D,R]=floyd(a);%通过福德算法得到距离矩阵(D)和路径矩阵(R)mrd=D(l,n);%提取从起点1到终点n的最短距离rd=R(l,n);%提取从起点1开始沿最短路径上下一个点的编号(rd)mr=[l,rd];%从起点1开始沿最短路径