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

運(yùn)籌學(xué)課件圖與網(wǎng)絡(luò)分析8.4最短路問(wèn)題

最短路問(wèn)題是重要的最優(yōu)化問(wèn)題之一，本節(jié)以賦權(quán)有向圖為例，介紹最短路問(wèn)題。第2頁(yè),共155頁(yè)，2024年2月25日，星期天8.4.1有向圖

設(shè)D=(V,A)是一個(gè)有向圖，對(duì)于D中的一條弧a=(u,v)，稱u為a的始點(diǎn)、v為a的終點(diǎn)，稱弧a是從u指向v的。若從D中去掉所有弧上的箭頭，就得到一個(gè)無(wú)向圖，稱之為D的基礎(chǔ)圖，記為G(D)。類(lèi)似于無(wú)向圖，可以定義簡(jiǎn)單有向圖、多重有向圖。第3頁(yè),共155頁(yè)，2024年2月25日，星期天有向圖及其基礎(chǔ)圖v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v8第4頁(yè),共155頁(yè)，2024年2月25日，星期天路與回路

給出D中的一個(gè)點(diǎn)、弧交替序列如果這個(gè)序列在基礎(chǔ)圖G(D)中所對(duì)應(yīng)的點(diǎn)、邊序列是一條鏈，則稱這個(gè)點(diǎn)、弧交替序列是D的一條鏈。類(lèi)似定義圈和初等鏈(圈)。如果是D的一條鏈，并且對(duì)t=1,2,…,k-1，均存在，稱之為從的一條路。若路的起點(diǎn)和終點(diǎn)相同，則稱之為回路。類(lèi)似定義初等路(回路)?！?,i1v,i1v,i1a,i2v,v,i2aik-1v,ik-1a,ikv…,,i1v,i1v,i1a,i2v,v,i2aik-1v,ik-1a,ikv()it+1v,itvi1a=()ikvi1v到第5頁(yè),共155頁(yè)，2024年2月25日，星期天8.4.2最短路問(wèn)題

給定一個(gè)賦權(quán)有向圖，

即給了一個(gè)有向圖D=(V,A)，對(duì)每一條弧a=(vi,vj)，相應(yīng)地有權(quán)w(a)=wij。又給定D中的兩個(gè)頂點(diǎn)vs,vt

，設(shè)P是D中從vs到vt的一條路，定義路P的權(quán)是P中所有弧的權(quán)之和，記為w(P)。最短路問(wèn)題就是要在所有從vs到vt的路中求一條權(quán)最小的路P0，路P0的權(quán)稱為從vs到vt的距離，記為d=(vs,vt)。第6頁(yè),共155頁(yè)，2024年2月25日，星期天引例v1v2v3v4v5v6v7235195733862已知如下圖所示的單行線交通網(wǎng)，第7頁(yè),共155頁(yè)，2024年2月25日，星期天設(shè)有向圖D=(V,A)，若D中的一條路是一條從的最短路，則其中任一條子路

,(r=1~k-1,s=2~k)

是從的最短路（最短路的子路必是最短路）。k1iiP…,,i1v,i1v,i2vikv=

()ikvi1v到最短路性質(zhì)ir+1v,sriiP…,,v,irisv=

()is-1v,isvirv到i1vir+1vi2virvisvikvis-1vik-1v第8頁(yè),共155頁(yè)，2024年2月25日，星期天8.4.3最短路算法第9頁(yè),共155頁(yè)，2024年2月25日，星期天Dijkstra算法適用條件：弧a=(vi,vj)的權(quán)wij≥0的賦權(quán)有向圖，邊e=[vi,vj]的權(quán)wij≥0的賦權(quán)無(wú)向圖。在這種情況下，圖中任一條路的權(quán)不小于其子路的權(quán)。求解特點(diǎn)：可以求得某點(diǎn)到其他各點(diǎn)的最短路。求解技術(shù)：圖的收縮。第10頁(yè),共155頁(yè)，2024年2月25日，星期天引例v1v2v3v4v5v6v7235195833862第11頁(yè),共155頁(yè)，2024年2月25日，星期天算法的要點(diǎn)v1v2v3v4v5v6v7235195833862v1v3v4v5v6v711,v24,v2351583386第12頁(yè),共155頁(yè)，2024年2月25日，星期天v1v3v4v5v6v711,v24,v2351583386第13頁(yè),共155頁(yè)，2024年2月25日，星期天v1v3v5v6v758338611,v24,v28,v4第14頁(yè),共155頁(yè)，2024年2月25日，星期天v1v5v6v738611,v28,v412,v37,v3第15頁(yè),共155頁(yè)，2024年2月25日，星期天v1v6v711,v212,v310,v515,v56第16頁(yè),共155頁(yè)，2024年2月25日，星期天v1v716,v615,v5第17頁(yè),共155頁(yè)，2024年2月25日，星期天路徑上溯v1v2v3v4v5v6v7235195733862第18頁(yè),共155頁(yè)，2024年2月25日，星期天Dijkstra算法的程序(i)令k=0,Sk=

