最短路應(yīng)用問題課件

1、最短路應(yīng)用問題課件 又如果已知不同役齡機器年末的處理價格如下表所示，那末在這計劃期內(nèi)機器的最優(yōu)更新計劃又會怎樣？第1年末第2年末第3年末第4年末機器處理價（萬元）2.01.61.31.1 解：關(guān)于第一問，把該問題看成一個最短路問題。設(shè) v1 和 v5 分別表示計劃期的始點和終點（x5 可理解為第4年年末）。圖中各邊 (vi , vj) 表示在第 i 年初購進(jìn)的機器使用到第 j 年初（即第 j 1 年底），邊旁的數(shù)字由表中的數(shù)據(jù)得到。 關(guān)于第二問，類似于第一問，可轉(zhuǎn)化為求下圖中從 v1 到 v5 的最短路問題。 按照最短路算法可得最短路 v1, v2, v3, v5，即計劃期內(nèi)機器更新最優(yōu)計劃為

2、第 1 年、第 3 年初各購進(jìn)一臺新機器，4 年總的支付費用為 6.8萬元。 選址問題選址問題。選址問題是指為一個或幾個服務(wù)設(shè)施在一定區(qū)域內(nèi)選定它的位置，使某一指標(biāo)達(dá)到最優(yōu)值。選址問題的數(shù)學(xué)模型依賴于設(shè)施可能的區(qū)域和評判位置優(yōu)劣的標(biāo)準(zhǔn)，有許多不同類型的選址問題。比較簡單的兩類選址問題是中心問題和重心問題。 中心問題：有些公共服務(wù)設(shè)施（例如一些緊急服務(wù)型設(shè)施如急救中心、消防戰(zhàn)等）的選址，要求網(wǎng)絡(luò)中最遠(yuǎn)的被服務(wù)點距離服務(wù)設(shè)施的距離盡可能小。例如：某城市要建立一個消防站，為該市所屬的七個區(qū)服務(wù)，如下圖所示。問應(yīng)設(shè)在那個區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最短。解：(1) 用 Floyd 算法求出距離矩陣 D

3、= (dij)vv： 05 . 15 . 55 . 86475 . 10475 . 45 . 25 . 55 . 54032475 . 8730571065 . 42502545 . 24720375 . 5710530D (2) 計算在各點 vi 設(shè)立服務(wù)設(shè)施的最大服務(wù)距離 S(vi) ，i = 1, 2, , v有：S(v1) = 10，S(v2) = 7，S(v3) = 6，S(v4) = 8.5，S(v5) = 7，S(v6) = 7，S(v7) = 8.5。 (3) 求出頂點 vk，使 ，則 vk 就是要求的建立消防站的地點。因為 S(v3) = 6最小，故應(yīng)將消防站設(shè)在 v3 處。

4、此點稱為圖的中心點中心點。 max)(1ijjidvS)(min)(1iikvSvS選址問題選址問題2 2 現(xiàn)準(zhǔn)備現(xiàn)準(zhǔn)備在在 n 個個居民點居民點v1, v2, , vn中設(shè)置一銀中設(shè)置一銀行行. .問設(shè)在哪個點問設(shè)在哪個點, ,可使最大服務(wù)距離最小可使最大服務(wù)距離最小? ? 若設(shè)若設(shè)置兩個銀行置兩個銀行, ,問設(shè)在哪兩個點問設(shè)在哪兩個點? ? 模型假設(shè)模型假設(shè) 假設(shè)各假設(shè)各個個居民點都有條件設(shè)置銀居民點都有條件設(shè)置銀行行, ,并有路相連并有路相連, ,且路長已知且路長已知. . 模型建立與求解模型建立與求解 用用Floyd算法求出任意兩算法求出任意兩個個居民點居民點vi , vj 之間的最短

5、距離之間的最短距離, ,并用并用dij 表示表示. . 設(shè)置一個銀行設(shè)置一個銀行, ,銀行設(shè)銀行設(shè)在在 vi 點點的最大服務(wù)的最大服務(wù)距離為距離為.,.,2 , 1,max1niddijnji求求k, ,使使.min1inikdd 即若設(shè)置一個銀行即若設(shè)置一個銀行, ,則銀行設(shè)在則銀行設(shè)在 vk 點點, ,可使最可使最大服務(wù)距離最小大服務(wù)距離最小. . 設(shè)置兩個銀行設(shè)置兩個銀行, ,假設(shè)銀行設(shè)假設(shè)銀行設(shè)在在vs , vt 點點使最使最大服務(wù)距離最小大服務(wù)距離最小. .記記.,minmax),(1jkiknkddjid則則s, ,t 滿足：滿足：).,(min),(1jidtsdnji進(jìn)一步進(jìn)一

6、步, ,若設(shè)置多個銀行呢？若設(shè)置多個銀行呢？ 重心問題：有些設(shè)施（例如一些非緊急型的公共服務(wù)設(shè)施，如郵局、學(xué)校等）的選址，要求設(shè)施到所有服務(wù)對象點的距離總和最小。一般要考慮人口密度問題，要使全體被服務(wù)對象來往的平均路程最短。例如，某礦區(qū)有七個礦點，如下圖所示。已知各礦點每天的產(chǎn)礦量q(vj)（標(biāo)在圖的各頂點上），現(xiàn)要從這七個礦點選一個來建造礦廠，問應(yīng)選在哪個礦點，才能使各礦點所產(chǎn)的礦運到選礦廠所在地的總運力（千噸公里）最小。 解：(1) 用 Floyd 算法求出距離矩陣 D = (dij)vv： (2) 計算各頂點作為選礦廠的總運力 m(vi) (3) 求 vk 使 ，則 vk 就是選礦廠應(yīng)設(shè)

7、之礦點。此點稱為圖的重心重心或中位點中位點。 vidvqvmijjji , , 2 , 1 ,)()(1)(min)(1iikvmvm作業(yè)某公司在六個城市某公司在六個城市C1，C6有分公司，從有分公司，從Ci到到Cj的直接航程票記在下述矩陣的（的直接航程票記在下述矩陣的（i,j）位置上。該公）位置上。該公司想要一張任兩城市間的票價最便宜的路線表，司想要一張任兩城市間的票價最便宜的路線表，試作出這樣的表格試作出這樣的表格 055252510550102025251001020402010015252015050102540500實驗作業(yè)實驗作業(yè) 生產(chǎn)策略問題生產(chǎn)策略問題：現(xiàn)代化生產(chǎn)過程中，生產(chǎn)部門面臨的突出問題之一，便是如何選取合理的生產(chǎn)率。生產(chǎn)率過高，導(dǎo)致產(chǎn)品大量積壓，使流動資金不能及時回籠；生產(chǎn)率過低，產(chǎn)品不能滿足市場需要，使生產(chǎn)部門失去獲利的機會?？梢?，生產(chǎn)部門在生產(chǎn)過程中必須時刻注意市場需求的變化，以便適時調(diào)整生產(chǎn)率，獲取最大收益。 某生產(chǎn)廠家年初要制定生產(chǎn)策略，已預(yù)知其產(chǎn)品在年初的需求量為a=6萬單位，并以b=1萬單位/月速度遞增。若