《实验三：使用matlab求解最小费用最大流算问题.docx》由会员分享，可在线阅读，更多相关《实验三：使用matlab求解最小费用最大流算问题.docx（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、北京联合大学实验报告工程名称：运筹学专题实验报告学院：自动化专业：物流工程班 级：1吸1B 学 号：班姓名：管水城成绩：2015年5月 6日实验三：使用matlab求解最小费用最大流算问题一、实验目的：使学生在程序设计方面得到进一步的训练;，学习Matlab语言进行程序设计求解最大流最 小费用问题。二、实验用仪器设备、器材或软件环境计算机，Matlab R2006a三、算法步骤、计算框图、计算程序等.最小费用最大流问题的概念。在网络D (V, A)中,对应每条弧(vi, vj) IA,规定其容量限制为cij (cijO),单位流 量通过弧(vi, vj)的费用为dij (dijAO),求从发点
2、到收点的最大流f,使得流量的 总费用 d(f)为最小，即 mind(f) =E(vi, vj)IA.求解原理。假设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 .最小费用流算法的框图描述。图一.计算最小费用最大流MATLAB源代码,文件名为mp_mc. m function Mm, me, Mmr =mp_mc (a, c)A=a; %各路径最大承载流量矩阵C=c; %各路径花费矩阵Mm=0
4、; %初始可行流设为零mc=01 %最小花费变量mcr=0;mrd=0;n= 0;while mrd=inf %一直叠代到以花费为权值找不到最短路径 fori=l:(size(mcr5,1)-1)if a(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=l:(size(mcr , 1)-1) if a(mcr(i), mcr (i+1)=infa (mcr(i+1), mc
5、r(i)=a(mcr(i+1), mcr(i) +n; elsea (mcr (i), mcr (i+1) =a (mcr (i), mcr (i+1) -n; end endMm=Mm+n; %将每次叠代后增加的流量累加，叠代完成时就得到最大流量 fori=l:size(a, 1) for j=l: size (a，, 1)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 %非饱合弧c(j, i)=C(j, i)
6、;c(i, j)=C(i, j);end end end endmcr, mrd=floyd_mr (c) %进行叠代，得到以花费为权值的最短路径矩阵 (mcr)和数值(mrd)n=inf;end%下面是计算最小花费的数值 fori=l:size(A, 1)for j=l: size (A, 1)if A(i, j)=infA(i, j)=0;endif a(i, j)=infa(i, j)=0;end end endMmr=A-a1 %将剩余空闲的流量减掉就得到了路径上的实际流量，行列交点处的非 零数值就是两点间路径的实际流量fori=l:size(Mmr, 1) for j=l:size(
7、Mmr5, 1) ifMmr (i, j)=0mc=mc+Mmr (i, j)*C(i, j) ; %最小花费为累加各条路径实际流 量与其单位流量花费的乘积end end end利用福得算法计算最短路径MATLAB源代码,文件名为floyd_mr. m functionmr, 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开始沿最短路径
8、到rd点的最短路径while rdn /通过循环将最短路径依次提取出来，直到rd点就是最后一个点mr=mr, R (rd, n); rd=R (rd, n);end福得算法MATLAB源代码，文件名为floyd. m functionD, R=floyd(a) n=size (a, 1);D=a;fori=l:nfor j=l:nR(i, J)=j；endendR；for k=l:nfori=l:nfor j=l:nif D(i,k)+D(k, j)D(i, j) D(i, j)=D(i,k)+D(k, j); R(i, j)=R(i, k);endendendk；D;R；endM=D(1,
9、n);.求解如下网络运输图中的最大流最小费用问题:图2翻开matlab软件，在COMND WINDOW窗口中输入矩阵程序如下： n=5;C=0 10 8 0 0;0 0 0 2 7;0 5 0 10 0;0 0 0 0 4;0 0 0 0 0 b=0 4 1 0 0;0 0 0 6 1;0 2 0 3 0;0 0 0 0 2;0 0 0 0 0 点击运行得到如下列图： n=5; C=0 10 8 0 0;0 0 0 2 7;0 5 0 10 0:0 0 0 0 4;0 0 0 0 00108000002一10501000000400000 b=00:0 0 0 6 1:0 2 0 3 0;0
10、0 0 0 2:0 0 0 0 0000000200100061030002000Command Window00003040080000040004040mrd =me =55A 图3由上图实验结果可知，该问题的最大流为11,最小费用为55。2 .求解如下最大流最小费用问题：(6,5)翻开matlab软件，在COMND WINDOW窗口中输入矩阵程序如下：n=6;C=0 3 0 4 0 0;0 0 6 0 4 0;0 0 0 0 0 7;0 0 5 0 3 0;0 0 0 0 0 3;0 0 0 0 0 0b=0 2 0 1 0 0;0 0 5 0 3 0;0 0 0 0 0 1;0 0 4
11、 0 3 0;0 0 0 0 0 1;0 0 0 0 0 0点击运行得到如下列图：Command Window n=6; C=0 30 40 0100 6 04 0:00 0 0 0 7:0 0 5 0 3 0;0 0 0 0 0 3:0 0 0 0 0 0C =03040000604000000一005030000003000000 b=0 20 10 0:00 5 03 0100 0 0 0 l;0 0 4 0 3 0;0 0 0 0 0 l;0 0 0 0 0 0b =020100005030000001004030000001000000fx mp_(C,b)mcrmcr0300000
12、00004000000400030004000003000me =42图4由上图实验结果可知，该问题的最大流为7,最小费用为42。四、实验总结本实验在程序文件中所使用的计算最小费用最大流的算法并没有先用福德 富克逊法算出最大流，然后再用对偶法算出最小费用，而是将两种算法结合, 最小费用和最大流一起算出。首先，福德一富克逊法要求对网络增加一个初始可 行流，那么不妨设初始可行流为零流。然后再寻找增广链，可以采用对偶法以费 用C为权通过福德算法先找从起点至终点的最短路，再以该最短路为增广链调整 流量，每一次调整都以矩阵a记录调整的结果。为了能够满足增广链上正向弧非 饱和、逆向弧非零流的条件，在每一次
13、以C为权寻找最短路之前，对费用C矩阵 进行调整。将正向饱和弧、逆向零流弧对应的C值设为无穷大，非饱和弧的C 值设为初始值，这样一来，计算出的最短路径增广链就不会包括正向饱和弧与逆 向零流弧了。每一次调整完网络流量之后，网络中的饱和弧、非饱和弧、零流弧 会相互转化，因此要对网络中弧所对应的C矩阵再次进行调整。调整的方法就是 回到上边：将正向饱和弧、逆向零流弧对应的C值设为无穷大、非饱和弧的C 值设为初始值,后再次以C为权通过福德算法寻找最短路径,这样构成一个循环, 直至以C为权找不到一条从起点至终点的最短路径为止。找不到最短路径的标志 就是福德算法返回从起点至终点的最短路径值为无穷大，此时网络已达最大流。