,

T(vs)=0,

(vs)=0

,

對(duì)每一個(gè)vj=vs,令T(vj)=+￥,

(vj)=M，轉(zhuǎn)入(ii)。(ii)令T()=min{T(vj)|vj

Sk}。若T()<+￥

，則把的T標(biāo)號(hào)變?yōu)?/p>

P標(biāo)號(hào)P()=T()，令Sk+1=Sk

{}。若Sk=V，計(jì)算終止，d(vs,vj)=P(vj),vj

Sk。若Sk

V，令l=ik

，把k換成k+1，轉(zhuǎn)入(iii)。若T()=+￥

，計(jì)算終止。d(vs,vj)=P(vj),vj

Sk;d(vs,vj)=T(vj)=+￥

,vj

Sk。

(iii)考查每個(gè)使(vl,vj)

A并且vj

Sk的點(diǎn)vj，若T(vj)>P(vl)+wlj，則把T(vj)修改為P(vl)+wlj，把

(vj)修改為l，轉(zhuǎn)入(ii)。ikvvi

kvi

kvi

kvi

kvi

kvi

kvi

kvi

kv第19頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)(2,1)5,1￥,M￥,M3

,1￥,M路長(zhǎng)標(biāo)號(hào)路徑標(biāo)號(hào)P標(biāo)號(hào)T標(biāo)號(hào)第20頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)￥,M￥,M￥,M￥,M￥,M￥,M路長(zhǎng)標(biāo)號(hào)路徑標(biāo)號(hào)第21頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v72351958338620,0￥,M￥,M￥,M￥,M￥,M￥,Mv1v2v3v4v5v6v72351958338620,0￥,M￥,M￥,M￥,M￥,M￥,M(0,0)2,15,13,1第22頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)(2

,1)4,211,2￥

,M3,1￥,Mv1v2v3v4v5v6v7235195833862(0,0)2,15,1￥,M￥,M3

,1￥,M(2,1)8,4(3,1)4,211,2第23頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)11,2￥

,M(3,1)7,3v1v2v3v4v5v6v7235195833862(0,0)(2,1)4,211,2￥,M(3

,1)8

,4(7,3)(4,2)7,310,515,5第24頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)(10,5)15,5(3,1)(7,3)v1v2v3v4v5v6v7235195833862(0,0)(2,1)(4,2)10,515,5(3

,1)(7

,3)(10,5)(15,5)第25頁(yè),共155頁(yè)，2024年2月25日，星期天最小樹(shù)與最短路v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)(10,5)（15,5）(3,1)(7,3)v1v2v3v4v5v6v7235195833862(0,0)(2,1)(4,2)（10,5）（15,5）(3

,1)(7

,3)第26頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v72351958338620,0￥,M￥,M￥,M￥,M￥,M￥,M(0,0)2,13,15,1(0,0)(2,1)4,2(2,1)(3,1)8,4(3,1)11,2(4,2)(4,2)7,3(7,3)(7,3)10,515,5(10,5)(15,5)(10,5)(15,5)第27頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v72351958338620,0￥,M￥,M￥,M￥,M￥,M￥,Mv1v2v3v4v5v6v72351958338620,0￥,M￥,M￥,M￥,M￥,M￥,M(0,0)2,15,13,1第28頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)(2

,1)4,211,2￥

,M3,1￥,Mv1v2v3v4v5v6v7235195833862(0,0)2,15,1￥,M￥,M3

,1￥,M(2,1)8,4(3,1)4,211,2第29頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)11,2￥

,M(3,1)7,3v1v2v3v4v5v6v7235195833862(0,0)(2,1)4,211,2￥,M(3

,1)8

