網(wǎng)絡(luò)最大流課件.ppt

網(wǎng)絡(luò)最大流課件.ppt

ID:57066418

大?。?.54 MB

頁(yè)數(shù):58頁(yè)

時(shí)間:2020-07-30

網(wǎng)絡(luò)最大流課件.ppt_第1頁(yè)
網(wǎng)絡(luò)最大流課件.ppt_第2頁(yè)
網(wǎng)絡(luò)最大流課件.ppt_第3頁(yè)
網(wǎng)絡(luò)最大流課件.ppt_第4頁(yè)
網(wǎng)絡(luò)最大流課件.ppt_第5頁(yè)
資源描述:

《網(wǎng)絡(luò)最大流課件.ppt》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第六章???網(wǎng)絡(luò)最大流網(wǎng)絡(luò)最大流問(wèn)題50年代福特(Ford)、富克遜(Fulkerson)建立的“網(wǎng)絡(luò)流理論”,是網(wǎng)絡(luò)應(yīng)用的重要組成部分。如同我們可以把一個(gè)實(shí)際的道路地圖抽象成一個(gè)有向圖來(lái)計(jì)算兩點(diǎn)之間的最短路徑,我們也可以將一個(gè)有向圖看作一個(gè)流網(wǎng)絡(luò)來(lái)解決另一類(lèi)型的問(wèn)題。流網(wǎng)絡(luò)比較適合用來(lái)模擬液體流經(jīng)管道、電流在電路網(wǎng)絡(luò)中的運(yùn)動(dòng)、信息網(wǎng)絡(luò)中信息的傳遞等等類(lèi)似的過(guò)程。問(wèn)題的提出在一個(gè)輸油管網(wǎng)中,有生產(chǎn)石油的油井、儲(chǔ)存石油的油庫(kù)、轉(zhuǎn)運(yùn)石油的中間泵站,同時(shí),還有各種口徑不同的輸油管。當(dāng)一個(gè)輸油管網(wǎng)給定后,單位時(shí)間內(nèi)最

2、多可把多少石油從油井輸送到油庫(kù)?具體方案如何?分析:就輸油管網(wǎng)絡(luò)問(wèn)題,可用頂點(diǎn)表示油井、油庫(kù)和中間泵站,用有向邊表示輸油管,用有向邊上的權(quán)表示單位時(shí)間沿相應(yīng)的輸油管可以輸送石油的最大數(shù)量(容量)。如果我們把圖看做輸油管道網(wǎng),為起點(diǎn),為終點(diǎn),為中轉(zhuǎn)站,邊上的數(shù)表示該管道的最大輸油能力,問(wèn)應(yīng)該如何安排各管道輸油量,才能使從到的總輸油量最大?問(wèn)題的提出管道網(wǎng)絡(luò)中每邊的最大通過(guò)能力即容量是有限的,實(shí)際流量也不一定等于容量,上述問(wèn)題就是要討論如何充分利用裝置的能力,以取得最好效果(流量最大),這類(lèi)問(wèn)題通常稱為最大流問(wèn)題

3、。vsv1v3vtv2v48799562510容量發(fā)點(diǎn)(源)收點(diǎn)(匯)中間點(diǎn)容量網(wǎng)絡(luò)網(wǎng)絡(luò)有向圖D=(V,A,C)網(wǎng)絡(luò)上流的基本概念vsv1v3vtv2v48799562510流vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)運(yùn)輸問(wèn)題中,每個(gè)運(yùn)輸方案就是一個(gè)流可行流網(wǎng)絡(luò)最大流問(wèn)題且滿足此為一個(gè)特殊的線性規(guī)劃問(wèn)題,將會(huì)看到利用圖的特點(diǎn),解決這個(gè)問(wèn)題的方法要比單純形法較為直觀方便。設(shè)是網(wǎng)絡(luò)D=(V,A,C)的一個(gè)可行流(v1,v2)是飽和的2、如果0≤fij

4、,該弧是非飽和??;(v1,v2)是不飽和的間隙為?12=c12-f12=5-3=21、如果fij=cij,該弧是飽和弧;弧關(guān)于流的分類(lèi)fij=5cij=5v1v2fij=3cij=5v1v2設(shè)是網(wǎng)絡(luò)D=(V,A,C)的一個(gè)可行流(v1,v2)是0流弧4、如果fij>0,該弧是非0??;(v1,v2)是非0弧3、如果fij=0,該弧是0流?。换£P(guān)于流的分類(lèi)fij=0cij=5v1v2fij>0cij=5v1v2鏈及可增廣鏈鏈在最大流問(wèn)題中,研究的是有向網(wǎng)絡(luò)圖。但是在求最大流的方法中,則要使用無(wú)向網(wǎng)絡(luò)中的鏈。vsv

5、1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)非0流弧可增廣鏈vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)非飽和弧割集和割集的容量設(shè)有網(wǎng)絡(luò)D={V,A,C},點(diǎn)vs與點(diǎn)vt的是集合V中的任意兩點(diǎn),若點(diǎn)集V被剖分成兩個(gè)非空集合,使,記以中的點(diǎn)為始點(diǎn),的A中弧的集合記為則稱這個(gè)弧的集合是分離點(diǎn)vs與點(diǎn)vt的割集(又稱截集)。中的點(diǎn)為終點(diǎn)割集的容量是割集中各弧的容量之和,用表示。割集的容量為9+9=18割集KKvsv

6、1v3vtv2v48(8)7(5)9(4)5(5)6(1)2(0)5(4)10(8)9(9)考慮KK的不同畫(huà)法vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)割集割集容量基本定理(可行流與割集的關(guān)系)由于有限網(wǎng)絡(luò)的割集只有有限多個(gè),則截集容量的集合是有限的實(shí)數(shù)集合,令稱割集容量為C0的割集為D的最小割集。(瓶頸)§2割切-定理6.1證明-1[]wffSjSijiij=-???,∵又∵0≤fij≤cij∴fij-fji≤fij≤cij因?yàn)楦罴侨我獾?,所以得證。

7、[]=≤-=??????SjSiijSjSijiijcffw,,C(S,)S∴證明增廣路定理:證明:1必要性v(f)為最大流,則不存在可增廣鏈;因?yàn)槿舸嬖谠鰪V鏈,則v(f)不為最大流。2充分性不存在可增廣鏈,則v(f)為最大流;若網(wǎng)絡(luò)流圖G中不存在可增廣路,則考察所有s到t的路徑,將滿足增廣條件路徑連接的節(jié)點(diǎn)并入集合S中,遇到不滿足條件點(diǎn)時(shí)停止;T=V/S,[S,T]為s-t割集。這時(shí),對(duì)于任意弧(i,j),若是前向弧,fij=cij,若是逆向弧,fji=0,下式成立,v(f)為最大流,C[S,T]為最小割。

8、[]==-=??????TjSiijTjSijiijcffw,,C(S,)T∴最大流-最小割定理:v(fmax)=Cmin[S,T];這樣就得到了一個(gè)尋求最大流的方法(算法思想):從一個(gè)可行流開(kāi)始,尋求關(guān)于這個(gè)可行流的可增廣鏈,若存在,則可以經(jīng)過(guò)調(diào)整,得到一個(gè)新的可行流,其流量比原來(lái)的可行流要大,重復(fù)這個(gè)過(guò)程,直到不存在關(guān)于該流的可增廣鏈時(shí)就得到了最大流。沿著這條鏈從vs到vt輸送流,還有潛力可挖,

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫(huà)的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無(wú)此問(wèn)題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫(kù)負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無(wú)法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。