最小費(fèi)用最大流問題算法研究匯總

1、最大流問題最大流問題 引例：引例：圖圖1是聯(lián)結(jié)某產(chǎn)地是聯(lián)結(jié)某產(chǎn)地 和銷地和銷地 的的交通網(wǎng)交通網(wǎng),產(chǎn)品經(jīng)過交通網(wǎng)從產(chǎn)品經(jīng)過交通網(wǎng)從 輸送到輸送到 。現(xiàn)要制定一個(gè)運(yùn)輸?，F(xiàn)要制定一個(gè)運(yùn)輸1v6v1v6v方案使從方案使從 運(yùn)到運(yùn)到 的產(chǎn)品數(shù)量最多。的產(chǎn)品數(shù)量最多。1v6v1v2v3v4v6v5v(17,2)(5,1)(11,6)(3,3)(4,1)(5,2)(3, 2 )(8 , 3 )(6, 3)(10,5)圖圖1 引例：引例：圖圖2是聯(lián)結(jié)某產(chǎn)地是聯(lián)結(jié)某產(chǎn)地 和銷地和銷地 的的交通網(wǎng)絡(luò)費(fèi)用圖交通網(wǎng)絡(luò)費(fèi)用圖,產(chǎn)品經(jīng)過交通網(wǎng)從產(chǎn)品經(jīng)過交通網(wǎng)從 輸送到輸送到 ?，F(xiàn)要制定一個(gè)運(yùn)輸?，F(xiàn)要制定一個(gè)運(yùn)輸1v6v

