管理運(yùn)籌學(xué)第七章網(wǎng)絡(luò)優(yōu)化模型

管理運(yùn)籌學(xué)第七章網(wǎng)絡(luò)優(yōu)化模型第1頁，共57頁，2023年，2月20日，星期二哥尼斯堡七橋問題ABDC簡捷表示事物之間的本質(zhì)聯(lián)系，歸納事物之間的一般規(guī)律ACDB第2頁，共57頁，2023年，2月20日，星期二在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來表示。(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e57.1圖與網(wǎng)絡(luò)的基本概念第3頁，共57頁，2023年，2月20日，星期二4

當(dāng)然圖論不僅僅是要描述對(duì)象之間關(guān)系，還要研究特定關(guān)系之間的內(nèi)在規(guī)律，一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的，如對(duì)趙等七人的相互認(rèn)識(shí)關(guān)系我們也可以用下圖來表示，可見圖論中的圖與幾何圖、工程圖是不一樣的。(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5第4頁，共57頁，2023年，2月20日，星期二5a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳

如果我們把上面例子中的“相互認(rèn)識(shí)”關(guān)系改為“認(rèn)識(shí)”的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入一個(gè)帶箭頭的聯(lián)線，稱為弧。圖11-3就是一個(gè)反映這七人“認(rèn)識(shí)”關(guān)系的圖。相互認(rèn)識(shí)用兩條反向的弧表示。第5頁，共57頁，2023年，2月20日，星期二7.1圖與網(wǎng)絡(luò)的基本概念7.1.1圖與網(wǎng)絡(luò)的概念及分類1、圖：圖由點(diǎn)和邊組成G=(V,E)點(diǎn)集V={vi}邊集E={ei}vjvie每一條邊和兩個(gè)端點(diǎn)關(guān)聯(lián)，一條邊可以用兩個(gè)端點(diǎn)表示（vi，vj）邊數(shù)：m(G)=|E|點(diǎn)數(shù)：n(G)=|V|

第6頁，共57頁，2023年，2月20日，星期二7.1圖與網(wǎng)絡(luò)的基本概念無向邊：有向邊：無向圖：由無向邊構(gòu)成的圖有向圖：由有向邊構(gòu)成的圖2、無向圖和有向圖第7頁，共57頁，2023年，2月20日，星期二7.1圖與網(wǎng)絡(luò)的基本概念3、簡單圖和多重圖環(huán)：e9

多重邊：e6和e7簡單圖：不含環(huán)和多重邊多重圖：含多重邊第8頁，共57頁，2023年，2月20日，星期二判斷下列哪些圖是簡單圖，哪些圖是多重圖？7.1圖與網(wǎng)絡(luò)的基本概念第9頁，共57頁，2023年，2月20日，星期二7.1圖與網(wǎng)絡(luò)的基本概念4、次：以點(diǎn)v為端點(diǎn)的邊數(shù)叫做點(diǎn)v的次，d(v)

奇點(diǎn)：次為奇數(shù) 偶點(diǎn)：次為偶數(shù)懸掛點(diǎn)：d(v)=1 孤立點(diǎn):d(v)=0定理7.1：任何圖，Σd(vi)=2m定理7.2：任何圖，奇點(diǎn)有偶數(shù)個(gè)第10頁，共57頁，2023年，2月20日，星期二7.1圖與網(wǎng)絡(luò)的基本概念出次d+(vi)

：有向圖中，以vi為始點(diǎn)的邊數(shù)入次d-(vi)

：有向圖中，以vi為終點(diǎn)的邊數(shù)Σd+(v)=Σd-(v)=m第11頁，共57頁，2023年，2月20日，星期二7.1圖與網(wǎng)絡(luò)的基本概念5、鏈、圈、路、回路、連通圖：鏈：無向圖G=（V,E）前后相繼的點(diǎn)邊序列稱為鏈初等鏈：點(diǎn)邊序列中沒有重復(fù)的點(diǎn)和重復(fù)邊的鏈稱為初等鏈(v1,e1,v2,e6,v4,e3,v3,e8,v5

)第12頁，共57頁，2023年，2月20日，星期二7.1圖與網(wǎng)絡(luò)的基本概念圈：無向圖G=（V,E）中起點(diǎn)和終點(diǎn)重合的鏈稱為圈初等圈：沒有重復(fù)點(diǎn)(除起點(diǎn)和終點(diǎn)外)和重復(fù)邊的圈稱為初等圈(v1,e1,v2,e6,v4,e3,v3,e5,v1

)第13頁，共57頁，2023年，2月20日，星期二7.1圖與網(wǎng)絡(luò)的基本概念對(duì)于有向圖來說，如果鏈和圈中邊的方向與有向圖中所標(biāo)方向相同，那么鏈就稱為道路，圈就稱為回路。連通圖：無向圖中，任意兩個(gè)點(diǎn)之間至少有一條鏈相連的圖稱為連通圖第14頁，共57頁，2023年，2月20日，星期二7.1圖與網(wǎng)絡(luò)的基本概念6、子圖與生成子圖：子圖：圖G=(V,E)，E’是E的子集，V’是V的子集，且E’的邊與V’的頂點(diǎn)想關(guān)聯(lián)，G’=(V’,E’)是圖G的一個(gè)子圖。生成子圖：若V’=V，則G’是G的生成子圖第15頁，共57頁，2023年，2月20日，星期二7.1圖與網(wǎng)絡(luò)的基本概念6、網(wǎng)絡(luò)：網(wǎng)絡(luò)（賦權(quán)圖）：由點(diǎn)、邊以及與點(diǎn)邊相關(guān)聯(lián)的權(quán)數(shù)所構(gòu)成的圖稱為網(wǎng)絡(luò)，記作N={V,E,W}v4v2v3v16215846v4v2v3v16215846無向網(wǎng)絡(luò) 有向網(wǎng)絡(luò)第16頁，共57頁，2023年，2月20日，星期二7.1圖與網(wǎng)絡(luò)的基本概念7.1.2樹的概念及性質(zhì)1、樹（T）：無圈的連通圖稱為樹

樹葉

分枝點(diǎn)第17頁，共57頁，2023年，2月20日，星期二7.1圖與網(wǎng)絡(luò)的基本概念7.1.2樹的概念及性質(zhì)2、樹的性質(zhì)性質(zhì)7.1

樹中任意兩點(diǎn)之間有且只有一條鏈。性質(zhì)7.2

如圖G中任意兩點(diǎn)之間，有且只有一條鏈，則該圖G是一個(gè)樹。性質(zhì)7.3

一個(gè)樹，則m=n-1。性質(zhì)7.4

樹中任意兩個(gè)不相鄰的點(diǎn)之間增加一條邊，則形成唯一的圈。性質(zhì)7.5

一個(gè)樹如果去掉任何一條邊，該圖就不再連通。第18頁，共57頁，2023年，2月20日，星期二7.1圖與網(wǎng)絡(luò)的基本概念7.1.2樹的概念及性質(zhì)3、圖的生成樹生成樹（支撐樹）：圖G的生成子圖是一棵樹，則稱該樹為G的生成樹圖G中屬于生成樹的邊稱為樹枝，不屬于生成樹的邊稱為弦定理7.3：圖G=（V,E）,有生成樹的充分必要條件為G是連通圖第19頁，共57頁，2023年，2月20日，星期二4、最小生成樹：圖G=(V，E)的生成樹所有樹枝上的權(quán)數(shù)的總和,稱為生成樹的權(quán)。權(quán)數(shù)最小的生成樹稱為最小生成樹。尋找最小生成樹的方法：避圈法、破圈法最小生成樹權(quán)=11第20頁，共57頁，2023年，2月20日，星期二5、根樹有向樹：若一個(gè)有向圖在不考慮邊的方向時(shí)是一棵樹，則稱這個(gè)有向圖為有向樹。根樹：有向樹T，恰有一個(gè)結(jié)點(diǎn)入次d-(vi)=0，其余各點(diǎn)入次d-(vi)=1，則稱T為根樹根樹中入次d-(vi)=0的點(diǎn)稱為根出次d+(vi)=0稱為葉其他點(diǎn)稱為分枝點(diǎn)7.1圖與網(wǎng)絡(luò)的基本概念第21頁，共57頁，2023年，2月20日，星期二在根樹中，若每個(gè)頂點(diǎn)的出次d-(vi)≤m，稱這棵樹為m叉樹。若每個(gè)頂點(diǎn)的出次d-(vi)=m或0，則稱這棵樹為完全m叉樹7.1圖與網(wǎng)絡(luò)的基本概念第22頁，共57頁，2023年，2月20日，星期二v2v3v7v1v8v4v5v66134105275934682求從v1到v8的最短路徑標(biāo)號(hào)：T標(biāo)號(hào)（試探性標(biāo)號(hào)）

P標(biāo)號(hào)（永久性標(biāo)號(hào)）1、狄克斯托算法（Dijkstra）:標(biāo)號(hào)法7.2最短路問題第23頁，共57頁，2023年，2月20日，星期二V2V3V7V1V8V4V5V66134105275934682S={v1}P(v1)=0,T(vi)=∞T(v2)=2,T(v4)=1,T(v6)=3min{T(v2),T(v4),T(v6)}=min{2，1，3}=1P(v4)

=1S={v1,v4}P(v1)=0L12=2L14=1L16=3P(v4)=1第24頁，共57頁，2023年，2月20日，星期二v2v3v7v1v8v4v5v66134105275934682S={v1,v4}P(v2)

=2P(v1)=0P(v4)=1T(v2)=2T(v6)=3T(v7)=3min{T(v2),T(v6),T(v7)}=min{2，3，3}=2P(v2)

=2S={v1,v4,v2}L12=2L16=3L42=11L47=3第25頁，共57頁，2023年，2月20日，星期二v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2}P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2L16=3L47=3L23=8L25=7T(v6)=3T(v7)=3T(v3)=8T(v5)=7min{T(v6),T(v7),T(v3),T(v5)}=min{3,

3,8,7}=3P(v6)

=3S={v1,v4,v2,v6}第26頁，共57頁，2023年，2月20日，星期二v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2,v6}P(v7)

