第十章網絡規劃組合優化理論

CombinatorialOptimizationTheory第十章網絡規劃我們生活在一個網絡世界中，從某種意義上說現代社會是一個由計算機信息網絡、電話通訊網絡、運輸服務網絡、能源和物質分派網絡等各種網絡所組成的復雜的網絡系統.網絡規劃就是研究如何有效地計劃、管理和控制這個網絡系統，使之發揮最大的社會和經濟效益

.

由于圖的結構的直觀性，運用圖論的方法更有助于我們分析問題、描述問題、解決問題

.

網絡規劃是運籌學（組合優化）的一個經典又重要分支，所研究的問題涉及經濟管理、工業工程、交通運輸、計算機科學與信息技術、通訊與網絡技術等諸多領域.第十章網絡規劃§1最小生成樹問題§2最短路問題§3最大流問題§4中國郵遞員問題§0圖的基本概念第十章網絡規劃§0圖的基本概念Example1七橋問題

18世紀的德國有個哥尼斯堡城，在流貫全城的普雷爾河兩岸和河中兩個島之間架設了七座橋，把河的兩岸和兩島連接起來，能否有這樣一種走法，它通過每座橋一次且僅一次.該問題由Euler在1736年解決ABCD則七橋問題就成為無向圖中是否存在通過每一邊一次且僅一次的路（即一筆畫）問題.§0圖的基本概念Example2人、狼、羊、菜渡河問題

一個擺渡人希望用一條小船把一只狼、一頭羊和一籃白菜從一條河的南岸渡到北岸去，而船小只能容納人、狼、羊、菜中的兩個，決不能在無人看守的情況下，留下狼和羊在一起或羊和白菜在一起，應怎樣渡河才能將狼、羊、白菜都運過河？狀態轉移問題人狼羊菜FWGC

考慮渡河過程中河南岸的變化情況，最初的狀態是人、狼、羊、菜，最終狀態成空狀態，中間的狀態為人、狼、羊、菜的不同組合

.共有16種狀態，但有6種狀態是不允許的，如狼、羊、菜等.FWGCFWGOFWCFGCFGWCWGC

則渡河問題歸結為尋找從頂點“FWGC”到頂點“O”的路線.

第十章網絡規劃Definition

圖：有序三元組G=(V，E，R)稱為一個圖，其中GraphVertexEdge①V={v1，v2,…，vn}是有窮非空集，稱為頂點集；②E

稱為邊集，其中的元素叫做邊；③

R

是從邊集E

到V中的有序或無序的元素偶對應的集合的映射，稱為關聯函數

.關系Relation無向圖：在圖G=(V，E)中，圖簡記為G=（V，E）與V中的無序偶對應的邊e,稱為圖G的無向邊，每條邊都是無向邊的圖，稱為無向圖

.v1v3v4v5v2e1e8e7e6e5e4e3e2§0圖的基本概念

E

中任一條邊e若連接頂點u

和v

，則記為

e=(u，v),并稱u

與v為無向邊的兩個端點；邊e與頂點u

及v

關聯，頂點u

與頂點v

相鄰

.與同一個頂點關聯的若干條邊稱為是相鄰的

.若e=(vi

,vj)簡記為eij自環：兩個端點重合為一個頂點的邊；平行邊：關聯于同一對頂點的兩條邊；沒有自環和平行邊的圖；簡單圖：完備圖：任兩個頂點之間恰有一條邊相關聯；v1v3v4v2e1e5e6e2e4e3子圖：

設G=(V,E)，G1=(V1,E1)都是圖，且V1

V,

E1

E,則稱圖G1

為圖G的子圖；v1v3v4v2e1e3e4e2e5e6v1v3v4v2e1e3e4e2e5e6Note:是圖第十章網絡規劃生成(支撐)子圖：若圖G1

是圖G的子圖，且V1=V，則稱G1

是G的生成子圖；鏈（道路）：圖G中一個由頂點和邊交錯而成的非空有限序列：W=v0e1v1e2…ekvk，ei

∈E，i=1,2,…,k，vj

∈V，j=0,1,2,…,k,且ei

=(vi-1，vi),則稱W

是G的一條鏈（道路）；v0、vk

稱為W

的起終點，k為路長；初等鏈：各頂點相異的鏈；回路：起點與終點重合的鏈；圈：起點與終點重合的初等鏈；§0圖的基本概念連通圖：圖G中任意兩點u和v存在一條鏈；線度：與頂點v關聯的邊數(環算兩次)稱為v的線度;記為

d(v).v1v3v4v5v2e1e8e7e6e5e4e3e2d(v2)=3，d(v3)=4割邊：若去掉邊e

將使連通圖G不再連通，則稱e為G的割邊；有向圖：在圖G=(V，E)中，與V中的有序偶對應的邊e,稱為圖G的有向邊（弧），每條邊都是有向邊的圖，稱為有向圖

