最大流與最小費(fèi)用流

1、7最大流問題7.1最大流問題的數(shù)學(xué)描述7.1.1網(wǎng)絡(luò)中的流定義 在以V為節(jié)點(diǎn)集，A為弧集的有向圖G = (V, A)上定義如下的權(quán)函數(shù)：L : A T R為孤上的權(quán)函數(shù)，弧(i, j)G A對(duì)應(yīng)的權(quán)L(i,j)記為匕.，稱為孤(i, j)的容量下界(lower bound)； U : A T R為弧上的權(quán)函數(shù)，弧(i, j) e A對(duì)應(yīng)的權(quán)U (i, j)記為u ，稱為孤(i, j)的容量上 界，或直接稱為容量(capacity)；D : V t R為頂點(diǎn)上的權(quán)函數(shù)，節(jié)點(diǎn)i e V對(duì)應(yīng)的權(quán)D (i)記為d，稱為頂點(diǎn)i的供需量(supply / demand)；此時(shí)所構(gòu)成的網(wǎng)絡(luò)稱為流網(wǎng)絡(luò)，可以記

2、為N = (V, A, L, U , D)。由于我們只討論V, A為有限集合的情況，所以對(duì)于弧上的權(quán)函數(shù)L,U和頂點(diǎn)上的權(quán)函數(shù)D，可以 直接用所有孤上對(duì)應(yīng)的權(quán)和頂點(diǎn)上的權(quán)組成的有限維向量表示，因此L,U , D有時(shí)直接稱為權(quán)向量，或 簡(jiǎn)稱權(quán)。由于給定有向圖G = (V, A)后，我們總是可以在它的弧集合和頂點(diǎn)集合上定義各種權(quán)函數(shù)， 所以流網(wǎng)絡(luò)一般也直接簡(jiǎn)稱為網(wǎng)絡(luò)。在流網(wǎng)絡(luò)中，弧(i, j)的容量下界l和容量上界u表示的物理意義分別是：通過該弧發(fā)送某種“物 質(zhì)”時(shí)，必須發(fā)送的最小數(shù)量為l，而發(fā)送的最大數(shù)量為u。頂點(diǎn)i e V對(duì)應(yīng)的供需量d則表示該頂 點(diǎn)從網(wǎng)絡(luò)外部獲得的“物質(zhì)”數(shù)量(d 0時(shí))，或

3、從該頂點(diǎn)發(fā)送到網(wǎng)絡(luò)外部的“物質(zhì)”數(shù)量(d 0 時(shí))。下面我們給出嚴(yán)格定義。定義 對(duì)于流網(wǎng)絡(luò)N = (V, A, L,U , D )，其上的一個(gè)流(flow) f是指從N的弧集A到R的一個(gè)函數(shù)，即對(duì)每條弧(i, j)賦予一個(gè)實(shí)數(shù)f(稱為弧(i,j)的流量)。如果流f滿足(1)E f廣 E f 廣 dt, V i e V, j:(i，j)e Aj:( j, i)e Al f 0時(shí)，表示有d個(gè)單位的流量從網(wǎng)絡(luò)外部流入該項(xiàng)點(diǎn)，因此頂點(diǎn)i稱為供應(yīng)點(diǎn)(supply node)或源(source)，有時(shí)也形象地稱為起始點(diǎn)或發(fā)點(diǎn)等；當(dāng)d 0時(shí)，表示有| d. |個(gè)單位的流量從 該頂點(diǎn)流失到網(wǎng)絡(luò)外部(或說被該項(xiàng)

4、點(diǎn)吸收)，因此頂點(diǎn)i稱為需求點(diǎn)(demand node)或匯(sink)，有 時(shí)也形象地稱為終止點(diǎn)或收點(diǎn)等；當(dāng)d = 0時(shí)，頂點(diǎn)i稱為轉(zhuǎn)運(yùn)點(diǎn)(transshipment node )或平衡點(diǎn)、中 間點(diǎn)等。此外，根據(jù)(1)可知，對(duì)于可行網(wǎng)絡(luò)，必有E d = 0(3)ieV也就是說，所有節(jié)點(diǎn)上的供需量之和為0是網(wǎng)絡(luò)中存在可行流的必要條件。一般來說，我們總是可以把L尹0的流網(wǎng)絡(luò)轉(zhuǎn)化為L(zhǎng) = 0的流網(wǎng)絡(luò)進(jìn)行研究。所以，除非特別說明， 以后我們總是假設(shè)L = 0 (即所有孤(i, j)的容量下界I, = 0 )，并將L = 0時(shí)的流網(wǎng)絡(luò)簡(jiǎn)記為 N = (V, A,U , D)。此時(shí)，相應(yīng)的容量約束(2)