,4(7,3)(4,2)7,310,515,5第30頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)(10,5)15,5(3,1)(7,3)v1v2v3v4v5v6v7235195833862(0,0)(2,1)(4,2)10,515,5(3

,1)(7

,3)(10,5)(15,5)第31頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v72351958338620,0￥,M￥,M￥,M￥,M￥,M￥,M(0,0)2,13,15,1(0,0)(2,1)4,2(2,1)(3,1)8,4(3,1)11,2(4,2)(4,2)7,3(7,3)(7,3)10,515,5(10,5)(15,5)(10,5)(15,5)第32頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v72351958338620,0￥,M￥,M￥,M￥,M￥,M￥,M(0,0)2,13,15,1(0,0)(2,1)4,2(2,1)(3,1)8,4(3,1)11,2(4,2)(4,2)7,3(7,3)(7,3)10,515,5(10,5)(15,5)(10,5)(15,5)第33頁(yè),共155頁(yè)，2024年2月25日，星期天最小樹(shù)與最短路v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)(10,5)（15,5）(3,1)(7,3)(0,0)(2,1)(4,2)（10,5）（15,5）(3

,1)(7

,3)v1v2v3v4v5v6v7235195833862第34頁(yè),共155頁(yè)，2024年2月25日，星期天應(yīng)用舉例

例8.第35頁(yè),共155頁(yè)，2024年2月25日，星期天第36頁(yè),共155頁(yè)，2024年2月25日，星期天網(wǎng)絡(luò)模型的要素設(shè)置用點(diǎn)vi代表第i年年初i=1~6;用弧(vi

,

vi)表示第i年年初購(gòu)買(mǎi)一臺(tái)新設(shè)備用到第j年年初報(bào)廢j=(i+1)~n；用弧的權(quán)wij作為設(shè)備的購(gòu)置費(fèi)與維修費(fèi)之和如w13=c1+(d1+d2)=11+(5+6)=22wij=ci+j-it1?=dt第37頁(yè),共155頁(yè)，2024年2月25日，星期天設(shè)備更新問(wèn)題的網(wǎng)絡(luò)模型v1v2v3v4v5v6161617171822304159222330314123第38頁(yè),共155頁(yè)，2024年2月25日，星期天設(shè)備更新問(wèn)題的網(wǎng)絡(luò)模型v1v2v3v4v5v61616171718223041592223303141第39頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6161617171822304159222330314123第40頁(yè),共155頁(yè)，2024年2月25日，星期天第41頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v7v863822-111-26-1-1-3-2-5-31第42頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v7v8第43頁(yè),共155頁(yè)，2024年2月25日，星期天v1v2v3v4v5v6v7v8第44頁(yè),共155頁(yè)，2024年2月25日，星期天第45頁(yè),共155頁(yè)，2024年2月25日，星期天迭代算法d(vs,vj)=min{d

(vs,vi)+wij|i

V}(i)當(dāng)t=1，令

d(1)(vs,vj)=wsj,j

V(ii)對(duì)t=2,3,…,使

d(t)(vs,vj)=min{d(t-1)(vs,vi)+wij|i

V},j

V(iii)若

t=k，有

d(k)(vs,vj)=d(k-1)(vs,vj),j

V

則{d(k)(vs,vj)|j

V}即為vs到各點(diǎn)vj的最短路的權(quán)。第46頁(yè),共155頁(yè)，2024年2月25日，星期天wij算例第47頁(yè),共155頁(yè)，2024年2月25日，星期天wij算例第48頁(yè),共155頁(yè)，2024年2月25日，星期天wij算例第49頁(yè),共155頁(yè)，2024年2月25日，星期天最短路路徑v1v2v3v4v5v6v7v863822-111-26-1-1-3-2-5-31第50頁(yè),共155頁(yè)，2024年2月25日，星期天8.5網(wǎng)絡(luò)最大流問(wèn)題

在圖論的應(yīng)用中，特別是在交通運(yùn)輸、信息傳遞方面，網(wǎng)絡(luò)最大流問(wèn)題占有重要地位。這個(gè)問(wèn)題也是網(wǎng)絡(luò)理論的中心問(wèn)題之一。第51頁(yè),共155頁(yè)，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)運(yùn)輸網(wǎng)絡(luò)第52頁(yè),共155頁(yè)，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)8.5.1問(wèn)題的提出輸送量是否可以增加？輸送量究竟能增加到多大？第53頁(yè),共155頁(yè)，2024年2月25日，星期天8.5.2問(wèn)題的形式基本概念容量網(wǎng)絡(luò)網(wǎng)絡(luò)流及弧流量點(diǎn)的流量發(fā)點(diǎn)和收點(diǎn)帶發(fā)、收點(diǎn)的容量網(wǎng)絡(luò)可行流問(wèn)題的數(shù)學(xué)模型第54頁(yè),共155頁(yè)，2024年2月25日，星期天容量網(wǎng)絡(luò)