.記為G=(Ｖ，Ａ)Arc對有向圖有類似無向圖的概念，如

d+(vi)，d-(vi).賦(加)權圖：圖G的每條邊

e=(vi，vj)與一實數

w(e)=wij

對應.w(e)=wij

稱為邊e

的權

.割集：邊的集合，從連通圖

G中移去這些邊，則G

不連通，且不存在這些邊的真子集使圖不連通.

記為v1v3v4v5v2e1e8e7e6e5e4e3e2S為一個連通分支的頂點集.圖的矩陣表示：第十章網絡規劃關聯矩陣：

對無向圖G=(V,E)，其中V={v1,…,vn},

E={e1,e2,…,em}.構造n×m

矩陣A=(aij)n×m

其中則稱矩陣A是圖G的關聯矩陣.v1v3v4v5v2e1e8e7e6e5e4e3e2v5§0圖的基本概念鄰接矩陣：

對無向圖G=(V,E)，其中V={v1,…,vn},構造n×n

矩陣B=(bij)n×n

其中則稱矩陣B是圖G的鄰接矩陣.v1v3v4v5v2e1e8e7e6e5e4e3e2對稱矩陣對有向圖可類似定義關聯矩陣、鄰接矩陣

.Goback§1最小生成樹問題第十章網絡規劃Definition10.1一個無圈且連通的無向圖G稱為樹

.不連通,稱為森林樹通常記為

T.v1v3v4v5v2e1e5e4e3e2v5如群試問題(GroupTesting)設有25枚硬幣，已知其中一枚是假的且偏輕，問如何用天平稱最少的次數找到假幣？結論：3k個硬幣，只需稱k

次即可

.不知道假硬幣是偏輕還是偏重，如何？如12枚一、樹、生成樹§1最小生成樹問題關于樹有以下性質：v1v3v4v5v2e1e5e4e3e2v53、在樹T中，任意兩頂點間有且僅有一條道路；1、在樹T中，任意兩個不相鄰頂點加上一條邊，則恰好得到一個圈；2、在樹T

中，去掉任意一條邊,

則樹為不連通的；4、在樹T

中，頂點數比邊數多1.

如果樹T

是圖G的生成子圖，則稱T

是G的一棵生成（支撐）樹

.Definition10.2第十章網絡規劃Note:圖G的生成樹一般不是唯一的

.v1v3v2v4v1v3v2v4v1v3v2v4v1v3v2v4v1v3v2v4v1v3v2v4共有多少？16棵§1最小生成樹問題Example3擬建造一個連接若干城鎮的通訊網絡，已知城鎮vi，vj

之間直接拉線的造價為cij

，試設計一個總造價最小的通訊網絡

.如7個城鎮：v3v2v7v6v4v5v1112223344567顯然，該通訊網絡必須包含所有頂點，連通、無圈，且權和最小.生成子圖生成樹最小生成樹Definition10.3二、最小生成樹

若T

為G的生成樹，T

中的邊e記為e∈T，則T的權若T*為G的生成樹，且有則稱T*為G的最小生成樹.第十章網絡規劃Theorem10.1若T*

是圖G的生成樹，則它是最小生成樹的充要條件是對T*

外G的每一條邊加入T

*

中后形成的圈中，該邊權最大.Proof

Theorem10.2若T*

是圖G的生成樹，則它是最小生成樹的充要條件是對T*

中的任何一條邊,將該邊從T

*中刪去后形成的割集中，該邊權最小.證略v1v3v4v5v228641233圈最優條件割最優條件Theorem10.1的證明Proof:反證法設T*是最小生成樹，對T*

外G的任一條邊e

，加入T*中后形成的圈中，如果該邊的權不是最大，設最大邊為e*.此時，T

*+e–e*也是生成樹，但它的權比T*更小，這與T

*

是最小生成樹矛盾.

設T*是生成樹并滿足定理條件，但不是最小的.設最小生成樹為

T0，則T

*

中至少有一條邊

(i,j)T0,將(i,j)加入T0

后必產生一個圈，且圈上至少有一條邊

(k,l)T*,由定理條件wij≤wkl

,又T0為最小生成樹,所以,wij≥wkl,

于是

wij

=wkl

.因此,T0+(i,j)–(k,l)也是最小生成樹，并與T*有更多的公共邊，重復該過程,最后，可以將T0變為T*，因此，T*

是最小生成樹.§1最小生成樹問題三、求最小生成樹的算法

求最小生成樹的方法很多且很簡單，理論基礎主要是定理10.1（圈最優條件）、定理10.2（割最優條件）.A、避圈法1、Kruskal

算法（逐邊生成）

2、Prim算法（逐點生成）B、破圈法

1、Kruskal

