數(shù)學建模-第十章網(wǎng)絡規(guī)劃

1、 第十章第十章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃 Combinatorial Optimization Theory第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃 我們生活在一個網(wǎng)絡世界中，從某種意義上說現(xiàn)我們生活在一個網(wǎng)絡世界中，從某種意義上說現(xiàn)代社會是一個由計算機信息網(wǎng)絡、電話通訊網(wǎng)絡、運代社會是一個由計算機信息網(wǎng)絡、電話通訊網(wǎng)絡、運輸服務網(wǎng)絡、能源和物質(zhì)分派網(wǎng)絡等各種網(wǎng)絡所組成輸服務網(wǎng)絡、能源和物質(zhì)分派網(wǎng)絡等各種網(wǎng)絡所組成的復雜的網(wǎng)絡系統(tǒng)的復雜的網(wǎng)絡系統(tǒng). . 網(wǎng)絡規(guī)劃就是研究如何有效地計網(wǎng)絡規(guī)劃就是研究如何有效地計劃、管理和控制這個網(wǎng)絡系統(tǒng)，使之發(fā)揮最大的社會劃、管理和控制這個網(wǎng)絡系統(tǒng)，使之發(fā)揮最大的社會和經(jīng)濟效益和

2、經(jīng)濟效益 . 由于圖的結(jié)構(gòu)的直觀性，運用圖論的方法更有助由于圖的結(jié)構(gòu)的直觀性，運用圖論的方法更有助于我們分析問題、描述問題、解決問題于我們分析問題、描述問題、解決問題 . 網(wǎng)絡規(guī)劃是運籌學（組合優(yōu)化）的一個經(jīng)典又重網(wǎng)絡規(guī)劃是運籌學（組合優(yōu)化）的一個經(jīng)典又重要分支，所研究的問題涉及經(jīng)濟管理、工業(yè)工程、交要分支，所研究的問題涉及經(jīng)濟管理、工業(yè)工程、交通運輸、計算機科學與信息技術(shù)、通訊與網(wǎng)絡技術(shù)等通運輸、計算機科學與信息技術(shù)、通訊與網(wǎng)絡技術(shù)等諸多領域諸多領域 . .第十章第十章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃1 最小生成樹問題最小生成樹問題2 最短路問題最短路問題3 最大流問題最大流問題4 中國郵遞員問題中國郵遞

3、員問題0 圖的基本概念圖的基本概念第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃Example 1七橋問題七橋問題 18世紀的德國有個哥尼斯堡城，在流貫全城的普世紀的德國有個哥尼斯堡城，在流貫全城的普雷爾河兩岸和河中兩個島之間架設了七座橋，把河的雷爾河兩岸和河中兩個島之間架設了七座橋，把河的兩岸和兩島連接起來，能否有這樣一種走法，它通過兩岸和兩島連接起來，能否有這樣一種走法，它通過每座橋一次且僅一次每座橋一次且僅一次 .該問題由該問題由Euler在在1736年解決年解決ABCD 則七橋問題就成為無向圖中是否存在通過每一邊則七橋問題就成為無向圖中是否存在通過每一邊一次且僅一次的路（即一筆畫）問題一次且僅一次的路

4、（即一筆畫）問題 . .Example 2人、狼、羊、菜渡河問題人、狼、羊、菜渡河問題 一一個擺渡人希望用一條小船把一只狼、一頭羊和個擺渡人希望用一條小船把一只狼、一頭羊和一籃白菜一籃白菜 從一條河的南岸渡到北岸去，而船小只能容從一條河的南岸渡到北岸去，而船小只能容納納人、狼、羊、菜人、狼、羊、菜中中的兩個，決不能在無人看守的情的兩個，決不能在無人看守的情況下，留下狼和羊在一起或羊和白菜在一起，應怎樣況下，留下狼和羊在一起或羊和白菜在一起，應怎樣渡河才能將狼、羊、白菜都運過河？渡河才能將狼、羊、白菜都運過河？狀態(tài)轉(zhuǎn)移問題狀態(tài)轉(zhuǎn)移問題人人 狼狼 羊羊 菜菜F W G C 考慮渡河過程中河南岸的變

5、化情況，最初的狀態(tài)考慮渡河過程中河南岸的變化情況，最初的狀態(tài)是人、狼、羊、菜，最終狀態(tài)成空狀態(tài)，中間的狀態(tài)是人、狼、羊、菜，最終狀態(tài)成空狀態(tài)，中間的狀態(tài)為人、狼、羊、菜的不同組合為人、狼、羊、菜的不同組合 .共有共有 16 種狀態(tài)種狀態(tài)，但有但有 6 種狀態(tài)是不允許的，如狼、羊、菜等種狀態(tài)是不允許的，如狼、羊、菜等.FWGCFWGOFWCFGCFGWCWGC 則渡河問題歸結(jié)為尋找從頂點則渡河問題歸結(jié)為尋找從頂點 “FWGC” 到頂?shù)巾旤c點“O” 的路線的路線 . 第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃Definition 圖：圖： 有序三元組有序三元組 G = ( V，E，R ) 稱為一個圖，其中稱為

6、一個圖，其中GraphVertexEdge V = v1，v2,，vn 是有窮非空集，稱為頂點集是有窮非空集，稱為頂點集； E 稱為邊集，其中的元素叫做邊；稱為邊集，其中的元素叫做邊； R 是從邊集是從邊集 E 到到 V 中的有序或無序的元素偶對應中的有序或無序的元素偶對應 的集合的映射，稱為關聯(lián)函數(shù)的集合的映射，稱為關聯(lián)函數(shù) . 關系關系Relation無向圖：無向圖：在圖在圖 G = (V，E) 中，中，圖簡記為圖簡記為G = （V，E）與與 V 中的無序偶對應的邊中的無序偶對應的邊 e , 稱稱為圖為圖 G 的無向邊，每條邊都是的無向邊，每條邊都是無向邊的圖，稱為無向邊的圖，稱為無向圖無