給定一個(gè)有向圖D=(V,A)，對(duì)D中每一條弧(vi,vj)

A

，賦一個(gè)非負(fù)的容量c(vi,vj)≥0(或簡(jiǎn)寫(xiě)為cij)，記C={cij}。D和C構(gòu)成的網(wǎng)絡(luò)稱為容量網(wǎng)絡(luò)，記作D=(V,A,C)。vsvtv2v4v1v3cs1=3cs2=6c12=5c24=4c41=1c13=5c43=2c3t=6c4t=3第55頁(yè),共155頁(yè)，2024年2月25日，星期天網(wǎng)絡(luò)流及弧流量

一個(gè)容量網(wǎng)絡(luò)D，給出一個(gè)運(yùn)輸方案，則D中每條弧(vi,vj)上的運(yùn)輸量叫作這條弧的弧流量，記作f(vi,vj)(簡(jiǎn)寫(xiě)為fij)，所有弧的弧流量組成的集合f={fij}稱為一個(gè)網(wǎng)絡(luò)流，簡(jiǎn)記為f。一個(gè)網(wǎng)絡(luò)流f表示容量網(wǎng)絡(luò)D

上一個(gè)運(yùn)輸方案。vsvtv2v4v1v3fs1=3fs2

=2

f12=2

f24=4

f41=1

f13=2f43=0

f3t

=2

f4t

=3

第56頁(yè),共155頁(yè)，2024年2月25日，星期天網(wǎng)絡(luò)流模型C={cs1=4,cs2=6,c12=5,…,c3t=6,c4t=3}f={fs1=3,fs2=2,f12=2,…,f3t=2,c4t=3}vsvtv2v4v1v3(cs1,fs1)(cs2,fs2)(c12,f12)(c24,f24)(c41,f41)(c13,f13)(c43,f43)(c3t,f3t

)(c4t,f4t

)第57頁(yè),共155頁(yè)，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)網(wǎng)絡(luò)流模型(算例)C={cs1=4,cs2=6,c12=5,…,c3t=6,c4t=3}f={fs1=3,fs2=2,f12=2,…,f3t=2,c4t=3}第58頁(yè),共155頁(yè)，2024年2月25日，星期天點(diǎn)的流量

以點(diǎn)vi作為起點(diǎn)的弧的集合記作(vi,V

)，這些弧的流量之和稱為點(diǎn)vi的流出量，記作f(vi,V

)，即

以點(diǎn)vi作為終點(diǎn)的弧的集合記作(V,vi),這些弧的流量之和稱為點(diǎn)vi的流入量，記作f(V,vi)，即

點(diǎn)vi的流出量與流入量之差稱為點(diǎn)vi的(凈)流量，即

f(vi,V

)-

f(V,vi)f(vi,V

)=fij?(vi,vj)?(vi,V

)

f(V,vi

)=fji?(vj,vi)?(V,

vi)

第59頁(yè),共155頁(yè)，2024年2月25日，星期天點(diǎn)的流量舉例(v1,V)={(v1,v2),(v1,v3)}(V,v1

)={(vs

,v1),(v4,v1)}點(diǎn)v1的流出量：f(v1,V)=f12+f13=2+2=4點(diǎn)v1的流入量：f(V,v1

)=fs1+f41=3+1=4點(diǎn)v1的(凈)流量：f(v1,V)-f(V,v1

)=4-4=

0vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)第60頁(yè),共155頁(yè)，2024年2月25日，星期天

發(fā)點(diǎn)和收點(diǎn)第61頁(yè),共155頁(yè)，2024年2月25日，星期天發(fā)點(diǎn)和收點(diǎn)舉例收點(diǎn)vt

:(vt

,V)=

,

(V,vt)

;f(vt

,V)=0,f(V,vt)

0.vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)發(fā)點(diǎn)vs

:(vs

,V)

,

(V,vs)=

;f(vs

,V)0,f(V,vs)=0.第62頁(yè),共155頁(yè)，2024年2月25日，星期天帶發(fā)、收點(diǎn)的容量網(wǎng)絡(luò)第63頁(yè),共155頁(yè)，2024年2月25日，星期天可行流

