最大流問題

最大流問題圖和收發(fā)點(diǎn)

一個(gè)圖是由點(diǎn)集V={v_i}和V中元素的無序?qū)Φ囊粋€(gè)集合E={e_k}所構(gòu)成的二元組，記為G=(V,E)，V中的元素v_i叫做頂點(diǎn)，E中的元素e_k，叫做邊。

僅有一個(gè)入次為0的點(diǎn)v_s稱為發(fā)點(diǎn)(源)，一個(gè)出次為0的點(diǎn)v_t稱為收點(diǎn)(匯)，其余點(diǎn)為中間點(diǎn)，這樣的網(wǎng)絡(luò)G稱為容量網(wǎng)絡(luò)，常記做G=(V,E,C)。

最大流問題容量和流量

設(shè)有向連通圖G=(V,E)，G的每條邊(v_i,v_j)上的非負(fù)數(shù)c_ij稱為邊的容量。對任一G中的邊(v_i,v_j)有流量f_ij，稱集合f={f_ij}為網(wǎng)絡(luò)G上的一個(gè)流。圖1即為一個(gè)有向連通圖，括號中第一個(gè)數(shù)字代表容量，第二個(gè)數(shù)字代表流量。

最大流問題可行流

稱滿足下列兩個(gè)條件的流為可行流：

1.容量限制條件：對G中的每條邊(v_i,v_j)，有0≤f_ij≤c_ij；即每條邊上的流量非負(fù)而且最大也只能達(dá)到容量的限制。

2.平衡條件：對中間點(diǎn)v_i，有

對發(fā)、收點(diǎn)v_s,v_t,，有

一個(gè)流f={f_ij}，當(dāng)f_ij=c_ij，則稱流f對邊(vi,vj)是飽和的，否則稱f對(v_i,v_j)不飽和。

最大流問題割（截）集

容量網(wǎng)路G=(V,E,C),v_s,v_t為發(fā)、收點(diǎn)，若有邊集E‘為E的子集，將G為兩個(gè)子圖G₁,G₂，即點(diǎn)集V被剖分其為兩個(gè)頂點(diǎn)集合分別記

1.若把整個(gè)截集的弧從網(wǎng)絡(luò)G=(V,E,C)中丟去，則不存在從v_s和vt的有向路，即圖(V,E-E')不連通。

2.只要沒把整個(gè)截集刪去，就存在從v_s和vt的有向路，即當(dāng)E’‘為E的真子集，圖G(V,E-E'')仍連通。

由此可知，截集是從起點(diǎn)v_s到終點(diǎn)v_t的必經(jīng)之路。

割集

由割集的定義不難看出，無論拿掉那個(gè)割集，發(fā)點(diǎn)v_s到收點(diǎn)v_t便不再相通，所以任何一個(gè)可行流都會經(jīng)過割集，且不會超過任一割集的容量。最小割如同瓶頸一般，即使是最大流也無法超過最小割，網(wǎng)絡(luò)的最大流與最小割容量滿足下面的定理（證明略）。

最大流問題定理一

設(shè)f為網(wǎng)絡(luò)G=(V,E,C)的任一可行流，流量為v(f)，

最大流問題定理二

由定理一可知，最大流的流量v(f)和某一割集K的容量相等，而且最大流的流量本身也不帶任一割集的容量，因此割集一定是最小的割集。

任一網(wǎng)絡(luò)G中，從v_s到v_t的最大流的流量等于分離v_s、v_t的最小割的容量（最小的割集的容量）。

最大流問題前后向弧

一條從起點(diǎn)v_s到終點(diǎn)vt的鏈μ，規(guī)定從v_s到v_t的方向?yàn)殒湨痰姆较?，鏈上與μ方向一致的邊叫前向?。ㄟ叄涀鳓?sup class="normal">-；與μ方向相反的邊稱為后向弧（邊），記作μ 。

最大流問題可增廣鏈

f是一個(gè)可行流，f_ij表示由i點(diǎn)指向j點(diǎn)的流量，如果滿足前向弧的流量非負(fù)且小于容量，或后向弧的流量大于0且不超過容量：

則稱μ為從v_s到v_t的關(guān)于f的可增廣鏈。

可增廣鏈的實(shí)際意義是：沿著這條從v_s到v_t輸送的流，仍有潛力可挖，只要前向弧的流量增加或后向弧的流量減少，就可以將截集的流量提高。調(diào)整后的流，在各點(diǎn)仍滿足平衡條件及容量限制條件，仍為可行流。

從另一個(gè)角度來說，可以提高流量的可行流也不是最大流，因此可行流f是最大流的充要條件是不存在從v_s到v_t的可增廣鏈。