7、向圖 .v1v3v4v5v2e1e8e7e6e5e4e3e2 E 中任一條邊中任一條邊 e 若連接頂點若連接頂點 u 和和 v ，則記為，則記為 e = (u，v), 并稱并稱 u 與與 v 為無向邊的兩個為無向邊的兩個端點端點；邊；邊 e 與與頂點頂點 u 及及 v 關聯(lián)關聯(lián)，頂點，頂點 u 與頂點與頂點 v 相鄰相鄰 . 與同一個頂與同一個頂點關聯(lián)的若干條邊稱為是點關聯(lián)的若干條邊稱為是相鄰相鄰的的 .若若 e = ( vi , vj )簡記為簡記為 eij自環(huán)：自環(huán)： 兩個端點重合為一個頂點的邊兩個端點重合為一個頂點的邊；平行邊：平行邊： 關聯(lián)于同一對頂點的兩條邊關聯(lián)于同一對頂點的兩條邊；

8、沒有自環(huán)和平行邊的圖；沒有自環(huán)和平行邊的圖；簡單圖：簡單圖：完備圖：完備圖：任兩個頂點之間恰有一條邊相關聯(lián)任兩個頂點之間恰有一條邊相關聯(lián)；v1v3v4v2e1e5e6e2e4e3子圖：子圖： 設設 G = (V, E)，G1 = (V1, E1) 都是圖，且都是圖，且V1 V, E1 E, 則稱圖則稱圖 G1 為圖為圖 G 的子圖；的子圖；v1v3v4v2e1e3e4e2e5e6v1v3v4v2e1e3e4e2e5e6Note : 是圖是圖第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃生成生成(支撐支撐)子圖：子圖： 若圖若圖 G1 是圖是圖 G 的子圖，且的子圖，且 V1 = V，則稱則稱 G1 是是 G

9、的生成子圖；的生成子圖；鏈（道路）：鏈（道路）： 圖圖 G 中一個由頂點和邊交錯而成的非空中一個由頂點和邊交錯而成的非空有限序列：有限序列：W = v0e1v1e2ekvk，ei E，i = 1,2,k，vj V，j =0,1,2,k, 且且 ei = (vi-1，vi), 則稱則稱 W 是是 G的一的一條鏈（道路）；條鏈（道路）； v0、vk 稱為稱為 W 的的起終點起終點，k為為路長路長；初等鏈：初等鏈： 各頂點相異的鏈；各頂點相異的鏈；回路：回路：起點與終點重合的鏈；起點與終點重合的鏈；圈：圈：起點與終點重合的初等鏈；起點與終點重合的初等鏈；連通圖：連通圖：圖圖 G 中任意兩點中任意兩點

10、 u 和和 v 存在一條鏈存在一條鏈；線度：線度：與頂點與頂點 v 關聯(lián)的邊數(shù)關聯(lián)的邊數(shù)(環(huán)算兩次環(huán)算兩次)稱為稱為 v 的線度的線度;記為記為 d(v) .v1v3v4v5v2e1e8e7e6e5e4e3e2d(v2) = 3，d(v3) = 4割邊：割邊： 若去掉邊若去掉邊 e 將使連通圖將使連通圖 G 不再連通，則稱不再連通，則稱 e 為為 G 的割邊；的割邊；有向圖：有向圖： 在圖在圖 G = (V，E) 中，與中，與 V 中的有序偶對應中的有序偶對應 的邊的邊 e , 稱為圖稱為圖 G 的有向邊（?。?，每條邊都是的有向邊（?。?，每條邊都是 有向邊的圖，稱為有向邊的圖，稱為有向圖有向圖

11、 . 記為記為 G =(，)Arc對有向圖有類似無向圖的概念，如對有向圖有類似無向圖的概念，如 d+(vi)，d-(vi) .賦賦(加加)權(quán)圖權(quán)圖：圖圖 G 的每條邊的每條邊 e = (vi，vj) 與一實數(shù)與一實數(shù) w(e) = wij 對應對應. w(e) = wij 稱為邊稱為邊 e 的權(quán)的權(quán) .割集割集：邊的集合，從連通圖：邊的集合，從連通圖 G 中移去這些邊，則中移去這些邊，則 G 不連通，且不存在這些邊的真子集使圖不連通不連通，且不存在這些邊的真子集使圖不連通 . 記為記為v1v3v4v5v2e1e8e7e6e5e4e3e2,S SS 為一個連通分支的頂點集為一個連通分支的頂點集.

12、 .圖的矩陣表示：圖的矩陣表示：第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃關聯(lián)矩陣：關聯(lián)矩陣： 對無向圖對無向圖 G = (V, E)，其中，其中 V = v1, ,vn , E = e1, e2,em . 構(gòu)造構(gòu)造 nm 矩陣矩陣 A =( aij ) nm 其中其中10ijijvea與 關聯(lián)否則12345678123451110000010000101001100110101100000001110eeeeeeeevvAvvv則稱矩陣則稱矩陣 A 是圖是圖 G 的關聯(lián)矩陣的關聯(lián)矩陣 .v1v3v4v5v2e1e8e7e6e5e4e3e2v5鄰接矩陣：鄰接矩陣： 對無向圖對無向圖 G = (V, E)，

13、其中，其中 V = v1, ,vn ,構(gòu)造構(gòu)造 nn 矩陣矩陣 B =( bij ) nn 其中其中1( ,)0ijijv vEb否則則稱矩陣則稱矩陣 B 是圖是圖 G 的鄰接矩陣的鄰接矩陣 .12345123450111010101110111010101110vvvvvvvBvvvv1v3v4v5v2e1e8e7e6e5e4e3e2對稱矩陣對稱矩陣對有向圖可類似定義關聯(lián)矩陣、鄰接矩陣對有向圖可類似定義關聯(lián)矩陣、鄰接矩陣 .Go back第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃Definition 10.1 一個無圈且連通的無向圖一個無圈且連通的無向圖 G 稱為稱為樹樹 .不連通不連通,稱為稱為森林森

