用網絡技術求解教育裝備用戶周期費用的最小值問題

摘要 敘述使用網絡技術中的最短路徑法求解教育裝備全壽命周期最低費用的方法，為使實用性和可操作性更強，專門介紹求最短路徑的Dijkstra算法。

關鍵詞 全壽命周期費用；最短路徑；Dijkstra算法

中圖分類號 G48 文獻標識碼 A 文章編號 1671-489X（2008）12-0001-03

在教育裝備的研究領域里，人們已經熟知了裝備的全壽命周期費用（LCC，Life Cycle Cost）管理理論。全壽命周期一般是指設備的設計階段、生產階段、使用階段和退役階段，其費用涉及公司成本、用戶成本和社會成本[1]。作為教育裝備使用與管理者，更關心的是設備在使用階段和退役階段的費用問題；并希望找到一個方法，能夠在保證設備性能的基礎上產生最低費用。網絡技術中的最短路徑法可以解決這一問題。

1 網絡技術與最短路徑

對研究對象（事物）特征的描述，可以通過對事物的狀態以及與其他事物之間的關系來表示。用結點表示事物的狀態，而用結點間的連線（稱為“邊”）表示事物之間的關系就形成了一個網絡（圖1）。如果用結點（A、B、…F）代表裝備的壽命周期時間分界點，而在邊上標注出費用情況，就可以用網絡技術來解決裝備的壽命周期最小費用問題。

如果計算從A結點出發到達F結點的總費用，A結點就稱為源結點，而F結點稱為目的結點。從源結點到目的結點可以有許多條不同的路徑，但其中有一條總費用最低的路徑，稱為最短路徑。

2 最短路徑法

世界著名計算機科學家Dijkstra提出一個求解網絡最短路徑的計算方法[2]。首先定義，1）D(v)：從源結點到第v個結點當前的路徑費用值；2）p(v)：從源結點到結點v的當前最低費用路徑上v的前一結點標號；3）N：從源結點出發的已知最低費用路徑所歷經結點的集合；4）與第v個結點不相鄰結點形成邊的費用值視為∞。表1反映了用這一算法對圖1所示網絡求最短路徑的計算過程。當集合N中收集了網絡的全部結點時，表示從源結點開始到其他所有結點的最短路徑都已查找遍，計算就結束了。然后，從目的結點開始沿著反向費用最低路段追溯到源結點，這便是所要求的最短路徑。

在步驟0時，v=A，結點A的相鄰結點有B、C、D。這3個結點與結點A之間形成邊的費用分別為2、5、1；而且3個結點的前一結點的標號都是A。結點E和F與結點A不相鄰，所以D(E) = D(F) = ∞。在與結點A相鄰的3個結點中，只有邊AD的費用最低，即D(D) = 1，所以選擇邊AD為當前的最短路徑，將D結點納入集合N中。在步驟1，v = D，當前結點D的相鄰結點有B、C、E。這3個結點到結點A的總費用分別為3、4、2，所以選擇費用低的結點E為下一結點，并將結點E納入集合N中。同時注意到，從A結點直接到B結點的費用為2，比經過D結點再到B結點的費用低，所以到B結點的最低費用已經求得。但是由于每一步驟只能將一個求得的結點放入集合N，這里選擇先將結點E納入集合N。在步驟2，v = E，當前結點E的相鄰結點有C和F，從源結點A到這兩個結點的費用分別為3和4。但是與結點A到結點B的費用2相比還不是最低的，所以將結點B納入集合N。在步驟3，比較到C、F結點的費用，選擇將C納入集合N。最后將結點F納入集合N。此時，集合N中包含了全部結點，從中得到從源結點A到達所有其他結點的最低費用路徑（如圖2中的粗實線所示）。

將前面推算的結果開列在表2中，根據表中的數據就可以推出最小費用路徑。

在表中可見，若選擇結點F為目的結點，則最短路徑的前一結點為結點E，總費用為4；而結點E的前一結點為結點D，結點D的前一結點為結點A，其順序為F-E-D-A。將該順序倒過來就是最短路徑順序A-D-E-F。

3 求解裝備壽命周期最小費用問題

為使問題簡化，我們只考慮裝備在使用階段的情況。而費用則僅考慮購置費用和設備的維修費用。設某學校需要在每年的年初時計劃更新購置并常年維護使用一批教學設備。從當年開始將該設備的平均購置費用逐年變化情況列于表3，而該設備平均維修費用逐年變化情況列于表4。

現在需要解決的問題是，如果在第1年初購置了該設備，那么在5年之內的哪一年初更新購置設備，可使得總體費用最低。為此，設前5年年初時的標號順序為A、B、C、D、E，而第5年末或第6年初用F來表示。表5反映了5年使用周期內的費用情況。

圖3是將表5反映的情況轉換成的網絡圖。每個結點表示年初，每條邊上的數字為周期費用。設A結點為源結點，F結點為目的結點，則上述需要解決的問題就轉化成在該網絡圖中求最短路徑的問題。

使用Dijkstra算法求最短路徑的過程開列在表6中。圖4為求得的最短路徑圖。

在這個求解過程中應注意幾個問題：1）因為每個結點都不存在“不相鄰”結點，所以沒有出現∞值；2）這個網絡圖中的邊為有向邊，在計算路徑費用時要沿著邊的指向進行，不可逆向計算；3）計算出的最低費用路徑有兩條，一條是A-B-F，另一條是A-D-F，兩條路徑的費用都為3.8。這一結果說明，如果在第1年初購置了該設備，則在第2年初或第4年初更新該設備，使得到第5年末（或第6年初）時總費用最低。但是，如果考慮到一臺設備的實際使用壽命應大于1年，同時第5年后還要長期使用這種設備，就應選擇路徑A-D-F，即在第4年初更新設備較為合理。

參考文獻

[1]陳曉川，方明倫.制造業中產品全生命周期成本的研究概況綜述[J].機械工程學報:中文版，2002，38(11):17-25

[2]Kurose J，Ross K.Computer Networking：A Top-Down Approach Featuring the Internet[M].3rd Edition.2004，7