最大流問題是一類應(yīng)用極為廣泛的問題，例如在交通網(wǎng)絡(luò)中有人流、車流、貨物流，供水網(wǎng)絡(luò)中有水流，金融系統(tǒng)中現(xiàn)金流，等等。求最大流的標(biāo)號算法最早由福特和福克遜于1956年提出，20世紀(jì)50年代福特(Ford)、?？诉d(Fulkerson)建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成成分。

最大流問題，是網(wǎng)絡(luò)流理論研究的一個(gè)基本問題，求網(wǎng)絡(luò)中一個(gè)可行流f*，使其流量v(f)達(dá)到最大， 這種流f稱為最大流，這個(gè)問題稱為(網(wǎng)絡(luò))最大流問題。最大流問題是一個(gè)特殊的線性規(guī)劃問題，就是在容量網(wǎng)絡(luò)中，尋找流量最大的可行流。

最大流問題可以建立如下形式的線性規(guī)劃數(shù)學(xué)模型：

式中v(f)稱為這個(gè)可行流的流量、發(fā)點(diǎn)的凈輸出量或收點(diǎn)的凈輸出量。∞一般用標(biāo)號法尋求有向最大流比用求線性規(guī)劃問題的一般方法要方便得多。

最大的標(biāo)號算法還用于解決多發(fā)點(diǎn)多收點(diǎn)網(wǎng)絡(luò)的最大問題，設(shè)容量網(wǎng)絡(luò)G有若干個(gè)發(fā)點(diǎn)x₁,x₂,...,x_m；若干收點(diǎn)y₁,y₂,...,y_n，可以添加兩個(gè)新點(diǎn)vs,vt，用容量為∞的有向邊分別連接兩個(gè)新點(diǎn)v_s與點(diǎn)x₁,x₂,...,x_m，點(diǎn)y₁,y₂,...,y_n與v_t，得到新的網(wǎng)路G‘。G’是一個(gè)只有一個(gè)收點(diǎn)和發(fā)點(diǎn)的網(wǎng)絡(luò)，求解最大流問題即可都得到G的解。

最大流問題算法思路

從可行流和可增廣鏈關(guān)系來看，就可以知道一種尋求最大流的方法：從一個(gè)可行流開始，尋求關(guān)于這個(gè)可行流的可增廣鏈，若存在，則可以經(jīng)過調(diào)整，得到一個(gè)新的可行流，其流量比原來的可行流要大，重復(fù)這個(gè)過程，直到不存在關(guān)于該流的可增廣鏈時(shí)就得到了最大流。 v這種算法由Ford 和 Fulkerson于1956年提出，故又稱 　Ford-Fulkerson標(biāo)號法。

最大流問題算法步驟

標(biāo)號的方法可分為兩步：第一步是標(biāo)號過程，通過標(biāo)號來尋找可增廣鏈；第二步是調(diào)整過程，沿可增廣鏈調(diào)整f以增加流量。

1.標(biāo)號過程

（1）給發(fā)點(diǎn)（始點(diǎn)）以標(biāo)號(△, ∞)或(0, ∞)。

（2）選擇一個(gè)已標(biāo)號的頂點(diǎn)v_i，對于v_i的所有未給標(biāo)號的鄰接點(diǎn)v_j按下列規(guī)則處理：

(a)若后向邊(v_j,v_i)∈E，且f_ji>0時(shí)，則令δ_j=min(f_ji,δ_i)，并給v_j以標(biāo)號(-v_i,δ_j)，這表明v_j點(diǎn)的v_i點(diǎn)的邊最多可以減少δ_j的流量以提高整個(gè)網(wǎng)絡(luò)的流量。

(b)若前向邊(v_i,v_j)∈E，且f_ij

括弧內(nèi)的第一個(gè)數(shù)字表示這個(gè)節(jié)點(diǎn)得到的得到標(biāo)號前的第一個(gè)結(jié)點(diǎn)的代號，第二個(gè)數(shù)字表示從上個(gè)標(biāo)號節(jié)點(diǎn)到這個(gè)標(biāo)號節(jié)點(diǎn)允許的最大調(diào)整量δ，假定發(fā)點(diǎn)的調(diào)整量不限，所以標(biāo)記為 ∞。

（3）重復(fù)（2）直到收點(diǎn)v_t被標(biāo)號或不再有頂點(diǎn)可被標(biāo)號為止。

