最短路擴展應(yīng)用問題

設(shè)備更新問題。某工廠的某臺機器可連續(xù)工作4年，決策者每年年初都要決定機器是否需要更新。若購置新的，就要支付一定的購置費用；若繼續(xù)使用，則要支付一定的維修與運行費用，而且隨著機器使用年限的增加費用逐年增多。計劃期（4年）中每年年初的購置價格及各個年限內(nèi)維修與運行費用由下表給出，試制訂今后4年的機器更新計劃，使總的支付費用最少。第i年初1234購置費（萬元）2.52.62.83.1使用年限1234每年的維修與運行費（萬元）11.524又如果已知不同役齡機器年末的處理價格如下表所示，那末在這計劃期內(nèi)機器的最優(yōu)更新計劃又會怎樣？年度第1年末第2年末第3年末第4年末機器處理價（萬元）2.01.61.31.1

解：關(guān)于第一問，把該問題看成一個最短路問題。設(shè)v1

和v5

分別表示計劃期的始點和終點（x5

可理解為第4年年末）。圖中各邊(vi

,vj)表示在第i年初購進的機器使用到第j年初（即第j

1年底），邊旁的數(shù)字由表中的數(shù)據(jù)得到。

關(guān)于第二問，類似于第一問，可轉(zhuǎn)化為求下圖中從v1

到v5

的最短路問題。按照最短路算法可得最短路{v1,v2,v3,v5}，即計劃期內(nèi)機器更新最優(yōu)計劃為第1年、第3年初各購進一臺新機器，4年總的支付費用為6.8萬元。選址問題。選址問題是指為一個或幾個服務(wù)設(shè)施在一定區(qū)域內(nèi)選定它的位置，使某一指標(biāo)達到最優(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=(dij)vv：

(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

處。此點稱為圖的中心點。

選址問題2現(xiàn)準(zhǔn)備在n個居民點v1,v2,…,vn中設(shè)置一銀行.問設(shè)在哪個點,可使最大服務(wù)距離最小?若設(shè)置兩個銀行,問設(shè)在哪兩個點?

模型假設(shè)假設(shè)各個居民點都有條件設(shè)置銀行,并有路相連,且路長已知.

模型建立與求解用Floyd算法求出任意兩個居民點vi,vj

之間的最短距離,并用dij

表示.⑴設(shè)置一個銀行,銀行設(shè)在vi點的最大服務(wù)距離為求k,使即若設(shè)置一個銀行,則銀行設(shè)在

vk

點,可使最大服務(wù)距離最小.⑵設(shè)置兩個銀行,假設(shè)銀行設(shè)在vs

,vt

點使最大服務(wù)距離最小.記則s,t滿足：進一步,若設(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è)之礦點。此點稱為圖的重心或中位點。作業(yè)某公司在六個城市C1，…C6有分公司，從Ci到Cj的直接航程票記在下述矩陣的（i,j）位置上。該公司想要一張任兩城市間的票價最便宜的路線表，試作出這樣的表格實驗作業(yè)

生產(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萬單位/月速度遞增。