14、林樹通常記為樹通常記為 T .v1v3v4v5v2e1e5e4e3e2v5如如 群試問題群試問題( Group Testing ) 設有設有 25 枚硬幣，已知其中枚硬幣，已知其中一枚是假的且偏輕，問如何用一枚是假的且偏輕，問如何用天平稱最少的次數(shù)找到假幣？天平稱最少的次數(shù)找到假幣？結(jié)論結(jié)論：3 k 個硬幣，只需稱個硬幣，只需稱 k 次即可次即可 .不知道假硬幣是偏輕還是偏重，如何？不知道假硬幣是偏輕還是偏重，如何？ 如如 12 枚枚一、樹、生成樹一、樹、生成樹關于樹有以下性質(zhì)：關于樹有以下性質(zhì)：v1v3v4v5v2e1e5e4e3e2v53、在樹在樹 T 中，任意兩頂點間有且僅有一條道路中，

15、任意兩頂點間有且僅有一條道路；1、在樹在樹 T 中，任意兩個不相鄰中，任意兩個不相鄰 頂點加上一條邊，則恰好得到頂點加上一條邊，則恰好得到 一個圈；一個圈；2、在樹在樹 T 中，去掉任意一條邊中，去掉任意一條邊, 則樹為不連通的；則樹為不連通的；4、在樹、在樹 T 中，頂點數(shù)比邊數(shù)多中，頂點數(shù)比邊數(shù)多 1 . 如果樹如果樹 T 是圖是圖 G 的生成的生成 子圖，則稱子圖，則稱 T 是是 G 的一棵生成（支撐）樹的一棵生成（支撐）樹 .Definition 10.2第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃Note:圖圖 G 的生成樹一般不是唯一的的生成樹一般不是唯一的 .v1v3v2v4v1v3v2v4v

16、1v3v2v4v1v3v2v4v1v3v2v4v1v3v2v4 共有多少？共有多少？16 棵棵Example 3 擬建造一個連接若干城鎮(zhèn)的通訊網(wǎng)絡，擬建造一個連接若干城鎮(zhèn)的通訊網(wǎng)絡，已知城鎮(zhèn)已知城鎮(zhèn) vi，vj 之間直接拉線的造價為之間直接拉線的造價為 cij ，試設計一，試設計一個總造價最小的通訊網(wǎng)絡個總造價最小的通訊網(wǎng)絡 .如如 7 個城鎮(zhèn)個城鎮(zhèn)：v3v2v7v6v4v5v1112223344567 顯然，該通訊網(wǎng)絡必須包顯然，該通訊網(wǎng)絡必須包含所有頂點，連通、無圈，且含所有頂點，連通、無圈，且權(quán)和最小權(quán)和最小.生成子圖生成子圖生成樹生成樹最小生成樹最小生成樹Definition 10.3

17、二、最小生成樹二、最小生成樹 若若 T 為為 G 的生成樹，的生成樹，T 中中的邊的邊 e 記為記為 eT，則，則T 的權(quán)的權(quán) ( )( )e Tw Tw e若若 T *為為 G 的生成樹，且有的生成樹，且有( *)min( )w Tw T TG為 的生成樹則稱則稱T *為為 G 的最小生成樹的最小生成樹.第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃Theorem 10.1 若若 T * 是圖是圖 G 的生成樹，則它是最小生的生成樹，則它是最小生成樹的充要條件是對成樹的充要條件是對 T * 外外 G 的每一條邊的每一條邊 加入加入 T * 中中后形成的圈中，該邊權(quán)最大后形成的圈中，該邊權(quán)最大 .Proof

18、Theorem 10.2 若若 T * 是圖是圖 G 的生成樹，則它是最小生的生成樹，則它是最小生成樹的充要條件是對成樹的充要條件是對 T * 中的任何一條邊中的任何一條邊, 將該邊從將該邊從T *中刪去后形成的割集中，該邊權(quán)最小中刪去后形成的割集中，該邊權(quán)最小 .證略證略v1v3v4v5v228641233圈圈最優(yōu)條件最優(yōu)條件割割最優(yōu)條件最優(yōu)條件Theorem 10.1 的證明的證明Proof :反證法反證法設設 T * 是最小生成樹，對是最小生成樹，對T * 外外G 的任一條邊的任一條邊 e ，加入，加入 T *中后形成的圈中，如果該邊中后形成的圈中，如果該邊的權(quán)不是最大，設最大邊為的權(quán)不

19、是最大，設最大邊為 e*. 此時，此時，T *+ e e* 也是也是生成樹，但它的權(quán)比生成樹，但它的權(quán)比 T *更小，這與更小，這與 T * 是最小生成樹是最小生成樹矛盾矛盾 . 設設 T * 是生成樹并滿足定理條件，但不是最小的是生成樹并滿足定理條件，但不是最小的.設最小生成樹為設最小生成樹為 T0，則則 T * 中至少有一條邊中至少有一條邊 (i, j) T0,將將 (i, j) 加入加入 T0 后必產(chǎn)生一個圈，且圈上至少有一條邊后必產(chǎn)生一個圈，且圈上至少有一條邊 (k, l) T * , 由定理條件由定理條件 wijwkl , 又又T0為最小生成樹為最小生成樹,所以所以, wijwkl

20、, 于是于是 wij = wkl . 因此因此, T0 + (i, j) (k, l) 也也是最小生成樹，并與是最小生成樹，并與T *有更多的公共邊，重復該過程有更多的公共邊，重復該過程,最后，可以將最后，可以將 T0變?yōu)樽優(yōu)門 *，因此，因此，T * 是最小生成樹是最小生成樹.三、求最小生成樹的算法三、求最小生成樹的算法 求最小生成樹的方法很多且很簡單，理論基礎主要求最小生成樹的方法很多且很簡單，理論基礎主要是定理是定理 10.1（圈最優(yōu)條件）、定理（圈最優(yōu)條件）、定理 10.2（割最優(yōu)條件）（割最優(yōu)條件）.A、 避圈法避圈法 1、Kruskal 算法（逐邊生成）算法（逐邊生成） 2、Pri

