歡迎來(lái)到裝配圖網(wǎng)! | 幫助中心 裝配圖網(wǎng)zhuangpeitu.com!
裝配圖網(wǎng)
ImageVerifierCode 換一換
首頁(yè) 裝配圖網(wǎng) > 資源分類(lèi) > PPT文檔下載  

運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析.ppt

  • 資源ID:3730260       資源大?。?span id="6611111" class="font-tahoma">2.54MB        全文頁(yè)數(shù):130頁(yè)
  • 資源格式: PPT        下載積分:14.9積分
快捷下載 游客一鍵下載
會(huì)員登錄下載
微信登錄下載
三方登錄下載: 微信開(kāi)放平臺(tái)登錄 支付寶登錄   QQ登錄   微博登錄  
二維碼
微信掃一掃登錄
下載資源需要14.9積分
郵箱/手機(jī):
溫馨提示:
用戶名和密碼都是您填寫(xiě)的郵箱或者手機(jī)號(hào),方便查詢和重復(fù)下載(系統(tǒng)自動(dòng)生成)
支付方式: 支付寶    微信支付   
驗(yàn)證碼:   換一換

 
賬號(hào):
密碼:
驗(yàn)證碼:   換一換
  忘記密碼?
    
友情提示
2、PDF文件下載后,可能會(huì)被瀏覽器默認(rèn)打開(kāi),此種情況可以點(diǎn)擊瀏覽器菜單,保存網(wǎng)頁(yè)到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請(qǐng)使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無(wú)水印,預(yù)覽文檔經(jīng)過(guò)壓縮,下載后原文更清晰。
5、試題試卷類(lèi)文檔,如果標(biāo)題沒(méi)有明確說(shuō)明有答案則都視為沒(méi)有答案,請(qǐng)知曉。

運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析.ppt