若網(wǎng)絡(luò)上的一個(gè)流f={fij}滿足下述條件：

(i)容量限制條件：對(duì)每條弧(vi,vj)

A

，

0≤

fij≤

cij

(ii)平衡條件：對(duì)每個(gè)中間點(diǎn)vi

A(i

s,t

)f(vi,V

)-

f(V,vi)=0

則f稱為一個(gè)可行流，而發(fā)點(diǎn)的流出量(或收點(diǎn)的流入量)稱為f的流量，記為v(f)或v

，即

v(f)=

f(vs,V

)

或

v(f)=

f(V,vt)第64頁(yè),共155頁(yè)，2024年2月25日，星期天最大流問(wèn)題的數(shù)學(xué)模型maxv(f)=

f(vs,V

)s.t.f(vi,V

)-

f(V,vi)=0(i

s,t

)0≤fij≤

cij

第65頁(yè),共155頁(yè)，2024年2月25日，星期天數(shù)學(xué)模型舉例maxv=fs1

+fs2s.t.f12+f13

-fs1-f41=0f24-fs2-f12=0f3t-f13-f43=0f41+f43+f4t

-f24=00≤

fij≤

cijvsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)第66頁(yè),共155頁(yè)，2024年2月25日，星期天最大流問(wèn)題與線性規(guī)劃問(wèn)題網(wǎng)絡(luò)最大流問(wèn)題平衡條件容量限制條件流量式可行流流的弧流量最大流最大流量中間點(diǎn)的個(gè)數(shù)弧的條數(shù)線性規(guī)劃問(wèn)題約束方程變量限制條件目標(biāo)函數(shù)可行解解的分量最優(yōu)解最優(yōu)值約束方程的個(gè)數(shù)變量的個(gè)數(shù)第67頁(yè),共155頁(yè)，2024年2月25日，星期天8.5.3問(wèn)題的求解第68頁(yè),共155頁(yè)，2024年2月25日，星期天1.求增廣鏈的標(biāo)號(hào)法第69頁(yè),共155頁(yè)，2024年2月25日，星期天飽和弧與零流弧

給出一個(gè)可行流f={fij}，按照弧流量與其上界或下界的關(guān)系，可將弧分類(lèi)：若fij=cij，則弧(vi

,vj

)稱為飽和?。环駝t，fij<cij，弧(vi

,vj

)稱為非飽和弧。若fij=0，則弧(vi

,vj

)稱為零流??；否則，fij

>0，弧(vi

,vj

)稱為非零流弧。

飽和弧必定是非零流弧，反之不然；零流弧必定是非飽和弧，反之不然。第70頁(yè),共155頁(yè)，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)飽和弧與零流弧舉例零流?。?v4,v3)非零流?。浩溆嗟幕★柡突。?v2,v4),(v4,v1),(v4,vt)非飽和弧:其余的弧第71頁(yè),共155頁(yè)，2024年2月25日，星期天前向弧與后向弧第72頁(yè),共155頁(yè)，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)前向弧與后向弧舉例

=(vs,v2,v1,v3,vt)

+={(vs,v2),(v1,v3),(v3,vt)}

-={(v1,v2)}第73頁(yè),共155頁(yè)，2024年2月25日，星期天增廣鏈

定義設(shè)f是一個(gè)可行流，

是從vs到vt的一條鏈，若滿足下述條件，稱之為(關(guān)于可行流f

的)一條增廣鏈。

+中每一條弧是非飽和?。?/p>

-中每一條弧是非零流弧。vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)第74頁(yè),共155頁(yè)，2024年2月25日，星期天可行流f={fij}的調(diào)整對(duì)于可行流f={fij}，若存在增廣鏈

，則可對(duì)f的弧流量fij作如下調(diào)整：確定調(diào)整量

，令

1=min{cij-

fij|(vi

,vj

)

+}

2=min{fij|(vi

,vj

)

-}

=min{

1,

2}調(diào)整弧流量fij，令

fij+

(vi

,vj

)

+fij-

(vi

,vj

)

-fij

(vi

,vj

)

fij′=第75頁(yè),共155頁(yè)，2024年2月25日，星期天可行流調(diào)整舉例可行流的增廣鏈

=(vs,v2,v1,v3,vt)

+={(vs,v2),(v1,v3), (v3,vt)}

-={(v1,v2)}確定調(diào)整量

