用網(wǎng)絡(luò)技術(shù)求解教育裝備用戶周期費(fèi)用的最小值問(wèn)題

摘要 敘述使用網(wǎng)絡(luò)技術(shù)中的最短路徑法求解教育裝備全壽命周期最低費(fèi)用的方法，為使實(shí)用性和可操作性更強(qiáng)，專門介紹求最短路徑的Dijkstra算法。

關(guān)鍵詞 全壽命周期費(fèi)用；最短路徑；Dijkstra算法

中圖分類號(hào) G48 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號(hào) 1671-489X（2008）12-0001-03

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

1 網(wǎng)絡(luò)技術(shù)與最短路徑

對(duì)研究對(duì)象（事物）特征的描述，可以通過(guò)對(duì)事物的狀態(tài)以及與其他事物之間的關(guān)系來(lái)表示。用結(jié)點(diǎn)表示事物的狀態(tài)，而用結(jié)點(diǎn)間的連線（稱為“邊”）表示事物之間的關(guān)系就形成了一個(gè)網(wǎng)絡(luò)（圖1）。如果用結(jié)點(diǎn)（A、B、…F）代表裝備的壽命周期時(shí)間分界點(diǎn)，而在邊上標(biāo)注出費(fèi)用情況，就可以用網(wǎng)絡(luò)技術(shù)來(lái)解決裝備的壽命周期最小費(fèi)用問(wèn)題。

如果計(jì)算從A結(jié)點(diǎn)出發(fā)到達(dá)F結(jié)點(diǎn)的總費(fèi)用，A結(jié)點(diǎn)就稱為源結(jié)點(diǎn)，而F結(jié)點(diǎn)稱為目的結(jié)點(diǎn)。從源結(jié)點(diǎn)到目的結(jié)點(diǎn)可以有許多條不同的路徑，但其中有一條總費(fèi)用最低的路徑，稱為最短路徑。

2 最短路徑法

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

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

將前面推算的結(jié)果開(kāi)列在表2中，根據(jù)表中的數(shù)據(jù)就可以推出最小費(fèi)用路徑。

在表中可見(jiàn)，若選擇結(jié)點(diǎn)F為目的結(jié)點(diǎn)，則最短路徑的前一結(jié)點(diǎn)為結(jié)點(diǎn)E，總費(fèi)用為4；而結(jié)點(diǎn)E的前一結(jié)點(diǎn)為結(jié)點(diǎn)D，結(jié)點(diǎn)D的前一結(jié)點(diǎn)為結(jié)點(diǎn)A，其順序?yàn)镕-E-D-A。將該順序倒過(guò)來(lái)就是最短路徑順序A-D-E-F。

3 求解裝備壽命周期最小費(fèi)用問(wèn)題

為使問(wèn)題簡(jiǎn)化，我們只考慮裝備在使用階段的情況。而費(fèi)用則僅考慮購(gòu)置費(fèi)用和設(shè)備的維修費(fèi)用。設(shè)某學(xué)校需要在每年的年初時(shí)計(jì)劃更新購(gòu)置并常年維護(hù)使用一批教學(xué)設(shè)備。從當(dāng)年開(kāi)始將該設(shè)備的平均購(gòu)置費(fèi)用逐年變化情況列于表3，而該設(shè)備平均維修費(fèi)用逐年變化情況列于表4。

現(xiàn)在需要解決的問(wèn)題是，如果在第1年初購(gòu)置了該設(shè)備，那么在5年之內(nèi)的哪一年初更新購(gòu)置設(shè)備，可使得總體費(fèi)用最低。為此，設(shè)前5年年初時(shí)的標(biāo)號(hào)順序?yàn)锳、B、C、D、E，而第5年末或第6年初用F來(lái)表示。表5反映了5年使用周期內(nèi)的費(fèi)用情況。

圖3是將表5反映的情況轉(zhuǎn)換成的網(wǎng)絡(luò)圖。每個(gè)結(jié)點(diǎn)表示年初，每條邊上的數(shù)字為周期費(fèi)用。設(shè)A結(jié)點(diǎn)為源結(jié)點(diǎn)，F(xiàn)結(jié)點(diǎn)為目的結(jié)點(diǎn)，則上述需要解決的問(wèn)題就轉(zhuǎn)化成在該網(wǎng)絡(luò)圖中求最短路徑的問(wèn)題。

使用Dijkstra算法求最短路徑的過(guò)程開(kāi)列在表6中。圖4為求得的最短路徑圖。

在這個(gè)求解過(guò)程中應(yīng)注意幾個(gè)問(wèn)題：1）因?yàn)槊總€(gè)結(jié)點(diǎn)都不存在“不相鄰”結(jié)點(diǎn)，所以沒(méi)有出現(xiàn)∞值；2）這個(gè)網(wǎng)絡(luò)圖中的邊為有向邊，在計(jì)算路徑費(fèi)用時(shí)要沿著邊的指向進(jìn)行，不可逆向計(jì)算；3）計(jì)算出的最低費(fèi)用路徑有兩條，一條是A-B-F，另一條是A-D-F，兩條路徑的費(fèi)用都為3.8。這一結(jié)果說(shuō)明，如果在第1年初購(gòu)置了該設(shè)備，則在第2年初或第4年初更新該設(shè)備，使得到第5年末（或第6年初）時(shí)總費(fèi)用最低。但是，如果考慮到一臺(tái)設(shè)備的實(shí)際使用壽命應(yīng)大于1年，同時(shí)第5年后還要長(zhǎng)期使用這種設(shè)備，就應(yīng)選擇路徑A-D-F，即在第4年初更新設(shè)備較為合理。

參考文獻(xiàn)

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

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