第11章圖與網(wǎng)絡(luò)模型課件_第1頁(yè)
第11章圖與網(wǎng)絡(luò)模型課件_第2頁(yè)
第11章圖與網(wǎng)絡(luò)模型課件_第3頁(yè)
第11章圖與網(wǎng)絡(luò)模型課件_第4頁(yè)
第11章圖與網(wǎng)絡(luò)模型課件_第5頁(yè)
已閱讀5頁(yè),還剩68頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

運(yùn)籌學(xué)

Operations

Research

Chapter11網(wǎng)絡(luò)模型NetworkModeling11.1基本概念11.2最小(支撐)樹問題11.3最短路問題11.4最大流問題11.5最小費(fèi)用最大流11.6中國(guó)郵路問題

8/3/2023

歐拉早年解決著名的哥尼斯堡七橋問題,哥尼斯堡城市中有一條河,河中有兩個(gè)島,河的兩岸和河中的兩個(gè)小島有7座橋。當(dāng)?shù)鼐用裉岢觯阂粋€(gè)步行者能否通過每座橋一次且僅一次就能返回原出發(fā)地。DCA岸B岸8/3/2023歐拉早年解決著名的哥尼斯堡七橋問題,哥尼斯堡城市中有一條河,歐拉將此問題歸為一筆畫問題,即能否從某點(diǎn)開始一筆畫出這個(gè)圖形,最后回到出發(fā)點(diǎn),而不重復(fù)。CDAB歐拉證明了這是不可能的。8/3/2023歐拉將此問題歸為一筆畫問題,即能否從某點(diǎn)開始一筆畫出這個(gè)圖形在這一時(shí)期,還有許多游戲問題,諸如環(huán)球旅行、迷宮問題、博奕問題等難題,吸引了許多學(xué)者,這些問題看起來(lái)似乎是一些無(wú)足輕重的游戲,但常常是由于這些游戲引出了許多實(shí)用意義的新問題,開辟了新學(xué)科。圖論在現(xiàn)實(shí)生活中很多,如各種通信網(wǎng)絡(luò)的合理架設(shè),交通網(wǎng)絡(luò)的合理分布,郵遞員送信,怎么走完他負(fù)責(zé)投遞的全部街道,完成任務(wù)回到郵局,使走的路線最短,電子商務(wù)物流配送中的最佳運(yùn)送路線的選擇等,都屬于圖論問題。8/3/2023在這一時(shí)期,還有許多游戲問題,諸如環(huán)球旅行、迷宮問題、博奕問5v1v2v3v4v5v6843752618圖11-1運(yùn)籌學(xué)中研究的圖具有下列特征:(1)用點(diǎn)表示研究對(duì)象,用邊(有方向或無(wú)方向)表示對(duì)象之間某種關(guān)系。(2)強(qiáng)調(diào)點(diǎn)與點(diǎn)之間的關(guān)聯(lián)關(guān)系,不講究圖的比例大小與形狀。(3)每條邊上都賦有一個(gè)權(quán),其圖稱為賦權(quán)圖。實(shí)際中權(quán)可以代表兩點(diǎn)之間的距離、費(fèi)用、利潤(rùn)、時(shí)間、容量等不同的含義。(4)建立一個(gè)網(wǎng)絡(luò)模型,求最大值或最小值。8/3/20235v1v2v3v4v5v6843752618圖11-1運(yùn)籌學(xué)11.1圖的基本概念

8/3/202311.1圖的基本概念7/31/2023例1:五個(gè)隊(duì)比賽的圖v1v3v4v1v3v4v2v1v1v58/3/2023例1:五個(gè)隊(duì)比賽的圖v1v3v4v1v3v4v2v1v1v5圖論不僅僅是要描述對(duì)象之間關(guān)系,還要研究特定關(guān)系之間的內(nèi)在規(guī)律,一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直,對(duì)于反映對(duì)象之間的關(guān)系并不是重要的,圖論中的圖與幾何圖、工程圖是不一樣的。8/3/2023圖論不僅僅是要描述對(duì)象之間關(guān)系,還要研究特定關(guān)系之間的內(nèi)在規(guī)從以上圖可看出圖:(1)圖是由一些點(diǎn)和一些點(diǎn)之間的連線(帶箭頭或不帶箭頭)所組成的。(2)具有“對(duì)稱性”和“不對(duì)稱性”概念:邊:兩點(diǎn)之間的不帶箭頭的連線。弧:兩點(diǎn)之間的帶箭頭的連線。無(wú)向圖:由點(diǎn)和邊組成。記為G=(V,E)點(diǎn)的集合邊的集合8/3/2023從以上圖可看出圖:點(diǎn)的集合邊的集合7/31/2023e3一條連結(jié)vi,vj∈V的邊,記為[vi,vj]或[vj,vi]上圖中:V={v1,v2,v3,v4}E={e1,e2,…..e7}e1=[v1,v2],e2=[v2,v1]………e7=[v4,v4]

