運(yùn)籌學(xué)第六章圖與網(wǎng)絡(luò)分析.ppt

第六章圖與網(wǎng)絡(luò)分析 6 1圖的基本概念與數(shù)學(xué)模型6 2樹圖和圖的最小部分樹6 3最短路問題6 4中國(guó)郵路問題6 5網(wǎng)絡(luò)最大流問題6 6網(wǎng)絡(luò)模型的實(shí)際應(yīng)用 第六章圖與網(wǎng)絡(luò)分析 圖是一種模型 如公路 鐵路交通圖 通訊網(wǎng)絡(luò)圖等 圖是對(duì)現(xiàn)實(shí)的抽象 以點(diǎn)和線段的連接組合表示 6 1圖的基本概念和模型 一 概念 1 圖 點(diǎn)V和邊E的集合 用以表示對(duì)某種現(xiàn)實(shí)事物的抽象 記作G V E V v1 v2 vn E e1 e2 em 點(diǎn) 表示所研究的事物對(duì)象 邊 表示事物之間的聯(lián)系 v1 v2 v3 v4 v0 e1 e2 e3 e4 e5 e6 e7 e0 2 若邊e的兩個(gè)端點(diǎn)重合 則稱e為環(huán) 3 多重邊 若某兩端點(diǎn)之間多于一條邊 則稱為多重邊 4 簡(jiǎn)單圖 無環(huán) 無多重邊的圖稱為簡(jiǎn)單圖 5 鏈 點(diǎn)和邊的交替序列 其中點(diǎn)可重復(fù) 但邊不能重復(fù) 6 路 點(diǎn)和邊的交替序列 但點(diǎn)和邊均不能重復(fù) 7 圈 始點(diǎn)和終點(diǎn)重合的鏈 8 回路 始點(diǎn)和終點(diǎn)重合的路 9 連通圖 若一個(gè)圖中 任意兩點(diǎn)之間至少存在一條鏈 稱這樣的圖為連通圖 10 子圖 部分圖 設(shè)圖G1 V1 E1 G2 V2 E2 如果有V1 V2 E1 E2 則稱G1是G2的一個(gè)子圖 若V1 V2 E1 E2 則稱G1是G2的一個(gè)部分圖 11 次 某點(diǎn)的關(guān)聯(lián)邊的個(gè)數(shù)稱為該點(diǎn)的次 以d vi 表示 二 圖的模型 例 有甲 乙 丙 丁 戊 己六名運(yùn)動(dòng)員報(bào)名參加A B C D E F六個(gè)項(xiàng)目的比賽 如表中所示 打 的項(xiàng)目是各運(yùn)動(dòng)員報(bào)名參加比賽的項(xiàng)目 問 六個(gè)項(xiàng)目的比賽順序應(yīng)如何安排 才能做到使每名運(yùn)動(dòng)員不連續(xù)地參加兩項(xiàng)比賽 甲乙丙丁戊己 項(xiàng)目 人 ABCDEF 建立模型 解 項(xiàng)目作為研究對(duì)象 排序 設(shè)點(diǎn) 表示運(yùn)動(dòng)項(xiàng)目 邊 若兩個(gè)項(xiàng)目之間無同一名運(yùn)動(dòng)員參加 A B C D E F A C D E F B A F E D C B A C B F E D A F B C D E 順序 6 2樹圖和圖的最小部分樹 1 樹 無圈的連通圖稱為樹圖 簡(jiǎn)稱為樹 一 樹圖的概念 2 樹的特性 樹是邊數(shù)最多的無圈連通圖 在樹中任加一條邊 就會(huì)形成圈 樹是邊數(shù)最少的連通圖 在樹中任減一條邊 則不連通 3 圖的最小部分樹 定義 若G1是G2的一個(gè)部分圖 且為樹圖 則稱G1是G2的一個(gè)部分樹 G2 A B C D 5 4 7 3 6 5 5 7 6 G1 A C B D 定義 樹枝總長(zhǎng)為最短的部分樹稱為圖的最小部分樹 二 最小部分樹的求法 例 要在下圖所示的各個(gè)位置之間建立起通信網(wǎng)絡(luò) 試確定使總距離最佳的方案 樹枝 樹圖中的邊稱為樹枝 S A B C D E T 2 5 2 4 1 4 3 1 7 5 5 7 最小部分樹長(zhǎng)Lmin 14 1 避圈法 1 避圈法 將圖中所有的點(diǎn)分V為V兩部分 V 最小部分樹內(nèi)點(diǎn)的集合V 非最小部分樹內(nèi)點(diǎn)的集合 任取一點(diǎn)vi加粗 令vi V 取V中與V相連的邊中一條最短的邊 vi vj 加粗 vi vj 令vj V 重復(fù) 至所有的點(diǎn)均在V之內(nèi) 2 破圈法 任取一圈 去掉其中一條最長(zhǎng)的邊 重復(fù) 至圖中不存在任何的圈為止 S A B C D E T 2 5 2 4 1 4 3 1 7 5 5 7 最小部分樹長(zhǎng)Lmin 14 2 破圈法 6 3最短路問題 在圖示的網(wǎng)絡(luò)圖中 從給定的點(diǎn)S出發(fā) 要到達(dá)目的地T 問 選擇怎樣的行走路線 可使總行程最短 方法 Dijkstra D氏 標(biāo)號(hào)法 按離出發(fā)點(diǎn)的距離由近至遠(yuǎn)逐漸標(biāo)出最短距離和最佳行進(jìn)路線 S 1 求某兩點(diǎn)間最短距離的D Dijkstra 氏標(biāo)號(hào)法 2 4 7 S A B C D E T 2 5 2 4 1 4 3 1 7 5 5 7 0 2 4 4 7 8 9 14 13 5 9 4 最短路線 S A B E D T最短距離 Lmin 13 2 求任意兩點(diǎn)間最短距離的矩陣算法 構(gòu)造任意兩點(diǎn)間直接到達(dá)的最短距離矩陣D 0 dij 0 SABCDETS0254 A202 7 B520153 C4 10 4 D 75 015E 34107T 570 D 0 構(gòu)造任意兩點(diǎn)間直接到達(dá) 或者最多經(jīng)過1個(gè)中間點(diǎn)到達(dá)的最短距離矩陣D 1 dij 1 其中dij 1 min dir 0 drj 0 SABCDETS024498 A20237512B42014310C43105411D9745015E8534106T 121011570 D 1 i r j dir 0 drj 0 r dSE 1 min dSS 0 dSE 0 dSA 0 dAE 0 dSB 0 dBE 0 dSC 0 dCE 0 dSD 0 dDE 0 dSE 0 dEE 0 dST 0 dTE 0 8 例如 其中dij 2 min dir 1 drj 1 SABCDETS02448714A20236511B4201439C43105410D8645015E7534106T1411910560 D 2 i r j dir 1 drj 1 r 構(gòu)造任意兩點(diǎn)間最多可經(jīng)過3個(gè)中間點(diǎn)到達(dá)的最短距離矩陣D 2 dij 2 其中dij 3 min dir 2 drj 2 SABCDETS02448713A20236511B4201439C43105410D8645015E7534106T1311910560 D 3 i r j dir 2 drj 2 r 構(gòu)造任意兩點(diǎn)間最多可經(jīng)過7個(gè)中間點(diǎn)到達(dá)的最短距離矩陣D 3 dij 3 說明 一般 對(duì)于D k dij k 其中dij k min dir k 1 drj k 1 k 0 1 2 3 最多可經(jīng)過2k 1個(gè)中間點(diǎn) 其數(shù)列為 0 1 3 7 15 31 2k 1 收斂條件 當(dāng)D k 1 D k 時(shí) 計(jì)算結(jié)束 設(shè)網(wǎng)絡(luò)中有p個(gè)點(diǎn) 即有p 2個(gè)中間點(diǎn) 則2k 1 1 p 2 2k 1 k 1 log2 p 1 k K log2 p 1 1 計(jì)算到k lg p 1 lg2 1時(shí) 收斂 計(jì)算結(jié)束 例 有7個(gè)村鎮(zhèn)要聯(lián)合建立一所小學(xué) 已知各村鎮(zhèn)小學(xué)生的人數(shù)大致為S 30人 A 40人 B 20人 C 15人 D 35人 E 25人 T 50人 問 學(xué)校應(yīng)建在那一個(gè)地點(diǎn) 可使學(xué)生總行程最少 SABCDETS02448713A20236511B4201439C43105410D8645015E7534106T1311910560 L 30402015352550 人數(shù) 1325103088010359108651485 T 解 6 4中國(guó)郵路問題 問題 一名郵遞員從郵局出發(fā) 試選擇一條最短的投遞路線 v1 v2 v3 v4 v5 v6 v8 v7 v9 v10 v11 v12 v13 郵局 4 4 4 5 5 1 2 4 1 2 5 4 4 7 4 2 2 奇點(diǎn) 圖中次為奇數(shù)的點(diǎn)稱為奇點(diǎn) 偶點(diǎn) 圖中次為偶數(shù)的點(diǎn)稱為偶點(diǎn) 結(jié)論 最短投遞路線應(yīng)具有下述特征 若圖中所有的點(diǎn)均為偶點(diǎn) 則可不重復(fù)走遍所有街道 重復(fù)走的路線長(zhǎng)度應(yīng)不超過所在回路總長(zhǎng)度的一半 步驟 兩兩連接所有的奇點(diǎn) 使之均成為偶點(diǎn) 2 檢查重復(fù)走的路線長(zhǎng)度 是否不超過其所在回路總長(zhǎng)的一半 若超過 則調(diào)整連線 改走另一半 v1 v2 v3 v4 v5 v6 v8 v7 v9 v10 v11 v12 v13 郵局 4 4 4 5 5 1 2 4 1 2 5 4 4 7 4 2 2 投遞距離 L 60 18 78 6 5網(wǎng)絡(luò)最大流問題 一 網(wǎng)絡(luò)最大流中有關(guān)概念 有向圖 含有以箭頭指示方向的邊的網(wǎng)絡(luò)圖 弧 有向圖上的邊稱為弧 用 vi vj 表示 弧的容量 弧上通過負(fù)載的最大能力 簡(jiǎn)稱容量 以cij表示 流 加在網(wǎng)絡(luò)每條弧上的一組負(fù)載量 以fij表示 可行流 能夠通過網(wǎng)絡(luò)的負(fù)載量 通常應(yīng)滿足兩個(gè)條件 容量限制條件 對(duì)所有的弧 0 fij cij 中間點(diǎn)平衡條件 對(duì)任何一個(gè)中間點(diǎn) 流入量 流出量 發(fā)點(diǎn) 收點(diǎn) 中間點(diǎn) 流的起源點(diǎn)稱發(fā)點(diǎn) 終到點(diǎn)稱收點(diǎn) 其余的點(diǎn)稱中間點(diǎn) 最大流 能夠通過網(wǎng)絡(luò)的最大流量 割集 一組弧的集合 割斷這些弧 能使流中斷 簡(jiǎn)稱割 8 8 v1 vs v2 v3 v4 vt 7 5 9 4 9 9 2 0 6 1 5 5 10 8 0 vs 2 v2 2 v1 2 v3 1 v4 1 5 4 cij fij 割的容量 割集中各弧的容量之和 最小割 所有割集中容量之和為最小的一個(gè)割集 前向弧 一條發(fā)點(diǎn)到收點(diǎn)鏈中 由發(fā)點(diǎn)指向收點(diǎn)的弧 又稱正向弧 后向弧 一條發(fā)點(diǎn)到收點(diǎn)鏈中 由收點(diǎn)指向發(fā)點(diǎn)的弧 又稱逆向弧 增廣鏈 由發(fā)點(diǎn)到收點(diǎn)之間的一條鏈 如果在前向弧上滿足流量小于容量 即fij0 則稱這樣的鏈為增廣鏈 二 兩個(gè)定理定理 網(wǎng)絡(luò)的最大流量等于它的最小割集的容量 定理 當(dāng)網(wǎng)絡(luò)中不存在任何增廣鏈時(shí) 則網(wǎng)絡(luò)達(dá)到最大流狀態(tài) s t 6 4 5 3 4 4 8 7 設(shè)有如下增廣鏈 f 1 該網(wǎng)絡(luò)沒有達(dá)到最大流狀態(tài) 三 網(wǎng)絡(luò)最大流的標(biāo)號(hào)算法 Ford Fulkerson標(biāo)號(hào)算法 基本思想 尋找增廣鏈 改善流量分布 再重復(fù) 直到不存在任何增廣鏈為止 步驟 給始點(diǎn)標(biāo)號(hào) 0 從已標(biāo)號(hào)點(diǎn)i出發(fā) 看與其相關(guān)聯(lián)的未標(biāo)號(hào)點(diǎn)j上的弧 對(duì) 若有0 fij cij 則可對(duì)j點(diǎn)標(biāo)號(hào) 記 i j 其中 j min i cij fij 對(duì) 若有0 fji cij 也可對(duì)j點(diǎn)標(biāo)號(hào) 記 i j 其中 j min i fji 注 若有多個(gè)可標(biāo)號(hào)點(diǎn) 可任選其中之一 若標(biāo)號(hào)中斷 則得到最大流狀態(tài) 否則 重復(fù) 繼續(xù)標(biāo)號(hào) 至收點(diǎn)得到標(biāo)號(hào) 轉(zhuǎn) 當(dāng)收點(diǎn)得到標(biāo)號(hào) 則沿標(biāo)號(hào)得到的增廣鏈進(jìn)行流量調(diào)整 對(duì) f ij fij t 對(duì) f ij fij t 其余弧上的流量不變 重復(fù)上述過程 最小割集 已標(biāo)號(hào)點(diǎn)集合與未標(biāo)號(hào)點(diǎn)集合相連接的弧中 流量 容量的弧 8 8 v1 vs v2 v3 v4 vt 7 6 9 5 9 9 2 0 6 0 5 5 10 9 5 3 0 vs 1 v2 1 v1 1 最大流量 fmax 14 最小割集 v3 vt v2 v4 6 6網(wǎng)絡(luò)模型的實(shí)際應(yīng)用 例1 王經(jīng)理花費(fèi)12000元購買了一臺(tái)微型車 以后年度的維護(hù)費(fèi)用取決于年初時(shí)汽車的役齡 如表示 為避免使用舊車帶來較高的維護(hù)費(fèi)用 王經(jīng)理可選擇賣掉舊車 購買新車使用的方案 舊車的預(yù)計(jì)收入如表示 為簡(jiǎn)化計(jì)算 假定任何時(shí)刻購買新車都需花費(fèi)12000元 王經(jīng)理的目標(biāo)是使凈費(fèi)用最小 購置費(fèi) 維護(hù)費(fèi) 賣舊車收入 役齡 年 年維護(hù)費(fèi) 預(yù)計(jì)收入 單位 元 012345 200040005000900012000 70006000200010000 解 用網(wǎng)絡(luò)圖模型描述 歸結(jié)為最短路問題 7 7 7 7 7 1 2 3 4 5 6 12 12 12 12 21 21 21 31 31 44 1年初 5年末 例2 圖示島嶼與河岸有數(shù)座橋相聯(lián) 問至少需要炸毀幾座橋 可中斷兩岸的交通 A B C D E F A B C F E D 2 2 2 1 3 1 1 1 1 例3 有3根相同的軸A1 A2 A3 另有三根相同的齒輪B1 B2 B3 因?yàn)榫炔桓?不能做到任意的互相配合 其中A1能與B1 B2配合 A2能與B2 B3配合 A3能與B1 B3配合 要求確定合適的配合方案 以得到最多的配合數(shù) 將此問題歸為網(wǎng)絡(luò)最大流問題 A1 A2 A3 B1 B2 B3 1 1 1 1 1 1 S T 1 1 1 1 1 1