=3P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2L47=3L23=8L25=7L67=7T(v7)=3T(v3)=8T(v5)=7min{T(v7),T(v3),T(v5)}=min{3,8,7}=3P(v7)

=3S={v1,v4,v2,v6,v7}第27頁，共57頁，2023年，2月20日，星期二v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2,v6,v7}P(v5)

=6P(v7)

=3P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2L23=8L25=7L75=6L78=11T(v3)=8T(v5)=6T(v8)=11min{T(v3),T(v5),T(v8)}=min{8,6,11}=6P(v5)

=6S={v1,v4,v2,v6,v7,v5}第28頁，共57頁，2023年，2月20日，星期二v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2,v6,v7,v5}P(v3)

=8P(v5)

=6P(v7)

=3P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2L23=8L53=15L58=10L78=11T(v3)=8T(v8)=10min{T(v3),T(v8)}=min{8,10}=8P(v3)

=8S={v1,v4,v2,v6,v7,

v5,

v3}第29頁，共57頁，2023年，2月20日，星期二v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2,v6,v7,

v5,

v3}P(v8)

=10P(v3)

=8P(v5)

=6P(v7)

=3P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2L38=14L58=10L78=11T(v8)=10P(v8)

=10S={v1,v4,v2,v6,v7,

v5,

v3,v8}第30頁，共57頁，2023年，2月20日，星期二v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2,v6,v7,