算法（1956年）Step0把G的邊按權由小到大的順序排列，即w(e1)≤…≤w(em);令i=1，j=0，T=.Step1判斷T∪ei

是否含圈,Y

轉Step2,N

轉Step3.Step2令i=i+1.若i≤m

轉Step1;否則結束，此時G

不連通，所以沒有最小生成樹.Step3令T=T∪ei

，j=j+1.若j=n-1，結束，T

是最小生成樹；否則，轉Strp2.第十章網絡規劃Example4v3v2v7v6v4v5v1112223344567用Kruskal

算法求右圖的最小生成樹

.Solution:首先，對所有邊按權由小到大順序排列：(2,7)，(2,3).(1,7)，(4,5)，(5,7)，(1,6)，(4,7)，(1,2)，(3,7)，(3,4)(6,7)，(5,6)然后，按順序將這些邊加入T

中，如圖，得到最小生成樹

T

*，w(T

*)=14如何判斷T∪ei

含圈？通過增加一個標號給每個頂點一個互不相同的標號，不妨為頂點的下標.

當加入一條邊時,判斷兩個頂點的標號,若相同,則產生圈；否則，將與標號大的相同的標號均改為與標號小的相同的標號.3276451112223344567655§1最小生成樹問題在算法進行過程中，T

始終不含圈.因此算法結束時，若T含n-1條邊，則T

為生成樹；否則，原圖不連通，不存在生成樹.由于邊已按權由小到大排序，而不加入T

的邊，必為產生圈中的最大權邊，由定理10.1知，T

為生成樹則必為最小生成樹.這說明Kruskal

算法的正確性

.該算法始終試圖把權盡可能小的邊加到T

中，僅當加入后使T

不是樹才放棄，對邊的選取，不必瞻前顧后，只看眼前利益.這就是簡單且重要的貪婪算法（Greedy）.第十章網絡規劃2、Prim

算法（1957年）Step0Step1Step2令S=S∪{v2}，E0=E0

∪{e*},轉Strp1.設v

為G的任一頂點，令S={v}，E0=若S=V，結束，T=(S,E0)為最小生成樹；否則轉Step2.若，則G不連通，結束；

否則，設,其中v3v2v7v6v4v5v1112223344567Prim算法的正確性由定理10.2不難得到.§1最小生成樹問題3、破圈法（1967年）v3v2v7v6v4v5v1112223344567四、應用舉例最小生成樹的理論和計算，在很多工程或技術領域中得到應用.如要在若干城市之間架設通訊線路、鋪設公路鐵路或各種管道，要求總的線路長度最短，材料最省，成本最低等.在實際的應用中，又提出了最小生成樹問題的各種推廣，其中較典型的問題多是在可行解的結構上增加一些約束.第十章網絡規劃1、最大生成樹問題v3v2v7v6v4v5v1112223344567在最小生成樹上，v1至v4路的特點Example5設某工廠運輸一很重的設備，需由設備庫v1

運至施工現場v4，中間需經過一些橋梁（如圖），已知這些橋梁的堅固程度不同，經專家測定其安全系數如示，試問應如何安排運輸路線最安全？最大值最小v6v5v4施工現場v3v2v1設備庫0.40.40.80.30.30.80.50.20.3Solution:v6v5v4v3v1v20.80.30.40.40.80.50.30.30.2最大生成樹上的路是最小者最大.先求得最大生成樹，如圖所以，v1至v4的最安全的路線為v1v6v5v3v4最不安全處最安全最不安全處系數為0.4§1最小生成樹問題2、容量約束最小生成樹問題在遠程信息處理網絡的設計中涉及這樣的問題：已給一個無向圖G=(V，E),每條邊(vi

,vj)具有費用

w(vi

,vj)以及容量c(vi,vj)，一個頂點為信息接收站.尋求一個生成樹，使所有信息沿樹的邊送到接收站，滿足容量約束，即每邊上所傳的信息量不超過容量費用最且小.稱為容量約束的最小生成樹問題，是NP-C問題.第十章網絡規劃3、度數約束最小生成樹問題生成樹在計算機和通訊網絡中有許多應用，其中的大多數問題對某些頂點的度數有限制.如一個頂點代表一個中央計算設備，其他頂點代表終端，它們必須靠電纜與中央設備連接，若現在中央機的度數為b,這可保證計算機的負荷分散在b個端口，求中央機度數為b

的最小生成樹，使所用電纜盡可能少.

若只有一個頂點受約束，是一個P

問題

.§1最小生成樹問題1、Steiner

樹（在歐氏距離下）補充：Example6假設電話剛發明，郵電部的第一個任務是要使北京、上海、蘭州三個城市間有線路相通.你是總工程師，如何設計路線呢？當然線路越短越好，由最小生成樹：北京—蘭州、北京—上海