5、為0 f. 七.，V (i, j) e A。定義 在流網(wǎng)絡(luò)N = (V, A, U , D)中，對(duì)于流f，如果f司=0, V (i, j) e A，則稱f為零流，否則為非零流。如果某條弧(i, j)上的流量等于其容量(七=u.)，則稱該弧為飽和弧 (saturated arc)；如果某條弧(i, j)上的流量小于其容量(f u.)，則稱該弧為非飽和?。蝗绻硹l弧(i, j)上的流量為0 ( f = 0 )，則稱該弧為空弧(void arc)。7.1.2最大流問題考慮如下流網(wǎng)絡(luò)N = (V, A, U , D):節(jié)點(diǎn)s為網(wǎng)絡(luò)中唯一的源點(diǎn)，t為唯一的匯點(diǎn)，而其它節(jié)點(diǎn)為轉(zhuǎn)運(yùn)點(diǎn)。如果網(wǎng)絡(luò)中存在可行流f

6、，此時(shí)稱流f的流量(或流值，flow value)為d (根據(jù)(3)，它自 然也等于-dt)，通常記為v或v(f)，即v = v (f) = d = d。對(duì)這種單源單匯的網(wǎng)絡(luò)，如果我們并不給定d和日，(即流量不給定)，則網(wǎng)絡(luò)一般記為 N = (s, t, V, A,U )。最大流問題(maximum flow problem)就是在N = (s, t, V, A,U )中找到流值最大的 可行流(即最大流)。我們將會(huì)看到，最大流問題的許多算法也可以用來求解流量給定的網(wǎng)絡(luò)中的可行 流。也就是說，當(dāng)我們解決了最大流問題以后，對(duì)于在流量給定的網(wǎng)絡(luò)中尋找可行流的問題，通常也就 可以解決了。因此，用線性規(guī)

