最小費用最大流問題

最小費用最大流問題最大流問題最小費用最大流問題2021/5/91

最大流問題引例

基本概念最大流算法算例Back2021/5/92continuedBack

引例假設(shè)某個公路網(wǎng)的每條公路只允許單向行駛，這樣的公路網(wǎng)稱為單行公路網(wǎng)．為了保證暢通，交通部門對每條公路在單位時間內(nèi)通過的車輛數(shù)目要作一個限制．問單位時間內(nèi)最多能有多少輛車從甲地出發(fā)經(jīng)過該公路網(wǎng)到達乙地？

網(wǎng)絡(luò)與流

增廣鏈2021/5/93一、網(wǎng)絡(luò)與流一個有向圖稱為一個網(wǎng)絡(luò)．其中，為圖的所有頂點集；為弧集；為各弧上容量集在中指定了兩點，分別稱為發(fā)點和收點，其余的點叫中間點．定義弧集合上的一個函數(shù)為網(wǎng)絡(luò)的一個流,并稱為弧上的流量，簡記為continued2021/5/94二、可行流與最大流一個流稱為一個可行流,如果滿足以下條件:

(1)容量限制條件:對

(2)平衡條件:

對中間點:流出量=流入量,即

對于發(fā)點

對于收點

式中稱為這個可行流的流量,即發(fā)點的凈輸出量(或收點的凈輸入量)2021/5/95最大流問題:

2021/5/96三、增廣鏈

1、給定一個可行流

稱

2、若是網(wǎng)絡(luò)中聯(lián)結(jié)發(fā)點和收點的一條鏈,定義鏈的方向是從到,則鏈上的弧被分為兩類:一類是弧的方向與鏈的方向一致,稱為前向弧,前向弧的全體記為另一類弧與鏈的方向相反,稱為后向弧,后向弧的全體記為

3、設(shè)f是一個可行流,是從到的一條鏈,稱為一條增廣鏈,如果2021/5/97四、截集

1、設(shè)把始點在,終點在中的所有弧構(gòu)成的集合,記為

2、給定網(wǎng)絡(luò)若點集被剖分為兩個非空集合使則弧集稱為分離和的截集.3、截集中所有弧的容量之和稱為此截集的容量,記為即2021/5/98

定理1可行流f是最大流不存在關(guān)于f的增廣鏈.

定理2任一個網(wǎng)絡(luò)中,從到的最大流的流量等于分離的最小截集的容量.Back2021/5/99求最大流的標(biāo)號法(Ford,Fulkerson)

1、標(biāo)號過程開始:先給標(biāo)上此時是標(biāo)號而未檢查的點,其余都是未標(biāo)號點.一般地,取一個標(biāo)號而未檢查的點,對一切未標(biāo)號點:(1)若在弧上則給標(biāo)號,這里.此時,點成為標(biāo)號而未檢查的點.(2)若在弧上則給標(biāo)號這里.此時,點成為標(biāo)號而未檢查的點.

于是成為標(biāo)號且已檢查過的點.重復(fù)上述步驟,一旦被標(biāo)上號,表明得到一條從到的增廣鏈,轉(zhuǎn)入調(diào)整過程.

若所有標(biāo)號都已經(jīng)檢查過,而標(biāo)號過程進行不下去時,則算法結(jié)束,此時的可行流就是最大流.2021/5/9102、調(diào)整過程

(1)尋找以為終點的增廣鏈----(反向追蹤法):(2)調(diào)整量

(3)流的調(diào)整

令去掉所有的標(biāo)號,對新的可行流重新進入標(biāo)號過程.Back2021/5/911continuedBack算例用標(biāo)號法求右下圖所示網(wǎng)絡(luò)的最大流.弧旁的數(shù)是解:(一)標(biāo)號過程

1、首先給標(biāo)上

2、檢查在弧上不滿足標(biāo)號條件;

在弧上則的標(biāo)號為.

其中,

2021/5/912continuedBack3、檢查在弧上不滿足標(biāo)號條件;

在弧上則的標(biāo)號為其中,4、檢查在弧上則的標(biāo)號為.

其中,

在弧上則的標(biāo)號為.

其中,2021/5/913continuedBack5、在中任選一個進行檢查.

例如在弧上則的標(biāo)號為其中,因有了標(biāo)號,故轉(zhuǎn)入調(diào)整過程.2021/5/914continuedBack(二)調(diào)整過程(1)尋找以為終點的增廣鏈----(反向追蹤法)(2)調(diào)整量2021/5/915continuedBack(3)流的調(diào)整

去掉所有的標(biāo)號,對新的可行流重新進入標(biāo)號過程.2021/5/916continuedBack

標(biāo)號過程無法繼續(xù)下去,算法結(jié)束.

此時的可行流即為所求的最大流.最大流量為最小截集:其中,為標(biāo)號點集合,為未標(biāo)號集合.2021/5/917最小費用最大流問題給定網(wǎng)絡(luò)每一弧上,除了已給容量外,還給了一個單位流量的費用(簡記為).所謂最小費用最大流問題就是要求一個最大流,使流的總輸送費用最小,即求,使

怎么求解這個問題?

2021/5/9181、定義增廣鏈的費用為

結(jié)論:若是流量為的所有可行流中費用最小者,而是關(guān)于的所有增廣鏈中費用最小的增廣鏈,則沿去調(diào)整,得到的可行流,就是流量為的所有可行流中的最小費用流.這樣,當(dāng)是最大流時,它即為所求的最小費用最大流.2、定義網(wǎng)絡(luò)D的一個可行流為,構(gòu)造其賦權(quán)有向圖,記為如下：

1)的頂點集是D的頂點集;

2)把D中的每一條弧變成兩個相反方向的弧和.定義中弧的權(quán)為:2021/5/919

在網(wǎng)絡(luò)D中求關(guān)于f的最小費用增廣鏈等價于在中求從到的最短路.最小費用最大流算法開始:取為初始可行流.(1)在第K-1步:最小費用流為,構(gòu)造賦權(quán)有向圖并在中,尋求從到的最短路.1)若不存在最短路,則就是最小費用最大流.2)若存在最短路,則在原網(wǎng)絡(luò)D中得相應(yīng)的增廣鏈,在增廣鏈上對進行調(diào)整.調(diào)整量為

令則得到新的可行流.轉(zhuǎn)(1).

2021/5/920

算例以下圖為例,求最小費用最大流.弧旁數(shù)字為

(1)取為初始可行流.(2)構(gòu)造賦權(quán)有向圖,并求出從到的最短路

,如圖1所示(雙箭頭).(3)在原網(wǎng)絡(luò)中,與這條最短路相應(yīng)的增廣鏈

(4)在