若v_t沒有得到標(biāo)號，說明標(biāo)號過程已無法進(jìn)行，可行流f已是最大流。若v_t得到標(biāo)號，說明存在一條可增廣鏈，轉(zhuǎn)入調(diào)整過程。標(biāo)號若有多條增廣鏈時(shí)，不用刻意考慮哪種調(diào)整更適合，只需一條一條地轉(zhuǎn)入調(diào)整過程，不用全盤考慮。

2.調(diào)整過程

（1）令這條被找到的增廣鏈中所有的前向弧全部加上δ_j的流量，所有的后向弧全部減去δ_j的流量，至于不在增廣鏈之中的邊的流量則不需要調(diào)整。

（2）去掉所有標(biāo)號，回到第1步，對可行流f’重新標(biāo)號。

最小費(fèi)用最大流問題是經(jīng)濟(jì)學(xué)和管理學(xué)中的一類典型問題。在一個(gè)網(wǎng)絡(luò)中每段路徑都有“容量”和“費(fèi)用”兩個(gè)限制的條件下，此類問題的研究試圖尋找出：流量從A到B，如何選擇路徑、分配經(jīng)過路徑的流量，可以達(dá)到所用的費(fèi)用最小的要求。

在實(shí)際中：n輛卡車要運(yùn)送物品，從A地到B地。由于每條路段都有不同的路費(fèi)要繳納，每條路能容納的車的數(shù)量有限制，如何分配卡車的出發(fā)路徑可以達(dá)到費(fèi)用最低，物品又能全部送到。

解決最小費(fèi)用最大流問題，一般有兩條途徑。一條途徑是先用最大流算法算出最大流，然后根據(jù)邊費(fèi)用，檢查是否有可能在流量平衡的前提下通過調(diào)整邊流量，使總費(fèi)用得以減少？只要有這個(gè)可能，就進(jìn)行這樣的調(diào)整。調(diào)整后，得到一個(gè)新的最大流。

然后，在這個(gè)新流的基礎(chǔ)上繼續(xù)檢查，調(diào)整。這樣迭代下去，直至無調(diào)整可能，便得到最小費(fèi)用最大流。這一思路的特點(diǎn)是保持問題的可行性（始終保持最大流），向最優(yōu)推進(jìn)。另一條解決途徑和前面介紹的最大流算法思路相類似，一般首先給出零流作為初始流。這個(gè)流的費(fèi)用為零，當(dāng)然是最小費(fèi)用的。然后尋找一條源點(diǎn)至匯點(diǎn)的增流鏈，但要求這條增流鏈必須是所有增流鏈中費(fèi)用最小的一條。如果能找出增流鏈，則在增流鏈上增流，得出新流。將這個(gè)流做為初始流看待，繼續(xù)尋找增流鏈增流。這樣迭代下去，直至找不出增流鏈，這時(shí)的流即為最小費(fèi)用最大流。這一算法思路的特點(diǎn)是保持解的最優(yōu)性（每次得到的新流都是費(fèi)用最小的流），而逐漸向可行解靠近（直至最大流時(shí)才是一個(gè)可行解）。

由于第二種算法和已介紹的最大流算法接近，且算法中尋找最小費(fèi)用增流鏈，可以轉(zhuǎn)化為一個(gè)尋求源點(diǎn)至匯點(diǎn)的最短路徑問題，所以這里介紹這一算法。

