第五章圖與網(wǎng)絡(luò)(二)

1、這兩個過程的步驟分述如下。A標號過程：i給發(fā)點標號為。ii假設(shè)頂點已經(jīng)標號，則對的所有未標號的鄰接頂點按以下規(guī)則標號： 假設(shè)，且時，令，則給頂點標號為，假設(shè)，則不給頂點標號。 ，且，令，則給標號為，假設(shè)，則不給標號。iii不斷地重復(fù)步驟ii直到收點被標號，或不再有頂點可以標號為止。當被標號時，說明存在一條從到的可增廣軌，則轉(zhuǎn)向增流過程B。如假設(shè)點不能被標號，且不存在其它可以標號的頂點時，說明不存在從到的可增廣軌，算法結(jié)束，此時所獲得的流就是最大流。B增流過程i令。ii假設(shè)的標號為，則；假設(shè)的標號為，則。iii假設(shè)，把全部標號去掉，并回到標號過程A。否則，令，并回到增流過程ii。求網(wǎng)絡(luò)中的最大流

2、的算法的程序設(shè)計具體步驟如下：對每個節(jié)點，其標號包括兩部分信息 該節(jié)點在可能的增廣路中的前一個節(jié)點，以及沿該可能的增廣路到該節(jié)點為止可以增廣的最大流量。STEP0 置初始可行流如零流；對節(jié)點標號，即令=任意正值如1。STEP1 假設(shè)，繼續(xù)下一步；否則停止，已經(jīng)得到最大流，結(jié)束。STEP2 取消所有節(jié)點的標號，即令，；令LIST=，對節(jié)點標號，即令充分大的正值。STEP3 如果LIST且，繼續(xù)下一步；否則：3a如果已經(jīng)有標號即，則找到了一條增廣路，沿該增廣路對流進行增廣增廣的流量為，增廣路可以根據(jù)pred回溯方便地得到，轉(zhuǎn)STEP1。3b如果沒有標號即LIST=且，轉(zhuǎn)STEP1。STEP4 從L

3、IST中移走一個節(jié)點；尋找從節(jié)點出發(fā)的所有可能的增廣弧：4a對非飽和前向弧，假設(shè)節(jié)點沒有標號即，對進行標號，即令，并將加入LIST中。4b對非空后向弧，假設(shè)節(jié)點沒有標號即，對進行標號，即令，并將加入LIST中。例14 用Ford-Fulkerson算法計算如下網(wǎng)絡(luò)中的最大流，每條弧上的兩個數(shù)字分別表示容量和當前流量。解 編寫程序如下：clc,clear,M=1000;u(1,2)=1;u(1,3)=1;u(1,4)=2;u(2,3)=1;u(2,5)=2;u(3,5)=1;u(4,3)=3;u(4,5)=3;f(1,2)=1;f(1,3)=0;f(1,4)=1;f(2,3)=0;f(2,5)=

