最小費用最大流問題算法研究匯總

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)從 輸送到輸送到 ?，F(xiàn)要制定一個運輸?，F(xiàn)要制定一個運輸1v6v1v6v方案使從方案使從 運到運到 的產(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ò)費用圖交通網(wǎng)絡(luò)費用圖,產(chǎn)品經(jīng)過交通網(wǎng)從產(chǎn)品經(jīng)過交通網(wǎng)從 輸送到輸送到 。現(xiàn)要制定一個運輸?，F(xiàn)要制定一個運輸1v6v

2、1v6v方案使從方案使從 運到運到 的產(chǎn)品數(shù)量最多，的產(chǎn)品數(shù)量最多，而總費用最小。而總費用最小。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最小費用最大流問題最小費用最大流問題),(CAVD vijijxbvb)(ijc),(jivvijbijx),(jivv),(jivv 其中，其中， 表示弧表示弧 上的容量，上的容量， 表示弧表示弧 上上通過單位流量所花費的費用，通過單位流量所花費的費用， 表示弧表示弧 上的流量。上的流量。 對

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

4、P1xP 在網(wǎng)絡(luò)費用圖上只要在網(wǎng)絡(luò)費用圖上只要找到找到其上的其上的最小費用增廣最小費用增廣鏈鏈，在該鏈上，在該鏈上調(diào)整流量調(diào)整流量，就得到，就得到增加流量后的最小增加流量后的最小費用流費用流。循環(huán)往復(fù)就可以求出最小費用最大流。循環(huán)往復(fù)就可以求出最小費用最大流。四、網(wǎng)絡(luò)圖的構(gòu)造四、網(wǎng)絡(luò)圖的構(gòu)造 頂點是原網(wǎng)絡(luò)費用圖頂點是原網(wǎng)絡(luò)費用圖 的頂點，而把的頂點，而把 中的中的每一每一DD條弧條弧 變成變成兩個相反方向兩個相反方向的弧的弧 和和 。定義。定義),(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é)合運用最短路算法與最大流算法的結(jié)合運用 1 1）構(gòu)造構(gòu)造初始可行流的初始可行流的增廣費用網(wǎng)絡(luò)圖增廣費用網(wǎng)絡(luò)圖，用，用最短路算法最短路算法求出最小費用增廣鏈。求出最小費用增廣鏈。 2 2）將最小費用增廣鏈）將最小費用增廣鏈還原還原到容量流量網(wǎng)絡(luò)到容量流量網(wǎng)絡(luò)圖中的增廣鏈，圖中的增廣鏈，調(diào)整調(diào)整流量流量得到新的得到新的可行流，繼可行流，繼續(xù)進行，續(xù)進行，直到直到用最短路算法用最短路算法找不到找不到最小費用增最小費用增廣鏈。廣鏈。 練習(xí)：練習(xí)：圖圖2是聯(lián)結(jié)某產(chǎn)地是聯(lián)結(jié)某產(chǎn)地 和銷地和銷地 的的交通網(wǎng)絡(luò)費用圖交通網(wǎng)絡(luò)費用圖,產(chǎn)品經(jīng)過交通網(wǎng)從產(chǎn)品經(jīng)過交通網(wǎng)從 輸送到輸送到 ?，F(xiàn)要制定一個運輸。現(xiàn)要制定一個運輸1v6v1v6v方案使從方案使從 運到運到 的產(chǎn)品數(shù)量最多，而總費用最小。的產(chǎn)