v5,

v3,v8}v1到v8的最短路徑為{v1,v4,v7,

v5,

v8}，長度為10P(v8)

=10P(v3)

=8P(v5)

=6P(v7)

=3P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2第31頁，共57頁，2023年，2月20日，星期二狄克斯托算法（Dijkstra）的適用條件：1、用于賦權(quán)有向圖。對(duì)于賦權(quán)無向圖的處理2、權(quán)數(shù)wij

≥0第32頁，共57頁，2023年，2月20日，星期二2、逐次逼近算法可用于網(wǎng)絡(luò)中有權(quán)數(shù)為負(fù)數(shù)的邊7.2最短路問題第33頁，共57頁，2023年，2月20日，星期二7.2最短路問題第34頁，共57頁，2023年，2月20日，星期二v1v3v4v2v5vtvsww6243743179887.3最大流問題第35頁，共57頁，2023年，2月20日，星期二1、流量和容量有向連通圖G=(V，E),G的每條邊（vi，vj）上有非負(fù)數(shù)cij稱為邊的容量，僅有一個(gè)入次為0的點(diǎn)vs稱為發(fā)點(diǎn)，一個(gè)出次為0的點(diǎn)vt稱為收點(diǎn)，其余點(diǎn)為中間點(diǎn)，這樣的網(wǎng)絡(luò)G稱為容量網(wǎng)絡(luò)，記為G=（V,E,C）。7.3.1基本概念7.3最大流問題第36頁，共57頁，2023年，2月20日，星期二2、可行流和最大流可行流必須滿足的兩個(gè)條件 （1）容量限定條件：0≤fij≤cij

（2）流量守恒條件：中間點(diǎn)的流入量等于流出量7.3最大流問題第37頁，共57頁，2023年，2月20日，星期二vjvifij=5cij=5飽和邊、不飽和邊、流量間隙(剩余流量)（vi，vj）是飽和的2、如果fij<cij，流從vi到vj的方向是不飽和的(vi，vj)是不飽和的間隙為δ12=c12-f12=5–3=21、如果cij=fij，流從vi到vj的方向是飽和的vjvifij=3cij=53、增廣鏈第38頁，共57頁，2023年，2月20日，星期二容量網(wǎng)絡(luò)G，若u為網(wǎng)絡(luò)中從vs到vt的一條鏈，u上的邊與u同向的稱為前向邊，與u反向的稱為后向邊給定一個(gè)G的一個(gè)可行流，u如果滿足：則稱u為從vs到vt的增廣鏈。定理7.4