21、m 算法算法 （逐點生成）（逐點生成）B、 破圈法破圈法 1、Kruskal 算法算法 （1956年）年）Step 0 把把 G 的邊按權(quán)由小到大的順序排列，即的邊按權(quán)由小到大的順序排列，即w(e1) w(em) ; 令令 i = 1，j = 0，T = . Step 1 判斷判斷 Tei 是否含圈是否含圈, Y 轉(zhuǎn)轉(zhuǎn)Step 2, N 轉(zhuǎn)轉(zhuǎn)Step 3 .Step 2 令令 i = i+1. 若若 im 轉(zhuǎn)轉(zhuǎn) Step 1; 否則結(jié)束，此時否則結(jié)束，此時 G 不連通，所以沒有最小生成樹不連通，所以沒有最小生成樹 .Step 3令令 T = Tei ，j = j+1 . 若若 j = n-1，

22、結(jié)束，結(jié)束，T 是最是最小生成樹；否則，轉(zhuǎn)小生成樹；否則，轉(zhuǎn) Strp 2 .第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃Example 4v3v2v7v6v4v5v1112223344567用用 Kruskal 算法求算法求右圖的最小生成樹右圖的最小生成樹 .Solution: 首先，對所有邊按權(quán)首先，對所有邊按權(quán)由小到大順序排列由小到大順序排列：(2, 7)，(2, 3) .(1, 7)，(4, 5)，(5, 7)，(1, 6)，(4, 7)，(1, 2)，(3, 7)，(3, 4)(6, 7)，(5, 6)然后，按順序?qū)⑦@些邊加入然后，按順序?qū)⑦@些邊加入 T 中，中，如圖，得到最小生成樹如圖，得到最小

23、生成樹 T *，w(T *) = 14如何判斷如何判斷Tei 含圈？含圈？通過增加一個標號通過增加一個標號 給每個頂點一個互不相同的標號，不妨為頂點的下標給每個頂點一個互不相同的標號，不妨為頂點的下標. 當加入一條邊時當加入一條邊時, ,判斷兩個頂點的標號判斷兩個頂點的標號, ,若相同若相同, ,則產(chǎn)生圈；否則產(chǎn)生圈；否則，將與標號大的相同的標號均改為與標號小的相同的標號則，將與標號大的相同的標號均改為與標號小的相同的標號. .32764511122233445676 55 在算法進行過程中，在算法進行過程中，T 始終不含圈始終不含圈. 因此算法結(jié)束因此算法結(jié)束時，若時，若 T 含含 n-1

24、條邊，則條邊，則 T 為生成樹；否則，原圖不為生成樹；否則，原圖不連通，不存在生成樹連通，不存在生成樹 . 由于邊已按權(quán)由小到大排序，而不加入由于邊已按權(quán)由小到大排序，而不加入 T 的邊，的邊，必為產(chǎn)生圈中的最大權(quán)邊，由定理必為產(chǎn)生圈中的最大權(quán)邊，由定理 10.1 知，知， T 為生成為生成樹則必為最小生成樹樹則必為最小生成樹 . 這說明這說明Kruskal 算法的正確性算法的正確性 . 該算法始終試圖把權(quán)盡可能小的邊加到該算法始終試圖把權(quán)盡可能小的邊加到 T 中，僅中，僅當加入后使當加入后使 T 不是樹才放棄，對邊的選取，不必瞻前不是樹才放棄，對邊的選取，不必瞻前顧后，只看眼前利益顧后，只看

25、眼前利益 . 這就是簡單且重要的這就是簡單且重要的貪婪算法貪婪算法（Greedy）.第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃2、Prim 算法算法 （1957年）年）Step 0Step 1Step 2令令 S = Sv2，E0 = E0 e*,轉(zhuǎn)轉(zhuǎn) Strp 1 .設設 v 為為 G 的任一頂點，令的任一頂點，令 S = v，E0 = ,S S , ( *)min( )eS Sw ew e若若 S = V，結(jié)束，結(jié)束，T = (S , E0) 為最小生成樹；為最小生成樹；否則否則 轉(zhuǎn)轉(zhuǎn) Step 2 .1212*( ,),.ev vvS vS若若 ，則，則 G 不連通，結(jié)束；不連通，結(jié)束； 否則，設否

26、則，設 , 其中其中 v3v2v7v6v4v5v1112223344567Prim 算法的正確性由定理算法的正確性由定理10.2 不難得到不難得到.3、破圈法破圈法 （1967年）年）v3v2v7v6v4v5v1112223344567四、應用舉例四、應用舉例 最小生成樹的理論和計算，最小生成樹的理論和計算，在很多工程或技術(shù)領域中得到應用在很多工程或技術(shù)領域中得到應用 . 如要在若干城市之間架設通訊線路、鋪設公路鐵路或如要在若干城市之間架設通訊線路、鋪設公路鐵路或各種管道，要求總的線路長度最短，材料最省，成本各種管道，要求總的線路長度最短，材料最省，成本最低等最低等. 在實際的應用中，又提出了

27、最小生成樹問題的各在實際的應用中，又提出了最小生成樹問題的各種推廣，其中較典型的問題多是在可行解的結(jié)構(gòu)上增種推廣，其中較典型的問題多是在可行解的結(jié)構(gòu)上增加一些約束加一些約束 .第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃1、最大生成樹問題最大生成樹問題v3v2v7v6v4v5v1112223344567在最小生成樹上，在最小生成樹上，v1至至v4路的特點路的特點Example 5 設某工廠運輸一很重的設備，需由設備庫設某工廠運輸一很重的設備，需由設備庫 v1 運至施工現(xiàn)場運至施工現(xiàn)場 v4，中間需經(jīng)過一些橋梁（如圖），中間需經(jīng)過一些橋梁（如圖），已知這些橋梁的堅固程度不同，經(jīng)專家測定其安全系已知這些橋梁的堅

28、固程度不同，經(jīng)專家測定其安全系數(shù)如示，試問應如何安排運輸路線最安全？數(shù)如示，試問應如何安排運輸路線最安全？最大值最小最大值最小v6v5v4施工現(xiàn)場施工現(xiàn)場v3v2v1設備庫設備庫Solution:v6v5v4v3v1v 最大生成樹上的路是最小者最大最大生成樹上的路是最小者最大.先求得最大生成樹，如圖先求得最大生成樹，如圖所以，所以，v1至至v4的最安全的路線為的最安全的路線為 v1 v6 v5 v3 v4最不安全處最安全最不安全處最安全最不安全處系數(shù)為最不安全處系數(shù)為 0.42、容量約