4、1;f(3,5)=1;f(4,3)=1;f(4,5)=0;n=length(u);list=;maxf(n)=1;while maxf(n)>0 maxf=zeros(1,n);pred=zeros(1,n); list=1;record=list;maxf(1)=M; while (isempty(list)&(maxf(n)=0) flag=list(1);list(1)=; index1=(find(u(flag,:)=0); label1=index1(find(u(flag,index1). -f(flag,index1)=0); label1=setdiff(labe

5、l1,record); list=union(list,label1); pred(label1)=flag; maxf(label1)=min(maxf(flag),u(flag,label1). -f(flag,label1); record=union(record,label1); label2=find(f(:,flag)=0); label2=label2' label2=setdiff(label2,record); list=union(list,label2); pred(label2)=-flag; maxf(label2)=min(maxf(flag),f(lab

6、el2,flag); record=union(record,label2); end if maxf(n)>0 v2=n; v1=pred(v2); while v2=1 if v1>0 f(v1,v2)=f(v1,v2)+maxf(n); else v1=abs(v1); f(v2,v1)=f(v2,v1)-maxf(n); end v2=v1; v1=pred(v2); end end endf§8 最小費用流及其求法8.1 最小費用流上面我們介紹了一個網(wǎng)絡(luò)上最短路以及最大流的算法，但是還沒有考慮到網(wǎng)絡(luò)上流的費用問題，在許多實際問題中，費用的因素很重要。例如，在運輸

7、問題中，人們總是希望在完成運輸任務(wù)的同時，尋求一個使總的運輸費用最小的運輸方案。這就是下面要介紹的最小費用流問題。在運輸網(wǎng)絡(luò)中，設(shè)是定義在上的非負函數(shù)，它表示通過弧單位流的費用。所謂最小費用流問題就是從發(fā)點到收點怎樣以最小費用輸送一已知量為的總流量。最小費用流問題可以用如下的線性規(guī)劃問題描述：s.t. ， .顯然，如果最大流，則本問題就是最小費用最大流問題。如果，則本問題無解。8.2 求最小費用流的一種方法迭代法這里所介紹的求最小費用流的方法叫做迭代法。這個方法是由Busacker和Gowan在1961年提出的。其主要步驟如下：(i)求出從發(fā)點到收點的最小費用通路。(ii)對該通路分配最大可能

8、的流量： 并讓通路上的所有邊的容量相應(yīng)減少。這時，對于通路上的飽和邊，其單位流費用相應(yīng)改為。(iii)作該通路上所有邊的反向邊。令，(iv)在這樣構(gòu)成的新網(wǎng)絡(luò)中，重復(fù)上述步驟(i)，(ii)，(iii)，直到從發(fā)點到收點的全部流量等于為止或者再也找不到從到的最小費用道路。下面我們編寫了用Floyd算法求最短路的函數(shù)floydpath和最小費用最大流函數(shù)mincostmaxflow。最短路函數(shù)如下：function path=floydpath(w);num=length(w);M=sum(sum(w).*num;w=w+(w=0)-eye(num).*M;p=zeros(num);for k=

9、1:num for i=1:num for j=1:num if w(i,j)>w(i,k)+w(k,j) w(i,j)=w(i,k)+w(k,j); p(i,j)=k; end end endendif w(1,num)>=M path=;else path=zeros(num); s=1;t=num;m=p(s,t); while isempty(m) if m(1) s=s,m(1);t=t,t(1);t(1)=m(1); m(1)=;m=p(s(1),t(1),m,p(s(end),t(end); else path(s(1),t(1)=1;s(1)=;m(1)=;t(1)

10、=; end endend最小費用最大流函數(shù)如下：function flow=mincostmaxflow(rongliang,cost,flowvalue);%第一個參數(shù)：容量矩陣；第二個參數(shù)：費用矩陣；%第三個參數(shù)：指定容量值可以不寫，表示求最小費用最大流%前兩個參數(shù)必須在不通路處置零，且為同維矩陣%返回值為可行流矩陣%必須有函數(shù)文件floydpath.mM=sum(sum(rongliang);flow=zeros(size(rongliang);allflow=sum(flow(1,:);if nargin<3 flowvalue=M;endwhile allflow<fl

11、owvalue w=(flow<rongliang).*cost-(flow>0).*cost)' path=floydpath(w);%調(diào)用floyd if isempty(path) return; end theta=min(min(path.*(rongliang-flow)+(path.*(rongliang-flow)=0).*M); theta=min(min(path'.*flow+(path'.*flow=0).*M),theta); if allflow+theta>flowvalue theta=flowvalue-allflow

12、; end flow=flow+(rongliang>0).*(path-path').*theta; allflow=sum(flow(1,:);end對于習題五中的第7題，我們的調(diào)用函數(shù)如下：clear;clc;cost= 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;rongliang= 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;y=mincostmaxflow(rongliang,cost)習 題 五1. 一只狼、一頭山羊和一籮卷心菜在河的

13、同側(cè)。一個擺渡人要將它們運過河去，但由于船小，他一次只能運三者之一過河。顯然，不管是狼和山羊，還是山羊和卷心菜，都不能在無人監(jiān)視的情況下留在一起。問擺渡人應(yīng)怎樣把它們運過河去？2. 北京Pe、東京(T)、紐約(N)、墨西哥城(M)、倫敦(L)、巴黎(Pa)各城市之間的航線距離如下表：LMNPaPeTL5635215160M5621577870N3521366868Pa2157365161Pe5178685113T6070686113由上述交通網(wǎng)絡(luò)的數(shù)據(jù)確定最小生成樹。3. 某臺機器可連續(xù)工作4年，也可于每年末賣掉，換一臺新的。已知于各年初購置一臺新機器的價格及不同役齡機器年末的的處理價如下表所示。又新機器第一年運行及維修費為0.3萬元，使用1-3年后機器每年的運行及維修費用分別為0.8，1.5，2.0萬元。試確定該機器的最優(yōu)更新策略，使4年內(nèi)用于更換、購買及運行維修的總費用為最省。第一年第二年第三年第四年年初購置價使用了年的機器處理價2.52.02.61.62.81.33.11.14. 某產(chǎn)品從倉庫運往市場銷售。已知各倉庫的可供量、各市場需求量及從倉庫至市場的路徑的運輸能力如下表所示表中數(shù)字0代表無路可通，試求從倉庫可運往市場的最大流量，各市場需求能否滿足？倉庫 市場1234可供量300201001001040405052020100需求量20206020 5. 某單位