【天津大學】《運籌學》（精品課） P33 - 33. 最短路問題 教學錄像（2）

接下來我們來看一下最短路模型在實際中的一個應用舉例 先來看這樣一個例題 設備更新問題 這是書上119頁例題 我們看這個問題是怎麼來描述的 某個廠使用一種設備 每年年初設備科需要對該設備的更新與否作出決策 若購置新設備就需要支付購置費 而若需要繼續使用舊設備的話則需要支付維修費 而設備使用的年數越長 每年所需要的維修費就越多 現在若第一年年初購置了一臺新設備 問在這五年內如何來制定設備的更新計劃 以便使新設備購置費用和舊設備維修費的總費用最小 以至設備在五年內各年初它的價格如表一所示 然後設備使用不同年號的維修費用如表二所示 好 下面我們有兩張表格 這兩個表格是第一個表是購置費 就是在第一年第二年第三年第四年第五年各個年初的購置費 第二個表格給的是維修費 就隨着使用壽命的年長 那麼在不同的壽命期內各年的維修費 在第一年內使用的時候一年的維修費是5萬元 在第二個年頭使用的時候一年的維修費是6萬元 第三個年頭是8萬元等等 這個問題就要求做這樣一個決策 剛纔說到了五年內每一年年初分別做一個設備更新與否的決策 使得這五年內總的維修費用加上購置費用總費用最低 我們可以簡單地分析一下這個問題 想一想如果在這五年內一次也不更新的話行不行 是不是維修費整個的費用最小呢 顯然不一定 因爲我們會看到隨着設備使用壽命的延長 第二張表格到了最後一年的維修費它的價格可能都超過了還不如買一臺新設備的費用 所以一直不更新不是一個最佳的策略 那麼過於頻繁的更新同樣也不是一個最佳策略 如果過於頻繁的更新設備還沒用就把它扔掉了換新的 這樣的話維修費倒是不多 但是購置費會上來了 實際上是一種浪費 於是需要我們做這樣一個決策 到底在哪個年頭要做更新可以使得五年內總的費用最低 不能更新的過快 也不能更新的過慢 有這樣一個平衡問題 當然這個問題我們可能也可以用其他的一些模型來糾結 比如說零一規劃模型 因爲每一年年初都要做一個更新與否 可以用1來表示更新 用0來表示否 當然在這樣的話 我們同樣一個問題 我們看看能不能用圖論的方法來求解這個問題 下面我們就來做具體的分析 如果用圖論的方法來求解這樣一個實際問題的話 首先我們需要把這個圖來畫出來 我們簡單回顧一下 一個網絡圖它的構成要素是有三個要素 分別是節點 邊或者是弧 第三個是全 在這樣一個問題裏邊 我們看看怎麼樣用這三個要素來表示各種各樣的含義 或者說不同的要素分別都表示什麼樣的含義 先來看 由於這個問題是做一個五年的更新策略 五年的話一共涉及到實際上是六個時間點 那麼是不是我們可以用不同的節點來表示某一年的年初這樣一個時間點 所以一共應該有六個節點構成了節點集合 邊呢 每一條邊我們可以具體地來表示一種這樣的一個設備的使用過程 具體地來爲i到爲j這條邊可以表示 第i年年初購買一直用到第j年年初這樣一個設備的使用過程 當然如果這樣的話顯然就要求j是大於i的 並且i的取值是1-5 j的取值是2-6 這是第二個要素 第三個要素我們比較容易想到 那就是在設備使用過程中 在vi到vj這條邊表示的設備使用過程中 一共花了哪些錢 或者具體說就是第i年年初到第j年年初這期間所涉及到的總費用 這個費用顯然包括兩塊 一個是第i年年初的購買費 再加上這些年裏的維修費 這樣的話我們就把這個網絡圖的三個要素都明確了 下面我們具體地來畫一下這個網絡圖 先把六個節點畫上 v1 v2 v3 v4 v5 v6 那麼爲了進一步說明這個問題 我在這首先任意地畫了一條從起點v1到終點v6的一個路線 或者說一條通路 請同學們一塊來理解一下 這條路線是不是表示了一個什麼樣的具體的含義 按照我們剛纔對邊的定義 我們先看這樣一條路 v1到v2到v5到v6 那麼v1到v2這條邊表示設備在第一年年初當然要購買新設備 然後一直用到第二年年初就換新的 只用了一年 然後v2到v5這條邊表示第二年換了新設備 買新設備一直用 又用到了第五年又換新設備 然後最後一直用到期末 那麼這樣連在一起這樣一條路徑 v1到v2到v5到v6 我們一塊來理解一下它應該是表示一個什麼樣的含義呢 應該是表示一個五年內的一個具體的更新方案 或者說是更新策略 因爲這樣連在一起 你看第一年年初購買新設備用到第二年 然後換新的一直用到第五年到了第六年 所以每一條從起點到終點的一條路線 都表示了一個具體的方案 而到時候我們可以在每一條邊上 標上一定的全數 表示相應的設備使用過程中所涉及到的費用 那麼這條路的長度就表示什麼呢 或者說各條邊上的全數之和 就表示這個路對應的方案所涉及到的五年內的總費用 那麼剛纔說到了 從起點到終點有若干條路徑 每一條路徑有不同的長度 不同的長度代表了不同的方案所對應的各自的所需要的總花費 那麼哪一種方案最好 或者說哪一個方案它對應的總花費最小呢 它就是最好的 當然就是最短路了 所以這個問題我們就轉化爲了 從起點到終點這樣求一個最短路的這樣一個問題 好 下面我們進一步的把這個圖繼續畫完它 V1到V2有邊了 V1到V3是不是也應該可能存在一條邊 這個邊表示第一年年初購買用到第三年 也可能直接用到第四年 所以V1到V4有邊 V1到V5有邊 V1到V6也可能有邊 我們前面說過 這個Vi到Vz這條邊要求只要j大於i 那麼就有可能構成一條邊 我們甚至可以看到V1到V6這條邊 它又是一條從起點到終點的一條路 這條路的長度 代表這個路的所對應的一個方案的總倍 而這個方案是什麼呢 就是從起點從開始購買一臺新設備 中間不做任何的更新 然後一直用到期末 那麼顯然這條邊這個路對應這個方案的不一定是最佳的 好 這是起點出發的 我們再來看V2節點出發的邊應該有哪些呢 V2可以到V3 V2可以到V4 到V5 到V6 再看V3節點 到V4 到V5 到V6 都有可能 V4可以到V5 或者到V6 V5可以到V6 這樣的話我們就把所有的邊都給畫上了 最後我們再把各條邊上的全數給標上 前面曾經定義過 那麼每一條邊它對應的全數表示這個設備使用這樣一個過程中所發費的總費用 我們先來看第一條邊 V1到V2 表示的是第一年年初要購買新設備 然後用了一年用到第二年年初 請朋友們從這兩張表格裏邊來計算一下 這條邊所對應的全數應該是多少呢 應該是11加上5是16 因爲第一年年初購置費是11萬元 然後用了一年 這一年內的維修費是5萬元 所以加起來應該是16 再來看V1到V3的條邊 這個相當於還是在第一年年初購買 但是要比原來剛纔用到第二年來說要多了一年 直接用到了第三年年初 那這期間花了多少錢呢 11的購置費 再加上第一年年頭內它這個維修費是5萬元 又多用了一年 也就是說維修費呢又多了一個6萬元 所以這樣這三個數加起來應該是22 或者我們從這個16 剛纔這個標的V1到V2這條邊上的16來看 在16的基礎上又多用了一年 在第二個年頭多用了這一年的維修費呢是6萬元 所以16加6是22 同樣V1到V4呢是在22的基礎上又多用了一年 加上8萬元的維修費 所以是30 V1到V5應該是41 V1到V6呢 V1的基礎上又加了18 59 59我們先來理解 就表示剛纔說過從起點到終點 這樣一條路徑 中間不做任何更新 所需要的總費用是59萬元 這個數可能不是最小的 我們繼續來求V2幾點出發的邊上 各個邊的全數 V2如果到V3 那表示第二年年初購買新設備 它需要的花費呢是11萬元 然後呢 用了一年 這一年的維修費呢是5萬元 加起來是16 所以是16 再來看V2到V4 在原來16的基礎上又多用了一年 第二個年頭的維修費呢是6萬元 所以V2到V4的全數應該是22 V2到V5呢 又多加了8萬元 所以是30 V2到V6是41 依次累推 V3到V4 第三年的購置費是12萬元 用了一年的維修費呢是5萬元 所以是17 V3到V5呢 是 在17的基礎上又加了6 所以是23 V3到V6是 31 再來看V4節點出發 第四年購買新設備 購置費是12萬元 然後到V5的話用了一年 所以加上5是17 V4到V6呢 再加上6就是23了 最後一條邊 V5到V6表示 第五年年初購買費用是13萬元 然後用了一年的維修費是5萬元 加起來是18 到這爲止呢 我們就把所有邊上的全數有標上了 那麼整個的網絡圖呢 我們也就畫完整了 我們再來理解一下 看一下從起點到終點 現在會看到有好多條路徑 好多條路 每一條路呢都有自己的長度 而不同的路徑的這個長度呢 表示了相應的 這個對應的這個更新策略的花費 比如說V1到V2到V5到V6 我們最開始給的這條路 它的長度是多少呢 是6 加上30 加上18 這樣是64 是這樣一種策略的 更新了兩次 在中間過程中間兩次 這種費用是64 不是最小的 那麼最小的是哪個呢 所以我們需要求一下最短路 從起點V1到V6的最短路 我們可以用前面剛纔介紹的 狄克斯塔拉標號法來具體的求助了 這是整個的標號過程 通過反向追蹤呢 可以把最短路線找出來 同學們可以看到有兩條最短路線 長度呢都是53 我們來看一下這兩條最短路線是什麼 第一條V1到V3到V6 第二條呢是V1到V4到V6 所以我們結論就出來了 整個的五年內的最優的更新策略有兩種 第一種呢 除了在第一年年初要購買新設備以外 在第三年年初再購買一次新設備 更新一次設備 一直用到期末 第二種方案呢是 在第四年年初進行一次更新設備 用到期末 或者總的來說 最優策略呢 就是在第三年或者第四年年初上 更新一次 這樣的話可以使得總花費最小 最小總花費呢是50大萬元 這個問題呢就是一個最短路模型的一個應用 我們看這樣一個設備更新問題 它的問題描述裏面根本沒有最短路這幾個字眼 但是我們確實是可以用這樣一個方法 這樣一個模型 把它來非常方便地來求解出來 也是很形象很直觀地來求解出來 從中呢也可以看到 圖論的方法 它在實際的管理和決策的問題中 有非常重要的應用 好 這是一個例題 接下來我們繼續來看後面的例題 例十七 是關於一個選址的中心問題 我們具體地來看一個例題先來 一隻某地區的交通網絡如圖所示 其中呢節點代表居民小區 邊呢代表公路 邊上的權術呢爲小區間的公路的距離 現在問題是 想在整個居民區裏面要設一個區中心醫院 那麼應該建在哪個小區 可以使得離醫院最遠的那個小區 居民就診時走的路程最近 這樣一個實際的問題 這個問題呢後面我們會給出定義 實際上就是求一個圖的中心問題 那麼怎麼來求呢 按照要求 需要求一下 假設建在某一個節點的話 那麼其他的節點到該節點的最短距離 分別是多少 然後找最遠的那個最短距離 最小 從而確定最終的這個中心的選擇 所以這個問題實際上可以化爲一系列的求解最短路問題 具體來說 比如我們可以先求出 位一到其他所有個點的最短距離 假設把這個距離記作第一陣 在這兒的距離我們就指的是最短距離 陣是從一到七去指 表示七個節點 七個居民點 在這求得的七個距離中 再來求一個最大值 並且把它記作大寫的D位一 那麼這個D位一表示什麼含義呢 它就表示 假設醫院選址在位一的話 那麼距離這個醫院最遠的小區 它那個距離是多少呢 就是這個D位一 類似的我們可以依次地來求出D位二 D位三 以至到D位七 每一個D分別表示 如果醫院建在相應的位置 那麼距離這個醫院最遠的小區 它的距離分別是多少 把整個的計算過程 接下來我們用這樣一張表格來具體地表示出來 請同學們來觀察一下這個表格 先以位一爲例 那麼第一行的數據 分別就表示了 位一到位七各個點到位一的最短距離 分別是0 30 50 63 93 45 60 然後再來求最大值 93 那麼這個就表示D位一 這個93具體的含義就是 如果醫院建在位一的話 距離位一醫院最遠的小區 它的距離就是93 也就是5號小區 在這兒我們插一句話 這些數是怎麼求出來的呢 我們當然就可以用我們前面所講到的 迪克斯特拉標號法來具體地求出起點到其他各點的最短距離 因爲我們說最短路標號算法 中間節點標的這些數 分別也就表示了起點到中間這些節點的最短距離 那包括終點的 所以我們在一次標號 從起點標到終點的過程中 所有中間這些節點 包括終點的這些標的這些數 就都可以計算出來了 然後再求一個最大值 再來看第二行 第二行就是假設醫院建在位二的話 我們分別來求一下所有的居民點跟位二的最短距離 那麼在具體的實施過程中 如果用標號法迪克斯特拉標號法來具體計算的話 我們在這就要把位二看作網絡圖的起點 然後求一下位二到其他各個節點的最短距離 最終求得了30 0 20 33 63 15 30這樣一些數 在這些數中再求最大值是63 這63就表示如果醫院建在位二的話 距離位二最遠的那個小區的距離就63了 也是五號小區 依次類推 可以分別地來計算出醫院選擇在各個小區時 那麼醫院距離最遠的那個區域 分別在最表格的最右邊這一列裏面去計算出來 進一步的我們來求一下最小值是哪一個呢 就是在最右邊這一列所有的數中 最小值顯然是位六對應的這個數 所以最終的結論就是醫院應該建在位六這個區別點 因爲這樣的話可以使得距離醫院最遠的小區的距離 最小 比其他的節點建立醫院的話都要小 這個問題就是圖的中心問題 我們把這個問題一般化 此問題稱爲求圖的中心問題 中心問題一般應用於求某一些公共設施服務設施的一個選址問題 那麼要求距離網絡中最遠的那個被服務點的距離儘可能的小 一般的假設有一個網絡 D等於VAC 那麼V是由V1到Vn的n個節點來構成 如果我們令dij表示是從V1到Vj的距離 就指的最短距離 並且令dvi爲dij當j大於等於1小於等於n之後求最大值得到的一個數 i變爲1到n 然後呢 並進一步的如果dvi在所有的dvi中取之最小 那麼這個dvi就稱作網絡的中心 那麼這個呢就是我們對網絡中心的一個具體的定義 這個實際上就剛纔這道例題的一個一般化 在中心的基礎上我們可以再進一步的來求所謂的圖的中心問題 還拿剛纔這個例題爲例 如果我們進一步的已知各小區的人數分別爲600 1450 550 300 200和650 現在問題是醫院應該建在何處可以使得小區居民就診時所走的走路程最近 每一個小區的所有的居民在就診時所走的所有的路程之和加起來最近 這個時候如果滿足這個要求的話 那麼醫院應該選在哪一個位置呢 仍然是一個選擇問題 這個問題我們叫做正心問題 請同學們來想一想這個問題怎麼來考慮求解呢 實際上在上例的基礎上 我們也是先來求出vi所有居民到其他各個節點的按人數的總的距離 這個距離可以記得Qi乘以dij這麼來計算 其中Qi表示dI個小區的人數 而dij如前所示表示的是dI和dj個小區之間的距離 然後再按列求和 具體的求解過程我們接下來也是有這樣一張表格來給列出來的 先請同學們自己看一下這張表格都表示什麼含義 下面我們來一塊看一下具體含義 以18000爲例來解釋一下這個是什麼含義 這個表示如果醫院建在vi的話 我們由前面的結論可以知道 vi到v2的最短距離是30 vi這個小區有600個人 所以所有的居民 vi小區所有居民到達v2就醫醫的話 走的總里程應該是600乘以30 是這樣一個數 同樣下面這個數表示如果醫院建在v3的話 那麼vi的所有居民到達v3就醫的話 走走的所有里程 下面我們按列來看 每一列各含義以第一列爲例 如果醫院建在vi的話 各個小區的居民走到vi所有的總的里程按人數來算的話 就分別是各個數 第一列的各個數 最後面一行我們要注意了 它是前這一列中所有的這些數加起來得到的這樣一行 它顯然表示如果在相應的vi建立醫院的話 該地區所有的居民就診時走走的總路程 也就是說如果醫院建在vi的話 那麼該地區所有居民到vi這個小區去就診的話 總的里程應該是163050 如果建在vi是86550等等 那麼最小值我們來求一個就得到了vi這個數 所以表示如果醫院建在vi的話 那麼整個地區所有居民到vi就診 所走的總路程應該是最短的 所以最終選擇醫院建在vi 這就是圖的重心問題的一個具體的實例 接下來我們對它進行一般化 什麼叫圖的重心問題呢 一般的也是假設有一個網絡 D等於VAC Q多了一個要素 就是說原來的普通的網絡圖 我們有三個要素 VAC我都知道什麼含義了 其中這個Q我特別的解釋一下 表示節點上的權重構成的計算 像剛纔這個例子具體的來表示 就是每一個小區它的所有的居民的人數 然後令HVJ等於QICDIJ I從1加到N這樣一個數 因爲這個HVJ實際上就是剛纔這個例題中 表格最下面那一行 所有的這些數再從1到N 然後如果HVR等於 所有的HVJ中最小的那個數 則VR稱爲網絡的重心 好這就是網絡的重心問題 那麼剛纔我們講到的兩個問題 圖的中心問題和圖的重心問題 也是圖的最短路問題的一個延伸 算作最短路問題的一個應用 好那麼到這爲止 我們網絡分析的最短路問題就介紹完了 同學們下課