，令

1=min{cs2

-

fs2,

c13

-

f13,

c3t-

f3t

}=min{6-2,5-2,6-2}=3

2=min{f12}=min{2

}=2

=min{3

,

2

}=2vsvtv2v4v1v3(4,3)(6,2+2)(5,2-2)(4,4)(1,1)(5,2+2

)(2,0)(6,2+2)(3,3)第76頁(yè),共155頁(yè)，2024年2月25日，星期天網(wǎng)絡(luò)流f′={fij′}的驗(yàn)證對(duì)于調(diào)整后的網(wǎng)絡(luò)流f′={fij′}，不難驗(yàn)證f′={fij′}是一個(gè)可行流v(f′)=v(f)+

>v(f)

fsl+

flm+

fnm-

fnt+

vsvlvmvnvt第77頁(yè),共155頁(yè)，2024年2月25日，星期天找增廣鏈的標(biāo)號(hào)法

對(duì)于可行流f={fij}，可用下述標(biāo)號(hào)找增廣鏈。

(0)首先給發(fā)點(diǎn)vs標(biāo)號(hào)“

0”。

(1)選取標(biāo)號(hào)無(wú)括號(hào)的點(diǎn)vi，如果這樣的點(diǎn)不存在，則沒(méi)有關(guān)于可行流f的增廣鏈；否則，轉(zhuǎn)(2)。

(2)檢查選取的點(diǎn)vi：

(i)對(duì)于所有以vi為起點(diǎn)的弧(vi

,vj

)，若fij<cij且終點(diǎn)vj

沒(méi)有標(biāo)號(hào)，則給vj標(biāo)號(hào)“+vi”；

(ii)對(duì)于所有以vi為終點(diǎn)的弧(vk,vi

)，若fki

>0且起點(diǎn)vk

沒(méi)有標(biāo)號(hào)，則給vk標(biāo)號(hào)“-vi”；

(iii)給點(diǎn)vi的標(biāo)號(hào)打上括號(hào)，轉(zhuǎn)(3)。

(3)若收點(diǎn)vs被標(biāo)號(hào)，則依據(jù)標(biāo)號(hào)采用“反向追蹤”的方法找出可行流f

的增廣鏈；否則，轉(zhuǎn)(1)。第78頁(yè),共155頁(yè)，2024年2月25日，星期天找增廣鏈的標(biāo)號(hào)法

對(duì)于可行流f={fij}，可用下述標(biāo)號(hào)找增廣鏈。

(0)首先給發(fā)點(diǎn)vs標(biāo)號(hào)“

0”。

(1)選取標(biāo)號(hào)無(wú)括號(hào)的點(diǎn)vi，如果這樣的點(diǎn)不存在，則沒(méi)有關(guān)于可行流f

的增廣鏈；否則，轉(zhuǎn)(2)。

(2)檢查選取的點(diǎn)vi：

(i)對(duì)于所有以vi為起點(diǎn)的弧(vi

,vj

)，若fij<cij且終點(diǎn)vj

沒(méi)有標(biāo)號(hào)，則給vj標(biāo)號(hào)“+vi”；

(ii)對(duì)于所有以vi為終點(diǎn)的弧(vk,vi

)，若fki

>0且起點(diǎn)vk

沒(méi)有標(biāo)號(hào)，則給vk標(biāo)號(hào)“-vi”；

(iii)給點(diǎn)vi的標(biāo)號(hào)打上括號(hào)，轉(zhuǎn)(3)。

(3)若收點(diǎn)vs被標(biāo)號(hào)，則依據(jù)標(biāo)號(hào)采用“反向追蹤”的方法找出可行流f

的增廣鏈；否則，轉(zhuǎn)(1)。第79頁(yè),共155頁(yè)，2024年2月25日，星期天0+vs+vs+v1-v1+v3標(biāo)號(hào)法找增廣鏈(正向標(biāo)號(hào))(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)vsvtv2v4v1v3第80頁(yè),共155頁(yè)，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)0+vs+vs+v1-v1+v3標(biāo)號(hào)法找增廣鏈(反向追蹤)第81頁(yè),共155頁(yè)，2024年2月25日，星期天0,+￥-v2,2+vs