可行流f是最大流的充要條件是不存在從vs到vt的可增廣鏈。7.3最大流問題第39頁，共57頁，2023年，2月20日，星期二v1v3v4v2v5vtvsww6243743179884、割集S=(vs,v3)=(v1,v2,v4,v5,vt)為G的割集割集E’的容量=14v1v3v4v2v5vtvsww624374317988其中S=(vs,v1,v3,v4)=(v2,v5,vt)為G的割集(vs,v1),(v3,v4),(v3,v5)的容量和為割集E’的容量=13第40頁，共57頁，2023年，2月20日，星期二其中容量最小的割集稱為網(wǎng)絡(luò)G的最小割集(最小割)定理7.5：（流量—割集定理）設(shè)f為網(wǎng)絡(luò)G=（V,E,C）的任一可行流，S是任一割集，則有W(f)≤定理7.6：(最大流-最小割定理)任一個(gè)網(wǎng)絡(luò)G中，從vi到vj的最大流的流量等于分離vi，vj的最小割的容量7.3最大流問題第41頁，共57頁，2023年，2月20日，星期二vsv2v3v1v4v5vtv6(5,0)(3,0)(4,0)(3,0)(2,0)(5,0)(3,0)(4,0)(5,0)(3,0)(2,0)ff7.3.2最大流算法7.3最大流問題第42頁，共57頁，2023年，2月20日，星期二vsv2v3v1v4v5vtv6(5,0)(3,0)(4,0)(3,0)(2,0)(5,0)(3,0)(4,0)(5,0)(3,0)(2,0)ff解：從零流開始，尋找增廣鏈vs→v1→v4→vt

最小容量min{5，5，4}=4(5,4)(5,4)(4,4)vs→v1→v5→vt

最小容量min{1，3，3}=1(5,5)(3,1)(3,1)vs→v2→v5→vt

最小容量min{4，3，2}=2(4,2)(3,2)(3,3)vs→v2→v6→vt

最小容量min{2，2，5}=2(4,4)(2,2)(5,2)vs→v3→v6→vt

最小容量min{3，2，3}=2(3,2)(2,2)(5,4)∴網(wǎng)絡(luò)最大流量=11，流量安排如上圖第43頁，共57頁，2023年，2月20日，星期二vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)從任一可行流開始尋找最大流，采用標(biāo)號(hào)法尋找增廣鏈(,+∞)解：先給發(fā)點(diǎn)標(biāo)號(hào)，即：vs標(biāo)（，+∞

）第44頁，共57頁，2023年，2月20日，星期二(vs，v1)fs1=cs1=5(vs，v2)

fs2=2<cs2=4δs2=2

所以給v2標(biāo)號(hào)(+vs，2)(vs，v3)

fs3=2<cs3=3δs3=1

所以給v3標(biāo)號(hào)(+vs，1)vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(,+∞)(+vs,2)(+vs,1)第45頁，共57頁，2023年，2月20日，星期二(v2，v5)f25=0<c25=3δ25=min[3,2]

所以給v5標(biāo)號(hào)(+v2，2)(v2，v6)

f26=2=c26(v3，v6)

f36=2=c36vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(,+∞)(+vs,2)(+vs,1)(+v2,2)第46頁，共57頁，2023年，2月20日，星期二(v5，vt)f5t=3=c5t(v5，v1)

f15=3>0δ51=min[3,2]=2

所以給v1標(biāo)號(hào)(-v5，2)vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(,+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)第47頁，共57頁，2023年，2月20日，星期二(v1，v4)f14=2<c24=5δ51=min[3,2]=2

所以給v2標(biāo)號(hào)(+v1，2)vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(,+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)第48頁，共57頁，2023年，2月20日，星期二(v4，vt)f4t=2<c4t=4δ4t=min[2,2]=2

所以給vt標(biāo)號(hào)(+v4，2)vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(,+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)(+v4,2)第49頁，共57頁，2023年，2月20日，星期二存在一條從vs到vt的可增廣鏈δ=2調(diào)整流量vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(,+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)(+v4,2)(4,4)(3,2)(3,1)(5,4)(4,4)第50頁，共57頁，2023年，2月20日，星期二(vs，v1)fs1=cs1=5(vs，v2)

fs2=4=cs2=4(vs，v3)

fs3=2<cs3=3δs3=1

所以給v3標(biāo)號(hào)(+vs，1)vsv2v3v1v4v5vtv6(5,5)(3,2)(4,4)(3,2)(2,2)(5,4)(3,3)(4,4)(5,4)(3,1)(2,2)(,+∞)(+vs,1)第51頁，共57頁，2023年，2月20日，星期二(v3，v6)fs1=c