實驗三：使用matlab求解最小費用最大流算問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上北京聯(lián)合大學(xué)實驗報告項目名稱： 運籌學(xué)專題實驗報告 學(xué) 院： 自動化 專 業(yè)： 物流工程 班 級： 1201B 學(xué) 號：81 姓 名： 管水城 成 績： 2015 年5月6日實驗三：使用matlab求解最小費用最大流算問題一、實驗?zāi)康模?1)使學(xué)生在程序設(shè)計方面得到進(jìn)一步的訓(xùn)練;，學(xué)習(xí)Matlab語言進(jìn)行程序設(shè)計求解最大流最小費用問題。二、實驗用儀器設(shè)備、器材或軟件環(huán)境 計算機, Matlab R2006a三、算法步驟、計算框圖、計算程序等1. 最小費用最大流問題的概念。在網(wǎng)絡(luò)D(V,A)中,對應(yīng)每條弧(vi,vj)IA,規(guī)定其容量限制為cij(cij0),單位流量通

2、過弧(vi,vj)的費用為dij(dij0),求從發(fā)點到收點的最大流f,使得流量的總費用d(f)為最小,即mind(f)=E(vi,vj)IA2.求解原理。若f是流值為W的所有可行流中費用最小者,而P是關(guān)于f的所有可擴充鏈中費用最小的可擴充鏈,沿P以E調(diào)整f得到可行流fc,則fc是流值為(W+E)的可行流中的最小費用流。根據(jù)這個結(jié)論,如果已知f是流值為W的最小費用流,則關(guān)鍵是要求出關(guān)于f的最小費用的可擴充鏈.為此,需要在原網(wǎng)絡(luò)D的基礎(chǔ)上構(gòu)造一個新的賦權(quán)有向圖E(f),使其頂點與D的頂點相同,且將D中每條弧(vi,vj)均變成兩個方向相反的弧(vi,vj)和(vj,vi)1新圖E(f)中各弧的權(quán)

3、值與f中弧的權(quán)值有密切關(guān)系,圖E(f)中各弧的權(quán)值定義為：新圖E(f)中不考慮原網(wǎng)絡(luò)D中各個弧的容量cij.為了使E(f)能比較清楚,一般將長度為的弧從圖E(f)中略去.由可擴充鏈費用的概念及圖E(f)中權(quán)的定義可知,在網(wǎng)絡(luò)D中尋求關(guān)于可行流f的最小費用可擴充鏈,等價于在圖E(f)中尋求從發(fā)點到收點的最短路.因圖E(f)中有負(fù)權(quán),所以求E(f)中的最短路需用Floyd算法。1. 最小費用流算法的框圖描述。圖一2. 計算最小費用最大流MATLAB源代碼,文件名為mp_mc.mfunctionMm,mc,Mmr=mp_mc(a,c)A=a; %各路徑最大承載流量矩陣C=c; %各路徑花費矩陣Mm=

4、0; %初始可行流設(shè)為零mc=0; %最小花費變量mcr=0;mrd=0;n=0;while mrd=inf %一直疊代到以花費為權(quán)值找不到最短路徑 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)

5、,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=j&a(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 %非飽合弧

6、c(j,i)=C(j,i); c(i,j)=C(i,j); end end end end mcr,mrd=floyd_mr(c) %進(jìn)行疊代，得到以花費為權(quán)值的最短路徑矩陣(mcr)和數(shù)值(mrd) n=inf;end%下面是計算最小花費的數(shù)值for i=1:size(A,1) for j=1:size(A',1) if A(i,j)=inf A(i,j)=0; end if a(i,j)=inf a(i,j)=0; end endendMmr=A-a; %將剩余空閑的流量減掉就得到了路徑上的實際流量，行列交點處的非零數(shù)值就是兩點間路徑的實際流量for i=1:size(Mmr,1)

7、 for j=1:size(Mmr',1) if Mmr(i,j)=0 mc=mc+Mmr(i,j)*C(i,j); %最小花費為累加各條路徑實際流量與其單位流量花費的乘積 end endend利用福得算法計算最短路徑MATLAB源代碼,文件名為floyd_mr.mfunctionmr,mrd=floyd_mr(a)n=size(a,1);D,R=floyd(a); %通過福德算法得到距離矩陣(D)和路徑矩陣(R)mrd=D(1,n); %提取從起點1到終點n的最短距離rd=R(1,n); %提取從起點1開始沿最短路徑上下一個點的編號(rd)mr=1,rd; %從起點1開始沿最短路徑到

8、rd點的最短路徑while rd=n %通過循環(huán)將最短路徑依次提取出來，直到rd點就是最后一個點 mr=mr,R(rd,n); rd=R(rd,n);end福得算法MATLAB源代碼,文件名為floyd.mfunctionD,R=floyd(a)n=size(a,1);D=a;for i=1:n for j=1:n R(i,j)=j; endendR;for 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); R(i,j)=R(i,k); end end end k; D; R;endM=D(1,

9、n);3. 求解如下網(wǎng)絡(luò)運輸圖中的最大流最小費用問題： 圖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 0b=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點擊運行得到如下圖：圖3由上圖實驗結(jié)果可知，該問題的最大流為11，最小費用為55。4. 求解如下最大流最小費用問題：（6,5） （7,1）（3,2）（4,3） （5,4）（3,1）（4,1） （3,3）打開matlab軟件，在COMND WINDOW窗

10、口中輸入矩陣程序如下：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 0 3 0;0 0 0 0 0 1;0 0 0 0 0 0點擊運行得到如下圖：圖4由上圖實驗結(jié)果可知，該問題的最大流為7，最小費用為42。四、實驗總結(jié)本實驗在程序文件中所使用的計算最小費用最大流的算法并沒有先用福德富克遜法算出最大流，然后再用對偶法算出最小費用，而是將兩種算法結(jié)合，最小費用和最大流一起算出。首先，福德富克遜法要求對網(wǎng)絡(luò)增加一個初始可行流，那么不妨設(shè)初始可行流為零流。然后再尋找增廣鏈，可以采用對偶法以費用C為權(quán)通過福德算法先找從起點至終點的最短路，再以該最短路為增廣鏈調(diào)整流量，每一次調(diào)整都以矩陣a記錄調(diào)整的結(jié)果。為了能夠滿足增廣鏈上正向弧非飽和、逆向弧非零流的條件，在每一次以C為權(quán)尋找最短路之前，對費用C矩陣進(jìn)行調(diào)整。將正向飽和弧、逆向零流弧對應(yīng)的C值設(shè)為無窮大，非飽和弧的C值設(shè)為初始值，這樣一來，計算出的最短路徑增廣鏈就不會包括正向飽和弧與逆向零流弧了。每一次調(diào)整完網(wǎng)絡(luò)流量之后，網(wǎng)絡(luò)中的飽和弧、非飽和弧、零流弧會相互轉(zhuǎn)化，因此要對網(wǎng)絡(luò)