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

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

2、流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ù)這個(gè)結(jié)論，如果已知f是流值為W的最小費(fèi)用流則關(guān)鍵是要求出關(guān)于f 的最小費(fèi)用的可擴(kuò)充鏈為此，需要在原網(wǎng)絡(luò)D的基礎(chǔ)上構(gòu)造一個(gè)新的賦權(quán)有向圖 E(f),使其頂點(diǎn)與D的頂點(diǎn)相同，且將D中每條弧(SM)均變成兩個(gè)方向相反的弧 (vi,vj)fQ(vj,vi)l新圖E(f)中各弧的權(quán)值與f中弧的權(quán)值有密切關(guān)系，圖E(f)中各弧的權(quán)值定義

3、為：dijfijV dj1薩gdg fij> 0fj=o新圖E(f)中不考慮原網(wǎng)絡(luò)D中各個(gè)弧的容量cij.為了使E(f)能比較清楚，一般 將長(zhǎng)度為的弧從圖E(f)中略去.由可擴(kuò)充鏈費(fèi)用的概念及圖E(f)中權(quán)的定義可知, 在網(wǎng)絡(luò)D中尋求關(guān)于可行流f的最小費(fèi)用可擴(kuò)充鏈，等價(jià)于在圖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.m function Mm,mc/Mmr = mp_mc(a,c)A二可各路徑最大承載流量矩陣C二c; %各路徑花費(fèi)矩陣

4、Mm=0; %初始可行流設(shè)為零mc=0; %最小花費(fèi)變量mcr=0;mrd=0; no-whiomrd >!.nffor iHlxsize(mcr-l)l) if a(mcr(一)mcr(i + l)T'!.nfQrH A(mcr(一 + l)mcr(一)a(mcr(一 + l)mcr(一)j e-seErHm(mcrsmcr(一+l)j endendfor iHlxsize(mcr-l)l) if a(mcr(一)mcr(i + l)T'!.nfm(mcr(i+l)mcr(i)=a(mcr(i+l)mcr(i)+m e-sea(mcr(i)mcr(i + l)Ta(mc

5、r(i)mcr(i + l)m endfor iHLSize(pl)for jHlsize(?-l)if i2=jR?a(ij)'!.nfpu B<QS% OH §e JOSQ giu4UHSU g<n®% ouAse Joso :3oxrv¥9()<" = (se 七oxsv4uhh(s<七(TtvorNs二丄2(pvorNs 二上OJpu luTu(PEMlsbE) &衆(zhòng)型養(yǎng)®EH更只那程 m 麗啞ettlhyffl& SEIM1end if a(ij) = = infa(ij)=O；ende

6、ndendMmr=A-可將剩余空閑的流量減掉就得到了路徑上的實(shí)際流量，行列交點(diǎn)處 的非零數(shù)值就是兩點(diǎn)間路徑的實(shí)際流量for i = l:size(Mmr,l)forj = l:size(Mmrl)if Mmr(iJ)=0mc=mc+Mmr(ij)*C(i,j); %最小花費(fèi)為累加各條路徑實(shí)際流量與其單位流量花費(fèi)的乘積endendend利用福得算法計(jì)算最短路徑MATLAB源代碼，文件名為function mr/mrd=floyd_mr(a)n 二 size(azl);D,R =floyd(a); %通過(guò)福德算法得到距離矩陣(D)和路徑矩陣(R)u：x=>|ojpue pue r=(r>

7、;)d U：日Oj uyoj 'e=Q !(l/e)azis=u(e)pXo|=y/auoipun)itrpAoij M牙切忑'蔗糾都 aVIlVIAlpU3f(u/pj)y=p jI(UP)*UJ二Ul呼l些彎者嗨呼P低阜，半并盜韶垛型刃§8辭坯業(yè)翱團(tuán)BI% u二p引!um刃刼辭60竽P低刃宜毋曹難畀扛T呼魯Yf% 4PF=w（P）臺(tái)撕用呼9山孫刼豳9場(chǎng)扛T呼曾屮陸酔 3PXP凰目!J爭(zhēng)曹用u竽蕩低t呼毎Yf陸靜 WDg二pwfor i=l:nfor j = l: nif D(i,k)+D(kj)<D(ij)D(ij)=D(i,k)+D(kj);R(i,j)二

8、 R(i,k);endendendk;D;R；endM = D(lfn);打開(kāi)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點(diǎn)擊運(yùn)行得到如下圖：» n=5;» C=0 10 S 0 0:0 0 0 2 7;0 5 0 10 0:0 0 0 0 4:0 0 0 0 0c =010800000270501000000400000>

9、> b=04 1 00:0 00 6 1;02030;00002;00000b =0410000061020300000200000(4,1)(5,4)打開(kāi)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 0 b 二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)行得到如下圖：Command Window»

10、n=6:»C= 0 30400:006040:000 0C =0304000 060400 00000 050300 000030 00000» b=0 2 0 1 00:00 5 03 0:0 00 0b =0 201000 050300 000010 040300 000010 00000fx » mp_(C,b)0 7:0 0 5 0 3 0;0 0 0 0 0 3:0 0 0 0 0 00 1:0 0 4 0 3 0:0 0 0 0 0 1:0 0 0 0 0 0iTicr =030400000030000004004000000003000000Hird

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