【學(xué)習(xí)】第三節(jié)最大流問(wèn)題

1、精品課程運(yùn)籌學(xué)整理課件精品課程運(yùn)籌學(xué)整理課件第三節(jié) 最大流問(wèn)題 n 流量問(wèn)題在實(shí)際中是一種常見(jiàn)的問(wèn)題。流量問(wèn)題在實(shí)際中是一種常見(jiàn)的問(wèn)題。如公路系統(tǒng)中有車輛流量問(wèn)題，供電系統(tǒng)如公路系統(tǒng)中有車輛流量問(wèn)題，供電系統(tǒng)中有電流量問(wèn)題等等。最大流問(wèn)題是在單中有電流量問(wèn)題等等。最大流問(wèn)題是在單位時(shí)間內(nèi)安排一個(gè)運(yùn)送方案，將發(fā)點(diǎn)的物位時(shí)間內(nèi)安排一個(gè)運(yùn)送方案，將發(fā)點(diǎn)的物質(zhì)沿著弧的方向運(yùn)送到收點(diǎn)，使總運(yùn)輸量質(zhì)沿著弧的方向運(yùn)送到收點(diǎn)，使總運(yùn)輸量最大。最大。精品課程運(yùn)籌學(xué)整理課件3.1 3.1 基本概念與定理基本概念與定理 設(shè)設(shè)c cijij為?。榛。╥ i，j j）的容量，）的容量，f fijij為?。榛。╥ i

2、，j j）的流量。容量是?。ǎ┑牧髁俊Ｈ萘渴腔。╥ i，j j）單位時(shí)間內(nèi)的）單位時(shí)間內(nèi)的最大通過(guò)能力，流量是?。ㄗ畲笸ㄟ^(guò)能力，流量是弧（i i，j j）單位時(shí)間內(nèi)）單位時(shí)間內(nèi)的實(shí)際通過(guò)量，流量的集合的實(shí)際通過(guò)量，流量的集合f=ff=fijij 稱為網(wǎng)絡(luò)的稱為網(wǎng)絡(luò)的流。發(fā)點(diǎn)到收點(diǎn)的總流量記為流。發(fā)點(diǎn)到收點(diǎn)的總流量記為v=v(f)v=v(f)。 設(shè)設(shè)D=(V,A)是一有向圖且對(duì)任意是一有向圖且對(duì)任意E均有容量均有容量cij =（vi，vj），記），記C=cij（vi，vj）A,此外此外精品課程運(yùn)籌學(xué)整理課件 D中只有一個(gè)源中只有一個(gè)源vs和匯和匯vt( 即即D中與中與vs相關(guān)聯(lián)的相關(guān)聯(lián)的弧只能以

3、弧只能以 vs為起點(diǎn)，與為起點(diǎn)，與vt相關(guān)聯(lián)的弧只能以相關(guān)聯(lián)的弧只能以 vt為為終點(diǎn)終點(diǎn))，則稱，則稱D=(V,A,C, vs,vt)為一網(wǎng)絡(luò)。為一網(wǎng)絡(luò)。例例6.3.1 6.3.1 圖圖6-3-16-3-1給出了一張網(wǎng)絡(luò)，其中：給出了一張網(wǎng)絡(luò)，其中：v vs s為源，為源，v vt t為匯，弧旁的數(shù)字為該段弧的容量為匯，弧旁的數(shù)字為該段弧的容量c cijij與流量與流量f fijij，則顯然有，則顯然有0f0fij ij c cijij 。 精品課程運(yùn)籌學(xué)整理課件 最大流問(wèn)題可以建立如下形式的線性規(guī)劃最大流問(wèn)題可以建立如下形式的線性規(guī)劃數(shù)學(xué)模型。圖數(shù)學(xué)模型。圖6-3-1最大流問(wèn)題的線性規(guī)劃數(shù)學(xué)