為最佳.北京蘭州上海真的沒辦法更短了嗎？鄭州但你的發現并沒有使舉世的科學家震動，因為這一事實早已被無數的數學書籍記載，這就是Steiner樹.你發現：北京—鄭州、上海—鄭州、蘭州—鄭州也滿足要求且總長度比最小生成樹更短

.

通過增加一些點（Steiner

點）使保存原來的所有點且連通，而總長度最短

.第十章網絡規劃v4v3v2v1如右圖：最小生成樹

zmin=31111但加上v5，則z

min=2=2.828問題：1、對于怎樣放置的n

個點，需要引進S–點；v1v3v2如：是不需要加點的.2、如何確定S–點的位置；3、引進幾個S–點最佳

.n=1、2是平凡的.n=3已解決，一般是NP-C

的

.Theorem10.3設有A、B、C

三點，若△ABC

的任一內角都小于120o

，則必存在內部一點P使PA、PB、PC的兩兩夾角均是120o，且此時

PA+PB+PC

＜△ABC

的任兩邊之和.不可能有另一點D比P的效果更好

.v5而當∠A≥120o

則z

min=AB+AC§1最小生成樹問題Theorem10.4三個點時，如何確定S

-點位置ABCS120o120oD能否再加點，使之更短呢？

對于n個點的網絡，至多可加入n–2個Steiner

點

.v4v3v2v11111v5最小生成樹

zmin=3但加上v5，則z

min=2=2.828120o120o此時，z

min=1+=2.732問：Steiner樹能使總長度比最小生成樹減少的最大比例是多少？

1968年兩位美國數學家提出該比例為13.4%的猜想，上世紀90年代初，被中國青年數學家堵丁柱解決，且方法很有價值.第十章網絡規劃2、擬陣（Matroid）問：怎樣的結構的組合優化問題可用Greedy

算法得到最優解？Definition10.4子集系統S=(E,l)是由有限集E及E

的一個子集族l

組成，在集合的包含關系下，l

是封閉的.l中的成員，稱為獨立集

.即若參照：E

為圖G的邊的集合，l是E

的無圈子集.關于子集系統S=(E,l)的組合優化問題是對每一個e∈

E

給定一個權w(e)≥0，求一個最大獨立集，使其權和最大（小）.Definition10.5設S=(E,l)是一子集系統，如果對S的任意兩個極大獨立集則稱S是擬陣.顯然，對G=(E,V),S=(E,l),l是無圈子圖，則S是擬陣.§1最小生成樹問題Theorem10.5

S是擬陣，則關于

S

的組合優化問題中每個例子，都可用Greedy算法得到最優解

.婚姻問題(matching)可以看成一個子集系統

S=(E,l),l—所有匹配，但不是擬陣.x3x1x2y2y1y3我們還學過其他擬陣結構嗎？

S=(E,l),E—一組向量l—所有線性無關子集，它是擬陣.

因為線性無關組的子集仍線性無關；極大線性無關組的所含向量個數相同.

則對每個向量加權，要求一個極大線性無關組，使其權和最大（小），可用Greedy

算法.Goback第十章網絡規劃§2最短路問題最短路問題是網絡優化中的一個相對基本而又非常重要的課題.許多網絡優化問題或者可以化為最短路問題，或者可用最短路的算法作為其子程序.如：通訊網絡中的最可靠路問題、物資的運輸路線、各種工藝路線的安排、廠區及貨場的布局、管道線網的鋪設以及設備的更新等問題都可化為最短路問題；而網絡流問題和中國郵遞員問題都要用最短路算法作為子程序.§2最短路問題設有向網絡D=(V,A,w)，其中弧(vi,vj)∈A對應的權wij

又稱為弧長或費用，對于其中的兩個頂點v1、vt

∈

V,以v1為起點vt

為終點的有向路稱為v1

vt

有向路P,其所經過的所有弧上的權之和為該有向路的權所有v1

vt

有向路中權和最小的一條稱為v1

vt

最短路P*.求最短路的方法的基本思想很樸素：設v1

vl

的最短路是v1…vi

vk…vl

,則v1

vk

的最短路是v1…vi

vk

第十章網絡規劃Example7利用前述思想求如下網絡中，v1

至v4的最短路.Solution:v1v2v3v4v5v6362423311從v1

逐步向外生長

目前v1

可達v2、v3

路長分別為6、3，這時求得了v1至v3

的最短路，長度為3.v1不可能通過其他頂點到達v3距離更短，因為wij

＞0再求v1或通過v3

可達的所有路的最短距離，v1v2;v1v3v2;v1v3v4路長分別為6、5、7.這時求得了v1至v2的最短路，路長為5.

再求

v1v3v2v4;v1v3v2v5;v1v3v4

路長分別為7、6、7.這時得v1

