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

北京联合大学 实验报告 项目名称： 运筹学专题实验报告 学 院： 自动化 专 业： 物流工程 班 级： 1201B 学 号：2012100358081 姓 名： 管水城 成 绩： 2015 年　5　月　6　日 实验三：使用matlab求解最小费用最大流算问题 一、实验目的： (1)使学生在程序设计方面得到进一步的训练;，学习Matlab语言进行程序设计求解最大流最小费用问题。 二、实验用仪器设备、器材或软件环境 计算机, Matlab R2006a 三、算法步骤、计算框图、计算程序等 1. 最小费用最大流问题的概念。 在网络D(V,A)中,对应每条弧(vi,vj)IA,规定其容量限制为cij(cij\0),单位流量通过弧(vi,vj)的费用为dij(dij\0),求从发点到收点的最大流f,使得流量的总费用d(f)为最小,即mind(f)=E(vi,vj)IA 2.求解原理。 若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中弧的权值有密切关系,图E(f)中各弧的权值定义为： 新图E(f)中不考虑原网络D中各个弧的容量cij.为了使E(f)能比较清楚,一般将长度为]的弧从图E(f)中略去.由可扩充链费用的概念及图E(f)中权的定义可知,在网络D中寻求关于可行流f的最小费用可扩充链,等价于在图E(f)中寻求从发点到收点的最短路.因图E(f)中有负权,所以求E(f)中的最短路需用Floyd算法。 最小费用流算法的框图描述。 图一 计算最小费用最大流MATLAB源代码,文件名为mp_mc.m function[Mm,mc,Mmr]=mp_mc(a,c) A=a; %各路径最大承载流量矩阵 C=c; %各路径花费矩阵 Mm=0; %初始可行流设为零 mc=0; %最小花费变量 mcr=0; mrd=0; n=0; while mrd~=inf %一直叠代到以花费为权值找不到最短路径 for i=1:(size(mcr,1)-1) if a(mcr(i),mcr(i+1))==inf ta=A(mcr(i+1),mcr(i))-a(mcr(i+1),mcr(i)); else ta=a(mcr(i),mcr(i+1)); end n=min(ta,n); %将最短路径上的最小允许流量提取出来 end for i=1:(size(mcr,1)-1) if a(mcr(i),mcr(i+1))==inf a(mcr(i+1),mcr(i))=a(mcr(i+1),mcr(i))+n; else a(mcr(i),mcr(i+1))=a(mcr(i),mcr(i+1))-n; end end Mm=Mm+n; %将每次叠代后增加的流量累加，叠代完成时就得到最大流量 for i=1:size(a,1) for j=1:size(a,1) if i~=ja(i,j)~=inf if a(i,j)==A(i,j) %零流弧 c(j,i)=inf; c(i,j)=C(i,j); elseif a(i,j)==0 %饱合弧 c(i,j)=inf; c(j,i)=C(j,i); elseif a(i,j)~=0 %非饱合弧