基于最短路徑問題在企業(yè)設(shè)備更新中的應(yīng)用

1、基于最短路徑問題在企業(yè)設(shè)備更新中的應(yīng)用摘要：介紹通過應(yīng)用書本中最短路徑的算法，來解決企業(yè)中設(shè)備的更新?lián)Q代問題。文中給出了企業(yè)設(shè)備更新中的數(shù)學(xué)模型，舉例說明了如何更新企業(yè)中設(shè)備，使得企業(yè)的投入最小，即最大限度地減少企業(yè)的成本。本例也說明了用數(shù)據(jù)結(jié)構(gòu)中的算法在解決實(shí)際問題中的應(yīng)用是十分廣泛、重要的。關(guān)鍵詞：最短路徑；Dijkstra算法;企業(yè)設(shè)備更新1. 問題的提出1.1問題的實(shí)質(zhì)設(shè)備更新問題。某企業(yè)使用某種設(shè)備，在每年的年初，企業(yè)領(lǐng)導(dǎo)部門就要決定是購置新的，還是繼續(xù)使用舊的。若購置新設(shè)備，就要支付一定的購置費(fèi)用；若繼續(xù)使用舊設(shè)備，則需支付一定的維修費(fèi)用?，F(xiàn)在的問題是如何制定一個(gè)幾年之內(nèi)的設(shè)備更新

2、計(jì)劃，使得總的支付費(fèi)用最少。1.2問題的意義由于現(xiàn)代企業(yè)競爭形勢的日益嚴(yán)峻，使得企業(yè)要降低生產(chǎn)成本，以取得最大限度利潤。而生產(chǎn)材料價(jià)格的透明化、生產(chǎn)力成本的固定化，迫使企業(yè)從生產(chǎn)設(shè)備著手來考慮生產(chǎn)成本的問題。設(shè)備更新問題，這對一個(gè)單位、公司來說是一筆較大的資金，所以如何使設(shè)備每年的投入最少，這是一個(gè)最短路徑問題，該問題可以使用Dijkstra算法來解決。1.3問題的分析在帶權(quán)連通平面圖中求最短路徑，是圖論的基本問題之一，在實(shí)際的工作中具有很重要的意義。對該問題的兩個(gè)比較典型的算法是Dijkstra算法。由于Dijkstra算法適合于較為復(fù)雜的帶權(quán)連通圖，所以在本文中應(yīng)用了最短路徑求解中的Dij

3、kstra算法，來解決如何以最低的代價(jià)換取最大的經(jīng)濟(jì)利潤。2.算法的基本概念2.1 Dijkstra算法基本思想把頂點(diǎn)集V分為兩組，令S表示已求出最短路徑的頂點(diǎn)集合為第一組，其余尚未確定最短路徑的頂點(diǎn)集合T為第二組。初始狀態(tài)時(shí)，集合S中只包含源點(diǎn)V，T中含除源點(diǎn)之外的其余頂點(diǎn)，此時(shí)各頂點(diǎn)的當(dāng)前最短路徑長度為源點(diǎn)到該結(jié)點(diǎn)的弧上的權(quán)值。然后不斷從集合T中選取到頂點(diǎn)V路徑長度最短的頂點(diǎn)u加入到集合S中，集合S中每加入一個(gè)新的u，都要修改頂點(diǎn)V到集合T中剩余頂點(diǎn)的最短路徑長度的值，集合T中各頂點(diǎn)新的最短路徑長度值為原來的最短路徑的值加上u到該頂點(diǎn)的路徑長度值中的較小值。重復(fù)此過程，直到集合T中的頂點(diǎn)全

4、部加入集合S為止。2.2 Dijkstra算法實(shí)現(xiàn)過程假設(shè)用帶權(quán)的鄰接矩陣arcs表示帶權(quán)有向圖，arcsij表示弧<vi,vj>上的權(quán)值。若<vi,vj>不存在，則置<vi,vj>為(在計(jì)算機(jī)上可用允許的最大值代替)。S為已找到從v出發(fā)的最短路徑的終點(diǎn)的集合，它的初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各頂點(diǎn)(終點(diǎn))vi可能達(dá)到的最短路徑長度的初值為：Di=arcsLoacate Vex(G,v)i viV。選擇vj,使得Dj=MinDi| vV-S，vj就是當(dāng)前求得的一條從v出發(fā)的最短路徑的終點(diǎn)，令S=Sj。修改從v出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最

5、短路徑長度。Dj+arcsjk<Dk，則修改Dk為Dk=Dj+arcsjk。重復(fù)操作以上步驟共n-1次。由此求得從v到圖上其余各頂點(diǎn)的最短路徑。3.分析問題3.1建立數(shù)學(xué)模型現(xiàn)在用一個(gè)簡單的數(shù)學(xué)模型來說明。假設(shè)某企業(yè)中，我們用一個(gè)五年之內(nèi)要更新某種設(shè)備的計(jì)劃為例來說明，若已知這種設(shè)備在每年年初的價(jià)格為：年限第1年第2年第3年第4年第5年單價(jià)（萬元）1111121213使用不同年限的設(shè)備所需要的維修費(fèi)用為：使用年限0112233445維修費(fèi)用(萬元)5681118可供選擇的設(shè)備更新方案顯然是很多的。例如，每年都購置一臺新設(shè)備，則其購置費(fèi)用為：11+11+12+12+13=59。而每年支付的

