基于Floyd最短路徑算法的教材中心選址問題

趙麗娜　李慧

摘 要 針對(duì)日益多元化的教育裝備，校區(qū)分散、規(guī)模龐大的高校必須考慮其購買、管理、維護(hù)成本，因此，裝備中心的選址尤為重要。依據(jù)Floyd算法，深入探討裝備中心的選址問題，并給出量化的計(jì)算結(jié)果，為教育裝備的管理工作提供依據(jù)。

關(guān)鍵詞 教育裝備；最短路徑；Floyd算法

中圖分類號(hào)：G48 文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1671-489X（2014）04-0040-03

以計(jì)算機(jī)和互聯(lián)網(wǎng)為代表的現(xiàn)代科技迅猛發(fā)展，越來越多的具有高科技含量的裝備在教育領(lǐng)域得到了廣泛應(yīng)用，使教育裝備的分配、管理、保障、運(yùn)輸和更新等工作變得更加復(fù)雜。這勢(shì)必要求學(xué)校的管理人員不僅要定性、更要定量地研究教育裝備的決策問題，否則將無法做出可行性決策，更不要提什么優(yōu)化了。同時(shí)，我國的社會(huì)發(fā)展階段和經(jīng)濟(jì)發(fā)展水平共同決定了教育經(jīng)費(fèi)的數(shù)目是有限的，在保證日常教學(xué)和科研的前提下，如何盡可能地壓縮管理成本是教育裝備管理工作中面臨的難題。

因此，本文以如何使教育裝備在運(yùn)輸過程中的成本最低為切入點(diǎn)，提出教育裝備中心選址的最優(yōu)化問題，采用Floyd最短路徑算法實(shí)現(xiàn)其求解，為教育裝備的管理工作提供科學(xué)依據(jù)。

1 數(shù)學(xué)模型

圖論的產(chǎn)生和發(fā)展經(jīng)歷了200多年歷史，1736年瑞士著名數(shù)學(xué)家歐拉（L.Euler）提出并解決了“哥尼斯堡七橋問題”，標(biāo)志著圖論的起源[1]。隨著現(xiàn)代生產(chǎn)和科學(xué)技術(shù)的迅猛發(fā)展，特別是計(jì)算機(jī)的出現(xiàn)和互聯(lián)網(wǎng)的普及，使圖論方法得以快速擴(kuò)展，圖論已成為現(xiàn)代數(shù)學(xué)科學(xué)中的一門引人注目的新興學(xué)科，滲透到物理學(xué)、化學(xué)、電工學(xué)、管理學(xué)、控制論、信息論等諸多學(xué)科[2-3]。

最短路徑的求取是圖論中的一個(gè)典型問題。所謂最短路徑是指在指定網(wǎng)絡(luò)中兩點(diǎn)間的一條距離最小的路[4]。在求解網(wǎng)絡(luò)上任意節(jié)點(diǎn)間最短路徑的方法中，學(xué)術(shù)界一致公認(rèn)的較好的算法是Dijkstra和Floyd算法。這兩個(gè)方法的主要區(qū)別是：Dijkstra算法可以計(jì)算從圖中某一點(diǎn)到其他各點(diǎn)的最短路徑；Floyd算法主要用于計(jì)算圖中所有點(diǎn)之間的最短路徑。顯然，在研究教育裝備運(yùn)輸問題時(shí)，可以采用Dijkstra方法進(jìn)行計(jì)算，從而得到裝備中心到目標(biāo)學(xué)校之間的最短路徑。

當(dāng)目標(biāo)學(xué)校有多個(gè)校區(qū)時(shí)，裝備中心地址的選擇必須考慮多方面因素，其中最基本的一點(diǎn)是保證該裝備中心到所有校區(qū)的最短路徑之和最小。此時(shí)，如果采用狄克斯屈拉算法，需要計(jì)算備選地址和各個(gè)校區(qū)之間的最短距離，該過程需要重復(fù)多次，且計(jì)算繁瑣；而計(jì)算圖中所有點(diǎn)之間的最短路徑正是Floyd算法所“擅長”的。因此，本文在研究教育裝備中心的選址問題時(shí)，優(yōu)選Floyd算法。

表1中每行的合計(jì)數(shù)表示教材配送中心建于該校區(qū)時(shí)，滿足所有校區(qū)每學(xué)期教學(xué)需要的大學(xué)英語教材運(yùn)輸?shù)膬?cè)千米數(shù)。從表中可以看出C列的合計(jì)數(shù)最小，表明當(dāng)把教材配送中心建于C校區(qū)時(shí)，教材運(yùn)輸?shù)膬?cè)千米數(shù)最小，為107 500。

3 結(jié)論

雖然規(guī)模龐大的高校校區(qū)比較分散，但是每學(xué)年在每個(gè)校區(qū)開設(shè)的專業(yè)和在校生規(guī)模基本保持不變，這就保證了每個(gè)校區(qū)每學(xué)年需要的教育裝備數(shù)目基本保持穩(wěn)定。因此，高校在建設(shè)裝備中心時(shí)的選址問題必須充分考慮如何使總的運(yùn)輸成本最低，往往一個(gè)錯(cuò)誤的決策將導(dǎo)致在以后每次裝備運(yùn)輸中都產(chǎn)生浪費(fèi)。本文依據(jù)Floyd最短路徑算法給出了定量計(jì)算，通過本文的實(shí)例相信可以為每位管理者提供嶄新的思路。

參考文獻(xiàn)

[1]李慧.教育裝備運(yùn)籌規(guī)劃[M].北京：北京大學(xué)出版社，2010：100-116.

[2]辛宇.基于運(yùn)籌學(xué)圖論的物流網(wǎng)絡(luò)優(yōu)化研究[J].中國外資，2011（6）：125-127.

[3]蔣智凱.淺談運(yùn)籌學(xué)教學(xué)[J].重慶科技學(xué)院學(xué)報(bào)：社會(huì)科學(xué)版，2010（24）：176-177.

[4]徐俊明.圖論及其應(yīng)用[M].3版.北京：中國科學(xué)技術(shù)大學(xué)出版社，2010：84-90.

[5]唐建清，鄒國霞.基于Floyd算法的旅游路徑智能選擇系統(tǒng)設(shè)計(jì)[J].中國科技信息.2006（14）：101-103

[6]楊軍慶，安容瑾.基于弗洛伊德算法的各院校間最短路徑問題的求解[J].甘肅科技縱橫，2010（5）：28-29

[7]王櫻，徐雨明，王靜.校園道路網(wǎng)最短路徑的分析與實(shí)現(xiàn)[J].衡陽師范學(xué)院學(xué)報(bào)，2004，12（6）：77-79.