29、束最小生成樹問題容量約束最小生成樹問題 在遠程信息處理網(wǎng)絡的設計中涉及這樣的問題：在遠程信息處理網(wǎng)絡的設計中涉及這樣的問題：已給一個無向圖已給一個無向圖 G = (V，E) , 每條邊每條邊 (vi , vj) 具有費用具有費用 w (vi , vj) 以及容量以及容量 c (vi , vj) ，一個頂點為信息接收站，一個頂點為信息接收站. 尋求一個生成樹，使所有信息沿樹的邊送到接收尋求一個生成樹，使所有信息沿樹的邊送到接收站，滿足容量約束，即每邊上所傳的信息量不超過容站，滿足容量約束，即每邊上所傳的信息量不超過容量費用最且小量費用最且小 . 稱為容量約束的最小生成樹問題，是稱為容量約束的最小

30、生成樹問題，是 NP-C問題問題.第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃3、度數(shù)約束最小生成樹問題度數(shù)約束最小生成樹問題 生成樹在計算機和通訊網(wǎng)絡中有許多應用，其中生成樹在計算機和通訊網(wǎng)絡中有許多應用，其中的大多數(shù)問題對某些頂點的度數(shù)有限制的大多數(shù)問題對某些頂點的度數(shù)有限制 . 如一個頂點如一個頂點代表一個中央計算設備，其他頂點代表終端，它們必代表一個中央計算設備，其他頂點代表終端，它們必須靠電纜與中央設備連接，若現(xiàn)在中央機的度數(shù)為須靠電纜與中央設備連接，若現(xiàn)在中央機的度數(shù)為 b ,這可保證計算機的負荷分散在這可保證計算機的負荷分散在 b 個端口，求中央機度個端口，求中央機度數(shù)為數(shù)為 b 的最小生成樹

31、，使所用電纜盡可能少的最小生成樹，使所用電纜盡可能少 . 若只有一個頂點受約束，是一個若只有一個頂點受約束，是一個 P 問題問題 .1、Steiner 樹樹（在歐氏距離下）（在歐氏距離下）補充：補充：Example 6 假設電話剛發(fā)明，郵電部的第一個任務假設電話剛發(fā)明，郵電部的第一個任務是要使北京、上海、蘭州三個城市間有線路相通是要使北京、上海、蘭州三個城市間有線路相通 . 你你是總工程師，如何設計路線呢？是總工程師，如何設計路線呢？ 當然線路越短越好，由最小生成樹：當然線路越短越好，由最小生成樹：北京北京蘭州、蘭州、北京北京上海上海 為最佳為最佳 .北京北京蘭州蘭州上海上海真的沒辦法更短了嗎

32、？真的沒辦法更短了嗎？鄭州鄭州 但你的發(fā)現(xiàn)并沒有使舉世的科學家震動，因為這一但你的發(fā)現(xiàn)并沒有使舉世的科學家震動，因為這一事實早已被無數(shù)的數(shù)學書籍記載，這就是事實早已被無數(shù)的數(shù)學書籍記載，這就是 Steiner 樹樹 . 你發(fā)現(xiàn)：你發(fā)現(xiàn)：北京北京鄭州、上海鄭州、上海鄭州、蘭州鄭州、蘭州鄭州鄭州 也滿足也滿足要求且總長度比最小生成樹更短要求且總長度比最小生成樹更短 . 通過增加一些點（通過增加一些點（Steiner 點）使保存原來的所有點）使保存原來的所有點且連通，而總長度最短點且連通，而總長度最短 .第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃v4v3v2v1如右圖：最小生成樹如右圖：最小生成樹 z min

33、= 31111但加上但加上 v5，則，則 z min = 2 = 2.8282問題：問題：1、對于怎樣放置的對于怎樣放置的 n 個點，需要引進個點，需要引進 S 點；點；v1v3v2如：如：是不需要加點的是不需要加點的. .2、如何確定如何確定 S 點的位置點的位置；3、引進幾個引進幾個 S 點最佳點最佳 .n = 1、2 是平凡的是平凡的 . n = 3 已解決，一般是已解決，一般是 NP-C 的的 .Theorem 10.3 設有設有 A、B、C 三點，若三點，若ABC 的任一的任一內(nèi)角都小于內(nèi)角都小于 120o ，則必存在內(nèi)部一點，則必存在內(nèi)部一點 P 使使 PA、PB、PC 的兩兩夾角

34、均是的兩兩夾角均是 120o ，且此時，且此時 PA + PB + PC ABC 的任兩邊之和的任兩邊之和 . 不可能有另一點不可能有另一點 D 比比 P 的效果的效果更好更好 .v5而當而當A 120o 則則 z min = AB+ACTheorem 10.4三個點時，如何確定三個點時，如何確定S - -點位置點位置ABCS120o120oD 能否再加點，能否再加點， 使之更短呢？使之更短呢？ 對于對于 n 個點個點的網(wǎng)絡，至多可加入的網(wǎng)絡，至多可加入 n 2 個個 Steiner 點點 .v4v3v2v11111v5最小生成樹最小生成樹 z min = 3但加上但加上 v5，則，則 z m

35、in = 2 = 2.8282120o120o此時此時， z min = 1+ = 2.7323問：問：Steiner 樹能使總樹能使總長度比最小生成樹減少長度比最小生成樹減少的最大比例是多少？的最大比例是多少？ 1968年兩位美國數(shù)學家提出該比例為年兩位美國數(shù)學家提出該比例為 13.4% 的猜想，上世紀的猜想，上世紀90年代初，被中國年代初，被中國青年數(shù)學家堵丁柱解決，且方法很有價值青年數(shù)學家堵丁柱解決，且方法很有價值.第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃2、擬陣擬陣 （Matroid）問：怎樣的結(jié)構(gòu)的組合問：怎樣的結(jié)構(gòu)的組合優(yōu)化問題可用優(yōu)化問題可用 Greedy 算法得到最優(yōu)解？算法得到最優(yōu)解？