v4v1v2v3e6e5e4e2e1e7e38/3/2023e3一條連結(jié)vi,vj∈V的邊,記為[vi,vj]或[vj,v9a2有向圖:由點(diǎn)和弧組成。記為D=(V,A)一條方向從vi→vj的弧,記為:(vi,vj)V={v1,…..,v7}A={a1,…….,a11}a1=(v1,v2)a2=(v1,v3)…….弧的集合v1a4a5a6a7a10a11v3v2v5v4v6v7a8a1a38/3/2023v9a2有向圖:由點(diǎn)和弧組成。記為D=(V,A)弧的集合v1點(diǎn)數(shù)記為:p(G),p(D)邊數(shù)記為:q(G)弧數(shù)記為:q(D)下面介紹一些名詞,先考慮無(wú)向圖:e=[u,v],稱u、v是e的端點(diǎn),也稱u、v是相鄰的。稱e是u(v)的關(guān)聯(lián)邊。多重邊:兩點(diǎn)之間有多于一條的邊。簡(jiǎn)單圖:無(wú)環(huán),無(wú)多重邊的圖。多重圖:無(wú)環(huán),但允許有多重邊的圖。8/3/2023點(diǎn)數(shù)記為:p(G),p(D)7/31/2023次:以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù),記為d(v).懸掛點(diǎn):次為1的點(diǎn)。懸掛邊:懸掛點(diǎn)的關(guān)聯(lián)邊孤立點(diǎn):次為0的點(diǎn)。定理1:在G=(V,E)中,所有點(diǎn)的次之和是邊數(shù)的兩倍。8/3/2023次:以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù),記為d(v).7/31/2023奇點(diǎn):次為奇數(shù)的點(diǎn)。偶點(diǎn):次為偶數(shù)的點(diǎn)。定理2:任一個(gè)圖中,奇點(diǎn)的個(gè)數(shù)為偶數(shù)。(因?yàn)槠纥c(diǎn)的邊數(shù)為奇數(shù),所以個(gè)數(shù)為偶數(shù))為偶數(shù)8/3/2023奇點(diǎn):次為奇數(shù)的點(diǎn)。為偶數(shù)7/31/2023鏈:G=(V,E),一個(gè)點(diǎn)、邊交錯(cuò)序列(vi1,ei1,vi2,ei2,…..,v(ik-1),e(ik-1),vik)。如滿足eit=[vit,v(it+1)],稱為一條連結(jié)vi1,vi2,…..,v(ik-1),vik的鏈。記為(vi1,vi2,…..,v(ik-1),vik)圈:鏈(vi1,vi2,…..,v(ik-1),vik)中,若vi1=vik,稱為圈。記為(vi1,vi2,…..,v(ik-1),vi1)。初等鏈:鏈中各點(diǎn)都不同。初等圈:圈中除頭尾外,中間點(diǎn)都不同。8/3/2023鏈:G=(V,E),一個(gè)點(diǎn)、邊交錯(cuò)序列(vi1,ei1,vie7e4簡(jiǎn)單鏈(圈):鏈(圈)中含的邊都不相同。(點(diǎn)可以相同)以后提到的鏈(圈),除非特別交代,都指初等鏈(圈)。v1e1e2e3e6e8e9v2v4v3v6v5v7e10v9v8e58/3/2023e7e4簡(jiǎn)單鏈(圈):鏈(圈)中含的邊都不相同。v1e1e2(v1,v2,v3,v4,v5,v3,v6,v7)是簡(jiǎn)單鏈。(v1,v2,v3,v6,v7)是初等鏈。連通圖:G中,若任何兩點(diǎn)之間,至少有一條鏈,否則,稱為不連通圖。連通分圖:若G不連通,它的每個(gè)連通,部分稱為連通分圖。支撐子圖:G=(V,E),如果G’=(V’,E’),使V=V’及E’E,則G’為G的一個(gè)支撐子圖.8/3/2023(v1,v2,v3,v4,v5,v3,v6,v7)是簡(jiǎn)單鏈。有向圖中:路:如有(vi1,ai1,vi2,ai2,…..,v(ik-1),a(ik-1),vik)是D中一條鏈,且有ait=(vit,v(it+1)),稱從vi1→vik的一條路?;芈罚喝袈分械谝稽c(diǎn)和最后一點(diǎn)相同,則稱為回路。支撐子圖8/3/2023支撐子圖7/31/202311.2最小(支撐)樹問題

Minimal(Spanning)TreeProblem8/3/202311.2最小(支撐)樹問題7/31/202311.2.1樹的概念一個(gè)無(wú)圈并且連通的無(wú)向圖稱為樹圖或簡(jiǎn)稱樹(Tree)。組織機(jī)構(gòu)、家譜、學(xué)科分支、因特網(wǎng)絡(luò)、通訊網(wǎng)絡(luò)及高壓線路網(wǎng)絡(luò)等都能表達(dá)成一個(gè)樹圖??梢宰C明:(1)一棵樹的邊數(shù)等于點(diǎn)數(shù)減1;(2)在樹中任意兩個(gè)點(diǎn)之間添加一條邊就形成圈;(3)在樹中去掉任意一條邊圖就變?yōu)椴贿B通。在一個(gè)連通圖G中,取部分邊連接G的所有點(diǎn)組成的樹稱為G的部分樹或支撐樹(SpanningTree

)。圖11-2是圖11-1的部分樹。v1v2v3v4v5v64321圖11-2711.2最小樹問題

