1、第三節(jié) 最大流問題3.1 基本概念與定理3.2 求解網(wǎng)絡(luò)最大流的方法（標(biāo)號(hào)法）精品課程運(yùn)籌學(xué)編輯ppt第三節(jié) 最大流問題 流量問題在實(shí)際中是一種常見的問題。如公路系統(tǒng)中有車輛流量問題，供電系統(tǒng)中有電流量問題等等。最大流問題是在單位時(shí)間內(nèi)安排一個(gè)運(yùn)送方案，將發(fā)點(diǎn)的物質(zhì)沿著弧的方向運(yùn)送到收點(diǎn)，使總運(yùn)輸量最大。精品課程運(yùn)籌學(xué)編輯ppt3.1 基本概念與定理 設(shè)cij為?。╥，j）的容量，fij為弧（i，j）的流量。容量是?。╥，j）單位時(shí)間內(nèi)的最大通過能力，流量是?。╥，j）單位時(shí)間內(nèi)的實(shí)際通過量，流量的集合f=fij稱為網(wǎng)絡(luò)的流。發(fā)點(diǎn)到收點(diǎn)的總流量記為v=v(f)。 設(shè)D=(V,A)是一有向圖且對(duì)

2、任意E均有容量cij =（vi，vj），記C=cij（vi，vj）A,此外精品課程運(yùn)籌學(xué)編輯ppt D中只有一個(gè)源vs和匯vt( 即D中與vs相關(guān)聯(lián)的弧只能以 vs為起點(diǎn)，與vt相關(guān)聯(lián)的弧只能以 vt為終點(diǎn))，則稱D=(V,A,C, vs,vt)為一網(wǎng)絡(luò)。例6.3.1 圖6-3-1給出了一張網(wǎng)絡(luò)，其中：vs為源，vt為匯，弧旁的數(shù)字為該段弧的容量cij與流量fij，則顯然有0fij cij 。 精品課程運(yùn)籌學(xué)編輯ppt 最大流問題可以建立如下形式的線性規(guī)劃數(shù)學(xué)模型。圖6-3-1最大流問題的線性規(guī)劃數(shù)學(xué)模型為 max v=fs1+fs2 所有弧(i,j) 由線性規(guī)劃理論知，滿足式上式的約束條件的

3、解fij稱為可行解，在最大流問題中稱為可行流。精品課程運(yùn)籌學(xué)編輯ppt可行流滿足下列三個(gè)條件： 條件（2）和條件（3）也稱為流量守恒條件。 精品課程運(yùn)籌學(xué)編輯ppt 在圖D中，從發(fā)點(diǎn)到收點(diǎn)的一條路線稱為鏈，從發(fā)點(diǎn)到收點(diǎn)的方向規(guī)定為鏈的方向。與鏈的方向相同的弧稱為前向弧，前向弧集合記為u+ ，與鏈的方向相反的弧稱為后向弧，后向弧集合記為u-。 設(shè)f是一個(gè)可行流，如果存在一條從發(fā)點(diǎn)vs到收點(diǎn)vt到的鏈u滿足： （1）所有前向弧上fijcij (2)所有后向弧上fij0 則稱鏈u為增廣鏈. 精品課程運(yùn)籌學(xué)編輯ppt 設(shè)S,TV,ST=,vsS,vtT則稱（S，T）=（vi，vj）viS,vjT為圖D

4、的一個(gè)割集；稱C（S，T）= 為割集（S，T）的容量。 顯然對(duì)任意可行流f及任意割集（S，T）總有V(f)=C(S,T).故有某個(gè)可行流f*及某一割集（S*，T*）使得V(f*)= C（S*，T*），則f*為D的最大流，（S*，T*）為最小容量割集。 定理6.3.1 圖D上的可行流f*是最大流的充要條件是D上不存在關(guān)于f*的增廣鏈。精品課程運(yùn)籌學(xué)編輯ppt 3.2 求解網(wǎng)絡(luò)最大流的方法（標(biāo)號(hào)法） 標(biāo)號(hào)法是一種圖上迭代計(jì)算方法，該算法首先給出一個(gè)初始可行流，通過標(biāo)號(hào)找出一條增廣鏈，然后調(diào)整增廣鏈上的流量，得到更大的流量。再用標(biāo)號(hào)找出一條新的增廣鏈，再調(diào)整直到標(biāo)號(hào)過程不能進(jìn)行下去為止，這時(shí)的可行流

5、就是最大流。 精品課程運(yùn)籌學(xué)編輯ppt標(biāo)號(hào)法步驟如下：第一步 找出一個(gè)初始可行流fij(0),例如所有弧的流量fij(0) =0.第二步 對(duì)點(diǎn)進(jìn)行標(biāo)號(hào)找出一條增廣鏈。 （1） 起點(diǎn)標(biāo)號(hào)（） （2）選一個(gè)點(diǎn)vi已標(biāo)號(hào)且另一端未標(biāo)號(hào)的弧沿著某條鏈向收點(diǎn)檢查 （a）如果弧是前向弧且有fijcij，則vj標(biāo)號(hào) j=cijfij（b）如果弧是后向弧且有fij0，則vj標(biāo)號(hào)j=fij精品課程運(yùn)籌學(xué)編輯ppt 當(dāng)收點(diǎn)已得到標(biāo)號(hào)時(shí)，說明已找到增廣鏈，依據(jù)v的標(biāo)號(hào)反向追蹤得到一條增廣鏈。當(dāng)收點(diǎn)不能得到標(biāo)號(hào)時(shí)，說明不存在增廣鏈，計(jì)算結(jié)束第三步 調(diào)整流量 (1) 求增廣鏈上點(diǎn)的vi標(biāo)號(hào)的最小值，得到調(diào)整量號(hào) = (2) 調(diào)整流量 精品課程運(yùn)籌學(xué)編輯ppt fij+ （vi，vj）u+f1= fij （vi，vj)u- fij （vi，vj ) u得到新的可行流f1，去掉所有標(biāo)號(hào)，返回到第二步從發(fā)點(diǎn)重新標(biāo)號(hào)尋找增廣鏈，直到收點(diǎn)不能標(biāo)號(hào)為止。 精品課程運(yùn)籌學(xué)編輯ppt例6.3.2用標(biāo)號(hào)法求網(wǎng)絡(luò)最大流（圖6-3-1），弧旁數(shù)字為（cij ，fij(0)）。解 （1） 標(biāo)號(hào)過程。見圖6-3-2。 （2） 增廣鏈為vs，v1，v2，v3，vt （注意（v2，v1），（v3，v2）u- ）。 （3）調(diào)整量=2調(diào)整后得圖6-3-3。 （4） 二次標(biāo)號(hào)過程。見圖6-3-