至v2的最短路,路長為5.這時求得v1至v4的最短路，路長為6.介紹了基本思想和方法，但有兩個需彌補的地方：1、計算量大O(n3);2、如何記錄最短路的走法.一、正費用網絡(wij＞0)§2最短路問題

1959年，Dijkstra

提出通過標號解決了上述問題.這是網絡規劃中常用手段該算法是目前公認的求正費用網絡最短路的較好的算法之一.基本如前（逐點生成），但在執行過程中，對未達到最短路的頂點，記錄目前v1

至該點的最短路長度.一旦有新的頂點被確定已達最短，則下一步其余（對未達到最短路的頂點）的頂點只需與它比較，來確定新的目前v1至這些點的最短路長度.ui

表示v1

至vi

的最短路長度；（是永久性的）t(vi)表示目前v1

至vi

的最短路長度；（是臨時性的）l(vi)表示v1

至vi

的目前最短路上vi

的前一個頂點的下標如：l(vi)=j

即v1…vj

vi第十章網絡規劃Dijkstr

算法（求v1至個頂點或至vh

的最短路）Step0令i=1,Si={v1},u1=0,l(v1)=0,對每個

令t1(vj)=M,l1(vj)=M

(M

為充分大的正數)，k=1Step1如果Si=V(或k=h

即v1至vh的最短路)結束否則,轉

Step2Step2對每條從vk

出發的弧(vk,vj)∈A,ti+1(vj)=min{ti(vj),uk+wkj}若ti+1(vj)=ti(vj)，則li+1(vj)=li(vj),否則li+1(vj)=

kStep3令如果ti+1(vji)＜M則令Si+1=Si

∪{vji},k=ji,i=i+1轉Step2否則結束.

當算法結束時，如果vj

∈Si,則v1

可達vj,uj

表示v1至vj

的最短路的長度，且通過l(vj)，可得其最短路.如果,則vi至vj

不存在路.§2最短路問題Example8用Dijkstra

算法求如下網絡中，v1

至各頂點的最短路.v1v2v3v4v5v61624253117Solution:i=1,令S1={v1}u1=0,l(v1)=0,t1(v2)=t1(v3)=t1(v4)=t1(v5)=t1(v6)=Ml1(v2)=l1(v3)=l1(v4)=l1(v5)=l1(v6)=Mk=1t2(v2)=min{M,u1+6}=6l2(v2)=1t2(v3)=min{M,u1+3}=3l2(v3)=1t2(v4)=min{M,u1+M}=M

l2(v4)=Mt2(v5),t2(v6)均不變.所以，則u2=t2(v3)=3,l(v3)=1,S={v1,v3}k=2,i=2Goon過程可由如下表格給出，打“*”者為uj

.v1v2v3v4v5v610*0MMMMMMMMMM2613*1MMMMMM3614*3MM10345*4649456*49467*5ti(vj)

li(vj)ivj第十章網絡規劃二、一般費用網絡對于wij＜0的情形，Dijkstra

算法是行不通的

.如圖:v1v2v3-221v1v2v3-22-1在沒有負圈的情況下，v1

至多通過n-2頂點到達vj

,

與wij≥0不同，可逐點進入Si

，但在這里，目前是最短的但完全可能通過其它點會更短

.但求最短路方法的基本思想還是成立的：設v1

vl

的最短路是v1…vi

vk…vl

,則v1

vk

的最短路是v1…vi

vk

§2最短路問題想法是這樣，從步數著手，一步可達、兩步、三步，…，至多n-1步.即如下遞推公式：其中表示t步內v1

至vj

的最短路長度.為加快速度，可用已計算的替換.當進行到某一步，如第k

步，對所有的j=2,3,…,n

有則如果當k

＞n-1,仍不出現則網絡中含有負圈

.這算法是由Ford1956年給出

.第十章網絡規劃

Example9（道路矩陣）

設某小航空公司在

4城市間的航行運行圖如右圖，某記者從城市d

出發，（1）有幾條經

3次航行到達城市

c

的線路；（2）有幾條經

4次航行回到城市

d

的線路；Solution:考察圖的鄰接矩陣的冪表明從c出發經兩次航行到達b的線路有兩條所以，§2最短路問題

一般地，的值表示從城市

i到城市

j經兩次航行到達

j的線路數；若記，則

=從城市

i到城市

j經k次航行到達

j的線路數.

于是，從

d出發經

3次航行到達

c的線路數為條，

從

d出發經

4次航行回到

d的線路數為條

=從頂點

i

到頂點

j

經少于

k+1步到達

j的道路數

第十章網絡規劃

Example10用Ford算法求如下網絡中v1至各頂點的最短路

.v1v2v3v4v5v6-26-182-5311v7v821-5-3-3-17-1Solution:得鄰接矩陣定義

Ai

*Bj=……§2最短路問題v1v2v3v4v5v6-2682-5311v7v821-5-3-3-17-1v1v2v3v4v5v6v7v8t=10-1-23mmmmt=2t=3t=4定義

