運籌學(xué)-圖論.ppt

圖論 第五章圖與網(wǎng)絡(luò)分析 主要內(nèi)容 1圖的基本概念與基本定理2樹和最小支撐樹3最短路問題4最大流問題5最小費用流問題 什么是圖 圖論中所謂的圖是由一些點 vertices 和一些連接兩點的邊 edges 所形成的 5 1圖的基本概念與基本定理 圖論是應(yīng)用非常廣泛的運籌學(xué)分支 它已經(jīng)廣泛地應(yīng)用于物理學(xué)控制論 信息論 工程技術(shù) 交通運輸 經(jīng)濟管理 電子計算機等各項領(lǐng)域 對于科學(xué)研究 市場和社會生活中的許多問題 可以同圖論的理論和方法來加以解決 例如 各種通信線路的架設(shè) 輸油管道的鋪設(shè) 鐵路或者公路交通網(wǎng)絡(luò)的合理布局等問題 都可以應(yīng)用圖論的方法 簡便 快捷地加以解決問題 關(guān)于圖的第一篇論文是瑞士數(shù)學(xué)家歐拉 E Euler 在1736年發(fā)表的解決 哥尼斯堡 七橋難題的論文 德國的哥尼斯堡城有一條普雷格爾河 河中有兩個島嶼 河的兩岸和島嶼之間有七座橋相互連接 當(dāng)?shù)氐木用駸嶂杂谶@樣一個問題 一個散步者如何能夠走過這七座橋 并且每座橋只能走過一次 最終回到原出發(fā)地 盡管試驗者很多 但是都沒有成功 為了尋找答案 1736年歐拉將這個問題抽象成圖所示圖形的一筆畫問題 K nigsberg Koenigsberg 哥尼斯堡 原為東普魯士 Prussia 首府 現(xiàn)屬俄羅斯 飛地 名為加里寧格勒 Kaliningrad 哥尼斯堡七橋問題 要如何走過每座橋恰一次 再返回出發(fā)點 普瑞格爾河 哥尼斯堡七橋問題 A B C D 哥尼斯堡七橋問題可簡化為以下圖形其中的四個頂點都是奇頂點 A B C D 哥尼斯堡七橋問題可以看成是 對這樣一個封閉的圖形 是否可以一筆畫完成它并且回到原點 數(shù)學(xué)家歐拉 Euler 1707 1783 于1736年嚴格地證明了上述哥尼斯堡七橋問題無解 并且由此開創(chuàng)了圖論的典型思維方式及論證方式 即能否從某一點開始不重復(fù)地一筆畫出這個圖形 最終回到原點 歐拉在他的論文中證明了這是不可能的 因為這個圖形中每一個頂點都與奇數(shù)條邊相連接 不可能將它一筆畫出 這就是古典圖論中的第一個著名問題 在實際的生產(chǎn)和生活中 人們?yōu)榱朔从呈挛镏g的關(guān)系 常常在紙上用點和線來畫出各式各樣的示意圖 圖論應(yīng)用舉例 例如 在組織生產(chǎn)中 為完成某項任務(wù) 各工序之間怎樣銜接 才能使生產(chǎn)任務(wù)完成得既快又好 一個郵遞員送信 要走完他負責(zé)投遞的全部街道 完成任務(wù)后回到郵局 應(yīng)該按照怎樣的路線走 所走的路程最短 各種通信網(wǎng)絡(luò)的合理架設(shè)交通網(wǎng)絡(luò)的合理分布等 生活中的一些例子 臺大網(wǎng)路架構(gòu)圖 例5 1圖5 2是我國北京 上海 重慶等十四個城市之間的鐵路交通圖 這里用點表示城市 用點與點之間的線表示城市之間的鐵路線 諸如此類還有城市中的市政管道圖 民用航空線圖等等 圖5 3 例5 2有六支球隊進行足球比賽 我們分別用點v1 v6表示這六支球隊 它們之間的比賽情況 也可以用圖反映出來 已知v1隊?wèi)?zhàn)勝v2隊 v2隊?wèi)?zhàn)勝v3隊 v3隊?wèi)?zhàn)勝v5隊 如此等等 這個勝負情況 可以用圖5 3所示的有向圖反映出來 從以上的幾個例子可以看出 我們用點和點之間的線所構(gòu)成的圖 反映實際生產(chǎn)和生活中的某些特定對象之間的特定關(guān)系 通常用點表示研究對象 用點與點之間的線表示研究對象之間的特定關(guān)系 由于在一般情況下 圖中對象的相對位置如何 點與點之間線的長短曲直 對于反映研究對象之間的關(guān)系 顯的并不重要 因此 圖論中的圖與幾何圖 工程圖等本質(zhì)上是不同的 圖論中的圖是由點 點與點之間的線所組成的 通常 我們把點與點之間不帶箭頭的線叫做邊 帶箭頭的線叫做弧 如果一個圖是由點和邊所構(gòu)成的 那么稱為無向圖 記作G V E 其中V表示圖G的點集合 E表示圖G的邊集合 連接點vi vj V的邊記作 vi vj 或者 vj vi 如果一個圖是由點和弧所構(gòu)成的 那么稱為它為有向圖 記作D V A 其中V表示有向圖D的點集合 A表示有向圖D的弧集合 一條方向從vi指向vj的弧 記作 vi vj 圖的基本概念 圖5 4是一個無向圖G V E 其中V v1 v2 v3 v4 E v1 v2 v2 v1 v2 v3 v3 v4 v1 v4 v2 v4 v3 v3 圖5 4 圖5 5是一個有向圖D V A 其中V v1 v2 v3 v4 v5 v6 v7 A v1 v2 v1 v3 v3 v2 v3 v4 v2 v4 v4 v5 v4 v6 v5 v3 v5 v4 v5 v6 v6 v7 圖5 5 圖的基本概念 一個圖G或有向圖D中的點數(shù) 記作P G 或P D 簡記作P 邊數(shù)或者弧數(shù) 記作q G 或者q D 簡記作q 如果邊 vi vj E 那么稱vi vj是邊的端點 或者vi vj是相鄰的 如果一個圖G中 一條邊的兩個端點是相同的 那么稱為這條邊是環(huán) 如圖5 4中的邊 v3 v3 是環(huán) 圖的基本概念 如果兩個端點之間有兩條以上的邊 那么稱為它們?yōu)槎嘀剡?如圖5 4中的邊 v1 v2 v2 v1 多重圖 一個無環(huán) 無多重邊的圖稱為簡單圖 一個無環(huán) 有多重邊的圖稱為多重圖 以點v為端點的邊的個數(shù)稱為點v的度 次 記作d v 如圖5 4中d v1 3 d v2 4 d v3 4 d v4 3 度為零的點稱為弧立點 度為1的點稱為懸掛點 懸掛點的邊稱為懸掛邊 度為奇數(shù)的點稱為奇點 度為偶數(shù)的點稱為偶點 端點的度d v 點v作為端點的邊的個數(shù)奇點 d v 奇數(shù) 偶點 d v 偶數(shù) 懸掛點 d v 1 懸掛邊 與懸掛點連接的邊 孤立點 d v 0 空圖 E 無邊圖 V v1 v2 v3 v4 v5 v6 v7 d v1 3 d v2 5 d v3 4 d v4 4 d v5 1 d v6 3 d v7 0 其中v5為懸掛點 v7為孤立點 圖5 7 定理5 1所有頂點度數(shù)之和等于所有邊數(shù)的2倍 證明 因為在計算各個點的度時 每條邊被它的兩個端點個用了一次 定理5 2在任一圖中 奇點的個數(shù)必為偶數(shù) 證明 設(shè)V1 V2分別是圖G中奇點和偶點的集合 由定理5 1 有 因為是偶數(shù) 也是偶數(shù) 因此 也必是偶數(shù) 從而V1中的點數(shù)是偶數(shù) 圖的連通性 鏈 由兩兩相鄰的點及其相關(guān)聯(lián)的邊構(gòu)成的點邊序列 如 v0 e1 v1 e2 v2 e3 v3 vn 1 en vn v0 vn分別為鏈的起點和終點 記作 v0 v1 v2 v3 vn 1 vn 簡單鏈 鏈中所含的邊均不相同 初等鏈 鏈中所含的點均不相同 也稱通路 圈 若v0 vn則稱該鏈為開鏈 否則稱為閉鏈或回路或圈 簡單圈 如果在一個圈中所含的邊均不相同初等圈 除起點和終點外鏈中所含的點均不相同的圈 v1 v2 v4 v3 v5 v6 v7 初等鏈 v1 v2 v3 v6 v7 v5 初等圈 v1 v2 v3 v5 v4 v1 簡單鏈 v1 v2 v3 v4 v5 v3 簡單圈 v4 v1 v2 v3 v5 v7 v6 v3 v4 以后除特別聲明 均指初等鏈和初等圈 v1 v2 v3 v4 v5 不連通圖 v1 v5 v4 v3 v2 v6 連通圖 圖中任意兩點之間均至少有一條通路 否則稱為不連通圖 連通圖 有向圖 關(guān)聯(lián)邊有方向弧 有向圖的邊a u v 起點u 終點v 路 若有從u到v不考慮方向的鏈 且各方向一致 則稱之為從u到v的路 初等路 各頂點都不相同的路 初等回路 u v的初等路 連通圖 若不考慮方向是無向連通圖 強連通圖 任兩點有路 基本概念 例一擺渡人欲將一只狼 一頭羊 一籃菜從河西渡過河到河?xùn)| 由于船小 一次只能帶一物過河 并且狼與羊 羊與菜不能獨處 給出渡河方法 解 用四維0 1向量表示 人 狼 羊 菜 在河西岸的狀態(tài) 在河西岸則分量取1 否則取0 共有24 16種狀態(tài) 在河?xùn)|岸的狀態(tài)類似記作 由題設(shè) 狀態(tài) 0 1 1 0 0 0 1 1 0 1 1 1 是不允許的 從而對應(yīng)狀態(tài) 1 0 0 1 1 1 0 0 1 0 0 0 也是不允許的 以可允許的10個狀態(tài)向量作為頂點 將可能互相轉(zhuǎn)移的狀態(tài)用線段連接起來構(gòu)成一個圖 根據(jù)此圖便可找到渡河方法 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 河西 人 狼 羊 菜 河?xùn)| 人 狼 羊 菜 將10個頂點分別記為A1 A2 A10 則渡河問題化為在該圖中求一條從A1到A10的路 從圖中易得到兩條路 A1A6A3A7A2A8A5A10 A1A6A3A9A4A8A5A10 圖的矩陣表示 1 鄰接矩陣Adjacencymatrix表示圖中兩點之間的相互關(guān)系兩點之間有弧或邊的 用1表示 否則用0表示 構(gòu)成一個矩陣A 有向圖 v1 v7 v2 v5 v3 v4 v6 v8 v9 矩陣A的元素全為0的行所對應(yīng)的點稱為匯點上圖v8矩陣A的元素全為0的列所對應(yīng)的點稱為源點上圖v1 v9 5 2樹和最小支撐樹 一 樹及其性質(zhì)在各種各樣的圖中 有一類圖是十分簡單又非常具有應(yīng)用價值的圖 這就是樹 例5 3已知有六個城市 它們之間要架設(shè)電話線 要求任意兩個城市均可以互相通話 并且電話線的總長度最短 如果用六個點v1 v6代表這六個城市 在任意兩個城市之間架設(shè)電話線 即在相應(yīng)的兩個點之間連一條邊 這樣 六個城市的一個電話網(wǎng)就作成一個圖 表示任意兩個城市之間均可以通話 這個圖必須是連通圖 并且 這個圖必須是無圈的 否則 從圈上任意去掉一條邊 剩下的圖仍然是六個城市的一個電話網(wǎng) 圖5 2 1是一個不含圈的連通圖 代表了一個電話線網(wǎng) 圖5 2 1 v6 v3 v4 v2 v5 v1 樹及其性質(zhì) 樹 既簡單又很有用樹 一個無圈的連通圖 組織結(jié)構(gòu)圖 榮國公 賈代善 賈赦 賈政 賈璉 賈珠 賈寶玉 賈環(huán) 賈蘭 定理 定理1 設(shè)G V E 是一個樹 p G 2 則G中至少有兩個懸掛點 定理2 圖G V E 是一個樹的充要條件是G不含圈 且恰有p 1條邊 定理3 圖G V E 是一個樹的充要條件是G是連通圖 且q G p G 1 定理4 圖G V E 是一個樹的充要條件是任意兩個頂點之間恰有一條鏈 推論 從一個樹中去掉任意一條邊 則余下的圖是不連通的 在樹中不相鄰的兩個點間添上一條邊 則恰好得到一個圈 圖的支撐樹 設(shè)圖T V E 是圖G V E 的一個支撐子圖 如果T是一個樹 則稱T是G的一個支撐樹定理5 圖G有支撐樹的充要條件是圖G是連通的 破圈法 任取一個圈 從中去掉一條邊 再對余下的圖重復(fù)直到不再含圖時為止 破圈法 避圈法 在圖中任取一條邊 找到一條與之不構(gòu)成圈的邊 再找一條前兩邊不構(gòu)成圈的邊重復(fù)直到不再能進行為止取出的邊數(shù)為p 1條 避圈法 最小支撐樹問題 給定圖G V E 對G中的每一條邊 vi vj 相應(yīng)地有一個數(shù)wij 則稱這樣的圖為賦權(quán)圖wij稱為邊 vi vj 上的權(quán)權(quán)是與邊有關(guān)的數(shù)量指標 可以是距離 時間 費用等 賦權(quán)圖不僅指出各個點之間的鄰接關(guān)系 而且同時也表示出各點之間的數(shù)量關(guān)系廣泛應(yīng)用于解決工程技術(shù)及管理等領(lǐng)域的最優(yōu)化問題最小支撐樹問題就是賦權(quán)圖上的最優(yōu)化問題之一 設(shè)有一個連通圖G V E 每一邊e vi vj 有一個非負權(quán)w e wij wij 0 如果T V E 是G的一個支撐樹 稱E 中所有邊的權(quán)之和為支撐樹T的權(quán) 記為w T 如果支撐樹T 的權(quán)w T 是G的所有支撐樹的權(quán)中最小者 則稱T 是G的最小支撐樹 最小樹 即 式中對G的所有支撐樹T取最小 最小支撐樹問題就是要求G的最小支撐樹 方法有二 避圈法Kruskal破圈法常見求賦權(quán)圖的最小樹 例5 4某廠內(nèi)聯(lián)結(jié)六個車間的道路網(wǎng)如下所示 已知每條路的長 要求沿道路架設(shè)聯(lián)結(jié)六個車間的電話線網(wǎng) 使電話線的總長最小 v1 v2 v4 v6 v3 v5 6 5 7 1 5 2 3 4 4 避圈法求最小支撐樹 v1 v2 v4 v6 v3 v5 1 5 2 3 4 i 1 E0 從E中選最小權(quán)邊 依次選最小權(quán)邊 并使之不構(gòu)成圈 共選5條邊 v1 v2 v4 v6 v5 6 5 7 1 5 2 3 4 4 最后 電話線總長1 2 3 4 5 15 v3 破圈法求最小支撐樹 任取一個圈 從中去掉一條權(quán)最大的邊 依次重復(fù) 直到不含圈為止 v1 v2 v4 v6 v5 6 5 7 1 5 2 3 4 4 最后 電話線總長1 2 3 4 5 15 v3 矩陣計算方法 T T T T T T T T T T T T T T T T T T T T T 矩陣計算結(jié)果 一 引言最短路徑問題是圖論中十分重要的最優(yōu)化問題之一 它作為一個經(jīng)常被用到的基本工具 可以解決生產(chǎn)實際中的許多問題 比如城市中的管道鋪設(shè) 線路安排 工廠布局 設(shè)備更新等等 也可以用于解決其它的最優(yōu)化問題 5 3最短路問題 例5 6如圖所示的單行線交通網(wǎng) 每弧旁的數(shù)字表示這條單行線的距離 現(xiàn)在某人要從v1出發(fā) 通過這個交通網(wǎng)到達v8 求使總距離最短的旅行線路 v1 v7 v2 v5 v3 v4 v6 v8 v9 路很多 v1 v7 v2 v5 v3 v4 v6 v8 v9 1 10 2 4 17 6 1 6 13 3 2 1 3 4 13 3 2 10 10 6 31 哪一條最短 最短路算法 如果P是D中從vs到vi的最短路 vi是P中的一個點 那么從vs沿P到vi的路是從vs到vi的最短路 1 圖形的標號法2 所有wij 0的情形 Dijkstra法1959 1 圖形的標號法 先標出離終點最近的一段 然后標號與該點距離最短的點 繼續(xù)逆推至始點 C4 A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 6 8 7 6 6 6 8 8 2 2 2 2 5 5 3 3 3 3 3 3 4 4 3 5 1 0 4 3 7 5 9 7 6 8 13 10 9 13 12 16 18 從A到G的最短路為 A B1 C2 D1 E2 F2 G 2 Dijkstra法 基本思路 從vs出發(fā) 逐步地向外探尋最短路 執(zhí)行過程中 與每個點對應(yīng) 記錄下一個數(shù) 稱為此點的標號 它或者表示從vs到該點的最短路的權(quán) 稱為P標號 或者是從vs到該點的最短路的權(quán)的上界 稱為T標號 方法的每一步是修改T標號 并且把某一個具T標號的點改變?yōu)榫逷標號的點 從而使D中具P標號的點多一個 如此經(jīng)過p 1步 就可以求出從vs到各點的最短路 Dijkstra法具體步驟 開始 i 0 令S0 vs P vs 0 vs 0 對每一個v vs 令T v v M 令k s1 如果Si V 算法終止 這時 對每個v Si d vs v P v 否則轉(zhuǎn)入步驟22 考察每個使 vk vj A且vj Si的點vj 如果T v P vk wkj 則把T vj 修改為P vk wkj 把 vj 修改為k 否則轉(zhuǎn)入步驟3 3 令T vji min T vj 如果T vji 則把vji的T標號變?yōu)镻標號P vji T vji 令Si 1 SiU vji k ji 把i換成i 1 轉(zhuǎn)入步驟1 否則終止 這時對每一個 而對每一個v Si d vs v T v v1 v2 v3 v4 v5 v6 v7 v8 0 v2 v3 v4 v5 v6 v7 v8 P T 0 0 M M M M M M M v1 v7 v2 v5 v3 v4 v6 v8 v9 若T v P vk wkj則T v P vk wkj vj 修改為k找到min T vj 將其T P標號P vj T vj S v1 6 3 1 1 1 1 1 v4 v3 11 4 3 5 3 5 v2 6 2 6 v5 10 5 9 5 12 5 9 v7 10 v6 12 v8 v1到v8最短路V13258 求s到t的最短路 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 0 S PQ s 2 3 4 5 6 7 t s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 0 S PQ s 2 3 4 5 6 7 t s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s PQ 2 3 4 5 6 7 t X X X s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s PQ 2 3 4 5 6 7 t X X X s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 PQ 3 4 5 6 7 t X X X s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 PQ 3 4 5 6 7 t X X X X 33 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 PQ 3 4 5 6 7 t X X X X 33 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 6 PQ 3 4 5 7 t X X X X 33 44 X X 32 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 6 PQ 3 4 5 7 t X X X 44 X X 33 X 32 s 3 t 2 6 7 4 5 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 6 7 PQ 3 4 5 t X X X 44 X 35 X 59 X 24 X 33 X 32 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 6 7 PQ 3 4 5 t X X X 44 X 35 X 59 X X 33 X 32 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 6 7 PQ 4 5 t X X X 44 X 35 X 59 X X 51 X 34 X 33 X 32 s 3 t 2 6 7 4 5 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 6 7 PQ 4 5 t X X X 44 X 35 X 59 X X 51 X 34 X 33 X 32 24 s 3 t 2 6 7 4 5 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 5 6 7 PQ 4 t X X X 44 X 35 X 59 X X 51 X 34 24 X 50 X 45 X 33 X 32 s 3 t 2 6 7 4 5 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 5 6 7 PQ 4 t X X X 44 X 35 X 59 X X 51 X 34 24 X 50 X 45 X 33 X 32 s 3 t 2 6 7 4 5 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 4 5 6 7 PQ t X X X 44 X 35 X 59 X X 51 X 34 24 X 50 X 45 X 33 X 32 s 3 t 2 6 7 4 5 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 4 5 6 7 PQ t X X X 44 X 35 X 59 X X 51 X 34 X 50 X 45 X 33 X 32 24 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 4 5 6 7 t PQ X X X 44 X 35 X 59 X X 51 X 34 X 50 X 45 X 33 X 32 s 3 t 2 6 7 4 5 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0 S s 2 3 4 5 6 7 t PQ X X X 44 X 35 X 59 X X 51 X 34 X 50 X 45 X 33 X 32 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 求從1到8的最短路徑 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 w1 0 min c12 c14 c16 min 0 2 0 1 0 3 min 2 1 3 1X 1 4 p4 1 p4 1 p1 0 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 4 min c12 c16 c42 c47 min 0 2 0 3 1 10 1 2 min 2 3 11 3 2X 1 2 4 p2 2 p1 0 p4 1 p2 2 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 min c13 c23 c25 c47 min 0 3 2 6 2 5 1 2 min 3 8 7 3 3X 1 2 4 6 p6 3 p2 2 p4 1 p1 0 p6 3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 6 min c23 c25 c47 c67 min 2 6 2 5 1 2 3 4 min 8 7 3 7 3X 1 2 4 6 7 p7 3 p2 2 p4 1 p1 0 p6 3 p7 3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 6 7 min c23 c25 c75 c78 min 2 6 2 5 3 3 3 8 min 8 7 6 11 6X 1 2 4 5 6 7 p5 6 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 6 7 min c23 c53 c58 c78 min 2 6 6 9 6 4 3 8 min 8 15 10 11 8X 1 2 3 4 5 6 7 p3 8 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 3 4 6 7 min c38 c58 c78 min 8 6 6 4 3 7 min 14 10 11 10X 1 2 3 4 5 6 7 8 p8 10 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 p8 10 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 3 4 6 7 8 1到8的最短路徑為 1 4 7 5 8 長度為10 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 p8 10 三 含有負權(quán)的最短路的求法 例 求從v1到v8的最短路 0 1 2 3 0 5 2 7 1 1 5 0 5 2 7 3 1 5 6 8 3 2 6 1 3 5 1 1 2 1 2 1 1 7 3 3 v1 v2 v3 v4 v5 v6 v7 v8 0 5 2 7 3 1 5 6 從v1到v8的最短路的長度為 6從v1到v8的最短路線為 v8 v6 v3 v1 應(yīng)用舉例 設(shè)備更新問題 某企業(yè)使用一臺設(shè)備 在每年年初 企業(yè)領(lǐng)導(dǎo)部門就要決定是購置新的 還是繼續(xù)使用舊的 若購置新設(shè)備 就要支付一定的購置費用 若繼續(xù)使用舊的 則需支付一定的維修費用 現(xiàn)在的問題是如何制定一個幾年之內(nèi)的設(shè)備更新計劃 使得總的支付費用最少 我們用一個五年之內(nèi)要更新某種設(shè)備的計劃為例 若已知該種設(shè)備在各年年初的價格如下表 還知使用不同時間的設(shè)備所需要的維修費用如下表 可供選擇的設(shè)備更新方案顯然是很多的 例如 每年都購置一臺新設(shè)備 則其購置費用為11 11 12 12 13 59 而每年支付的維修費用為5 五年合計為25 于是5年的總費用為59 25 84再如 每1 3 5年各購進一臺 此時設(shè)備購置費用為11 12 13 36 維修費用為5 6 5 6 5 27 5年總費用為36 27 63 如何制定總費用最省的設(shè)備更新計劃呢 轉(zhuǎn)化為最短路問題 用點代表 第i年年初購進一臺新設(shè)備 這樣上述設(shè)備更新問題就變?yōu)?在有向賦權(quán)圖G V E F 圖解如下 中求v1到v6的最短路問題 由實際問題可知 設(shè)備使用三年后應(yīng)當(dāng)更新 因此刪除該圖中v1到v5 v1到v6 v2到v6的連線 又設(shè)備使用一年后就更新則不劃算 因此再刪除該圖中v1v2 v2v3 v3v4 v4v5 v5v6五條連線后得到 從上圖中容易得到v1到v6只有兩條路 v1v3v6和v1v4v6 而這兩條路都是v1到v6的最短路 五年的總費用為53 例揀貨路徑問題Pickpath 貨架分布要揀貨物 第1步從第1通道到第2通道每條路徑代表圖中的一條邊 第2步找出從第2通道到第3通道的每條路徑 第3步找出從第3通道到第4通道的每條路徑 第4步找出從第4通道到完成的每條路徑 Findtheshortestpathoftheassociatedgraph Theshortestpathontheassociatedgraphgivesanefficientpickpathinwarehouse 對應(yīng)圖的最短路給出了倉庫的有效揀選路徑 5 4網(wǎng)絡(luò)的最大流 5 4 1網(wǎng)絡(luò)的最大流的概念網(wǎng)絡(luò)流一般在有向圖上討論定義網(wǎng)絡(luò)上支路的容量為其最大通過能力 記為cij 支路上的實際流量記為fij圖中規(guī)定一個發(fā)點s 一個收點t節(jié)點沒有容量限制 流在節(jié)點不會存儲容量限制條件 0 fij cij平衡條件 5 4網(wǎng)絡(luò)的最大流 圖中規(guī)定一個發(fā)點s 一個收點t 節(jié)點沒有容量限制 流在節(jié)點不會存儲 容量限制條件 0 fij cij 平衡條件 滿足上述條件的網(wǎng)絡(luò)流稱為可行流 總存在最大可行流當(dāng)支路上fij cij 稱為飽和弧 v f 為可行流的流量最大流問題也是一個線性規(guī)劃問題 定義 設(shè)f是一個可行流 是vs從vt到的一條鏈 若 滿足下列條件 則 是可行流的一條增廣鏈 1 弧 vi vj 上 即 中每一條弧是非飽和弧 2 弧 vi vj 上 即 中每一條弧是非零流弧 定義 把網(wǎng)絡(luò)分割為兩個成分的弧的最小集合 其中一個成分包含s點 另一個包含t點 一般包含s點的成分中的節(jié)點集合用V表示 包含t點的成分中的節(jié)點集合用V表示截量集容量是指截量集中前向弧的容量之和 福特 富克森定理 網(wǎng)絡(luò)的最大流等于最小截量集容量 5 4 2確定網(wǎng)絡(luò)最大流的標號法 從任一個初始可行流出發(fā) 如0流基本算法 找一條從s到t點的增廣鏈 若在當(dāng)前可行流下找不到增廣鏈 則已得到最大流增廣鏈中與s到t方向一致的弧稱為前向弧 反之后向弧 增廣過程 前向弧f ij fij 后向弧f ij fij 增廣后仍是可行流 最大流最小截量的標號法步驟 第一步 標號過程 找一條增廣鏈1 給源點s標號 s q s 表示從s點有無限流出潛力2 找出與已標號節(jié)點i相鄰的所有未標號節(jié)點j 若 1 i j 是前向弧且飽和 則節(jié)點j不標號 2 i j 是前向弧且未飽和 則節(jié)點j標號為 i q j 表示從節(jié)點i正向流出 可增廣q j min q i cij fij 3 j i 是后向弧 若fji 0 則節(jié)點j不標號 4 j i 是后向弧 若fji 0 則節(jié)點j標號為 i q j 表示從節(jié)點j流向i 可增廣q j min q i fji 最大流最小截量的標號法步驟 3 重復(fù)步驟2 可能出現(xiàn)兩種情況 1 節(jié)點t尚未標號 但無法繼續(xù)標記 說明網(wǎng)絡(luò)中已不存在增廣鏈 當(dāng)前流v f 就是最大流 所有獲標號的節(jié)點在V中 未獲標號節(jié)點在V中 V與V間的弧即為最小截量集 算法結(jié)束 2 節(jié)點t獲得標號 找到一條增廣鏈 由節(jié)點t標號回溯可找出該增廣鏈 到第二步 最大流最小截量的標號法步驟 第二步 增廣過程1 對增廣鏈中的前向弧 令f f q t q t 為節(jié)點t的標記值2 對增廣鏈中的后向弧 令f f q t 3 非增廣鏈上的所有支路流量保持不變第三步 抹除圖上所有標號 回到第一步一次只找一條增廣鏈 增廣一次換一張圖最后一次用廣探法 以便找出最小截量集 最大流最小截量集的標號法舉例 s s 6 2 6 3 1 4 1 s s 5 2 2 5 2 4 2 s s 3 2 3 最小截量集 5 5最小費用最大流問題 在實際的網(wǎng)絡(luò)系統(tǒng)中 當(dāng)涉及到有關(guān)流的問題的時候 我們往往不僅僅考慮的是流量 還經(jīng)常要考慮費用的問題 比 如一個鐵路系統(tǒng)的運輸網(wǎng)絡(luò)流 即要考慮網(wǎng)絡(luò)流的貨運量最大 又要考慮總費用最小 最小費用最大流問題就是要解決這一類問題 我們首先考察 在一個網(wǎng)絡(luò)D中 當(dāng)沿可行流f的一條增廣鏈 以調(diào)整量 1改進f 得到的新可行流f 的流量 有v f v f 1 而此時總費用b f 比b f 增加了 設(shè)一個網(wǎng)絡(luò)D V A C 對于每一個弧 vi vj A 給定一個單位流量的費用bij 0 網(wǎng)絡(luò)系統(tǒng)的最小費用最大流問題 是指要尋求一個最大流f 并且流的總費用達到最小 結(jié)論 如果可行流f在流量為v f 的所有可行流中的費用最小 并且 是關(guān)于f的所有增廣鏈中的費用最小的增廣鏈 那么沿增廣鏈 調(diào)整可行流f 得到的 我們將叫做這條增廣鏈的費用 新可行流f 也是流量為v f 的所有可行流中的最小費用流 依次類推 當(dāng)f 是最大流時 就是所要求的最小費用最大流 顯然 零流f 0 是流量為0的最小費用流 尋求最小費用流 總可以從零流f 0 開始 下面的問題是 如果已知f是流量為v f 的最小費用流 那么就要去尋找關(guān)于f的最小費用增廣鏈 對此 重新構(gòu)造一個賦權(quán)有向圖M f 其頂點是原網(wǎng)絡(luò)D的頂點 而將D中的每一條弧 vi vj 變成兩個相反方向的弧 vi vj 和 vj vi 并且定義M f 中弧的權(quán)wij為 并且將權(quán)為 的弧從M f 中略去 這樣 在網(wǎng)絡(luò)D中尋找關(guān)于f的最小費用增廣鏈就等于價于在M f 中尋求從vs到vt的最短路 算法開始 取零流f 0 0 一般地 如果在第K 1步得到最小費用流f K 1 則構(gòu)造圖M f k 1 在圖M f k 1 中 尋求從vs到vt的最短路 如果存在最短路 則f k 1 就是最小費用最大流 如果存在最短路 則在原網(wǎng)絡(luò)D中得到相對應(yīng) 一一對應(yīng) 的增廣鏈 0 在增廣鏈 上對f k 1 進行調(diào)整 取調(diào)整量 令 得到一個新的可行流f k 在對f k 重復(fù)以上的步驟 直到D中找不到相對應(yīng)的增廣鏈時為止 例求圖5 5 1所示網(wǎng)絡(luò)中的最小費用最大流 弧旁的權(quán)是 bij cij 圖5 5 1 解 1 取初始可行流為零流f 0 0 構(gòu)造賦權(quán)有向圖M f 0 求出從vs到vt的最短路 vs v2 v1 vt 如圖5 5 1a中雙箭頭所示 圖5 5 1a 2 在原網(wǎng)絡(luò)D中 與這條最短路相對應(yīng)的增廣鏈為 vs v2 v1 vt 3 在 上對f 0 0 進行調(diào)整 取 5 得到新可行流f 1 如圖5 5 1b所示 按照以上的算法 依次類推 可以得到f 1 f 2 f 3 f 4 流量分別為5 7 10 11 并且分別構(gòu)造相對應(yīng)的賦權(quán)有向圖M f 1 M f 2 M f 3 M f 4 由于在M f 4 中已經(jīng)不存在從vs到vt的最短路 因此 可行流f 4 v f 1 11是最小費用最大流 M f 1 圖5 5 1c M f 2 圖5 5 1e 8 8 10 3 4 3 2 0 7 7 10 2 5 5 圖5 5 1f f 3 v f 3 10 v1 vs v2 v3 vt ApplicationsofNetworkOptimization網(wǎng)絡(luò)最優(yōu)化模型的應(yīng)用 網(wǎng)絡(luò)在交通 電子和通訊網(wǎng)絡(luò)遍及我們?nèi)粘Ｉ畹母鱾€方面 網(wǎng)絡(luò)規(guī)劃也廣泛用于解決不同領(lǐng)域中的各種問題 如生產(chǎn) 分配 項目計劃 廠址選擇 資源管理和財務(wù)策劃等等 網(wǎng)絡(luò)規(guī)劃為描述系統(tǒng)各組成部分之間的關(guān)系提供了非常有效直觀和概念上的幫助 廣泛應(yīng)用于科學(xué) 社會和經(jīng)濟活動的每個領(lǐng)域中 Networkrepresentation網(wǎng)絡(luò)表述 這種描述還有其他應(yīng)用嗎 TypesofNetworkOptimizationProblem網(wǎng)絡(luò)最優(yōu)化問題類型 MinimumCostNetworkFlowModel最小費用流問題MaximumFlowProblems最大流問題ShortestPathProblem最短路問題MinimumSpanningTreeProblem最小支撐樹問題 MinimumCostNetworkFlowModel最小費用流問題 最小費用流問題的構(gòu)成 節(jié)點 nodes 供應(yīng)點 需求點 轉(zhuǎn)運點 弧 arcs 目標 通過網(wǎng)絡(luò)滿足需求提供供應(yīng) 最小化流的總成本 AssumptionsofMinimumCostNetworkFlow最小費用流問題的假設(shè) 至少一個供應(yīng)點一個需求點剩下都是轉(zhuǎn)運點通過弧的流只允許沿著箭頭方向流動 通過弧的最大流量取決于該弧的容量網(wǎng)絡(luò)中有足夠的弧提供足夠容量 使得所有在供應(yīng)點中產(chǎn)生的流都能夠到達需求點在流的單位成本已知前提下 通過每一條弧的流的成本和流量成正比 CharacteristicofSolution解的特征 具有可行解的特征 在以上的假設(shè)下 當(dāng)且僅當(dāng)供應(yīng)點所提供的流量總和等于需求點所需要的流量總和時 最小費用流問題有可行解 具有整數(shù)解的特征 只要其所有的供應(yīng) 需求和弧的容量都是整數(shù)值 那么任何最小費用流問題的可行解就一定有所有流量都是整數(shù)的最優(yōu)解 DistributionUnlimitedCo 無限配送公司 無限配送公司的最小成本流問題的電子表格模型 實際舉例 NetworkSimplexMethod網(wǎng)絡(luò)單純形法 實際運用中解決比較大型問題時需要用不同的方法 網(wǎng)絡(luò)單純形法可以用來解決那些對于單純形法來說太大而無法解決的大型問題 ExcelSolver軟件中沒有網(wǎng)絡(luò)單純形法 但是其他的線性規(guī)劃的商業(yè)軟件包通常都有這種方法 SomeApplications一些實際