Minimaltreeproblem8/3/202311.2.1樹的概念一個(gè)無(wú)圈并且連通的無(wú)向圖稱為樹圖或簡(jiǎn)稱11.2.2最小部分樹將網(wǎng)絡(luò)圖G邊上的權(quán)看作兩點(diǎn)間的長(zhǎng)度(距離、費(fèi)用、時(shí)間),定義G的部分樹T的長(zhǎng)度等于T中每條邊的長(zhǎng)度之和,記為C(T)。G的所有部分樹中長(zhǎng)度最小的部分樹稱為最小部分樹,或簡(jiǎn)稱為最小樹。最小部分樹可以直接用作圖的方法求解,常用的有破圈法和加邊法。破圈法:任取一圈,去掉圈中最長(zhǎng)邊,直到無(wú)圈。11.2最小樹問題

Minimaltreeproblem8/3/202311.2.2最小部分樹將網(wǎng)絡(luò)圖G邊上的權(quán)看作兩點(diǎn)間的長(zhǎng)度(5v1v2v3v4v5v6843752618圖11-1【例11.1】用破圈法求圖11-1的最小樹。圖11-4圖11-4就是圖11-1的最小部分樹,最小樹長(zhǎng)為C(T)=4+3+5+2+1=15。當(dāng)一個(gè)圈中有多個(gè)相同的最長(zhǎng)邊時(shí),不能同時(shí)都去掉,只能去掉其中任意一條邊。最小部分樹有可能不唯一,但最小樹的長(zhǎng)度相同11.2最小樹問題

Minimaltreeproblem8/3/20235v1v2v3v4v5v6843752618圖11-1【例1加邊法:取圖G的n個(gè)孤立點(diǎn){v1,v2,…,vn}作為一個(gè)支撐圖,從最短邊開始往支撐圖中添加,見圈回避,直到連通(有n-1條邊)

v1v2v3v4v5v643521圖11-5在圖11-5中,如果添加邊[v1,v2]就形成圈{v1,v2,v4},這時(shí)就應(yīng)避開添加邊[v1,v2],添加下一條最短邊[v3,v6]。破圈法和加邊法得到樹的形狀可能不一樣,但最小樹的長(zhǎng)度相等5v1v3v515v2v4v684375268×MinC(T)=1511.2最小樹問題

Minimaltreeproblem8/3/2023加邊法:取圖G的n個(gè)孤立點(diǎn){v1,v2,…,vn}作為一個(gè)下一節(jié):最短路問題1.樹、支撐樹、最小支撐樹的概念2.掌握求最小樹的方法:(1)破圈法(2)加邊法11.2最小樹問題

Minimaltreeproblem8/3/2023下一節(jié):最短路問題1.樹、支撐樹、最小支撐樹的概念11.211.3最短路問題ShortestPathProblem8/3/202311.3最短路問題7/31/2023最短路問題在實(shí)際中具有廣泛的應(yīng)用,如管道鋪設(shè)、線路選擇等問題,還有些如設(shè)備更新、投資等問題也可以歸結(jié)為求最短路問題求最短路有兩種算法:一是求從某一點(diǎn)至其它各點(diǎn)之間最短離的狄克斯屈拉(Dijkstra)算法另一種是求網(wǎng)絡(luò)圖上任意兩點(diǎn)之間最短路的Floyd(弗洛伊德)矩陣算法。最短路問題,就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路11.3.1最短路問題的網(wǎng)絡(luò)模型11.3最短路問題ShortestPathProblem

8/3/2023最短路問題在實(shí)際中具有廣泛的應(yīng)用,如管道鋪設(shè)、線路選擇等問題①②③④⑤⑥⑦610123214675811165圖11-69【例11.2】圖11-6中的權(quán)cij表示vi到vj的距離(費(fèi)用、時(shí)間),從v1修一條公路或架設(shè)一條高壓線到v7,如何選擇一條路線使距離最短,建立該問題的網(wǎng)絡(luò)數(shù)學(xué)模型。11.3最短路問題ShortestPathProblem

8/3/2023①②③④⑤⑥⑦610123214675811165圖11-611.3.2有向圖的狄克斯屈拉(Dijkstra)標(biāo)號(hào)算法點(diǎn)標(biāo)號(hào):b(j)—起點(diǎn)vs到點(diǎn)vj的最短路長(zhǎng);邊標(biāo)號(hào):k(i,j)=b(i)+cij,步驟:(1)令起點(diǎn)的標(biāo)號(hào);b(s)=0。先求有向圖的最短路,設(shè)網(wǎng)絡(luò)圖的起點(diǎn)是vs,終點(diǎn)是vt,以vi為起點(diǎn)vj為終點(diǎn)的弧記為(i,j),距離為cij(2)找出所有vi已標(biāo)號(hào)vj未標(biāo)號(hào)的弧集合B={(i,j)},如果這樣的弧不存在或vt已標(biāo)號(hào)則計(jì)算結(jié)束;(3)計(jì)算集合B中弧k(i,j)=b(i)+cij的標(biāo)號(hào)(4)選一個(gè)點(diǎn)標(biāo)號(hào)返回到第(2)步。11.3最短路問題ShortestPathProblem

8/3/202311.3.2有向圖的狄克斯屈拉(Dijkstra)標(biāo)號(hào)算法點(diǎn)②③④⑤⑥⑦610123214675811165圖11-690610129209186①161217162432182929【例11.3】用Dijkstra算法求圖11-6所示v1到v7的最短路及最短路長(zhǎng)v1到v7的最短路為:p17={v1,v2,v3,v5,v7},最短路長(zhǎng)為L(zhǎng)17=2911.3最短路問題ShortestPathProblem

14S={①}T={②③④⑤⑥⑦}min{0+c12,0+c13,0+c14}S={①②}①②↓↓T={③④⑤⑥⑦}min{0+c13,0+c14,6+c23,6+c25}S={①②③}①②③↓↓↓T={④⑤⑥⑦}min{0+c14,6+c25,9+c35,9+c36,9+c34}8/3/2023②③④⑤⑥⑦610123214675811165圖11-69從上例知,只要某點(diǎn)已標(biāo)號(hào),說明已找到起點(diǎn)vs到該點(diǎn)的最短路線及最短距離,因此可以將每個(gè)點(diǎn)標(biāo)號(hào),求出vs到任意點(diǎn)的最短路線,如果某個(gè)點(diǎn)vj不能標(biāo)號(hào),說明vs不可達(dá)vj。11.3.3無(wú)向圖最短路的求法無(wú)向圖最短路的求法只將上述步驟(2)改動(dòng)一下即可。點(diǎn)標(biāo)號(hào):b(i)—起點(diǎn)vs到點(diǎn)vj的最短路長(zhǎng);邊標(biāo)號(hào):k(i,j)=b(i)+cij,步驟:(1)令起點(diǎn)的標(biāo)號(hào);b(s)=0。(3)計(jì)算集合B中邊標(biāo)號(hào):k[i,j]=b(i)+cij(4)選一個(gè)點(diǎn)標(biāo)號(hào):返回到第(2)步。(2)找出所有一端vi已標(biāo)號(hào)另一端vj未標(biāo)號(hào)的邊集合B={[i,j]}如果這樣的邊不存在或vt已標(biāo)號(hào)則計(jì)算結(jié)束;11.3最短路問題ShortestPathProblem

8/3/2023從上例知,只要某點(diǎn)已標(biāo)號(hào),說明已找到起點(diǎn)vs到該點(diǎn)的最短路線【例11.4】求圖11-10所示v1到各點(diǎn)的最短路及最短距離①②③④⑤⑥⑦⑧4526178393261216180452231039612641166188122482418所有點(diǎn)都已標(biāo)號(hào),點(diǎn)上的標(biāo)號(hào)就是v1到該點(diǎn)的最短距離,最短路線就是紅色的鏈。圖11-1011.3最短路問題ShortestPathProblem

8/3/2023【例11.4】求圖11-10所示v1到各點(diǎn)的最短路及最短距離下一節(jié):最大流問題11.3最短路問題ShortestPathProblem

1.最短路的概念及應(yīng)用。2.有向圖、無(wú)向圖一點(diǎn)到各點(diǎn)最短路的Dijkstra算法8/3/2023下一節(jié):最大流問題11.3最短路問題1.最短路的概念及應(yīng)11.4最大流問題MaximalFlowProblem8/3/202311.4最大流問題7/31/202311.4最大流問題MaximalFlowProblem11.4.1基本概念①②③④⑤⑥814563381076⑦3圖11-184圖11-18所示的網(wǎng)絡(luò)圖中定義了一個(gè)發(fā)點(diǎn)v1,稱為源(source,supplynode),定義了一個(gè)收點(diǎn)v7,稱為匯(sink,demandnode),其余點(diǎn)v2,v3,…,v6為中間點(diǎn),稱為轉(zhuǎn)運(yùn)點(diǎn)(transshipmentnodes)。如果有多個(gè)發(fā)點(diǎn)和收點(diǎn),則虛設(shè)發(fā)點(diǎn)和收點(diǎn)轉(zhuǎn)化成一個(gè)發(fā)點(diǎn)和收點(diǎn)。圖中的權(quán)是該弧在單位時(shí)間內(nèi)的最大通過能力,稱為弧的容量(capacity)。最大流問題是在單位時(shí)間內(nèi)安排一個(gè)運(yùn)送方案,將發(fā)點(diǎn)的物質(zhì)沿著弧的方向運(yùn)送到收點(diǎn),使總運(yùn)輸量最大。8/3/202311.4最大流問題11.4.1基本概念①②③④⑤⑥814設(shè)cij為?。╥,j)的容量,fij為?。╥,j)的流量。容量是?。╥,j)單位時(shí)間內(nèi)的最大通過能力,流量是?。╥,j)單位時(shí)間內(nèi)的實(shí)際通過量,流量的集合f={fij}稱為網(wǎng)絡(luò)的流。發(fā)點(diǎn)到收點(diǎn)的總流量記為v=val(f),v也是網(wǎng)絡(luò)的流量。圖11-18最大流問題的線性規(guī)劃數(shù)學(xué)模型為111.4最大流問題MaximalFlowProblem8/3/2023設(shè)cij為?。╥,j)的容量,fij為?。╥,j)的流量。圖滿足下例3個(gè)條件的流fij的集合f={fij

}稱為可行流發(fā)點(diǎn)vs流出的總流量等于流入收點(diǎn)vt的總流量11.4最大流問題MaximalFlowProblem8/3/2023滿足下例3個(gè)條件的流fij的集合f={fij}稱為鏈:從發(fā)點(diǎn)到收點(diǎn)的一條路線(弧的方向不一定都同向)稱為鏈。從發(fā)點(diǎn)到收點(diǎn)的方向規(guī)定為鏈的方向。前向?。号c鏈的方向相同的弧稱為前向弧。后向?。号c鏈的方向相反的弧稱為后向弧。增廣鏈:設(shè)f是一個(gè)可行流,如果存在一條從vs到vt的鏈,滿足:1.所有前向弧上fij<Cij2.所有后向弧上fij>0則該鏈稱為增廣鏈①②③④⑤⑥前向弧后向弧容量流量這是一條增廣鏈84469(5)(2)(3)(4)(6)11.4最大流問題MaximalFlowProblem8/3/2023鏈:從發(fā)點(diǎn)到收點(diǎn)的一條路線(弧的方向不一定都同向)稱為鏈。從步驟如下:第二步:對(duì)點(diǎn)進(jìn)行標(biāo)號(hào)找一條增廣鏈。(1)發(fā)點(diǎn)標(biāo)號(hào)(∞)(2)選一個(gè)點(diǎn)vi已標(biāo)號(hào)并且另一端未標(biāo)號(hào)的弧沿著某條鏈向收點(diǎn)檢查:A.如果弧的方向向前(前向?。┎⑶矣衒ij<cij,則vj標(biāo)號(hào):θj=cij-fijB.如果弧的方向指向vi(后向?。┎⑶矣衒ji>0,則vj標(biāo)號(hào):

θj=fji當(dāng)收點(diǎn)已得到標(biāo)號(hào)時(shí),說明已找到增廣鏈,依據(jù)vi

的標(biāo)號(hào)反向跟蹤得到一條增廣鏈。當(dāng)收點(diǎn)不能得到標(biāo)號(hào)時(shí),說明不存在增廣鏈,計(jì)算結(jié)束。第一步:找出第一個(gè)可行流,例如所有弧的流量fij

=011.4.2Ford-Fulkerson標(biāo)號(hào)算法11.4最大流問題MaximalFlowProblem例8/3/2023步驟如下:第二步:對(duì)點(diǎn)進(jìn)行標(biāo)號(hào)找一條增廣鏈。第一步:找出第第三步:調(diào)整流量(1)求增廣鏈上點(diǎn)vi

的標(biāo)號(hào)的最小值,得到調(diào)整量(2)調(diào)整流量得到新的可行流f1,去掉所有標(biāo)號(hào),返回到第二步從發(fā)點(diǎn)重新標(biāo)號(hào)尋找增廣鏈,直到收點(diǎn)不能標(biāo)號(hào)為止【定理11.1】可行流f是最大流的充分必要條件是不存在發(fā)點(diǎn)到收點(diǎn)的增廣鏈11.4最大流問題MaximalFlowProblem8/3/2023第三步:調(diào)整流量(2)調(diào)整流量得到新的可行流f1,去掉所有標(biāo)①②③④⑤⑥814563381076⑦3圖11-19(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)【例11.10】求圖11-18發(fā)點(diǎn)v1到收點(diǎn)v7的最大流及最大流量【解】給定初始可行流,見圖11-1911.4最大流問題MaximalFlowProblem8/3/2023①②③④⑤⑥814563381076⑦3圖11-19(10)①②③④⑤⑥814563381076⑦3圖11-20(b)(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)∞2337第一輪標(biāo)號(hào):c12>f12,v2標(biāo)號(hào)2cij=fij,v4、v5不能標(biāo)號(hào)后向弧f32>0,v3標(biāo)號(hào)θ3=f32增廣鏈μ={(1,2),(3,2),(3,4),(4,7)},μ+={(1,2),(3,4),(4,7)},μ-={(3,2)},調(diào)整量為增廣鏈上點(diǎn)標(biāo)號(hào)的最小值θ=min{∞,2,3,3,7}=211.4最大流問題MaximalFlowProblemstep8/3/2023①②③④⑤⑥814563381076⑦3圖11-20(b)(①②③④⑤⑥814563381076⑦3圖11-21(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)調(diào)整后的可行流:11.4最大流問題MaximalFlowProblem8/3/2023①②③④⑤⑥814563381076⑦3圖11-21(10)①②③④⑤⑥814563381076⑦3圖11-22(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)∞4415第二輪標(biāo)號(hào):Cij=fij,v4、v5不能標(biāo)號(hào),返回到v3增廣鏈μ=μ+={(1,3),(3,4),(4,7)},調(diào)整量為θ=min{∞,4,1,5}=111.4最大流問題MaximalFlowProblem8/3/2023①②③④⑤⑥814563381076⑦3圖11-22(10)①②③④⑤⑥814563381076⑦3圖11-23(11)(8)(1)(6)(3)(7)(3)(6)(1)4(6)(1)(7)調(diào)整后得到可行流:11.4最大流問題MaximalFlowProblem8/3/2023①②③④⑤⑥814563381076⑦3圖11-23(11)①②③④⑤⑥814563381076⑦3圖11-22(11)(8)(1)(6)(3)(7)(3)(6)(1)4(6)(1)(7)∞314第三輪標(biāo)號(hào):增廣鏈μ=μ+={(1,3),(3,6),(6,4),(4,7)},調(diào)整量為θ=min{∞,3,1,2,4}=1211.4最大流問題MaximalFlowProblem8/3/2023①②③④⑤⑥814563381076⑦3圖11-22(11)①②③④⑤⑥814563381076⑦3圖11-25(12)(8)(1)(6)(3)(8)(3)(6)(2)4(7)(1)(7)調(diào)整后得到可行流:114最大流問題MaximalFlowProblem8/3/2023①②③④⑤⑥814563381076⑦3圖11-25(12)①②③④⑤⑥814563381076⑦3圖11-22(12)(8)(1)(6)(3)(8)(3)(6)(2)4(7)(1)(7)∞2第四輪標(biāo)號(hào):v7得不到標(biāo)號(hào),不存在v1到v7的增廣鏈,圖6-22所示的可行流是最大流,最大流量為v=f12+f13=8+12=20Cij=fij,v4、v5不能標(biāo)號(hào)Cij=fij,v4、v6不能標(biāo)號(hào)411.4最大流問題MaximalFlowProblem8/3/2023①②③④⑤⑥814563381076⑦3圖11-22(12)無(wú)向圖最大流標(biāo)號(hào)算法無(wú)向圖不存在后向弧,可以理解為所有弧都是前向弧,對(duì)一端vi已標(biāo)號(hào)另一端vj未標(biāo)號(hào)的邊只要滿足Cij-fij>0則vj就可標(biāo)號(hào)(Cij-fij)【例11.11】求下圖v1到則v7標(biāo)的最大流7①②③④⑤⑥⑦1292085148691316(10)(6)(10)(8)(2)(3)(7)(6)(5)(13)(0)(13)∞2399311.4最大流問題MaximalFlowProblem8/3/2023無(wú)向圖最大流標(biāo)號(hào)算法無(wú)向圖不存在后向弧,可以理解為所有弧都是7①②③④⑤⑥⑦1292085148691316(12)(6)(10)(8)(4)(3)(7)(6)(7)(13)(2)(15)∞37717①②③④⑤⑥⑦1292085148691316(12)(7)(10)(8)(4)(3)(7)(6)(8)(13)(3)(16)V=29∞1056611.4最大流問題MaximalFlowProblem18/3/20237①②③④⑤⑥⑦1292085148691316(12)(6【例11.12】某石油公司擁有一個(gè)管道網(wǎng)絡(luò),使用這個(gè)網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷售點(diǎn),這個(gè)網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑的變化,它的各段管道(vi,vj)的流量cij(容量)也是不一樣的。cij的單位為萬(wàn)加侖/小時(shí)。如果使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從采地v1向銷地v7運(yùn)送石油,問每小時(shí)能運(yùn)送多少加侖石油?v563522241263v1v2v7v4v3v6圖11-26最大流另一解法—只給出最大流時(shí)8/3/2023【例11.12】某石油公司擁有一個(gè)管道網(wǎng)絡(luò),使用這個(gè)網(wǎng)絡(luò)可以最大流問題網(wǎng)絡(luò)圖論的解法

對(duì)網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。為省去弧的方向,如下圖:(a)和(b)、(c)和(d)的意義相同。

用以上方法對(duì)例11.12的圖的容量標(biāo)號(hào)作改進(jìn),得下圖vivjvivjcij0(a)(b)cijcijvivj(cji)(c)vivjcijcji(d)63522241263v1v2v5v7v4v3v600000000000最大流另一解法8/3/2023最大流問題網(wǎng)絡(luò)圖論的解法

對(duì)網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)

求最大流的基本算法(1)找出一條從發(fā)點(diǎn)到收點(diǎn)的路,在這條路上的每一條弧順流方向的容量都大于零。如果不存在這樣的路,則已經(jīng)求得最大流。(2)找出這條路上各條弧的最小的順流的容量pf,通過這條路增加網(wǎng)絡(luò)的流量pf。(3)在這條路上,減少每一條弧的順流容量pf,同時(shí)增加這些弧的逆流容量pf,返回步驟(1)。用此方法對(duì)例11.12求解:第一次迭代:選擇路為v1v4v7?;。╲4,

v7)的順流容量為2,決定了pf=2,改進(jìn)的網(wǎng)絡(luò)流量圖如下圖:63522241263v1v2v5v7v4v3v6000000000004202最大流另一解法8/3/2023求最大流的基本算法63522241263v1第二次迭代:選擇路為v1v2v5v7?;。╲2,

v5)的順流容量為3,決定了pf=3,改進(jìn)的網(wǎng)絡(luò)流量圖如下圖:第三次迭代:選擇路為v1v4v6v7?;。╲4,

v6)的順流容量為1,決定了pf=1,改進(jìn)的網(wǎng)絡(luò)流量圖如下圖:635222413v1v2v5v7v4v3v60000000042022033303222413v1v2v5v7v4v3v600000042022033333013最大流另一解法8/3/2023第二次迭代:選擇路為v1v2第四次迭代:選擇路為v1v4v3v6v7?;。╲3,