Ai

*Bj=0-5-2-71-15m0-5-2-76-1-5-30-5-2-76-1-5-3當t=3和t=4v1

至各頂點路長不變（步數增加也不會變）.此時，已得所求.-1第十章網絡規劃求網絡中所有頂點之間的最短路

.當然，可以通過n

次調用Ford算法來完成，但計算量為O(n2m).1962年Floyd-Warshall

提出的算法計算量為O(n3).

算法可用如下遞推公式表示：§2最短路問題Floyd-Warshall

算法Step0t=0,對于所有頂點vi,vj令Step1對于所有頂點vi,vj若令否則,令Step2如果t=n,則結束;否則令t=t+1轉Step1.第十章網絡規劃

Example11Solution:用Floyd-Warshall

算法求如下網絡中所有頂點之間的最短路

.v1v2v3v464-73105-3-36記最短路長度矩陣為U,最短路矩陣為

P初始值為第一次迭代后得到第二次迭代后得到§2最短路問題第三次迭代后得到第四次迭代后得到終點

v1v2v3v4

起點

v1(v1,v2)(v1,v3)(v1,v3)(v3,v4)v2(v2,v1)(v2,v3)(v2,v3)(v3,v4)v3(v3,v4)(v4,v2)(v2,v1)(v3,v4)(v4,v2)(v3,v4)v4(v4,v2)(v2,v1)(v4,v2)(v4,v2)(v2,v3)最短路長度可直接由U(5)得到,根據P(5)最后得到的最短路為第十章網絡規劃三、應用舉例

選址問題或設點問題是指為一個或幾個服務設施在一定區域內選定它的位置,使某一指標達到最優

.選址問題的數學模型依賴于設施可能的區域和評判位置優劣的標準,有許多不同種類的選址問題

.(1)中心問題對一些緊急服務型的設施(如急救中心、消防站等)，要求距網絡中最遠的被服務點距離盡可能小

.可以在點上、邊上、區域內§2最短路問題Example12

現準備在v1,v2,…,v7

七個居民點中設置醫院.各點之間的距離如圖,問設一個醫院在哪個居民點,可使最大服務距離為最小;若設兩個,問應設在哪兩個居民點?v1v2v3v4v5v662.531.81.5v721.534Solution:求出任意兩點的最短路長度,得矩陣D=(dij):稱

l(vi)為vi

的最大服務距離l(vi)取

min{l(v1),l(v2),…,l(v7)}=4.8=l(v6)所以,若設一個醫院,則設在居民點v6

處最好.第十章網絡規劃v1v2v3v4v5v662.531.81.5v721.534考察設置兩個醫院若設在v3,v6

那么對v1

來說,居民可以到v3

處看病,也可以在v6處看病,由d

知d13=5及d16=4.5,則v1

的居民自然選擇v6

處看病,其服務距離為4.5.依次找出居民點v2,…,v7

的服務距離,得:點

vjv1v2v3v4v5v6v7

d(vj,v3)520462.54

d(vj,v6)4.51.52.51.84.801.5服務距離4.51.501.84.801.5則設在v3,v6

的最大服務距離為4.8(記l(v3,v6)).求出任意對頂點的最大服務距離l(vi,vj)

由矩陣L

可知l(v2,v4)=l(v2,v5)=3為最小,故醫院設在v2

及v4

或v2

及v5.§2最短路問題(2)重心問題對一些服務型的設施(如郵局、學校、圖書館等)，要求設施到所有服務對象點的距離加權和最小.v1v2v3v4v5v662.531.81.5v721.534Example13

現準備在v1,v2,…,v7

七個居民點中設置超市.各點之間的距離如圖,問超市設在哪個居民點,可使全體被服務對象來往的加權和最小?q(vi)表示vi

居民數.Solution:1、求距離矩陣D=(dij);2、計算各頂點作為超市的加權和；3、求vk

使vk

稱為圖G的重心或中位點第十章網絡規劃Example14設備更新問題某企業使用一種設備，在每年年初企業要決定是否更行，若購置新設備，需支付購置費及使用費，若繼續使用舊設備，則需支付更多的使用費，問題是在保證有一臺設備在運行下，使得總的支付費用最少

.以下是一個五年計劃情況：年12345購置費1111121213年0-11-22-33-44-5使用費5681118Solution:v1v2v3v4v5v659

vi

表示第

i

年初，v6

為第五年末.