4、最大流問(wèn)題的線性規(guī)劃數(shù)學(xué)模型為模型為 max v=fs1+fs2 所有弧所有弧(i,j) 由線性規(guī)劃理論知，滿足式上式的約束條由線性規(guī)劃理論知，滿足式上式的約束條件的解件的解fij稱為可行解，在最大流問(wèn)題中稱為稱為可行解，在最大流問(wèn)題中稱為可行流可行流。),(0tsiffiijjijijijcf 0精品課程運(yùn)籌學(xué)整理課件可行流滿足下列三個(gè)條件：可行流滿足下列三個(gè)條件： 條件（條件（2）和條件（）和條件（3）也稱為流量守恒條件。）也稱為流量守恒條件。 ijijcf 0vmkmvmimffvsvtitsjffv精品課程運(yùn)籌學(xué)整理課件 在圖在圖D中，從發(fā)點(diǎn)到收點(diǎn)的一條路線稱為鏈，中，從發(fā)點(diǎn)到收點(diǎn)的一

5、條路線稱為鏈，從發(fā)點(diǎn)到收點(diǎn)的方向規(guī)定為鏈的方向。與鏈的從發(fā)點(diǎn)到收點(diǎn)的方向規(guī)定為鏈的方向。與鏈的方向相同的弧稱為方向相同的弧稱為前向弧前向弧，前向弧集合記為，前向弧集合記為u+ ，與鏈的方向相反的弧稱為與鏈的方向相反的弧稱為后向弧后向弧，后向弧集合，后向弧集合記為記為u-。 設(shè)設(shè)f是一個(gè)可行流，如果存在一條從發(fā)點(diǎn)是一個(gè)可行流，如果存在一條從發(fā)點(diǎn)vs到收點(diǎn)到收點(diǎn)vt到的鏈到的鏈u滿足：滿足： （1）所有前向弧上）所有前向弧上fijcijn (2) 所有后向弧上所有后向弧上fij0 則稱鏈則稱鏈u為為增廣鏈增廣鏈. 精品課程運(yùn)籌學(xué)整理課件 設(shè)設(shè)S,TV,ST=,vsS,vtT則稱（則稱（S，T）=（

6、vi，vj）viS,vjT為圖為圖D的一個(gè)的一個(gè)割集割集；稱稱C（S，T）= 為割集（為割集（S，T）的）的容量容量。 顯然對(duì)任意可行流顯然對(duì)任意可行流f及任意割集（及任意割集（S，T）總有總有V(f)=C(S,T).故有某個(gè)可行流故有某個(gè)可行流f*及某一割集及某一割集（S*，T*）使得）使得V(f*)= C（S*，T*），則），則f*為為D的最大流，（的最大流，（S*，T*）為最小容量割集。）為最小容量割集。 定理定理 圖圖D上的可行流上的可行流f*是最大流的充要條件是最大流的充要條件是是D上不存在關(guān)于上不存在關(guān)于f*的增廣鏈。的增廣鏈。),(),(),(tsvvjijivvc精品課程運(yùn)籌學(xué)

7、整理課件 求解網(wǎng)絡(luò)最大流的方法（標(biāo)號(hào)法）求解網(wǎng)絡(luò)最大流的方法（標(biāo)號(hào)法） 標(biāo)號(hào)法是一種圖上迭代計(jì)算方法，該算標(biāo)號(hào)法是一種圖上迭代計(jì)算方法，該算法首先給出一個(gè)初始可行流，通過(guò)標(biāo)號(hào)找出法首先給出一個(gè)初始可行流，通過(guò)標(biāo)號(hào)找出一條增廣鏈，然后調(diào)整增廣鏈上的流量，得一條增廣鏈，然后調(diào)整增廣鏈上的流量，得到更大的流量。再用標(biāo)號(hào)找出一條新的增廣到更大的流量。再用標(biāo)號(hào)找出一條新的增廣鏈，再調(diào)整直到標(biāo)號(hào)過(guò)程不能進(jìn)行下去為止，鏈，再調(diào)整直到標(biāo)號(hào)過(guò)程不能進(jìn)行下去為止，這時(shí)的可行流就是最大流。這時(shí)的可行流就是最大流。 精品課程運(yùn)籌學(xué)整理課件標(biāo)號(hào)法步驟如下：標(biāo)號(hào)法步驟如下：第一步第一步 找出一個(gè)初始可行流找出一個(gè)初始可行

8、流fij(0),例如所有弧的流例如所有弧的流量量fij(0) =0.第二步第二步 對(duì)點(diǎn)進(jìn)行標(biāo)號(hào)找出一條增廣鏈。對(duì)點(diǎn)進(jìn)行標(biāo)號(hào)找出一條增廣鏈。 （1 1） 起點(diǎn)標(biāo)號(hào)（起點(diǎn)標(biāo)號(hào)（） （2 2） 選一個(gè)點(diǎn)選一個(gè)點(diǎn)vi已標(biāo)號(hào)且另一端未標(biāo)號(hào)的弧沿已標(biāo)號(hào)且另一端未標(biāo)號(hào)的弧沿著某條鏈向收點(diǎn)檢查著某條鏈向收點(diǎn)檢查 （a）如果弧是前向弧且有）如果弧是前向弧且有fijcij，則，則vj標(biāo)號(hào)標(biāo)號(hào) j=cijfij（b）如果弧是后向弧且有）如果弧是后向弧且有fij0，則，則vj標(biāo)號(hào)標(biāo)號(hào)j=fij精品課程運(yùn)籌學(xué)整理課件 當(dāng)收點(diǎn)已得到標(biāo)號(hào)時(shí)，說(shuō)明已找到增廣鏈，當(dāng)收點(diǎn)已得到標(biāo)號(hào)時(shí)，說(shuō)明已找到增廣鏈，依據(jù)依據(jù)v的標(biāo)號(hào)反向追蹤得

9、到一條增廣鏈。當(dāng)收的標(biāo)號(hào)反向追蹤得到一條增廣鏈。當(dāng)收點(diǎn)不能得到標(biāo)號(hào)時(shí)，說(shuō)明不存在增廣鏈，計(jì)算點(diǎn)不能得到標(biāo)號(hào)時(shí)，說(shuō)明不存在增廣鏈，計(jì)算結(jié)束結(jié)束第三步第三步 調(diào)整流量調(diào)整流量 (1) 求增廣鏈上點(diǎn)的求增廣鏈上點(diǎn)的vi標(biāo)號(hào)的最小值，得到調(diào)整標(biāo)號(hào)的最小值，得到調(diào)整量號(hào)量號(hào) = (2) 調(diào)整流量調(diào)整流量 jjmin精品課程運(yùn)籌學(xué)整理課件 f fijij+ + （v vi i，v vj j）u u+ +f f1 1= = f fijij （v vi i，v vj j)u u- - f fijij （v vi i，v vj j ) u u 得到新的可行流得到新的可行流f f1 1，去掉所有標(biāo)號(hào)，返回到第，去掉所有標(biāo)號(hào)，返回到第二步從發(fā)點(diǎn)重新標(biāo)號(hào)尋找增廣鏈，直到收點(diǎn)不二步從發(fā)點(diǎn)重新標(biāo)號(hào)尋找增廣鏈，直到收點(diǎn)不能標(biāo)號(hào)為止。能標(biāo)號(hào)為止。 精品課程運(yùn)籌學(xué)整理課件例用標(biāo)號(hào)法求網(wǎng)絡(luò)最大流（圖例用標(biāo)號(hào)法求網(wǎng)絡(luò)最大流（圖6-3-1），弧旁），弧旁數(shù)字為（數(shù)字為（cij ，fij(0)）。）。解解 （1） 標(biāo)號(hào)過(guò)程。見(jiàn)圖標(biāo)號(hào)過(guò)程。見(jiàn)圖6-3-2。 （2） 增廣鏈為增廣鏈為vs，v1，v2，v3，vt （注意（注意（v2，v1），（），（v3，v2）u- ）。）。