36、Definition 10.4 子集系統(tǒng)子集系統(tǒng) S = (E , l) 是由有限集是由有限集 E 及及 E 的一個子集族的一個子集族 l 組成，在集合的包含關系下，組成，在集合的包含關系下， l 是封是封閉的閉的. l 中的成員，稱為獨立集中的成員，稱為獨立集 .即若即若,AlAAAl則參照參照：E 為圖為圖 G 的邊的集合，的邊的集合，l 是是E 的無圈子集的無圈子集. 關于子集系統(tǒng)關于子集系統(tǒng) S = (E , l) 的組合優(yōu)化問題是對每一的組合優(yōu)化問題是對每一個個 e E 給定一個權(quán)給定一個權(quán) w(e) 0 ，求一個最大獨立集，求一個最大獨立集，使其權(quán)和最大（?。┦蛊錂?quán)和最大（?。?D

37、efinition 10.5 設設 S = (E , l) 是一子集系統(tǒng)，如果對是一子集系統(tǒng)，如果對 S的任意兩個極大獨立集的任意兩個極大獨立集 則稱則稱 S 是擬陣是擬陣.,A AAA有顯然，對顯然，對G = (E , V) , S = (E , l) , l 是無圈子圖，則是無圈子圖，則 S 是擬陣是擬陣 .Theorem 10.5 S 是擬陣，則關于是擬陣，則關于 S 的組合優(yōu)化問題的組合優(yōu)化問題中每個例子，都可用中每個例子，都可用 Greedy 算法得到最優(yōu)解算法得到最優(yōu)解 . 婚姻問題婚姻問題 (matching ) 可以看成一個子集系統(tǒng)可以看成一個子集系統(tǒng) S = ( E , l)

38、 , l 所有匹配，但不是擬陣所有匹配，但不是擬陣.x3x1x2y2y1y3我們還學過其他我們還學過其他擬陣結(jié)構(gòu)嗎？擬陣結(jié)構(gòu)嗎？ S = ( E , l) , E 一組向量一組向量 l 所有線性無關子所有線性無關子集，它是擬陣集，它是擬陣. 因為線性無關組的子集因為線性無關組的子集仍線性無關；極大線性無關仍線性無關；極大線性無關組的所含向量個數(shù)相同組的所含向量個數(shù)相同 . . 則對每個向量加權(quán)，要求一個極大則對每個向量加權(quán)，要求一個極大線性無關組，使其權(quán)和最大（?。?，可線性無關組，使其權(quán)和最大（?。?，可用用 Greedy 算法算法.Go back第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃 最短路問題是網(wǎng)絡

39、優(yōu)化中的一個相對基本而又非最短路問題是網(wǎng)絡優(yōu)化中的一個相對基本而又非常重要的課題常重要的課題. . 許多網(wǎng)絡優(yōu)化問題或者可以化為最短許多網(wǎng)絡優(yōu)化問題或者可以化為最短路問題，或者可用最短路的算法作為其子程序路問題，或者可用最短路的算法作為其子程序. . 如：如：通訊網(wǎng)絡中的最可靠路問題、物資的運輸路線、各種通訊網(wǎng)絡中的最可靠路問題、物資的運輸路線、各種工藝路線的安排、廠區(qū)及貨場的布局、管道線網(wǎng)的鋪工藝路線的安排、廠區(qū)及貨場的布局、管道線網(wǎng)的鋪設以及設備的更新等問題都可化為最短路問題；而網(wǎng)設以及設備的更新等問題都可化為最短路問題；而網(wǎng)絡流問題和中國郵遞員問題都要用最短路算法作為子絡流問題和中國郵遞

40、員問題都要用最短路算法作為子程序程序 . . 設有向網(wǎng)絡設有向網(wǎng)絡 D = (V , A , w)，其中弧，其中弧 ( vi , vj) A對對應的權(quán)應的權(quán) wij 又稱為弧長或費用，對于其中的兩個頂點又稱為弧長或費用，對于其中的兩個頂點 v1、vt V, 以以v1為起點為起點 vt 為終點的有向路稱為為終點的有向路稱為 v1 vt 有向路有向路 P , 其所經(jīng)過的所有弧上的權(quán)之和為該有向路的其所經(jīng)過的所有弧上的權(quán)之和為該有向路的權(quán)權(quán) (,)( )ijijv vPw Pw 所有所有 v1 vt 有向路中權(quán)和最小的一條稱為有向路中權(quán)和最小的一條稱為 v1 vt 最短路最短路 P*.求最短路的方法

41、的基本思想很樸素求最短路的方法的基本思想很樸素： 設設 v1 vl 的最短路是的最短路是 v1 vi vk vl , 則則 v1 vk 的最短路是的最短路是 v1 vi vk 第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃Example 7 利用前述思想求如利用前述思想求如下網(wǎng)絡中，下網(wǎng)絡中，v1 至至 v4 的的最短路最短路 .Solution:v1v2v3v4v5v6362423311從從 v1 逐步向外生長逐步向外生長 目前目前 v1 可達可達 v2、v3 路長分路長分別為別為6、3，這時求得了這時求得了v1至至 v3 的最短路，長度為的最短路，長度為 3 .v1不可能通過其他頂不可能通過其他頂點到達點

42、到達v3 距離更短，距離更短，因為因為 wij 0 再求再求 v1或通過或通過 v3 可達的所有路的最短距離，可達的所有路的最短距離，v1 v2;v1 v3 v2; v1 v3 v4 路長分別為路長分別為6、5、7. 這時求這時求得了得了 v1 至至v2的最短路，路長為的最短路，路長為 5 . 再求再求 v1 v3 v2 v4; v1 v3 v2 v5; v1 v3 v4 路長分別為路長分別為 7、6、7. 這時得這時得 v1 至至v2的最短路的最短路, 路長為路長為 5 .這時求得這時求得 v1至至v4 的最短路的最短路 ，路長為，路長為 6 . 介紹了基本思想和方法，但有兩個需彌補的地方：