(vi,vj)表示第i年初購一臺設備使用至第j-1年末.4130221616223041172331172318問題轉化為求v1至v6的最短路.最優方案：第1、3年年初各購一臺新設備或第1、4年年初各購一臺新設備，總費用53.Goback第十章網絡規劃§3最大流問題最大流問題是以網絡中的流為研究對象，所謂網絡中的流其意義類似于在網絡中將一些“物質”從一個頂點沿弧發送到另一個頂點.許多系統包含了流量問題，如：交通系統有車輛流、金融系統有現金流、供水（供氣）系統有水（氣）流、控制系統有信息流、通訊系統中有電話通話流等等.最大流問題主要是確定這類系統網絡所能承受的最大流量以及如何達到這個最大流量

.§3最大流問題一、基本概念與定理Definition10.6給一個有向圖D=(V,A)，在V中指定了一點稱為發點(源),記為vs(沒有入弧)，另一個點稱為收點(匯),記為

vt

(沒有出弧)，其余的點稱為中間點.對于每一條弧(vi,vj)∈A，對應有一個c(vi,vj)≥0(簡記為cij

)，稱為弧的容量.則稱D為一個網絡記作D=(V,A,C).v1v2v3v4v5vsvt12364421326107在弧集A

上定義一個非負函數f={f(vi

,

vj)}，f(vi,vj)為弧(vi,vj)上的流量，簡記fij.稱f

是網絡上的流

.14134104113825顯然，這不可行Definition10.7

……vs1vt1vsvskvs2vt2vthvtmmmmmm本節的m是指足夠大的整數第十章網絡規劃v1v2v3v4v5vsvt1236442132610714134104113825滿足a、容量限制條件：對每一弧(vi,vj)∈A0≤fij≤cijb、平衡條件：對于中間點：對每個i(i≠s,t

)有Definition10.8的流f

，稱為可行流

.稱為f

的流值.用(cij,fij)表示弧(vi,vj)的容量和流量

.(12,5)(3,3)(6,4)(2,2)(4,2)(3,1)(6,3)(2,1)(1,1)(7,3)(10,5)(4,2)可驗證，這是一個可行流，v(f)=9.任何網絡可行流總是存在的，如fij=0對任意(vi,vj)∈A.§3最大流問題最大流問題：這是一個特殊的線性規劃問題，可用單純形法解，但在圖上可提出更簡潔、直觀的方法

.Definition10.9設D=(V,A,C)是一網絡，S

為V

的一個子集，

稱弧集

為網絡D的一個割集

.并稱為割集的容量.第十章網絡規劃v1v2v3v4v5vsvt(12,5)(3,3)(6,4)(2,2)(4,2)(3,1)(6,3)(2,1)(1,1)(7,3)(10,5)(4,2)顯然，網絡D的割集是不唯一的.

Svs

(vs,v1)(vs,v2)vs,v1(vs,v2)(v1,v2)(v1,v3)(v1,v4)vs,v2(vs,v1)(v2,v5)(v2,v3)vs,v1,v3

(vs,v2)(v1,v2)

(v1,v4)(v3,v4)(v3,v5)(v3,vt)vs,v1,v2,v3

(v1,v4)(v3,v4)(v3,v5)(v3,vt)(v2,v5)1815221914…………若則稱為最小割集.若把割集的弧全部從D中移去，則vs

至vt

的路就不存在了，即不能產生從vs

至vt

的流，故不難理解，D的任一流f

的流值.

(v1,v2)是割集中的弧嗎？§3最大流問題Definition6.8在網絡D=(V,A,C)中，若給定一個可行流f={fij

},稱滿足fij=cij

的弧為飽和弧；滿足0≤fij＜cij

的弧為非飽和弧；滿足fij=0的弧為零流弧;滿足0＜fij

≤cij

的弧為非零流弧

.v1v2v3v4v5vsvt(12,5)(3,3)(6,4)(2,2)(4,2)(3,1)(6,3)(2,1)(1,1)(7,3)(10,5)(4,2)vsv2v1v4vt(6,4)(3,1)(4,2)(10,5)不考慮方向,這是vs

至vt

的路,稱為vs

至vt

的鏈.與鏈方向一致的弧，稱為前向弧

l+;反之,稱為后向弧

l-.

一條弧是前向弧還是后向弧，取決于（相對于）鏈而言.可否增加流量?Definition10.10設f={fij}是網絡D=(V,A,C)上的一個可行流,l是從vs

到vt

的一條鏈,若l

滿足下列條件:(1)l

+

上的弧(vi,vj)，為非飽和弧；

(2)l

-

上的弧

(vi,vj)，為非零流弧

.

則稱l

是關于f

的一條增廣鏈

.能增加多少？第十章網絡規劃Theorem10.6在網絡D=(V,A,C)中，可行流f*={f*ij}是最大流的充分必要條件是D中不存在關于f*的增廣鏈

.ProofTheorem10.7

（最大流最小割定理）對于任意給定的網絡D={V,A,C},從vs

到vt

最大流的流量必等于最小割集的容量

.Theorem10.8