2、1v6v方案使從方案使從 運(yùn)到運(yùn)到 的產(chǎn)品數(shù)量最多，的產(chǎn)品數(shù)量最多，而總費(fèi)用最小。而總費(fèi)用最小。1v6v1v2v3v4v6v5v(17,2,7)(5,1, 5)(11,6,2)(3,3,4)(4,1, 5)(5,2,3)(3, 2, 4 )(8 , 3, 8 )(6, 3, 4)(10,5,10)圖圖2最小費(fèi)用最大流問題最小費(fèi)用最大流問題),(CAVD vijijxbvb)(ijc),(jivvijbijx),(jivv),(jivv 其中，其中， 表示弧表示弧 上的容量，上的容量， 表示弧表示弧 上上通過單位流量所花費(fèi)的費(fèi)用，通過單位流量所花費(fèi)的費(fèi)用， 表示弧表示弧 上的流量。上的流量。 對(duì)

3、每一條弧都給出對(duì)每一條弧都給出的的容量網(wǎng)絡(luò)容量網(wǎng)絡(luò) 中，求取中，求取最大流最大流 ，使輸送流量的，使輸送流量的總費(fèi)用總費(fèi)用 為最小為最小的一類優(yōu)化問題。的一類優(yōu)化問題。vivj),(ijijijbxcvivj(,)ijijc bijc),(jivvijb),(jivv 其中，其中， 表示弧表示弧 上的容量，上的容量， 表示弧表示弧 上上通過單位流量所花費(fèi)的費(fèi)用通過單位流量所花費(fèi)的費(fèi)用 。 當(dāng)沿著一條關(guān)于可行流當(dāng)沿著一條關(guān)于可行流 的增廣鏈（流量修的增廣鏈（流量修正路線）正路線） ，以修正量，以修正量 進(jìn)行調(diào)整進(jìn)行調(diào)整，得到新的，得到新的可行流可行流 ，則稱，則稱 為為( )( )b xb xx

4、P1xP 在網(wǎng)絡(luò)費(fèi)用圖上只要在網(wǎng)絡(luò)費(fèi)用圖上只要找到找到其上的其上的最小費(fèi)用增廣最小費(fèi)用增廣鏈鏈，在該鏈上，在該鏈上調(diào)整流量調(diào)整流量，就得到，就得到增加流量后的最小增加流量后的最小費(fèi)用流費(fèi)用流。循環(huán)往復(fù)就可以求出最小費(fèi)用最大流。循環(huán)往復(fù)就可以求出最小費(fèi)用最大流。四、網(wǎng)絡(luò)圖的構(gòu)造四、網(wǎng)絡(luò)圖的構(gòu)造 頂點(diǎn)是原網(wǎng)絡(luò)費(fèi)用圖頂點(diǎn)是原網(wǎng)絡(luò)費(fèi)用圖 的頂點(diǎn)，而把的頂點(diǎn)，而把 中的中的每一每一DD條弧條弧 變成變成兩個(gè)相反方向兩個(gè)相反方向的弧的弧 和和 。定義。定義),(jivv),(jivv(,)jiv v弧的權(quán)為弧的權(quán)為:ijw00ijijijjiijijijijijijxxbwcxcxbw若若若若ivjviv

5、jvijwjiw vsvtv2v3v1(10,4)(7,1)(8,1)(10,3)(4,2)(5,2)(2,6)3vsvtv2v3v1411226tsvvvv12vsvtv2v3v1(10,0,4)(7,0,1)(8,0,1)(10,0,3)(4,0,2)(5,0,2)(2,0,6)vsvtv2v3v1(10,0,4)(7,1,1)(8,1,1)(10,0,3)(4,0,2)(5,1,2)(2,0,6)31-12-2vsvtv2v3v1426-11tsvvvv12vsvtv2v3v1(10,0,4)(7,5,1)(8,5,1)(10,0,3)(4,0,2)(5,5,2)(2,0,6)3vsv2

6、v3v14-1126-1-21vt1stvvv vsvtv2v3v1(10,2,4)(7,7,1)(8,5,1)(10,0,3)(4,0,2)(5,5,2)(2,0,6)3vsv2v3v14-1126-1-2vt-423stvvvvvsvtv2v3v1(10,2,4)(7,7,1)(8,8,1)(10,3,3)(4,3,2)(5,5,2)(2,0,6)3vsv2v3v14-126-1-2vt-4-3-213stvvvv 123stvvvvv vsvtv2v3v1(10,3,4)(7,7,1)(8,8,1)(10,4,3)(4,4,2)(5,4,2)(2,0,6)-33vsv2v3v14-1-1

7、-2vt-4-262總總 結(jié)結(jié)最短路算法與最大流算法的結(jié)合運(yùn)用最短路算法與最大流算法的結(jié)合運(yùn)用 1 1）構(gòu)造構(gòu)造初始可行流的初始可行流的增廣費(fèi)用網(wǎng)絡(luò)圖增廣費(fèi)用網(wǎng)絡(luò)圖，用，用最短路算法最短路算法求出最小費(fèi)用增廣鏈。求出最小費(fèi)用增廣鏈。 2 2）將最小費(fèi)用增廣鏈）將最小費(fèi)用增廣鏈還原還原到容量流量網(wǎng)絡(luò)到容量流量網(wǎng)絡(luò)圖中的增廣鏈，圖中的增廣鏈，調(diào)整調(diào)整流量流量得到新的得到新的可行流，繼可行流，繼續(xù)進(jìn)行，續(xù)進(jìn)行，直到直到用最短路算法用最短路算法找不到找不到最小費(fèi)用增最小費(fèi)用增廣鏈。廣鏈。 練習(xí)：練習(xí)：圖圖2是聯(lián)結(jié)某產(chǎn)地是聯(lián)結(jié)某產(chǎn)地 和銷地和銷地 的的交通網(wǎng)絡(luò)費(fèi)用圖交通網(wǎng)絡(luò)費(fèi)用圖,產(chǎn)品經(jīng)過交通網(wǎng)從產(chǎn)品經(jīng)過交通網(wǎng)從 輸送到輸送到 ?，F(xiàn)要制定一個(gè)運(yùn)輸?，F(xiàn)要制定一個(gè)運(yùn)輸1v6v1v6v方案使從方案使從 運(yùn)到運(yùn)到 的產(chǎn)品數(shù)量最多，而總費(fèi)用最小。的產(chǎn)