實(shí)驗(yàn)三使用matlab求解最小費(fèi)用最大流算問題

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

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

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

4、0; %最小花費(fèi)變量mcr=0;mrd=0;n=0;while mrd=inf %一直疊代到以花費(fèi)為權(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),mcr(i)=a(mcr(i+1),mcr(i)

5、+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 %非飽合弧 c(j,i)=C(j,i); c(i,j)=C(i,j); end

6、end end end mcr,mrd=floyd_mr(c) %進(jìn)行疊代，得到以花費(fèi)為權(quán)值的最短路徑矩陣(mcr)和數(shù)值(mrd) n=inf;end%下面是計(jì)算最小花費(fèi)的數(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í)際流量，行列交點(diǎn)處的非零數(shù)值就是兩點(diǎn)間路徑的實(shí)際流量for i=1:size(Mmr,1) for j=1:size(Mmr,1) if Mmr(i,j)=0 mc=m

7、c+Mmr(i,j)*C(i,j); %最小花費(fèi)為累加各條路徑實(shí)際流量與其單位流量花費(fèi)的乘積 end endend利用福得算法計(jì)算最短路徑MATLAB源代碼,文件名為floyd_mr.mfunctionmr,mrd=floyd_mr(a)n=size(a,1);D,R=floyd(a); %通過福德算法得到距離矩陣(D)和路徑矩陣(R)mrd=D(1,n); %提取從起點(diǎn)1到終點(diǎn)n的最短距離rd=R(1,n); %提取從起點(diǎn)1開始沿最短路徑上下一個點(diǎn)的編號(rd)mr=1,rd; %從起點(diǎn)1開始沿最短路徑到rd點(diǎn)的最短路徑while rd=n %通過循環(huán)將最短路徑依次提取出來，直到rd點(diǎn)就是最

8、后一個點(diǎn) 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,n);3. 求解如下網(wǎng)絡(luò)運(yùn)輸圖中的最大流最小費(fèi)用問題： 圖2打開matlab軟件，在COMND

9、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點(diǎn)擊運(yùn)行得到如下圖：圖3由上圖實(shí)驗(yàn)結(jié)果可知，該問題的最大流為11，最小費(fèi)用為55。4. 求解如下最大流最小費(fèi)用問題：（6,5） （7,1）（3,2）（4,3） （5,4）（3,1）（4,1） （3,3）打開matlab軟件，在COMND WINDOW窗口中輸入矩陣程序如下：n=6;C=0 3 0 4 0 0;0 0 6 0 4 0;0 0 0 0

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