（整流定理）對于任意給定的網絡D={V,A,C},如果所有弧容量是整數，則一定存在整數最大流，即每條弧的流量都取整數值.Goon§3最大流問題Theorem10.6的證明Proof:用反證法.若f*是最大流，假設D中存在關于f*的增廣鏈l，令由增廣鏈的定義可知，令不難證明{f**}是可行流,且有這與f*是最大流的假設矛盾

.設流f={fij}不存在增廣鏈，令顯然,由S

的定義對一切有fij=cij

;fji=0vsv2v1v3v7(10,8)(3,3)(4,3)(2,0)(12,11)(8,8)即流的值等于割的容量.所以f為最大流.第十章網絡規劃二、最大流問題的算法上述定理實質給出了尋求最大流的一個方法，即1、從可行流出發；2、判別有無vs

到vt

的增廣鏈，若無則為最大流；若有，則在增廣鏈上增加流量（按定理10.6必要性證明），繼續.可行流沒問題，問題是如何判斷是否有增廣鏈，若有，鏈是怎樣的.根據定理10.6充分性證明中定義S

的方法，按vt

是否屬于S

來判斷D中有無關于f

的增廣鏈.vsv2v1v4vt(6,4)(3,1)(4,2)(10,5)可通過標號來實現.給頂點vi

以標號（±li,hi）li

:vi的前繼或后繼頂點的下標;hi:目前允許增加的流量.(0,m)(s,2)(-2,1)(1,1)(4,1)標號的作用：既給出了可增廣鏈的走向，有記錄了可增加的流量.若vt

被標號，則增廣鏈找到

.§3最大流問題標號算法（Ford-Fulkerson算法，1957）Step0求得D的一個可行整數流f,作為初始可行流；Step1求f

的增廣鏈：1.0

給vs

以標號(0,m)，并把該頂點標為未檢查；1.1

如果所有已標號頂點都已檢查，轉Step3；否則任取一個已標號未被檢查頂點vi

，檢查所有與vi

關聯、未給標號的頂點vj

：若(vi,vj)∈A，且fij<cij，令hj=min{cij

-fij,hi

}則給vj

以標號(i,hj)(或(+i,hj))，并標為未檢查；若(vj,vi)∈A，且fij>0，令hj=min{

fji,hi

}則給vj

以標號(-i,hj)，并標為未檢查；

當所有與vi

關聯、未給標號的頂點都已檢查，則令vi

為已檢查，轉

1.2.

第十章網絡規劃1.2

如果vt

得到標號，則已經找到一條f

的增廣鏈，轉Step2；否則轉1.1

；對f

增廣：Step22.0

取

vj=vt;2.1

若vj

的標號lj=0，即vj=vs

，增廣結束，取消D

中所有標號(除vs

的)，轉Step1，否則轉2.2;2.2

若lj=i,令fij:=fij+ht,vj=vi,轉

2.1;

若

lj

=-i,令fij:=fij-ht,vj=vi

,轉

2.1.Step3f是D中最大流.此時已標號頂點的集合記為S,則是D中最小割集

.§3最大流問題Example15用標號算法求如下網絡的最大流、最小割集

.v1v2v3v4v5vsvt(12,3)(2,2)(10,6)(2,2)(4,3)(3,2)(9,1)(8,1)(2,2)(10,6)(7,3)(3,3)Solution:已有一個流量為9的可行流,進行標號.v1v2v3v4v5vsvt(12,3)(2,2)(10,6)(2,2)(4,3)(3,2)(9,1)(8,1)(2,2)(10,6)(7,3)(3,3)(0,m)(s,9)(s,4)(1,1)(-4,1)能標號的都要標,選誰檢查是任意的(4,1)v1v2v3v4v5vs(12,3)(2,2)(10,6)(2,2)(4,3)(3,2)(9,1)(8,1)(2,2)(10,6)(7,3)(3,3)vt(7,4)(4,4)(12,4)(0,m)(s,8)(s,4)(2,4)(3,4)(5,4)v1v2v3v4v5vs(12,4)(2,2)(10,6)(2,2)(4,4)(3,2)(9,1)(8,1)(2,2)(10,6)(7,4)(3,3)vt(10,10)(8,5)(10,10)(9,5)(0,m)(s,8)(-1,2)(2,2)(3,2)(-5,2)(4,2)v1v2v3v4v5vs(12,4)(2,2)(10,10)(2,2)(4,4)(3,2)(9,5)(8,5)(2,2)(10,10)(7,4)(3,3)vt(7,6)(2,0)(8,7)(9,7)(3,0)(12,6)(0,m)(s,6)此時為最大流

v(fmax)=16最小割集為={(vs,v2),(v1,v3),(v1,v4)}第十章網絡規劃v1v2v3v4v5vs(k,0)vtv6(k,0)(k,0)(k,0)(k,0)(k,0)(k,0)(k,0)(1,0)v(fmax)=2k

(0,m