43、介紹了基本思想和方法，但有兩個需彌補的地方：1、計算量大、計算量大 O(n3);2、如何記錄最短路的走法、如何記錄最短路的走法 .一、正費用網(wǎng)絡一、正費用網(wǎng)絡(wij0) 1959年，年，Dijkstra 提出通過提出通過標號標號解決了上述問題解決了上述問題 .這是網(wǎng)絡規(guī)劃中這是網(wǎng)絡規(guī)劃中常用手段常用手段該算法是目前公認的求正費用網(wǎng)絡最短路的較好的算法該算法是目前公認的求正費用網(wǎng)絡最短路的較好的算法之一之一 . 基本如前（逐點生成），但在執(zhí)行過程中，對未基本如前（逐點生成），但在執(zhí)行過程中，對未達到最短路的頂點，記錄目前達到最短路的頂點，記錄目前 v1 至該點的最短路長度至該點的最短路長度.一

44、旦有新的頂點被確定已達最短，則下一步其余（對未一旦有新的頂點被確定已達最短，則下一步其余（對未達到最短路的頂點）的頂點只需與它比較，來確定新的達到最短路的頂點）的頂點只需與它比較，來確定新的目前目前 v1至這些點的最短路長度至這些點的最短路長度 .ui 表示表示 v1 至至vi 的最短路長度；（是永久性的）的最短路長度；（是永久性的）t(vi)表示目前表示目前 v1 至至vi 的最短路長度；（是臨時性的）的最短路長度；（是臨時性的）l(vi)表示表示v1 至至vi 的目前最短路上的目前最短路上 vi 的前一個頂點的下標的前一個頂點的下標如：如：l(vi) = j 即即 v1 vj vi第十第十

45、章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃Dijkstr 算法算法（求（求v1至個頂點或至至個頂點或至vh 的最短路）的最短路）Step 0令令 i = 1 , Si =v1 , u1 = 0 , l(v1) = 0 , 對每個對每個 jivS()jivS11()min()ijiijijvStvtv令令 t1(vj) = M , l1(vj) = M (M 為充分大的正數(shù)為充分大的正數(shù))，k = 1Step 1如果如果 Si = V (或或 k = h 即即 v1至至vh的最短路的最短路) 結(jié)束結(jié)束否則否則 , 轉(zhuǎn)轉(zhuǎn) Step 2Step 2 對每條從對每條從 vk 出發(fā)的弧出發(fā)的弧 (vk , vj) A ,

46、ti+1(vj) = min ti(vj) , uk + wkj 若若 ti+1(vj) = ti(vj) ，則，則 li+1(vj) = li(vj) , 否則否則 li+1(vj) = kStep 3令令如果如果 ti+1(vji) M則則 11()()()iiiijijjijutvl vlv令令 Si+1 = Si vji , k = ji , i = i+1 轉(zhuǎn)轉(zhuǎn) Step 2 否則否則 結(jié)束結(jié)束. 當算法結(jié)束時，如果當算法結(jié)束時，如果 vj Si , 則則 v1 可達可達 vj , uj 表表示示 v1至至vj 的最短路的長度，且通過的最短路的長度，且通過 l(vj)，可得其最短，可

47、得其最短路路 . 如果如果 , 則則vi至至vj 不存在路不存在路 .jivSExample 8 用用 Dijkstra 算法求如下網(wǎng)絡中，算法求如下網(wǎng)絡中，v1 至各頂至各頂點的最短路點的最短路 .v1v2v3v4v5v61624253117Solution:i = 1 , 令令 S1 = v1u1 = 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 = 6 l2(v2)

48、 = 1t2(v3) = min M , u1 +3 = 3 l2(v3) = 1t2(v4) = min M , u1 + M = M l2(v4) = Mt2(v5) , t2(v6) 均不變均不變 .所以，所以， 則則 u2 = t2(v3) = 3 , l(v3) = 1 , S = v1 , v31232()min ()jjvSt vt vk = 2 , i = 2 Go on過程可由如下表格給出，打過程可由如下表格給出，打“*”者為者為 uj . v1v2v3v4v5v6 10* 0M MM MM MM MM M 26 13* 1M MM MM M 36 14* 3M M10 3

49、45* 46 49 4 56* 49 4 67* 5ti(vj) li(vj)ivj第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃二、一般費用網(wǎng)絡二、一般費用網(wǎng)絡 對于對于 wij0 的情形，的情形，Dijkstra 算法是行不通的算法是行不通的 . 如圖如圖:v1v2v3-221v1v2v3-22-1 在沒有負圈的情況下，在沒有負圈的情況下，v1 至多通過至多通過 n-2 頂點到達頂點到達 vj , 與與 wij0 不同，可逐點進入不同，可逐點進入 Si ，但在這里，目前是最，但在這里，目前是最短的但完全可能通過其它點會更短短的但完全可能通過其它點會更短 .但求最短路方法的基本思想還是成立的但求最短路方法的

50、基本思想還是成立的： 設設 v1 vl 的最短路是的最短路是 v1 vi vk vl , 則則 v1 vk 的最短路是的最短路是 v1 vi vk 想法是這樣，從步數(shù)著手，一步可達、兩步、三想法是這樣，從步數(shù)著手，一步可達、兩步、三步，步，至多，至多 n-1 步步 . 即如下遞推公式：即如下遞推公式：1(1)1( )(1)0min2,3,.,2,3,.,1jjttjiijiuuwuuwjn tn( ) tju其中其中 表示表示 t 步內(nèi)步內(nèi) v1 至至 vj 的最短路長度的最短路長度.為加快速度，可用為加快速度，可用已計算的已計算的 替換替換.( ) tju當進行到某一步，如第當進行到某一步，

51、如第 k 步，對所有的步，對所有的 j = 2,3,n 有有( )(1)kkjjuu( )2,3,.,kjjuujn則則如果如果 當當 k n-1, 仍不出現(xiàn)仍不出現(xiàn)( )(1)2,3,.,kkjjuujn則網(wǎng)絡中含有負圈則網(wǎng)絡中含有負圈 .這算法是由這算法是由 Ford 1956年給出年給出 .第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃 ；0110101010010110abcdabAcd2(2)():ijAa(2)321010011 00 1201a cabcdb(2)322a 一般地，一般地， 的值表示從城市的值表示從城市 i 到城市到城市 j 經(jīng)兩次航經(jīng)兩次航行到達行到達 j 的線路數(shù)；若記的線路

