matlab最小費用最大流函數,使用matlab求解最小費用最大流算問題

《使用matlab求解最小費用最大流算問題》由會員分享，可線上閱讀，更多相關《使用matlab求解最小費用最大流算問題(8頁珍藏版)》請在人人文庫網上搜尋。

1、北京聯合大學實驗報告項目名稱： 運籌學專題實驗報告 學 院： 自動化 專 業： 物流工程 班 級： 1201B 學 号：81 姓 名： 管水城 成 績： 2015 年5月6日實驗三：使用matlab求解最小費用最大流算問題一、實驗目的：(1)使學生在程式設計方面得到進一步的訓練;，學習Matlab語言進行程式設計求解最大流最小費用問題。二、實驗用儀器裝置、器材或軟體環境計算機, Matlab R2006a三、算法步驟、計算框圖、計算程式等1. 最小費用最大流問題的概念。在網絡D(V,A)中,對應每條弧(vi,vj)IA,規定其容量限制為cij(cij0),機關流量通過弧(vi,vj)的費用為d。

2、ij(dij0),求從發點到收點的最大流f,使得流量的總費用d(f)為最小,即mind(f)=E(vi,vj)IA2.求解原理。若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. 最小費用流算法的框圖描述。圖一2. 計算最小費用最大流MATLAB源代碼,檔案名為mp_mc.mfunctionMm,mc,Mmr=mp_mc(a,c)A=a; %各路徑最大承載流量矩陣C=c; %各路徑花費矩陣Mm=0; %初始可行流設為零mc。

4、=0; %最小花費變量mcr=0;mrd=0;n=0;while mrd=inf %一直疊代到以花費為權值找不到最短路徑for i=1:(size(mcr,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); %将最短路徑上的最小允許流量提取出來endfor i=1:(size(mcr,1)-1)if a(mcr(i),mcr(i+1)=infa(mcr(i+1),mcr(i)=a(mcr(i+1),mcr(i)+n;elsea(m。

5、cr(i),mcr(i+1)=a(mcr(i),mcr(i+1)-n;endendMm=Mm+n; %将每次疊代後增加的流量累加，疊代完成時就得到最大流量for i=1:size(a,1)for j=1:size(a,1)if i=j&a(i,j)=infif 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);endendendendmcr,mrd=floyd_mr(c) 。

6、%進行疊代，得到以花費為權值的最短路徑矩陣(mcr)和數值(mrd)n=inf;end%下面是計算最小花費的數值for i=1:size(A,1)for j=1:size(A,1)if A(i,j)=infA(i,j)=0;endif a(i,j)=infa(i,j)=0;endendendMmr=A-a; %将剩餘空閑的流量減掉就得到了路徑上的實際流量，行列交點處的非零數值就是兩點間路徑的實際流量for i=1:size(Mmr,1)for j=1:size(Mmr,1)if Mmr(i,j)=0mc=mc+Mmr(i,j)*C(i,j); %最小花費為累加各條路徑實際流量與其機關流量花費的。

7、乘積endendend利用福得算法計算最短路徑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開始沿最短路徑到rd點的最短路徑while rd=n %通過循環将最短路徑依次提取出來，直到rd點就是最後一個點mr=mr,R(rd,n);rd=R(rd,n);end福得算法MATLAB源代碼,。

8、檔案名為floyd.mfunctionD,R=floyd(a)n=size(a,1);D=a;for i=1:nfor j=1:nR(i,j)=j;endendR;for k=1:nfor i=1:nfor j=1: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,n);3. 求解如下網絡運輸圖中的最大流最小費用問題：圖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。

9、 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由上圖實驗結果可知，該問題的最大流為11，最小費用為55。4. 求解如下最大流最小費用問題：(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 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。

10、 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由上圖實驗結果可知，該問題的最大流為7，最小費用為42。四、實驗總結本實驗在程式檔案中所使用的計算最小費用最大流的算法并沒有先用福德富克遜法算出最大流，然後再用對偶法算出最小費用，而是将兩種算法結合，最小費用和最大流一起算出。首先，福德富克遜法要求對網絡增加一個初始可行流，那麼不妨設初始可行流為零流。然後再尋找增廣鍊，可以采用對偶法以費用C為權通過福德算法先找從起點至終點的最短路，再以該最短路為增廣鍊調整流量，每一次調整都以矩陣a記錄調整的結果。為了能夠滿足增廣鍊上正向弧。

11、非飽和、逆向弧非零流的條件，在每一次以C為權尋找最短路之前，對費用C矩陣進行調整。将正向飽和弧、逆向零流弧對應的C值設為無窮大，非飽和弧的C值設為初始值，這樣一來，計算出的最短路徑增廣鍊就不會包括正向飽和弧與逆向零流弧了。每一次調整完網絡流量之後，網絡中的飽和弧、非飽和弧、零流弧會互相轉化，是以要對網絡中弧所對應的C矩陣再次進行調整。調整的方法就是回到上邊：将正向飽和弧、逆向零流弧對應的C值設為無窮大、非飽和弧的C值設為初始值，後再次以C為權通過福德算法尋找最短路徑，這樣構成一個循環，直至以C為權找不到一條從起點至終點的最短路徑為止。找不到最短路徑的标志就是福德算法傳回從起點至終點的最短路徑值為無窮大，此時網絡已達最大流。