,4+v1,2-v1,1+v3,2vsvtv2v4v1v3(4,4)(6,2)(5,2)(4,4)(1,1)(5,3)(2,0)(6,3)(3,3)標(biāo)號(hào)法找增廣鏈(之二)第82頁(yè),共155頁(yè)，2024年2月25日，星期天vsvtv2v4v1v3(4,4)(6,4)(5,0)(4,4)(1,1)(5,5)(2,0)(6,5)(3,3)0,+￥+vs

,2標(biāo)號(hào)法找增廣鏈(之三)第83頁(yè),共155頁(yè)，2024年2月25日，星期天2.最大流算法(Ford,Fulkerson)

步1

給出初始可行流f={fij}，(一般為零流，即fij=0)；

步2

用標(biāo)號(hào)法找當(dāng)前可行流f的增廣鏈

，若不存在關(guān)于f的增廣鏈

，則f為最大流，計(jì)算停止。否則，記

中的前向弧為

+、后向弧為

-；

步3

對(duì)當(dāng)前可行流f進(jìn)行調(diào)整，令

=min{min{cij-

fij|aij

+},

min{fij|aij

-}}

得到新的可行流f′={fij′

}(以f′代替f)，轉(zhuǎn)步2。

fij+

(vi

,vj

)

+fij-

(vi

,vj

)

-fij

(vi

,vj

)

fij′=第84頁(yè),共155頁(yè)，2024年2月25日，星期天11,012,06,06,03,06,09,05,03,08,0v4vsvtv1v6v3v2v50第85頁(yè),共155頁(yè)，2024年2月25日，星期天11,012,06,06,03,06,09,05,03,08,0v4vsvtv1v6v3v2v50,+￥+vs,12+vs,6+v1,11+v2,6+v2,6+v3,3+v4,61第86頁(yè),共155頁(yè)，2024年2月25日，星期天11,012,06,66,03,06,69,65,03,08,0v4vsvtv1v6v3v2v520,+￥+vs,12+v1,11+v3,8+v3,3+v4,3第87頁(yè),共155頁(yè)，2024年2月25日，星期天11,312,36,66,03,06,69,95,03,08,3v4vsvtv1v6v3v2v530,+￥+vs,9+v1,8+v3,5+v3,3+v6,3-v4,5第88頁(yè),共155頁(yè)，2024年2月25日，星期天11,612,66,66,03,36,69,95,33,08,3v4vsvtv1v6v3v2v50,+￥+vs,6+v1,5+v3,5+v5,3-v4,5+v2,54第89頁(yè),共155頁(yè)，2024年2月25日，星期天11,912,96,36,33,36,69,95,33,38,6v4vsvtv1v6v3v2v550,+￥+vs,3+v1,2+v3,2-v4,2第90頁(yè),共155頁(yè)，2024年2月25日，星期天8.5.4問(wèn)題的論證

截集與最大流

增廣鏈與最大流第91頁(yè),共155頁(yè)，2024年2月25日，星期天1.截集與最大流

設(shè)S

T=V,S

T=

，則S,T稱為V的一個(gè)剖分；并把始點(diǎn)在S中，終點(diǎn)在T中的所有弧的集合記為(S,T)。vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)ST第92頁(yè),共155頁(yè)，2024年2月25日，星期天截集

定義8.6對(duì)于容量網(wǎng)絡(luò)D=(V,A,C)，若D的點(diǎn)集V被剖分為兩個(gè)非空的子集Vk和Vk

，使vs

Vk,vt

Vk

，則把弧集(Vk,Vk

)稱為D

中(分離vs和vt)的截集。

vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)VkVk

第93頁(yè),共155頁(yè)，2024年2月25日，星期天必經(jīng)之道

定義8.6對(duì)于容量網(wǎng)絡(luò)D=(V,A,C)，若D的點(diǎn)集V被剖分為兩個(gè)非空的子集Vk和Vk，使vs

Vk，vt

Vk

，則把弧集(Vk,Vk

)稱為D

中(分離vs和vt)的截集。

vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)VkVk

第94頁(yè),共155頁(yè)，2024年2月25日，星期天第95頁(yè),共155頁(yè)，2024年2月25日，星期天截量

定義8.6對(duì)于截集(Vk,Vk

)，把截集(Vk,Vk

)中所有弧的容量之和稱為這個(gè)截集的容量(簡(jiǎn)稱為截量)，記為c(Vk,Vk

)，即相應(yīng)地，把截集(Vk,Vk

)中所有弧的流量之和記為f(Vk,Vk

)，即cij?(vi,vj)?(Vk,Vk

)c

(Vk,Vk

)=fij?(vi,vj)?(Vk,Vk

)f