第5章圖論與網(wǎng)絡(luò)分析,圖的基本概念,網(wǎng)絡(luò)分析,最小支撐樹(shù)問(wèn)題最短路徑問(wèn)題網(wǎng)絡(luò)最大流問(wèn)題,圖論起源:哥尼斯堡七橋問(wèn)題,問(wèn)題:一個(gè)散步者能否從任一塊陸地出發(fā),走過(guò)七座橋,且每座橋只走過(guò)一次,最后回到出發(fā)點(diǎn)?,結(jié)論:每個(gè)結(jié)點(diǎn)關(guān)聯(lián)的邊數(shù)均為偶數(shù),1圖的基本概念,由點(diǎn)和邊組成,記作G=(V,E),其中V=(v1,v2,vn)為結(jié)點(diǎn)的集合,E=(e1,e2,em)為邊的集合。,點(diǎn)表示研究對(duì)象,邊表示研究對(duì)象之間的特定關(guān)系,1.圖,p114,圖,無(wú)向圖,記作G=(V,E),有向圖,記作D=(V,A),例1:哥尼斯堡橋問(wèn)題的圖為一個(gè)無(wú)向圖。,有向圖的邊稱(chēng)為弧。,2、圖的分類(lèi),例,圖1,圖2,3、鏈與路、圈與回路,鏈,點(diǎn)邊交錯(cuò)的序列,路,點(diǎn)弧交錯(cuò)的序列,回路,起點(diǎn)=終點(diǎn)的路,無(wú)向圖:,有向圖:,鏈與路中的點(diǎn)均不相同,則稱(chēng)為初等鏈(路)類(lèi)似可定義初等圈(回路),4、連通圖,G1為不連通圖,G2為連通圖,例:,5、支撐子圖,圖G=(V,E)和G=(V,E),若V=V且EE,則稱(chēng)G為G的支撐子圖。,G2為G1的支撐子圖,例:,G2是G1的子圖;,例:,6、賦權(quán)圖(網(wǎng)絡(luò)),圖的每條邊都有一個(gè)表示一定實(shí)際含義的權(quán)數(shù),稱(chēng)為賦權(quán)圖。記作D=(V,A,C)。,例:,2最小支撐樹(shù)問(wèn)題,本節(jié)主要內(nèi)容:,樹(shù),支撐樹(shù),最小支撐樹(shù),樹(shù):無(wú)圈的連通圖,記為T(mén)。,一、樹(shù)的概念與性質(zhì),樹(shù)的性質(zhì):(1)樹(shù)的任2點(diǎn)間有且僅有1鏈;(2)在樹(shù)中任去掉1邊,則不連通;故樹(shù)是使圖保持連通且具有最少邊數(shù)的一種圖形(3)在樹(shù)中不相鄰2點(diǎn)間添1邊,恰成1圈;(4)若樹(shù)T有m個(gè)頂點(diǎn),則T有m-1條邊。,若一個(gè)圖G=(V,E)的支撐子圖T=(V,E)構(gòu)成樹(shù),則稱(chēng)T為G的支撐樹(shù),又稱(chēng)生成樹(shù)。,二、圖的支撐樹(shù),例,例某地新建5處居民點(diǎn),擬修道路連接5處,經(jīng)勘測(cè)其道路可鋪成如圖所示。為使5處居民點(diǎn)都有道路相連,問(wèn)至少要鋪幾條路?,解:,該問(wèn)題實(shí)為求圖的支撐樹(shù)問(wèn)題,共需鋪4條路。,圖的支撐樹(shù)的應(yīng)用舉例,用破圈法求出下圖的一個(gè)生成樹(shù)。,最小支撐樹(shù):求網(wǎng)絡(luò)的支撐樹(shù),使其權(quán)和最小。,三、最小支撐樹(shù)問(wèn)題,算法1(破圈法):在給定的賦權(quán)的連通圖上找一個(gè)圈;在所找的圈中去掉一條權(quán)數(shù)最大的邊(若有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊,則任意去掉其中一條):若所余下的圖已不含圈,則計(jì)算結(jié)束,所余下的圖即為最小支撐樹(shù),否則,返問(wèn)。,例求上例中的最小支撐樹(shù),解:,5,5.5,v1,v2,v3,v4,v5,3.5,7.5,4,2,3,4,算法2(避圈法):從某一點(diǎn)開(kāi)始,把邊按權(quán)從小到大依次添入圖中,若出現(xiàn)圈,則刪去其中最大邊,直至填滿n-1條邊為止(n為結(jié)點(diǎn)數(shù))。,最小生成樹(shù)舉例:某六個(gè)城市之間的道路網(wǎng)如圖所示,要求沿著已知長(zhǎng)度的道路聯(lián)結(jié)六個(gè)城市的電話線網(wǎng),使電話線的總長(zhǎng)度最短。,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,聯(lián)系今有煤氣站A,將給一居民區(qū)供應(yīng)煤氣,居民區(qū)各用戶所在位置如圖所示,鋪設(shè)各用戶點(diǎn)的煤氣管道所需的費(fèi)用(單位:萬(wàn)元)如圖邊上的數(shù)字所示。要求設(shè)計(jì)一個(gè)最經(jīng)濟(jì)的煤氣管道路線,并求所需的總費(fèi)用。,練習(xí)今有煤氣站A,將給一居民區(qū)供應(yīng)煤氣,居民區(qū)各用戶所在位置如圖所示,鋪設(shè)各用戶點(diǎn)的煤氣管道所需的費(fèi)用(單位:萬(wàn)元)如圖邊上的數(shù)字所示。要求設(shè)計(jì)一個(gè)最經(jīng)濟(jì)的煤氣管道路線,并求所需的總費(fèi)用。,例今有煤氣站A,將給一居民區(qū)供應(yīng)煤氣,居民區(qū)各用戶所在位置如圖所示,鋪設(shè)各用戶點(diǎn)的煤氣管道所需的費(fèi)用(單位:萬(wàn)元)如圖邊上的數(shù)字所示。要求設(shè)計(jì)一個(gè)最經(jīng)濟(jì)的煤氣管道路線,并求所需的總費(fèi)用。,例今有煤氣站A,將給一居民區(qū)供應(yīng)煤氣,居民區(qū)各用戶所在位置如圖所示,鋪設(shè)各用戶點(diǎn)的煤氣管道所需的費(fèi)用(單位:萬(wàn)元)如圖邊上的數(shù)字所示。要求設(shè)計(jì)一個(gè)最經(jīng)濟(jì)的煤氣管道路線,并求所需的總費(fèi)用。,例今有煤氣站A,將給一居民區(qū)供應(yīng)煤氣,居民區(qū)各用戶所在位置如圖所示,鋪設(shè)各用戶點(diǎn)的煤氣管道所需的費(fèi)用(單位:萬(wàn)元)如圖邊上的數(shù)字所示。要求設(shè)計(jì)一個(gè)最經(jīng)濟(jì)的煤氣管道路線,并求所需的總費(fèi)用。,例今有煤氣站A,將給一居民區(qū)供應(yīng)煤氣,居民區(qū)各用戶所在位置如圖所示,鋪設(shè)各用戶點(diǎn)的煤氣管道所需的費(fèi)用(單位:萬(wàn)元)如圖邊上的數(shù)字所示。要求設(shè)計(jì)一個(gè)最經(jīng)濟(jì)的煤氣管道路線,并求所需的總費(fèi)用。,例今有煤氣站A,將給一居民區(qū)供應(yīng)煤氣,居民區(qū)各用戶所在位置如圖所示,鋪設(shè)各用戶點(diǎn)的煤氣管道所需的費(fèi)用(單位:萬(wàn)元)如圖邊上的數(shù)字所示。要求設(shè)計(jì)一個(gè)最經(jīng)濟(jì)的煤氣管道路線,并求所需的總費(fèi)用。,此即為最經(jīng)濟(jì)的煤氣管道路線,所需的總費(fèi)用為25萬(wàn)元,3最短路徑問(wèn)題,最短路問(wèn)題是在一個(gè)網(wǎng)絡(luò)(賦權(quán)有向圖)中尋找從起點(diǎn)到某個(gè)節(jié)點(diǎn)之間一條最短的路線。現(xiàn)欲求出1至6距離最短的路徑。,基本思想:從起點(diǎn)vs開(kāi)始,逐步給每個(gè)結(jié)點(diǎn)vj標(biāo)號(hào)dj,vi,其中dj為起點(diǎn)vs到vj的最短距離,vi為該最短路線上的前一節(jié)點(diǎn).若給終點(diǎn)vt標(biāo)上號(hào)dt,vi,表示已求出v1至vt的最短路其最短路長(zhǎng)為dt,最短路徑可根據(jù)標(biāo)號(hào)vi反向追蹤而得,最短路問(wèn)題的Dijstra解法(狄克拉斯),0,v1,1,v1,(3)考慮所有這樣的邊vi,vj,其中viVA,vjVB,挑選其中與起點(diǎn)v1距離最短(mindi+cij)的vj,對(duì)vj進(jìn)行標(biāo)號(hào),(4)重復(fù)(2)、(3),直至終點(diǎn)vn標(biāo)上號(hào)dn,vi,則dn即為v1vn的最短距離,反向追蹤可求出最短路。,(1)給起點(diǎn)v1標(biāo)號(hào)0,v1,0,v1,1,v1,(3)考慮所有這樣的邊vi,vj,其中viVA,vjVB,挑選其中與起點(diǎn)v1距離最短(mindi+cij)的vj,對(duì)vj進(jìn)行標(biāo)號(hào),(4)重復(fù)(2)、(3),直至終點(diǎn)vn標(biāo)上號(hào)dn,vi,則dn即為v1vn的最短距離,反向追蹤可求出最短路。,(1)給起點(diǎn)v1標(biāo)號(hào)0,v1,3,v1,0,v1,1,v1,3,v1,5,v3,0,v1,1,v1,3,v1,5,v3,6,v2,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,10,v5,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,10,v5,12,v5,此時(shí)終點(diǎn)v9已標(biāo)號(hào)12,v5,則12即為v1vn的最短距離,反向追蹤可求出最短路,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,10,v5,12,v5,v1到v9的最短路為:v1v3v2v5v9,最短距離為12,p119,練習(xí):用Dijkstra算法求下圖中V1至V8的最短路及最短路長(zhǎng)。,關(guān)鍵線路:1.V1-V2-V4-V6-V82.V1-V2-V4V7-V8最短路長(zhǎng):12,課堂練習(xí)無(wú)向圖情形,求網(wǎng)絡(luò)中v1至v7的最短路。,課堂練習(xí)無(wú)向圖情形,v1,v2,v3,v4,v5,v6,v7,2,2,5,3,5,5,7,1,5,7,1,3,0,v1,2,v1,3,v1,4,v2/v4,7,v3,8,v5,13,v6,課堂練習(xí)無(wú)向圖情形,答案(2):,v1,v2,v3,v4,v5,v6,v7,2,2,5,3,5,5,7,1,5,7,1,3,0,v1,2,v1,3,v1,4,v2/v4,7,v3,8,v5,13,v6,最短路模型的應(yīng)用設(shè)備更新問(wèn)題,例某工廠使用一種設(shè)備,這種設(shè)備在一定的年限內(nèi)隨著時(shí)間的推移逐漸損壞。所以工廠在每年年初都要決定設(shè)備是否更新。若購(gòu)置設(shè)備,每年需支付購(gòu)置費(fèi)用;若繼續(xù)使用舊設(shè)備,需要支付維修與運(yùn)行費(fèi)用。計(jì)劃期(五年)內(nèi)中每年的購(gòu)置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)如表所示,工廠要制定今后五年設(shè)備更新計(jì)劃,問(wèn)采用何種方案才能使包括購(gòu)置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)在內(nèi)的總費(fèi)用最小。,最短路模型的應(yīng)用設(shè)備更新問(wèn)題,分析:,結(jié)點(diǎn):V=v1,v6,vi表示第i年初;,?。篈=(vi,vj)表示第i年初購(gòu)買(mǎi),用至第j年初;i=1,5;j=2,6,權(quán)cij:i年初j年初的費(fèi)用,即cij=i年初購(gòu)買(mǎi)費(fèi)+(j-i)年里的維修費(fèi),通路:表示一個(gè)更新策略。例如v1-v2-v6表示第一年購(gòu)買(mǎi)用到第二年更新,繼續(xù)用至第五年末的一個(gè)更新策略,最短路模型的應(yīng)用設(shè)備更新問(wèn)題,0,v1,16,v1,22,v1,30,v1,41,v1,53,v3/v4,16,30,22,41,59,16,22,30,41,17,23,31,17,23,18,建模:,求解:,求得兩個(gè)最優(yōu)更新策略:v1-v4-v6,即第一年購(gòu)買(mǎi)設(shè)備,用到第四年更新,再用至第五年年末V1-v3-v6,即第一年購(gòu)買(mǎi)設(shè)備,用到第三年更新,再用至第五年年末最優(yōu)費(fèi)用為53,計(jì)劃期(五年)內(nèi)中每年的購(gòu)置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)如表所示,工廠要制定今后五年設(shè)備更新計(jì)劃,問(wèn)采用何種方案才能使包括購(gòu)置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)在內(nèi)的總費(fèi)用最小。,練習(xí):設(shè)備更新問(wèn)題,28,v1,v2,v3,v4,v5,v6,23,25,26,29,30,42,60,85,32,44,62,33,45,30,算法的基本思路與步驟:首先設(shè)任一點(diǎn)vi到任一點(diǎn)vj都有一條弧。無(wú)弧相連的點(diǎn)之間假設(shè)存在權(quán)為+的弧相連。從v1到vj的最短路是從v1出發(fā),沿著這條路到某個(gè)點(diǎn)vi再沿弧(vi,vj)到vj。則v1到vi的這條路必然也是v1到vi的所有路中的最短路。設(shè)P1j表示從v1到vj的最短路長(zhǎng),P1i表示從v1到vi的最短路長(zhǎng),則有下列方程:,(二)Ford法(逐次逼近法)(權(quán)有負(fù)數(shù)),開(kāi)始時(shí),令即用v1到vj的直接距離做初始解。,從第二步起,使用遞推公式:,求,當(dāng)進(jìn)行到第t步,若出現(xiàn),即為v1到各點(diǎn)的最短路長(zhǎng)。,則停止計(jì)算,,例:,從第二步起,使用遞推公式,從第二步起,使用遞推公式,為了求出從v1到各個(gè)點(diǎn)的最短路,一般采用反向追蹤的方法:如果已知d(vs,vj),那么尋求一個(gè)點(diǎn)vk,使得d(vs,vk)+wkj=d(vs,vj),然后記錄下(vk,vj);在看d(vs,vk),尋求一個(gè)點(diǎn)vi,使得d(vs,vi)+wik=d(vs,vk)依次類(lèi)推,一直到達(dá)為止。這樣,從vs到vj的最短路是(vs,vi,vk,vj),d(v1,v8)=6,由于d(v1,v6)+w68=(-1)+7記錄下v6由于d(v1,v3)+w36=d(v1,v6),記錄下v3由于d(v1,v1)+w13=d(v1,v3),于是,從v1到v8的最短路是(v1,v3,v6,v8)。,4網(wǎng)絡(luò)最大流問(wèn)題,引例:下圖為V1到V6的一交通網(wǎng),權(quán)表示相應(yīng)運(yùn)輸線的最大通過(guò)能力,制定一方案,使從V1到V6的運(yùn)輸產(chǎn)品數(shù)量最多。,已知網(wǎng)絡(luò)D=(V,A,C),其中V為頂點(diǎn)集,A為弧集,C=cij為容量集,cij為弧(vi,vj)上的容量。現(xiàn)D上要通過(guò)一個(gè)流f=fij,其中fij為弧(vi,vj)上的流量。問(wèn)題:應(yīng)如何安排流量fij可使D上通過(guò)的總流量v最大?,一、一般提法,二、最大流問(wèn)題的數(shù)學(xué)模型,maxv=v(f),容量約束,平衡約束,P125,滿足上述所有約束條件的流成為可行流。,(1)容量條件:對(duì)于每一個(gè)弧(vi,vj)A,有0fijcij。(2)平衡條件:對(duì)于發(fā)點(diǎn)vs,有對(duì)于收點(diǎn)vt,有對(duì)于中間點(diǎn),有為可行流f的流量(發(fā)點(diǎn)的凈輸出量或收點(diǎn)的凈輸入量),1、稱(chēng)滿足下列條件的流f為可行流:,三、基本概念和定理,可行流特征:(1)容量條件:每一個(gè)弧上的流量不能超過(guò)該弧的容量。(2)每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和為零。(轉(zhuǎn)運(yùn)的作用)(3)出發(fā)點(diǎn)的總流出量與收點(diǎn)的總流入量必相等。,任意一個(gè)網(wǎng)絡(luò)上的可行流總是存在的。例如零流v(f)=0,就是滿足以上條件的可行流。網(wǎng)絡(luò)系統(tǒng)中最大流問(wèn)題就是在給定的網(wǎng)絡(luò)上尋求一個(gè)可行流f,其流量v(f)達(dá)到最大值。,可行流中fijcij的弧叫做飽和?。籪ijcij的弧叫做非飽和?。籪ij0的弧叫做非零流?。籪ij0的弧叫做零流弧。,2、飽和弧與零流弧,f為一可行流,u為vs至vt的鏈,令u+=正向弧,u-=反向弧。若u+中弧皆非飽,且u-中弧皆非零,則稱(chēng)u為關(guān)于f的一條增廣鏈。,3、增廣鏈,增廣鏈,顯然圖中增廣鏈不止一條,增廣鏈,容量網(wǎng)絡(luò)D=(V,A,C),vs為始點(diǎn),vt為終點(diǎn)。如果把V分成兩個(gè)非空集合使則所有始點(diǎn)屬于V1,而終點(diǎn)屬于的弧的集合,稱(chēng)為分離vs和vt的截集。,4、截集和截集的截量,截集是連接起點(diǎn)和終點(diǎn)的必經(jīng)之路。,截集中所有弧的容量之和,稱(chēng)為這個(gè)截集的截量,記為,則截集為,設(shè),容量為24,設(shè),則截集為,容量為20,流量與截量的關(guān)系:,任一可行流的流量都不會(huì)超過(guò)任一截集的截量,v1,vs,v2,v3,vt,(2,2),(4,3),(3,1),(1,0),(3,3),(5,2),(2,2),最大流最小截定理:任一網(wǎng)絡(luò)D中,從vs至vt的最大流的流量等于分離vs、vt的最小截集的容量。,例.如圖所示的網(wǎng)絡(luò)中,弧旁數(shù)字為(cij,fij),v1,vs,v2,v3,vt,(2,2),(4,3),(3,1),(1,0),(3,3),(5,2),(2,2),(1)確定所有的截集;(2)求最小截集的容量;(3)證明圖中的流為最大流;,v1,vs,v2,v3,vt,(2,2),(4,3),(3,1),(1,0),(3,3),(5,2),(2,2),(1)所有的截集:,V1=vs,,截集為(vs,v1),(vs,v2),截量為:6,v1,vs,v2,v3,vt,(2,2),(4,3),(3,1),(1,0),(3,3),(5,2),(2,2),(1)所有的截集:,V1=vs,截集為(vs,v1),(vs,v2),截量為:6,V1=vs,v1,截集為(vs,v2),(v1,vt),截量為:7,v1,vs,v2,v3,vt,(2,2),(4,3),(3,1),(1,0),(3,3),(5,2),(2,2),(1)所有的截集:,V1=vs,截集為(vs,v1),(vs,v2),截量為:6V1=vs,v1,截集為(vs,v2),(v1,vt),截量為:7V1=vs,v2,截集為,截量為:7,V1=vs,截集為(vs,v1),(vs,v2),截量為:6V1=vs,v1,截集為(vs,v2),(v1,vt),截量為:7V1=vs,v2,截集為,截量為:7V1=vs,v3,截集為,截量為:12,v1,vs,v2,v3,vt,(2,2),(4,3),(3,1),(1,0),(3,3),(5,2),(2,2),(1)所有的截集:,v1,vs,v2,v3,vt,(2,2),(4,3),(3,1),(1,0),(3,3),(5,2),(2,2),(1)所有的截集:,V1=vs,截集為(vs,v1),(vs,v2),截量為:6V1=vs,v1,截集為(vs,v2),(v1,vt),截量為:7V1=vs,v2,截集為,截量為:7V1=vs,v3,截集為,截量為:12V1=vs,v1,v2,截集為,截量為:5,(2)最小截量minC(V1,V2)=5;(3)v(f*)=5=minC(V1,V2)f*是最大流。,最大流判定定理:可行流f*是最大流的充分必要條件是當(dāng)且僅當(dāng)不存在從vs到vt的關(guān)于f*的增廣鏈。,p124,尋求網(wǎng)絡(luò)最大流問(wèn)題的主要步驟:(1)確定初始可行流(觀察法和零流法)(2)檢驗(yàn)當(dāng)前可行流是否是網(wǎng)絡(luò)中的最大流(對(duì)已知可行流用標(biāo)號(hào)法尋找可擴(kuò)充鏈,若存在,則當(dāng)前可行流不是最大流,轉(zhuǎn)(3);若不存在,則是最大流)(3)將當(dāng)前的可行流調(diào)整成一個(gè)流量更大的新可行流再由(2)檢驗(yàn),四、求最大流方法標(biāo)號(hào)法,思路:從始點(diǎn)開(kāi)始標(biāo)號(hào),尋找是否存在增廣鏈。給vj標(biāo)號(hào)為j,vi,其中j為調(diào)整量,vi為前一節(jié)點(diǎn)。,標(biāo)號(hào)具體步驟:,(b)標(biāo)號(hào)終止,說(shuō)明不存在可擴(kuò)充鏈,當(dāng)前即為流為最大流,并得最小截集,(a)說(shuō)明存在可擴(kuò)充鏈,反向追蹤找出,轉(zhuǎn)(4),例5用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流。,(2,2),(1,1),(3,3),(1,1),(4,3),(5,1),(3,0),(2,1),(5,3),步驟:(1)給vs標(biāo)號(hào)為,vs,選與vs關(guān)聯(lián)的流出未飽和弧(vs,vj),給vj標(biāo)號(hào)j,vs,其中j=csj-fsj,例5用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流。,(2,2),(1,1),(3,3),(1,1),(4,3),(5,1),(3,0),(2,1),(5,3),例5用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流。,(2,2),(1,1),(3,3),(1,1),(4,3),(5,1),(3,0),(2,1),(5,3),(2,2),(1,1),(3,3),(1,1),(4,3),(5,1),(3,0),(2,1),(5,3),例5用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流。,vt已標(biāo)號(hào),得到一條增廣鏈u(反向追蹤),轉(zhuǎn)(5);vt未標(biāo)號(hào),且無(wú)法再標(biāo)號(hào),此時(shí)的流為最大流,此時(shí)的截集為最小截。,(4)重復(fù)(2),(3),依次進(jìn)行的結(jié)局可能為:,(2,2),(1,1),(3,3),(1,1),(4,3),(5,1),(3,0),(2,1),(5,3),例5用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流。,vt已標(biāo)號(hào),得到一條增廣鏈u(反向追蹤),轉(zhuǎn)(5);vt未標(biāo)號(hào),且無(wú)法再標(biāo)號(hào),此時(shí)的流為最大流,此時(shí)的截集為最小截。,(4)重復(fù)(2),(3),依次進(jìn)行的結(jié)局可能為:,(2,2),(1,1),(3,3),(1,1),(4,3),(5,1),(3,0),(2,1),(5,3),例5用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流。,vt已標(biāo)號(hào),得到一條增廣鏈u(反向追蹤),轉(zhuǎn)(5);vt未標(biāo)號(hào),且無(wú)法再標(biāo)號(hào),此時(shí)的流為最大流,此時(shí)的截集為最小截。,(4)重復(fù)(2),(3),依次進(jìn)行的結(jié)局可能為:,例5用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流。,(5)調(diào)整。取=t,令,,得新流fij轉(zhuǎn)(1)。,(2,2),(1,0),(3,3),(1,1),(4,4),(5,2),(3,0),(2,1),(5,4),此時(shí)標(biāo)號(hào)無(wú)法進(jìn)行,當(dāng)前流為最大流,最大流量為5;最小截為(vs,v2),(v1,v3),截量為:5,練習(xí):有三個(gè)發(fā)電站v1,v2,v3,發(fā)電能力分別為15、10和40兆瓦,經(jīng)輸電網(wǎng)可把電力送到8號(hào)地區(qū),電網(wǎng)能力如圖所示。求三個(gè)發(fā)電站輸?shù)皆摰貐^(qū)的最大電力。,v0,(1)由于網(wǎng)絡(luò)圖中只有一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn),所以有必要添加一個(gè)虛設(shè)的起點(diǎn)和弧弧上各容量為,分別為三點(diǎn)的發(fā)電能力,如圖所示:,v0,10,10,15,15,15,0,10,10,10,10,15,25,(2)由觀察法得一初始可行流即圖上所標(biāo)。為弧上容量,為弧上流量。,(2)由觀察法得一初始可行流即圖上所標(biāo)。為弧上容量,為弧上流量。,v3,(40,10),(15,15),(30,10),(15,15),(45,25),(10,10),(15,15),(10,0),(20,10),v0,(10,10),(15,15),(40,10),(3)用標(biāo)號(hào)法尋找可擴(kuò)充鏈,v0,|,|,v6,|,v5,v4,|,v2,v1,v7,v8,反向追蹤,得一v0-v8的可擴(kuò)充鏈:v0-v3-v6-v5-v2-v7-v8,v3,(40,10),(15,15),(30,10),(15,15),(45,25),(10,10),(15,15),(10,0),(20,10),v0,(10,10),(15,15),(40,10),v0,|,|,v6,|,v5,v4,|,v2,v1,v7,v8,(4)調(diào)整流量。由可擴(kuò)充鏈確定一新可行流,可擴(kuò)充鏈上前向弧上流量均增加,(45,35),(40,20),(10,10),(20,20),(30,20),(40,20),(5)繼續(xù)用標(biāo)號(hào)法檢驗(yàn)當(dāng)前可行流是否為最大流,v3,(40,20),(15,15),(30,20),(15,15),(45,35),(10,10),(15,15),(10,10),(20,20),v0,(10,10),(15,15),(40,20),v0,|,|,v6,|,v5,v4,v2,v1,v7,v8,|,標(biāo)號(hào)完畢,且終點(diǎn)未標(biāo)號(hào)。這說(shuō)明網(wǎng)絡(luò)中已找不到可擴(kuò)充鏈,當(dāng)前即為最大流,最大流流量為:20+15+1045即三個(gè)發(fā)電站輸送到8號(hào)地區(qū)的最大電力為45兆瓦。,練習(xí):圖中A、B、C、D、E、F分別表示陸地和島嶼,表示橋梁及其編號(hào)。河兩岸分別互為敵對(duì)的雙方部隊(duì)占領(lǐng),問(wèn)至少應(yīng)切斷幾座橋梁(具體指出編號(hào))才能達(dá)到阻止對(duì)方部隊(duì)過(guò)河的目的。試用圖論方法進(jìn)行分析。,分析:轉(zhuǎn)化為一個(gè)網(wǎng)絡(luò)圖,弧的容量為兩點(diǎn)間的橋梁數(shù)。,則問(wèn)題為求最小截。,步驟(1)確定初始可行流,1(1),1(0),分析:轉(zhuǎn)化為一個(gè)網(wǎng)絡(luò)圖,弧的容量為兩點(diǎn)間的橋梁數(shù)。,則問(wèn)題為求最小截。,答案:最小截為AE、CD、CF,A,B,C,D,E,F,2(1),1(1),1(1),1(1),1(0),2(2),2(1),2(1),2(1),2(2),2(2),步驟(1)確定初始可行流,(2)標(biāo)號(hào)法求最大流得最小截,1(0),1(0),2(0),2(0),2(0),案例:有一批人從我國(guó)A城赴俄羅斯B城,可能的旅行路線如圖:,邊防隊(duì)擬建立足夠數(shù)量檢查站以便使每輛汽車(chē)至少必經(jīng)過(guò)一個(gè)檢查站,建立檢查站的費(fèi)用根據(jù)各路段條件有所不同(如圖數(shù)字所示),求最小費(fèi)用解。,(分析:最小截問(wèn)題),分析:轉(zhuǎn)化為一個(gè)網(wǎng)絡(luò)圖,弧的容量為各路段得費(fèi)用。則問(wèn)題為求最小截。步驟,a,B,A,b,c,d,e,f,g,4,6,8,2,3,2,5,7,3,8,4,3,7,6,4,4(4),6(6),8(3),2(2),3(3),2(2),5(5),7(6),3(0),8(4),4(3),3(3),7(3),6(6),4(4),(1)確定初始可行流,(2)標(biāo)號(hào)法求最大流得最小截,答案:最小截為Aa、Ab、cb,即在這三個(gè)路段修建檢查站,最小費(fèi)用為13,案例:垃圾處理問(wèn)題某地區(qū)有3個(gè)城鎮(zhèn),各城鎮(zhèn)每天產(chǎn)生的垃圾要運(yùn)往該地區(qū)的4個(gè)垃圾處理場(chǎng)處理,現(xiàn)考慮各城鎮(zhèn)到各處理場(chǎng)的道路對(duì)各城鎮(zhèn)垃圾外運(yùn)的影響。假設(shè)各城鎮(zhèn)每日產(chǎn)生的垃圾量、各處理場(chǎng)的日處理能力及各條道路(可供運(yùn)垃圾部分)的容量(其中容量為0表示無(wú)此直接道路)如右表所示,試用網(wǎng)絡(luò)流方法分析目前的道路狀況能否使所有垃圾都運(yùn)到處理場(chǎng)得到處理,如果不能,應(yīng)首先拓寬哪條道路。,分析:轉(zhuǎn)化為一個(gè)網(wǎng)絡(luò)圖,弧的容量為各路段能處理垃圾的數(shù)量。,a,b,c,1,2,3,4,s,t,80,50,40,20,50,60,40,90,30,20,70,30,50,10,20,40,則問(wèn)題為求最小截。,b,80(80),50(30),40(20),20(0),50(30),60(60),40(40),90(20),30(30),20(20),70(20),30(30),50(50),10(0),20(20),40(0),80,50,40,20,50,60,40,90,20,70,30,50,10,20,40,s,(1)確定初始可行流,30,(2)標(biāo)號(hào)法求最大流得最小截,4,c,3,2,1,a,t,b,80(80),50(30),40(20),20(0),50(30),60(60),40(40),90(20),30(30),20(20),70(20),30(30),50(50),10(0),20(20),40(0),s,(3)反向追蹤,找可擴(kuò)充鏈,4,c,3,2,1,a,t,90(40),20(20),50(10),40(20),70(40),得一s-t的可擴(kuò)充鏈:,s-b-4-c-3-t,調(diào)整量,b,90(40),50(10),40(20),70(40),80(80),50(30),40(20),20(20),60(60),40(40),30(30),20(20),30(30),50(50),10(0),20(20),(4)重復(fù)標(biāo)號(hào),3,2,1,a,t,s,4,c,a,2,1,a,3,(5)反向追蹤,找可擴(kuò)充鏈,(6)找到可擴(kuò)充流S-b-4-c-3-t,調(diào)整量為10,b,80(80),50(40),40(20),20(20),60(60),40(40),30(30),20(20),30(20),50(50),10(10),20(20),3,2,1,a,t,s,4,c,a,2,1,a,3,(6)找到可擴(kuò)充流S-b-4-c-3-t,調(diào)整量為10,90(50),50(0),40(30),70(50),90(50),20(20),50(0),40(30),70(50),80(80),50(40),40(20),60(60),40(40),30(30),20(20),30(20),50(50),10(10),20(20),(4)重復(fù)標(biāo)號(hào),直至終止,3,2,1,a,t,c,3,2,1,a,t,s,b,4,答案:最小截為sa、sc、b3、4t,垃圾最大處理量為180<50+70+80,答案,綜上,目前的道路狀況不能使所有垃圾都運(yùn)到處理場(chǎng)得到處理。從圖上不難發(fā)現(xiàn),理論上應(yīng)當(dāng)拓寬割集所在的道路。但由于sa,sc和4t都是添加的虛擬道路,所以只有拓寬割集中的b3道路的路寬,或者增大4號(hào)處理場(chǎng)處理垃圾的能力,才能解決問(wèn)題。,練習(xí):過(guò)紐約ALBANY的北-南高速公路,路況通過(guò)能力如下圖所示,圖中弧上數(shù)字單位:千輛/小時(shí)。求(1)該路網(wǎng)能承受的北-南向最大流量;(2)若要擴(kuò)充通過(guò)能力,應(yīng)在那一組路段上擴(kuò)充,說(shuō)明原因。,(1)選取一個(gè)可行流,1,2,3,5,4,6,(,進(jìn)入Albany(北),離開(kāi)Albany(南),2(2),4(1),3(0),1(1),6(5),3(3),2(2),3(3),6(2),1(1),V1V4V2V5V6,可擴(kuò)充量為1,調(diào)整成新流,繼續(xù)標(biāo)號(hào),用標(biāo)號(hào)法得可擴(kuò)充鏈,1,2,3,5,4,6,(,進(jìn)入Albany(北),離開(kāi)Albany(南),2(2),4(2),3(1),1(1),6(5),3(3),2(2),3(3),6(3),1(0),標(biāo)號(hào)終止,當(dāng)前流為最大流,最大流量為8割集為:12,45,46,36應(yīng)該在割集弧上擴(kuò)大流量,練習(xí)1,0,v1,4,v1,3,v1,5,v2,6,v2,9,v7,7,v4/v6,8.5,v6,6,v2,有9個(gè)城市v1、v2、v9,其公路網(wǎng)如圖所示。弧旁數(shù)字是該段公路的長(zhǎng)度,有一批物資要從v1運(yùn)到v9,問(wèn)走哪條路最近?,習(xí)題課練習(xí)(最小支撐樹(shù)),已知有A、B、C、D、E、F六個(gè)城鎮(zhèn)間的道路網(wǎng)絡(luò)如圖,現(xiàn)要在六個(gè)城鎮(zhèn)間架設(shè)通訊網(wǎng)絡(luò)(均沿道路架設(shè)),每段道路上的架設(shè)費(fèi)用如圖。求能保證各城鎮(zhèn)均能通話且總架設(shè)費(fèi)用最少的架設(shè)方案。,練習(xí)2,第四節(jié)最小費(fèi)用最大流問(wèn)題,在實(shí)際的網(wǎng)絡(luò)系統(tǒng)中,當(dāng)涉及到有關(guān)流的問(wèn)題的時(shí)候,我們往往不僅僅考慮的是流量,還經(jīng)常要考慮費(fèi)用的問(wèn)題。比如一個(gè)鐵路系統(tǒng)的運(yùn)輸網(wǎng)絡(luò)流,即要考慮網(wǎng)絡(luò)流的貨運(yùn)量最大,又要考慮總費(fèi)用最小。最小費(fèi)用最大流問(wèn)題就是要解決這一類(lèi)問(wèn)題。,設(shè)一個(gè)網(wǎng)絡(luò)D=(V,A,C),對(duì)于每一個(gè)弧(vi,vj)A,給定一個(gè)單位流量的費(fèi)用bij0,網(wǎng)絡(luò)系統(tǒng)的最小費(fèi)用最大流問(wèn)題,是指要尋求一個(gè)最大流f,并且流的總費(fèi)用達(dá)到最小。,而此時(shí)總費(fèi)用b(f)比b(f)增加了,我們將叫做這條增廣鏈的費(fèi)用。,我們首先考察,在一個(gè)網(wǎng)絡(luò)D中,當(dāng)沿可行流f的一條增廣鏈,以調(diào)整量=1改進(jìn)f,得到的新可行流f的流量,有v(f)=v(f)+1,顯然,零流f=0是流量為0的最小費(fèi)用流。一般地,尋求最小費(fèi)用流,總可以從零流f=0開(kāi)始。問(wèn)題是:如果已知f是流量為v(f)的最小費(fèi)用流,如何尋找關(guān)于f的最小費(fèi)用增廣鏈?,結(jié)論:若f是流量為v(f)的所有可行流中的費(fèi)用最小,而是關(guān)于f的所有增廣鏈中的費(fèi)用最小的增廣鏈,則f沿增廣鏈調(diào)整量為1得到的新可行流f,一定是流量為v(f)+1的所有可行流中的最小費(fèi)用流。依次類(lèi)推,當(dāng)f是最大流時(shí),就是所要求的最小費(fèi)用最大流。,若u是從vs到vt關(guān)于f的增廣鏈,它的費(fèi)用,若果把u-中的邊(vi,vj)反向,并且令它的權(quán)是-bij,而u+中的方向不變,并且的它的權(quán)是bij,這樣就把求從vs到vt關(guān)于f的最小費(fèi)用增廣鏈就轉(zhuǎn)換成尋求從vs到vt的最短路。,構(gòu)造一個(gè)賦權(quán)有向圖M(f),其頂點(diǎn)是原網(wǎng)絡(luò)D的頂點(diǎn),他的邊根據(jù)f的情況確定:,若原圖中(vi,vj)邊中fij=0,則M(f)中連接(vi,vj),并令其權(quán)L(vi,vj)=bij;若原圖中(vi,vj)邊中fij=cij,則M(f)中連接(vi,vj),并令其權(quán)L(vi,vj)=-bij;若原圖中(vi,vj)邊中fij=0,則M(f)中連接(vi,vj)和(vj,vi),并令其權(quán)L(vi,vj)=bij,L(vi,vj)=-bij;,步驟:(1)取零流為初始可行流,f(0)=0。(2)一般地,如果在第k-1步得到最小費(fèi)用流f(k-1),則構(gòu)造圖L(f(k-1)。(3)在L(f(k-1)中,尋求從vs到vt的最短路。若不存在最短路,則f(k-1)就是最小費(fèi)用最大流;否則轉(zhuǎn)(4)。(4)如果存在最短路,則在可行流f(k1)的圖中得到與此最短路相對(duì)應(yīng)的增廣鏈,在增廣鏈上,對(duì)f(k1)進(jìn)行調(diào)整,調(diào)整量為:,得到新可行流f(k)。對(duì)f(k)重復(fù)上面步驟,返回(2)。,例求圖8-24所示網(wǎng)絡(luò)中的最小費(fèi)用最大流,弧旁的權(quán)是(bij,cij).,圖8-24,4,由于在M(f(4)中已經(jīng)不存在從vs到vt的最短路,因此,可行流f(4),v(f(4)=11是最小費(fèi)用最大流。,例8.11求網(wǎng)絡(luò)的最小費(fèi)用最大流,弧旁權(quán)是(bij,cij),

注意事項(xiàng)

本文(運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析.ppt)為本站會(huì)員(xt****7)主動(dòng)上傳,裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。 若此文所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng)(點(diǎn)擊聯(lián)系客服),我們立即給予刪除!

溫馨提示:如果因?yàn)榫W(wǎng)速或其他原因下載失敗請(qǐng)重新下載,重復(fù)下載不扣分。




關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!