v6)的順流容量為2,決定了pf=2,改進(jìn)的網(wǎng)絡(luò)流量圖如下圖:第五次迭代:選擇路為v1v2v3v5v7?;。╲2,

v3)的順流容量為2,決定了pf=2,改進(jìn)的網(wǎng)絡(luò)流量圖如下圖:22243v1v2v5v7v4v3v6100001203203335031200231322v1v2v5v7v4v3v61012020333501202313150020205最大流另一解法8/3/2023第四次迭代:選擇路為v1v4

經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點(diǎn)到收點(diǎn)的一條路,路上的每一條弧順流容量都大于零,運(yùn)算停止。得到最大流量為10。最大流量圖如下圖:22v1v2v5v7v4v3v6123522355“管理運(yùn)籌學(xué)軟件”中還有專門的子程序用于解決最大流問題。最大流另一解法8/3/2023經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點(diǎn)到收點(diǎn)11.4.4最大流應(yīng)用舉例1.二分圖的最大匹配問題【例11.13】某公司需要招聘5個(gè)專業(yè)的畢業(yè)生各一個(gè),通過本人報(bào)名和篩選,公司最后認(rèn)為有6人都達(dá)到錄取條件。這6人所學(xué)專業(yè)見表11-10,表中打“√”表示該生所學(xué)專業(yè)。公司應(yīng)招聘哪幾位畢業(yè)生,如何分配他們的工作畢業(yè)生A.市場(chǎng)營(yíng)銷B.工程管理C.管理信息D.計(jì)算機(jī)E.企業(yè)管理1√√2√√3√√4√√5√√6√√表11-1011.4最大流問題MaximalFlowProblem8/3/202311.4.4最大流應(yīng)用舉例1.二分圖的最大匹配問題【例11①②③④⑤⑥ABCDEst(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)圖11-32【解】畫出一個(gè)二分圖,虛設(shè)一個(gè)發(fā)點(diǎn)和一收點(diǎn),每條弧上的容量等于1,問題為求發(fā)點(diǎn)到收點(diǎn)的最大流,求解結(jié)果之一見圖11-32。公司錄取第2~6號(hào)畢業(yè)生,安排的工作依次為管理信息、企業(yè)管理、市場(chǎng)營(yíng)銷、工程管理和計(jì)算機(jī)。11.4最大流問題MaximalFlowProblem8/3/2023①②③④⑤⑥ABCDEst(1)(1)(1)(1)(1)(11.最大流的概念:容量、流量、可行流、最大流、前向弧、后向弧、增廣鏈。2.有向圖、無(wú)向圖最大流的Ford-Fulkerson標(biāo)號(hào)算法3.本節(jié)介紹了應(yīng)用:最大匹配問題11.4最大流問題MaximalFlowProblem8/3/20231

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論