(Vk,Vk

)=第96頁(yè),共155頁(yè)，2024年2月25日，星期天截集及其截量V1={vs

,v1

,v2},V1

={v3,v4

,vt

}(V1

,V1

)={(v1

,v3),(v2

,v4)}c(V1,V1

)=c13+c24=5+4=9f(V1,V1

)=f13+f24=2+4=6vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)第97頁(yè),共155頁(yè)，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)截集的分劃V1={vs

,v1

,v2},V1

={v3,v4

,vt

}(V1

,V1

)={(v1

,v3),(v2

,v4)}c(V1,V1

)=c13+c24=5+4=9f(V1,V1

)=f13+f24=2+4=6第98頁(yè),共155頁(yè)，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)截集及其截量(二)V2={vs

,v1

,v2,v3},V2

={v4

,vt

}(V2

,V2

)={(v2

,v4),(v1

,v3)}c(V2,V2

)=c24+c3t=4+6=10f(V2,V2

)=f24+f3t=4+2=6第99頁(yè),共155頁(yè)，2024年2月25日，星期天截集的計(jì)數(shù)Cp-2?i=0ip-2第100頁(yè),共155頁(yè)，2024年2月25日，星期天vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)截集與反向弧V1={vs

,v1

,v2},V1

={v3,v4

,vt

}(V1

,V1

)={(v1

,v3),(v2

,v4)}(V1

,V1)={(v4

,v1)}c(V1

,V1)=f41=1第101頁(yè),共155頁(yè)，2024年2月25日，星期天流量與截量

定理8.6對(duì)于容量網(wǎng)絡(luò)D，設(shè)

f={fij}是任一可行流，(Vk,Vk

)是任一截集，則

v(f)

≤

c(Vk,Vk

)第102頁(yè),共155頁(yè)，2024年2月25日，星期天最大流與最小截集

推論8.6設(shè)f*={f*ij}是D上的一個(gè)可行流，(Vk*,Vk

*)是一個(gè)截集，若

v(f*)

=

c(Vk*,Vk

*)

則f*是最大流，而(Vk*,Vk

*)是最小截集。第103頁(yè),共155頁(yè)，2024年2月25日，星期天2.增廣鏈與最大流

定理8.6可行流f*是最大流的充分必要條件是，不存在關(guān)于f*的增廣鏈。第104頁(yè),共155頁(yè)，2024年2月25日，星期天最大流量與最小截集量第105頁(yè),共155頁(yè)，2024年2月25日，星期天截集及其截量V1={vs

,v1

,v2},V1

={v3,v4

,vt

}(V1

,V1

)={(v1

,v3),(v2

,v4)}c(V1,V1

)=c13+c24=5+4=9f(V1,V1

)=f13+f24=2+4=6vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)第106頁(yè),共155頁(yè)，2024年2月25日，星期天8.5.5網(wǎng)絡(luò)等價(jià)變換第107頁(yè),共155頁(yè)，2024年2月25日，星期天1.無(wú)向網(wǎng)絡(luò)vivjc(vi,vj)vivjcij=c(vi,vj)

cji

=c(vi,vj)

第108頁(yè),共155頁(yè)，2024年2月25日，星期天2.頂點(diǎn)具有容量vic(vi)vi’vi”c(vi’,vi”)=

c(vi)第109頁(yè),共155頁(yè)，2024年2月25日，星期天多個(gè)源或匯vsvtvs1vs2vt1vt2vt3+￥+￥+￥+￥+￥第110頁(yè),共155頁(yè)，2024年2月25日，星期天作業(yè)

求網(wǎng)絡(luò)D的最大流和最小截集。1312629436582v5vsvtv2v3v4v1v6第111頁(yè),共155頁(yè)，2024年2月25日，星期天8.6最小費(fèi)用最大流問(wèn)題bs1

,cs1vsvtv1v2v3b23

,c23bs2

,cs2b21

,c21b13

,c13b1t,c1tb3t

,c3t第112頁(yè),共155頁(yè)，2024年2月25日，星期天vsvtv1v2v34

,103

,101

,82,56

,21,72

,4vsvtv1v2v34

,103

,101

,82,56

,21,72

,44

,103

,101

,82,56

,21,72

,4vsvtv1v2v3第113頁(yè),共155頁(yè)，2024年2月25日，星期天vsvtv1v2v3431-2612vsvtv1v2v34

,103

,101

,82,56

,21