《第三節(jié) 最大流問題》由會(huì)員分享，可在線閱讀，更多相關(guān)《第三節(jié) 最大流問題（14頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、精品課程運(yùn)籌學(xué)3.1 基本概念與定理基本概念與定理3.2 求解網(wǎng)絡(luò)最大流的方法（標(biāo)號(hào)法）求解網(wǎng)絡(luò)最大流的方法（標(biāo)號(hào)法）精品課程運(yùn)籌學(xué)第三節(jié) 最大流問題 n 流量問題在實(shí)際中是一種常見的問題。流量問題在實(shí)際中是一種常見的問題。如公路系統(tǒng)中有車輛流量問題，供電系統(tǒng)如公路系統(tǒng)中有車輛流量問題，供電系統(tǒng)中有電流量問題等等。最大流問題是在單中有電流量問題等等。最大流問題是在單位時(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 ciji
2、j為?。榛。╥ i，j j）的容量，）的容量，f fijij為?。榛。╥ i，j j）的流量。容量是?。ǎ┑牧髁俊Ｈ萘渴腔。╥ i，j j）單位時(shí)間內(nèi)的）單位時(shí)間內(nèi)的最大通過能力，流量是?。ㄗ畲笸ㄟ^能力，流量是?。╥ i，j j）單位時(shí)間內(nèi)）單位時(shí)間內(nèi)的實(shí)際通過量，流量的集合的實(shí)際通過量，流量的集合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è)源中
3、只有一個(gè)源vs和匯和匯vt( 即即D中與中與vs相關(guān)聯(lián)的相關(guān)聯(lián)的弧只能以弧只能以 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.16.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，則顯然有，則顯然有0 0f fij ij c cijij 。 精品課程運(yùn)籌學(xué) 最大流問題可以建立如下形式的線性規(guī)劃最大流問題可以建立如下形式的
4、線性規(guī)劃數(shù)學(xué)模型。圖數(shù)學(xué)模型。圖6-3-1最大流問題的線性規(guī)劃數(shù)學(xué)最大流問題的線性規(guī)劃數(shù)學(xué)模型為模型為 max v=fs1+fs2 所有所有弧弧(i,j) 由線性規(guī)劃理論知，滿足式上式的約束條由線性規(guī)劃理論知，滿足式上式的約束條件的解件的解fij稱為可行解，在最大流問題中稱為稱為可行解，在最大流問題中稱為可行流可行流。),(0tsiffiijjijijijcf 0精品課程運(yùn)籌學(xué)可行流滿足下列三個(gè)條件：可行流滿足下列三個(gè)條件： 條件（條件（2）和條件（）和條件（3）也稱為流量守恒條件。）也稱為流量守恒條件。 ijijcf 0vmkmvmimffvsvtitsjffv精品課程運(yùn)籌學(xué) 在圖在圖D中，
5、從發(fā)點(diǎn)到收點(diǎn)的一條路線稱為鏈，中，從發(fā)點(diǎn)到收點(diǎn)的一條路線稱為鏈，從發(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
6、=,vsS,vtT則稱（則稱（S，T）=（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*）為最小容量割集。）為最小容量割集。 定理定理6.3.1 圖圖D上的可行流上的可行流f*是最大流的充要是最大流的充要條件是條件是D上不存在關(guān)于上不存在關(guān)于f*的增廣鏈。的增廣鏈。)
7、,(),(),(tsvvjijivvc精品課程運(yùn)籌學(xué) 3.23.2 求解網(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è)初始可行流，通過標(biāo)號(hào)找出法首先給出一個(gè)初始可行流，通過標(biāo)號(hào)找出一條增廣鏈，然后調(diào)整增廣鏈上的流量，得一條增廣鏈，然后調(diào)整增廣鏈上的流量，得到更大的流量。再用標(biāo)號(hào)找出一條新的增廣到更大的流量。再用標(biāo)號(hào)找出一條新的增廣鏈，再調(diào)整直到標(biāo)號(hào)過程不能進(jìn)行下去為止，鏈，再調(diào)整直到標(biāo)號(hào)過程不能進(jìn)行下去為止，這時(shí)的可行流就是最大流。這時(shí)的可行流就是最大流。 精品課程運(yùn)籌學(xué)標(biāo)號(hào)法步驟如下：標(biāo)號(hào)法步驟如下
8、：第一步第一步 找出一個(gè)初始可行流找出一個(gè)初始可行流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í)，說明已找到增廣鏈，當(dāng)收點(diǎn)已得到標(biāo)號(hào)時(shí)，說
9、明已找到增廣鏈，依據(jù)依據(jù)v的標(biāo)號(hào)反向追蹤得到一條增廣鏈。當(dāng)收的標(biāo)號(hào)反向追蹤得到一條增廣鏈。當(dāng)收點(diǎn)不能得到標(biāo)號(hào)時(shí)，說明不存在增廣鏈，計(jì)算點(diǎn)不能得到標(biāo)號(hào)時(shí)，說明不存在增廣鏈，計(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 f
10、1 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é)例例6.3.2用標(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)過程。見圖標(biāo)號(hào)過程。見圖6-3-2。 （2） 增廣鏈為增廣鏈為vs，v1，v2，v3，vt （注意（注意（v2，v1），（），（v3，v2）u- ）。）。 （3）調(diào)整量）調(diào)整量=2調(diào)整后得圖調(diào)整后得圖6-3-3。 （4） 二次標(biāo)號(hào)過程。見圖二次標(biāo)號(hào)過程。見圖6-3-3。精品課程運(yùn)籌學(xué) 標(biāo)號(hào)無法進(jìn)行下去，最大流流量標(biāo)號(hào)無法進(jìn)行下去，最大流流量V(f*)=3+6=9，最小割集（最小割集（S*，T*）, S*=vs, T*= v1，v2，v3，v4，vt。
第三節(jié) 最大流問題
