最大流问题
?
目錄
1 最大流問題的數學描述
1.1 網絡中的流 定義? ? ? ? ? ? ? ? ? ?可行流(feasible flow)
1.2 最大流問題? ? ? ? ? ? ?用線性規劃描述最大流問題? ? ? ? ? ? ? ? ?整流定理
1.3 單源和單匯運輸網絡? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?多源多匯網絡?轉化成單源單匯網絡
2 最大流和最小割關系? ? ? ? ? ? ? ? ? ? ? ? ?割的容量
3 最大流的一種算法—標號法? ? ? ? ? ? ??(A)標號過程:? ? ? ? ? ? ?(B)增流過程? ? ? ? ? ? ? ? ??網絡最大流 x 的求解步驟
1 最大流問題的數學描述
1.1 網絡中的流 定義
在以V 為節點集, A 為弧集的有向圖G = (V, A) 上定義如下的權函數:
(i) L : A → R 為孤上的權函數,弧 (i, j)∈ A 對應的權 L(i, j) 記為?,稱為孤 (i, j) 的容量下界(lower bound);
(ii)U : A → R 為弧上的權函數,弧(i, j)∈ A對應的權U(i, j) 記為?,稱為孤 (i, j) 的容量上界或容量(capacity);
(iii) D :V → R 為頂點上的權函數,節點i ∈V 對應的權 D(i) 記為 ?,稱為頂 點i 的供需量(supply/demand);
此時所構成的網絡稱為流網絡,可以記為 N = (V, A, L,U,D) 。 由于我們只討論V, A 為有限集合的情況,所以對于弧上的權函數 L,U 和頂點上的 權函數 D ,可以直接用所有孤上對應的權和頂點上的權組成的有限維向量表示,因此 L,U, D 有時直接稱為權向量,或簡稱權。由于給定有向圖G = (V, A) 后,我們總是可 以在它的弧集合和頂點集合上定義各種權函數,所以流網絡一般也直接簡稱為網絡。
在流網絡中,弧(i, j) 的容量下界 和容量上界表示的物理意義分別是:通過該 弧發送某種“物質”時,必須發送的最小數量為 ,而發送的最大數量為 。頂點i ∈V 對應的供需量則表示該頂點從網絡外部獲得的“物質”數量( > 0時),或從該頂 點發送到網絡外部的“物質”數量(< 0 時)。下面我們給出嚴格定義。
可行流(feasible flow)
可見,當 di > 0時,表示有di 個單位的流量從網絡外部流入該頂點,因此頂點i 稱 為供應點(supply node)或源(source),有時也形象地稱為起始點或發點等;當di < 0 時,表示有|di | 個單位的流量從該頂點流失到網絡外部(或說被該頂點吸收),因此頂 點i 稱為需求點(demand node)或匯(sink),有時也形象地稱為終止點或收點等;當 di = 0時,頂點i 稱為轉運點(transshipment node)或平衡點、中間點等。此外,根據 (1)可知,對于可行網絡,必有
也就是說,所有節點上的供需量之和為 0 是網絡中存在可行流的必要條件
1.2 最大流問題
考慮如下流網絡 N = (V, A,U,D):節點 s 為網絡中唯一的源點,t 為唯一的匯點, 而其它節點為轉運點。如果網絡中存在可行流 f ,此時稱流 f 的流量(或流值,flow value)為?(根據(3),它自然也等于 ? ?),通常記為v 或v( f ) ,即
對這種單源單匯的網絡,如果我們并不給定 和 ?(即流量不給定),則網絡一 般記為 N = (s,t,V, A,U) 。最大流問題( maximum flow problem )就是在 N = (s,t,V, A,U) 中找到流值最大的可行流(即最大流)。我們將會看到,最大流問題 的許多算法也可以用來求解流量給定的網絡中的可行流。也就是說,當我們解決了最大 流問題以后,對于在流量給定的網絡中尋找可行流的問題,通常也就可以解決了。
用線性規劃描述最大流問題
因此,用線性規劃的方法,最大流問題可以形式地描述如下:
【定義】 如果一個矩陣 A 的任何子方陣的行列式的值都等于0,1或 ?1,則稱 A 是 全幺模的(totally unimodular TU,又譯為全單位模的),或稱 A 是全幺模矩陣。
整流定理
【定理 7】(整流定理) 最大流問題所對應的約束矩陣是全幺模矩陣。若所有弧容量 均為正整數,則問題的最優解為整數解。 最大流問題是一個特殊的線性規劃問題。我們將會看到利用圖的特點,解決這個問 題的方法較之線性規劃的一般方法要方便、直觀得多。
1.3 單源和單匯運輸網絡
多源多匯網絡?轉化成單源單匯網絡
實際問題往往是多源多匯網絡,為了計算的規格化,可將多源多匯網絡G 化成單 源單匯網絡G' 。設 X 是G 的源,Y 是G 的匯,具體轉化方法如下:
(i)在原圖G 中增加兩個新的頂點 x 和 y ,令為新圖G' 中之單源和單匯,則G 中 所有頂點V 成為G' 之中間頂點集。
(ii)用一條容量為∞的弧把 x 連接到 X 中的每個頂點。
(iii)用一條容量為∞的弧把Y 中的每個頂點連接到 y 。 G 和G' 中的流以一個簡單的方式相互對應。若 f 是G 中的流,則由
2 最大流和最小割關系
割的容量
則在這條可增廣軌上每條前向弧的流都可以增加一個量δ ,而相應的后向弧的流可減 少δ ,這樣就可使得網絡的流量獲得增加,同時可以使每條弧的流量不超過它的容量, 而且保持為正,也不影響其它弧的流量。總之,網絡中 f 可增廣軌的存在是有意義的, 因為這意味著 f 不是最大流。
3 最大流的一種算法—標號法
標號法是由 Ford 和 Fulkerson 在 1957 年提出的。用標號法尋求網絡中最大流的基 本思想是尋找可增廣軌,使網絡的流量得到增加,直到最大為止。即首先給出一個初始 流,這樣的流是存在的,例如零流。如果存在關于它的可增廣軌,那么調整該軌上每條 弧上的流量,就可以得到新的流。對于新的流,如果仍存在可增廣軌,則用同樣的方法 使流的值增大,繼續這個過程,直到網絡中不存在關于新得到流的可增廣軌為止,則該 流就是所求的最大流。
這種方法分為以下兩個過程:
A.標號過程:通過標號過程尋找一條可增廣軌。
B.增流過程:沿著可增廣軌增加網絡的流量。
這兩個過程的步驟分述如下。
(A)標號過程:
(B)增流過程
網絡最大流 x 的求解步驟
求網絡 N = (s,t,V, A,U) 中的最大流 x 的算法的程序設計具體步驟如下:
對每個節點 j ,其標號包括兩部分信息 (pred( j),maxf(j))
該節點在可能的增廣路中的前一個節點 pred( j) ,以及沿該可能的增廣路到該節點為止 可以增廣的最大流量 maxf( j)。
并將 j 加入 LIST 中。
例 17 用 Ford-Fulkerson 算法計算如圖 6 網絡中的最大流,每條弧上的兩個數字分 別表示容量和當前流量。
解 編寫程序如下:
clc,clear 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)=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)=inf;% list是未檢查鄰接點的標號點,record是已標號點 while (~isempty(list))&(maxf(n)==0)flag=list(1);list(1)=[];label1= find(u(flag,:)-f(flag,:));label1=setdiff(label1,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));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 v1>0f(v1,v2)=f(v1,v2)+maxf(n);elsev1=abs(v1);f(v2,v1)=f(v2,v1)-maxf(n);endv2=v1; v1=pred(v2);endend end f例18 現需要將城市 s 的石油通過管道運送到城市t ,中間有4個中轉站 ?v1 ,v2 ,v3 和 ?v4 ,城市與中轉站的連接以及管道的容量如圖7所示,求從城市 s 到城市t 的最大流。
解 使用最大流的數學規劃表達式,編寫LINGO程序如下:
model: sets: nodes/s,1,2,3,4,t/; arcs(nodes,nodes)/s 1,s 3,1 2,1 3,2 3,2 t,3 4,4 2,4 t/:c,f; endsets data: c=8 7 9 5 2 5 9 6 10; enddata n=@size(nodes); !頂點的個數; max=flow; @for(nodes(i)|i #ne#1 #and# i #ne# n:@sum(arcs(i,j):f(i,j))=@sum(arcs(j,i):f(j,i) @sum(arcs(i,j)|i #eq# 1:f(i,j))=flow; @sum(arcs(i,j)|j #eq# n:f(i,j))=flow; @for(arcs:@bnd(0,f,c)); end在上面的程序中,采用了稀疏集的編寫方法。下面介紹的程序編寫方法是利用賦權鄰 接矩陣,這樣可以不使用稀疏集的編寫方法,更便于推廣到復雜網絡。
model: sets: nodes/s,1,2,3,4,t/; arcs(nodes,nodes):c,f; endsets data: c=0; @text('fdata.txt')=f; enddata calc: c(1,2)=8;c(1,4)=7; c(2,3)=9;c(2,4)=5; c(3,4)=2;c(3,6)=5; c(4,5)=9;c(5,3)=6;c(5,6)=10; endcalc n=@size(nodes); !頂點的個數; max=flow; @for(nodes(i)|i #ne#1 #and# i #ne# n:@sum(nodes(j):f(i,j))=@sum(nodes(j):f(j,i))); @sum(nodes(i):f(1,i))=flow; @sum(nodes(i):f(i,n))=flow; @for(arcs:@bnd(0,f,c)); end?
?
?
?
總結
- 上一篇: python tfidf特征变换_机器学
- 下一篇: word 编辑域中的汉字_word中插入