6、維修費(fèi)用為5，五年合計(jì)25。于是五年總的支付費(fèi)用為59+25=84。又如決定在第1、3、5年各購進(jìn)一臺，這個(gè)方案的設(shè)備購置費(fèi)用為：11+12+13=36，維修費(fèi)用為5+6+5+6+5=27。五年總的支付費(fèi)用為36+27=63。如何制定方案使得總的支付費(fèi)用最少呢？可以把這個(gè)問題轉(zhuǎn)化為求最短路徑問題，見下圖，用Vi代表“第i年年初購進(jìn)一臺新設(shè)備”這種狀態(tài)。假設(shè)一頂點(diǎn)V6可理解為第五年年底。從Vi，Vi+1，.，V6各畫一條弧?；?Vi，Vj)表示第i年年初購進(jìn)的設(shè)備一直使用到第j年年初(第j-1年年底)。每條弧的權(quán)可按已知資料(例如給定的兩張表)計(jì)算出來。例如(V1，V4)是第1年年初購進(jìn)設(shè)備(支

7、付購置費(fèi)11)，一直使用到第3年年底(支付維修費(fèi)5+6+8=19)，故(V1，V4)上的權(quán)值為30。進(jìn)而轉(zhuǎn)化為帶權(quán)連通圖，如下圖所示。這樣，制定一個(gè)最優(yōu)的設(shè)備更新計(jì)劃的問題就等價(jià)于尋求從V1到V6的最短路徑問題。3.2算法設(shè)計(jì)思想首先設(shè)兩個(gè)集合，S是最短距離已經(jīng)確定的V中的頂點(diǎn)集；T=V-S是最短距離尚未確定的頂點(diǎn)集。將第1年年初V1視為設(shè)備更新的起點(diǎn)，先把V1計(jì)入一個(gè)集合S中，從V1開始，遍歷其余頂點(diǎn)尋找最短路徑。此時(shí)與V1相連的5個(gè)頂點(diǎn)中，路徑最短的為V1到V2的距離，所以將V2計(jì)入集合S內(nèi)，然后從S中的所有頂點(diǎn)出發(fā)，尋找下一個(gè)路徑最短且頂點(diǎn)不在集合S中的頂點(diǎn)。即在V-S中選minDi=K

8、(iV-S),將K加入S中：S=SK，T=T-K。調(diào)整Dn中各頂點(diǎn)的最短距離Dj：若Dj>DK+W(K, j),則Dj=DK+W(K,j)，否則不改變Dj的原來值。若T=V-S為空，或T=V-S中頂點(diǎn)的Dj全為終止，否則繼續(xù)。3.3算法實(shí)現(xiàn)輸入：頂點(diǎn)數(shù)；各頂點(diǎn)之間的路徑值。輸出：最優(yōu)方案，包括起始頂點(diǎn)、中間頂點(diǎn)、終止頂點(diǎn)及頂點(diǎn)之間的路徑值之和。方法：SN為布爾向量，當(dāng)i號頂點(diǎn)納入時(shí)Si=TRUE；Di初值為源點(diǎn)s到其它各頂點(diǎn)的直接距離。1）輸入頂點(diǎn)數(shù)：6；2）再輸入邊數(shù)：15；3）然后輸入每條邊的起點(diǎn)、終點(diǎn)及對應(yīng)權(quán)值；4）最后輸入源點(diǎn)序號。此過程為一個(gè)程序，其功能是：輸入n年年初設(shè)備的價(jià)

9、格與使用不同時(shí)間（年）的設(shè)備所需要的維修費(fèi)用，為該企業(yè)領(lǐng)導(dǎo)部門確定一個(gè)方案使得在n年內(nèi)為這臺機(jī)器支付的總費(fèi)用最少。3.4運(yùn)行結(jié)果及說明最后求得V1，V3，V6及V1，V4，V6均為最短路徑。即有兩個(gè)最優(yōu)方案：一個(gè)方案是第1年、第3年各購置一臺新設(shè)備。4.計(jì)算復(fù)雜度分析通過該算法編寫的程序已經(jīng)在Microsoft Visual C+6.0的運(yùn)行環(huán)境下編譯通過，并運(yùn)行成功，得出的結(jié)果與預(yù)期的相同，有兩條備選方案。第一個(gè)循環(huán)的時(shí)間復(fù)雜度是O(n)，第二個(gè)循環(huán)共進(jìn)行n-1次，每次執(zhí)行的時(shí)間是O(n)。所以總的時(shí)間復(fù)雜度是O(n2)。如果用帶權(quán)的鄰接表作為有向圖的存儲結(jié)構(gòu)，則顯然修改D的時(shí)間可以減少，但

10、由于在D向量中選擇最小分量的時(shí)間不變，所以總的時(shí)間仍為. O(n2)。5.結(jié)語Dijkstra算法總是做出在當(dāng)前看來最好的選擇，也就是說該算法并不是從整體上的最優(yōu)考慮，它做出的選擇只是在某種意義上的局部最優(yōu)選擇，但最終能得到整個(gè)問題的最優(yōu)解。Dijkstra算法不僅僅應(yīng)用于企業(yè)設(shè)備更新問題，還可應(yīng)用于其他很多地方，例如：網(wǎng)線和電線的輔設(shè)、管道的輔設(shè)等，用此算法都可以得到最優(yōu)的布線路徑，達(dá)到省時(shí)、省料、省力的目的。從此算法也可以看出，Dijkstra算法在現(xiàn)實(shí)生活中的應(yīng)用是十分廣泛的。參考文獻(xiàn):1嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)題集（C語言版）M.北京：清華大學(xué)出版社，1997.2譚浩強(qiáng).C語言程序設(shè)計(jì)（第二版）M.北京：清華大學(xué)出版社， 2000.3余祥宣，崔國華，鄒海明.計(jì)算機(jī)算法基礎(chǔ)（第二版）M.武漢：