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

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

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

和v5

分別表示計(jì)劃期的始點(diǎn)和終點(diǎn)（x5

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

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

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

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

到v5

的最短路問題。按照最短路算法可得最短路{v1,v2,v3,v5}，即計(jì)劃期內(nèi)機(jī)器更新最優(yōu)計(jì)劃為第1年、第3年初各購進(jìn)一臺(tái)新機(jī)器，4年總的支付費(fèi)用為6.8萬元。選址問題。選址問題是指為一個(gè)或幾個(gè)服務(wù)設(shè)施在一定區(qū)域內(nèi)選定它的位置，使某一指標(biāo)達(dá)到最優(yōu)值。選址問題的數(shù)學(xué)模型依賴于設(shè)施可能的區(qū)域和評(píng)判位置優(yōu)劣的標(biāo)準(zhǔn)，有許多不同類型的選址問題。比較簡(jiǎn)單的兩類選址問題是中心問題和重心問題。

中心問題：有些公共服務(wù)設(shè)施（例如一些緊急服務(wù)型設(shè)施如急救中心、消防戰(zhàn)等）的選址，要求網(wǎng)絡(luò)中最遠(yuǎn)的被服務(wù)點(diǎn)距離服務(wù)設(shè)施的距離盡可能小。例如：某城市要建立一個(gè)消防站，為該市所屬的七個(gè)區(qū)服務(wù)，如下圖所示。問應(yīng)設(shè)在那個(gè)區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最短。解：(1)用Floyd算法求出距離矩陣D=(dij)vv：

(2)計(jì)算在各點(diǎn)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)求出頂點(diǎn)vk，使，則vk

就是要求的建立消防站的地點(diǎn)。因?yàn)镾(v3)=6最小，故應(yīng)將消防站設(shè)在v3

處。此點(diǎn)稱為圖的中心點(diǎn)。

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

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

模型建立與求解用Floyd算法求出任意兩個(gè)居民點(diǎn)vi,vj

之間的最短距離,并用dij

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

vk

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

,vt

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

(2)計(jì)算各頂點(diǎn)作為選礦廠的總運(yùn)力m(vi)

(3)求vk

使，則vk

就是選礦廠應(yīng)設(shè)之礦點(diǎn)。此點(diǎn)稱為圖的重心或中位點(diǎn)。作業(yè)某公司在六個(gè)城市C1，…C6有分公司，從Ci到Cj的直接航程票記在下述矩陣的（i,j）位置上。該公司想要一張任兩城市間的票價(jià)最便宜的路線表，試作出這樣的表格實(shí)驗(yàn)作業(yè)

生產(chǎn)策略問題：現(xiàn)代化生產(chǎn)過程中，生產(chǎn)部門面臨的突出問題之一，便是如何選取合理的生產(chǎn)率。生產(chǎn)率過高，導(dǎo)致產(chǎn)品大量積壓，使流動(dòng)資金不能及時(shí)回籠；生產(chǎn)率過低，產(chǎn)品不能滿足市場(chǎng)需要，使生產(chǎn)部門失去獲利的機(jī)會(huì)。可見，生產(chǎn)部門在生產(chǎn)過程中必須時(shí)刻注意市場(chǎng)需求的變化，以便適時(shí)調(diào)整生產(chǎn)率，獲取最大收益。

某生產(chǎn)廠家年初要制定生產(chǎn)策略，已預(yù)知其產(chǎn)品在年初的需求量為a=6萬單位，并以b=1萬單位/月速度遞增。