在這一算法中，為了尋求最小費(fèi)用的增流鏈，對每一當(dāng)前流，需建立伴隨這一網(wǎng)絡(luò)流的增流網(wǎng)絡(luò)。例如圖 1 網(wǎng)絡(luò)G 是具有最小 費(fèi)用的流，邊旁參數(shù)為c(e),f(e),w(e），而圖 2 即為該網(wǎng)絡(luò)流 的增流網(wǎng)絡(luò)G′。增流網(wǎng)絡(luò)的頂點(diǎn)和原網(wǎng)絡(luò)相同。按以下原則建 立增流網(wǎng)絡(luò)的邊：若G中邊（u，v）流量未飽，即f(u,v) < e(u,v），則G ' 中建邊（u,v），賦權(quán)w ' (u,v)=w(u,v）；若G中邊（u,v）已有流量，即f(u,v）〉0，則G′中建邊（v,u），賦權(quán)w′（v,u) =-w(u,v）。建立增流網(wǎng)絡(luò)后，即可在此網(wǎng)絡(luò)上求源點(diǎn)至匯點(diǎn)的最短路徑，以此決定增流路徑，然后在原網(wǎng)絡(luò)上循此路徑增流。這里，運(yùn)用的仍然是最大流算法的增流原理，唯必須選定最小費(fèi)用的增流鏈增流。

計(jì)算中有一個(gè)問題需要解決。這就是增流網(wǎng)絡(luò)G ′中有負(fù)權(quán)邊，因而不能直接應(yīng)用標(biāo)號法來尋找x至y的最短路徑，采用其它計(jì)算有負(fù)權(quán)邊的網(wǎng)絡(luò)最短路徑的方法來尋找x至y的最短路徑，將 大大降低計(jì)算效率。為了仍然采用標(biāo)號法計(jì)算最短路徑，在每次建立增流網(wǎng)絡(luò)求得最短路徑后，可將網(wǎng)絡(luò)G的權(quán)w(e）做一次修正，使再建的增流網(wǎng)絡(luò)不會出現(xiàn)負(fù)權(quán)邊，并保證最短路徑不至于因此而改變。下面介紹這種修改方法。當(dāng)流值為零，第一次建增流網(wǎng)絡(luò)求最短路徑時(shí)，因無負(fù)權(quán)邊，當(dāng)然可以采用標(biāo)號法進(jìn)行計(jì)算。為了使以后建立增流網(wǎng)絡(luò)時(shí)不出現(xiàn)負(fù)權(quán)邊，采取的辦法是將 G中有流邊（f(e)>0）的權(quán)w(e）修正為0。為此， 每次在增流網(wǎng)絡(luò)上求得最短路徑后，以下式計(jì)算G中新的邊權(quán)w " (u,v）：

w " (u,v)=L(u)-L(v) w(u,v) (*)

式中 L(u),L(v) -- 計(jì)算G′的x至y最短路徑時(shí)u和v的標(biāo)號值。第一次求最短徑時(shí)如果（u,v）是增流路徑上的邊， 則據(jù)最短 路徑算法一定有 L(v)=L(u) w ' (u,v)=L(u) w(u,v）， 代入（*）式必有

w″（u,v)=0。

如果（u,v）不是增流路徑上的邊，則一定有：

L(v）≤L(u) w(u,v）， 代入（*）式則有 w(u,v）≥0。

可見第一次修正w(e）后，對任一邊，皆有w(e）≥0， 且有流 的邊（增流鏈上的邊），一定有w(e)=0。以后每次迭代計(jì)算，若 f(u,v)>0，增流網(wǎng)絡(luò)需建立（v,u）邊，邊權(quán)數(shù)w ' (v,u)=-w(u,v) =0，即不會再出現(xiàn)負(fù)權(quán)邊。 此外，每次迭代計(jì)算用（*）式修正一切w(e）， 不難證明對每一條x至y的路徑而言，其路徑長度都同樣增加L(x)-L(y）。因此，x至y的最短路徑不會因?qū)(e）的修正而發(fā)生變化。

【計(jì)算步驟】

⒈ 對網(wǎng)絡(luò)G=[V,E,C,W]，給出流值為零的初始流。

⒉ 作伴隨這個(gè)流的增流網(wǎng)絡(luò)G′=[V′，E′，W′]。G′的頂點(diǎn)同G：V′=V。若G中f(u,v)0，則G′中建邊（v,u），w′（v,u)=-w(u,v）。

⒊ 若G′不存在x至y的路徑，則G的流即為最小費(fèi)用最大流， 停止計(jì)算；否則用標(biāo)號法找出x至y的最短路徑P。

⒋ 根據(jù)P，在G上增流：對P的每條邊（u,v），若G存在（u,v），則（u,v）增流；若G存在（v,u），則（v,u）減流。增（減）流后，應(yīng)保證對任一邊有c(e）≥ f(e）≥0。

⒌ 根據(jù)計(jì)算最短路徑時(shí)的各頂點(diǎn)的標(biāo)號值L(v），按下式修 改G一切邊的權(quán)數(shù)w(e):

L(u)-L(v) w(e）→w(e）。

⒍ 將新流視為初始流，轉(zhuǎn)2。

在圖論中，網(wǎng)絡(luò)流（英語：Network flow）是指在一個(gè)每條邊都有容量（capacity）的有向圖分配流，使一條邊的流量不會超過它的容量。通常在運(yùn)籌學(xué)中，有向圖稱為網(wǎng)絡(luò)。頂點(diǎn)稱為節(jié)點(diǎn)（node）而邊稱為?。╝rc）。一道流必須匹配一個(gè)結(jié)點(diǎn)的進(jìn)出的流量相同的限制，除非這是一個(gè)源點(diǎn)（source）──有較多向外的流，或是一個(gè)匯點(diǎn)（sink）──有較多向內(nèi)的流。一個(gè)網(wǎng)絡(luò)可以用來模擬道路系統(tǒng)的交通量、管中的液體、電路中的電流或類似一些東西在一個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)中游動的任何事物。