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

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