52、數(shù)；若記 ，則，則 (2)ija( )()kkijAa( )kija=從城市從城市 i 到城市到城市 j 經(jīng)經(jīng) k 次航行到達次航行到達 j 的線路數(shù)的線路數(shù).22011111102202011A31331223140221331A46253535326626253A 于是，從于是，從 d 出發(fā)經(jīng)出發(fā)經(jīng) 3 次航行到達次航行到達 c 的線路數(shù)為的線路數(shù)為 條，條，(3)433a;.dcdcdbacdcac 從從 d 出發(fā)經(jīng)出發(fā)經(jīng) 4 次航行回到次航行回到 d 的線路數(shù)為的線路數(shù)為 條條(4)443a;.dcdcddbacddcacd ( )23().kkijCcAAAA =從頂點從頂點 i 到

53、頂點到頂點 j 經(jīng)少于經(jīng)少于 k +1步到達步到達 j 的道路數(shù)的道路數(shù) ( )kijc第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃 用用 Ford 算法求如下網(wǎng)絡中算法求如下網(wǎng)絡中 v1至各頂點至各頂點的最短路的最短路 .v1v2v3v4v5v6-26-182-5311v7v821-5-3-3-17-10123602305180210101710350mmmmmmmmmmmmmmmmmmAmmmmmmmmmmmmmmmmmmmmm(1)(1)(1)(1)1281.uuuuA121288.AABBBA得鄰接矩陣得鄰接矩陣(2)(1)(1)(1)128128.*.uuuuBBB定義定義 Ai * Bj =11

54、8miniijiab ( )(1)(1)(1)128128.*.ttttuuuuBBBv1v2v3v4v5v6-2682-5311v7v821-5-3-3-17-10123602305180210101710350mmmmmmmmmmmmmmmmmmAmmmmmmmmmmmmmmmmmmmmmv1v2v3v4v5v6v7v8t=10-1-23mmmmt=2t=3t=4定義定義 Ai * Bj =118miniijiab ( ) tju0-5-2-71-15m0-5-2-76-1-5-30-5-2-76-1-5-3 當當 t = 3 和和 t = 4v1 至各頂點路長不至各頂點路長不變（步數(shù)增加

55、也不變（步數(shù)增加也不會變）會變）. 此時，已得此時，已得所求所求 .-1第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃 求網(wǎng)絡中所有頂點之間的最短路求網(wǎng)絡中所有頂點之間的最短路 . 當然，可以通過當然，可以通過 n 次調(diào)用次調(diào)用 Ford算法來完成，但計算法來完成，但計算量為算量為 O(n2m) . 1962年年 Floyd- -Warshall 提出的算法計提出的算法計算量為算量為 O(n3) . (1)(1)(1)( )( )( )0min, ,1,2,.,iiijijttttijijittjuuwijuuuui j tn 算法可用如下遞推公式表示算法可用如下遞推公式表示：(1)(1)(1),0,()ij

56、iiijijPjuuwij( )( )( )tttijittjuuu(1)( )(1)( )( )tttttijitijittjPPuuuFloyd- -Warshall 算法算法Step 0( 1)( )ttijijPP(1)( )ttijijuut = 0 , 對于所有頂點對于所有頂點 vi , vj令令Step 1對于所有頂點對于所有頂點 vi , vj若若令令否則否則, , 令令Step 2如果如果 t = n , 則結(jié)束則結(jié)束 ; 否則否則 令令 t = t+1 轉(zhuǎn)轉(zhuǎn)Step 1.第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃 用用 Floyd-Warshall 算法求如下網(wǎng)絡中所算法求如下網(wǎng)絡中所

57、有頂點之間的最短路有頂點之間的最短路 .v1v2v3v464-73105-3-36記最短路長度記最短路長度矩陣為矩陣為 U, 最短路矩陣為最短路矩陣為 P初始值為初始值為(1)(1)043123430712341003123456601234mmUPm(2)(2)043123430712341003123456201214mmUPm(3)(3)0431234307123471003223436102224mmUP第一次迭代后得到第一次迭代后得到第二次迭代后得到第二次迭代后得到(4)(4)043012333074123371003223436102224UP第三次迭代后得到第三次迭代后得到(5)

58、(5)04301233307412336903443436102224UP第四次迭代后得到第四次迭代后得到 終終 點點 v1 v2 v3 v4 起起 點點 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)得到得到

59、, 根據(jù)根據(jù) P(5)最最后得到的最短路為后得到的最短路為第十第十章章 網(wǎng)絡規(guī)劃網(wǎng)絡規(guī)劃三、應用舉例三、應用舉例 選址問題選址問題或設點問題是指為一個或幾個服務設施或設點問題是指為一個或幾個服務設施在一定區(qū)域內(nèi)選定它的位置在一定區(qū)域內(nèi)選定它的位置, , 使某一指標達到最使某一指標達到最優(yōu)優(yōu) . 選址問題的數(shù)學模型依賴于設施可能的區(qū)域和評選址問題的數(shù)學模型依賴于設施可能的區(qū)域和評判位置優(yōu)劣的標準判位置優(yōu)劣的標準, ,有許多不同種類的選址問題有許多不同種類的選址問題 .(1) 中心問題中心問題 對一些緊急服務型的設施對一些緊急服務型的設施( (如急救中心、消防站如急救中心、消防站等等) )，要求距

60、網(wǎng)絡中最遠的被服務點距離盡可能小，要求距網(wǎng)絡中最遠的被服務點距離盡可能小 .可以在點上、邊可以在點上、邊上、區(qū)域內(nèi)上、區(qū)域內(nèi)Example 12 現(xiàn)準備在現(xiàn)準備在 v1, v2, ,v7 七個居民點中設置七個居民點中設置醫(yī)院醫(yī)院 . 各點之間的距離如圖各點之間的距離如圖, 問設一個醫(yī)院在哪個居民問設一個醫(yī)院在哪個居民點點,可使最大服務距離為最小可使最大服務距離為最小 ; 若設兩個若設兩個,問應設在哪兩問應設在哪兩個居民點個居民點 ?v1v2v3v4v5v662.531.81.5v721.534 求出任意兩點的最短路求出任意兩點的最短路長度長度, 得矩陣得矩陣 D = (dij) :0356.3