7、劃的方法，最大流問題可以形式地描述如下：max v TOC o 1-5 h z v,i = ss.t. Z f Z f =-v, 1 = t ，(4)j:(l, j沱 Aj:(j,i沱 A0, l。S, t0 f u , V(l, j) G A .(5)定義 如果一個(gè)矩陣A的任何子方陣的行列式的值都等于0，1或-1，則稱A是全幺模的(totally unimodular TU，又譯為全單位模的)，或稱A是全幺模矩陣。定理8 (整流定理)最大流問題所對(duì)應(yīng)的約束矩陣是全幺模矩陣。若所有弧容量均為正整數(shù)，則 問題的最優(yōu)解為整數(shù)解。最大流問題是一個(gè)特殊的線性規(guī)劃問題。我們將會(huì)看到利用圖的特點(diǎn)，解決這個(gè)

8、問題的方法較之線 性規(guī)劃的一般方法要方便、直觀得多。7.1.3單源和單匯運(yùn)輸網(wǎng)絡(luò)實(shí)際問題往往是多源多匯網(wǎng)絡(luò)，為了計(jì)算的規(guī)格化，可將多源多匯網(wǎng)絡(luò)G化成單源單匯網(wǎng)絡(luò)G。設(shè)X是G的源，y是G的匯，具體轉(zhuǎn)化方法如下：在原圖G中增加兩個(gè)新的頂點(diǎn)x和y，令為新圖G中之單源和單匯，則G中所有頂點(diǎn)V成 為G之中間頂點(diǎn)集。用一條容量為8的弧把x連接到X中的每個(gè)頂點(diǎn)。用一條容量為8的弧把y中的每個(gè)頂點(diǎn)連接到y(tǒng)。G和G中的流以一個(gè)簡(jiǎn)單的方式相互對(duì)應(yīng)。若f是G中的流，則由f (a), 若a是G的弧f(a) = f + (v) f - (v),若 a = (x, v) f (v) f + (v),若a = (v, y)

9、所定義的函數(shù)f 是G中使得v (廣)=v (f)的流，這里f + (v)表示流出v的流量，f - (v)表示流入v的 流量(在G中)。反之，G中的流在G的弧集上的限制就是G中具有相同值的流。7.2最大流和最小割關(guān)系設(shè) N = (s,t,V, A,U )，S u V，s g S，t g V S，則稱(S, S )為網(wǎng)絡(luò)的一個(gè)割，其中 S = V S， (S, S)為尾在S，頭在S的弧集，稱C (S, S ) = Z ulj(l, j)g A-lG S, jGS為割(S, S)的容量。定理9 f是最大流，(S,S)是容量最小的割的充要條件是v (f) = C (S, S)。在網(wǎng)絡(luò)N = (s, t

10、,V , A,U )中，對(duì)于軌(s, v , , v , t)(此軌為無向的)，若v v G A，則稱它為2n 1l l +1前向??；若V V G A，則稱它為后向弧。對(duì)所有的后向弧(i, j)恒在網(wǎng)絡(luò)N中，從s到t的軌P上，若對(duì)所有的前向弧(i,j)都有f則稱這條軌P為從s到t的關(guān)于f的可增廣軌。&fu j - f .，當(dāng)(九j)為前向弧j I f， 當(dāng)(i，j)為后向弧I ij5 = min 5 則在這條可增廣軌上每條前向弧的流都可以增加一個(gè)量5，而相應(yīng)的后向弧的流可減少5，這樣就可 使得網(wǎng)絡(luò)的流量獲得增加，同時(shí)可以使每條弧的流量不超過它的容量，而且保持為正，也不影響其它弧 的流量。總之，

11、網(wǎng)絡(luò)中f可增廣軌的存在是有意義的，因?yàn)檫@意味著f不是最大流。7.3最大流的一種算法一標(biāo)號(hào)法標(biāo)號(hào)法是由Ford和Fulkerson在1957年提出的。用標(biāo)號(hào)法尋求網(wǎng)絡(luò)中最大流的基本思想是尋找可 增廣軌，使網(wǎng)絡(luò)的流量得到增加，直到最大為止。即首先給出一個(gè)初始流，這樣的流是存在的，例如零 流。如果存在關(guān)于它的可增廣軌，那么調(diào)整該軌上每條弧上的流量，就可以得到新的流。對(duì)于新的流， 如果仍存在可增廣軌，則用同樣的方法使流的值增大，繼續(xù)這個(gè)過程，直到網(wǎng)絡(luò)中不存在關(guān)于新得到流 的可增廣軌為止，則該流就是所求的最大流。這種方法分為以下兩個(gè)過程：標(biāo)號(hào)過程：通過標(biāo)號(hào)過程尋找一條可增廣軌。增流過程：沿著可增廣軌增加

12、網(wǎng)絡(luò)的流量。這兩個(gè)過程的步驟分述如下。(A)標(biāo)號(hào)過程：給發(fā)點(diǎn)標(biāo)號(hào)為(s +,初。若頂點(diǎn)X已經(jīng)標(biāo)號(hào)，則對(duì)X的所有未標(biāo)號(hào)的鄰接頂點(diǎn)y按以下規(guī)則標(biāo)號(hào):若(x , y) g A，且 f 0，令5 = mn f ,5 ，則給y標(biāo)號(hào)為(X-,5 )，若f = 0，則不給y 標(biāo)號(hào)。yXyyX Xy yX(iii)不斷地重復(fù)步驟(ii)直到收點(diǎn)t被標(biāo)號(hào)，或不再有頂點(diǎn)可以標(biāo)號(hào)為止。當(dāng)t被標(biāo)號(hào)時(shí)，表明 存在一條從s到t的可增廣軌，則轉(zhuǎn)向增流過程(B)。如若t點(diǎn)不能被標(biāo)號(hào)，且不存在其它可以標(biāo)號(hào)的 頂點(diǎn)時(shí)，表明不存在從s到t的可增廣軌，算法結(jié)束，此時(shí)所獲得的流就是最大流。(B)增流過程令u = t。若u的標(biāo)號(hào)為(v

13、+,5)，則f = f + 5 ；若u的標(biāo)號(hào)為(V-,5 )，則f = f - 5。tvuvu ttuvuv t若u = s，把全部標(biāo)號(hào)去掉，并回到標(biāo)號(hào)過程(A)。否則，令u = v，并回到增流過程(ii)。求網(wǎng)絡(luò)N = (s, t, V, A,U )中的最大流x的算法的程序設(shè)計(jì)具體步驟如下：對(duì)每個(gè)節(jié)點(diǎn)j，其標(biāo)號(hào)包括兩部分信息(pred (j), max f(j)該節(jié)點(diǎn)在可能的增廣路中的前一個(gè)節(jié)點(diǎn)pred (j)，以及沿該可能的增廣路到該節(jié)點(diǎn)為止可以增廣的最大 流量 max f (j)。STEP0置初始可行流x (如零流)；對(duì)節(jié)點(diǎn)t標(biāo)號(hào)，即令max f(t)=任意正值(如1)。STEP1若ma

14、x f(t) 0，繼續(xù)下一步；否則停止，已經(jīng)得到最大流，結(jié)束。STEP2取消所有節(jié)點(diǎn)j g V的標(biāo)號(hào)，即令max f( j) = 0，pred (j) = 0 ；令LIST= s ，對(duì)節(jié)點(diǎn)s標(biāo)號(hào)，即令max f(s)=充分大的正值。STEP3如果LIST尹且max f( t) = 0，繼續(xù)下一步；否則：(3a)如果t已經(jīng)有標(biāo)號(hào)(即max f(t) 0)，則找到了一條增廣路，沿該增廣路對(duì)流X進(jìn)行增廣(增廣的流量為max f(t)，增廣路 可以根據(jù)pred回溯方便地得到)，轉(zhuǎn)STEP1。(3b)如果t沒有標(biāo)號(hào)(即LIST=且max f( t) = 0)，轉(zhuǎn)STEP1。STEP4從LIST中移走一個(gè)

15、節(jié)點(diǎn)Z ；尋找從節(jié)點(diǎn)z出發(fā)的所有可能的增廣?。?4a)對(duì)非飽和前向 弧(, j)，若節(jié)點(diǎn)j沒有標(biāo)號(hào)(即pred (j) = 0)，對(duì)j進(jìn)行標(biāo)號(hào)，即令max f (j) = minmax f( z), u 一 x ，pred (j) = i，并將j加入LIST中。j j(4b)對(duì)非空后向弧(j,i)，若節(jié)點(diǎn)j沒有標(biāo)號(hào)(即pred (j) = 0)，對(duì)j進(jìn)行標(biāo)號(hào)，即令max f (j) = minmax f( i), x ， pred (j) = -i，并將j加入LIST中。例14用Ford-Fulkerson算法計(jì)算如下網(wǎng)絡(luò)中的最大流，每條弧上的兩個(gè)數(shù)字分別表示容量和當(dāng)前 流量。解 編寫程序如下

16、：clc,clear,M=1000; 0maxf=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(label1,record);list=union(list,label1);pred(label1)=flag;maxf(label1)=m

17、in(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(label2,flag);record=union(record,label2);endif maxf(n)0v2=n;v1=pred(v2);while v2=1if

18、v10f(v1,v2)=f(v1,v2)+maxf(n);elsev1=abs(v1);f(v2,v1)=f(v2,v1)-maxf(n);endv2=v1;v1=pred(v2);endendendf8最小費(fèi)用流及其求法8.1最小費(fèi)用流上面我們介紹了一個(gè)網(wǎng)絡(luò)上最短路以及最大流的算法，但是還沒有考慮到網(wǎng)絡(luò)上流的費(fèi)用問題，在 許多實(shí)際問題中，費(fèi)用的因素很重要。例如，在運(yùn)輸問題中，人們總是希望在完成運(yùn)輸任務(wù)的同時(shí)，尋 求一個(gè)使總的運(yùn)輸費(fèi)用最小的運(yùn)輸方案。這就是下面要介紹的最小費(fèi)用流問題。在運(yùn)輸網(wǎng)絡(luò)N = (s,t, V, A,U )中，設(shè)c是定義在A上的非負(fù)函數(shù)，它表示通過弧(i,j)單位流的費(fèi)

19、用。所謂最小費(fèi)用流問題就是從發(fā)點(diǎn)到收點(diǎn)怎樣以最小費(fèi)用輸送一已知量為v(f)的總流量。最小費(fèi)用流問題可以用如下的線性規(guī)劃問題描述：min cfijij(i, j)e Av (f),i = ss.t. f-f = -v (fi = tijjij:(i, j)e Aj:( j,i)eA0, i尹s, t0 fv(fmax)，則 本問題無解。8.2求最小費(fèi)用流的一種方法一迭代法這里所介紹的求最小費(fèi)用流的方法叫做迭代法。這個(gè)方法是由Busacker和Gowan在1961年提出 的。其主要步驟如下：求出從發(fā)點(diǎn)到收點(diǎn)的最小費(fèi)用通路口 (s, t)。對(duì)該通路口 (s, t)分配最大可能的流量：f = min

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

21、).*num;w=w+(w=0)-eye(num).*M;p=zeros(num);for k=1:numfor i=1:numfor j=1:numif w(i,j)w(i,k)+w(k,j)w(i,j)=w(i,k)+w(k,j);p(i,j)=k;endendendendif w(1,num)=Mpath=;elsepath=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);elsepath(s(1),

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

23、dwhile allflowflowvaluew=(flow0).*cost);path=floydpath(w);% 調(diào)用 floydif isempty(path)return;endtheta=min(min(path.*(rongliang-flow)+(path.*(rongliang-flow)=0).*M);theta=min(min(path.*flow+(path.*flow=0).*M),theta);if allflow+thetaflowvaluetheta=flowvalue-allflow;endflow=flow+(rongliang0).*(path-path).*theta;allflow=sum(flow(1,:);end對(duì)于習(xí)題五中的第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)習(xí)題五一只狼、一頭山羊和一籮卷心菜在河的同側(cè)。一個(gè)擺渡人要將它們運(yùn)過河去，但由于船小，