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

趙麗娜　李慧

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

關鍵詞 教育裝備；最短路徑；Floyd算法

中圖分類號：G48 文獻標識碼：B

文章編號：1671-489X（2014）04-0040-03

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

因此，本文以如何使教育裝備在運輸過程中的成本最低為切入點，提出教育裝備中心選址的最優化問題，采用Floyd最短路徑算法實現其求解，為教育裝備的管理工作提供科學依據。

1 數學模型

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

最短路徑的求取是圖論中的一個典型問題。所謂最短路徑是指在指定網絡中兩點間的一條距離最小的路[4]。在求解網絡上任意節點間最短路徑的方法中，學術界一致公認的較好的算法是Dijkstra和Floyd算法。這兩個方法的主要區別是：Dijkstra算法可以計算從圖中某一點到其他各點的最短路徑；Floyd算法主要用于計算圖中所有點之間的最短路徑。顯然，在研究教育裝備運輸問題時，可以采用Dijkstra方法進行計算，從而得到裝備中心到目標學校之間的最短路徑。

當目標學校有多個校區時，裝備中心地址的選擇必須考慮多方面因素，其中最基本的一點是保證該裝備中心到所有校區的最短路徑之和最小。此時，如果采用狄克斯屈拉算法，需要計算備選地址和各個校區之間的最短距離，該過程需要重復多次，且計算繁瑣；而計算圖中所有點之間的最短路徑正是Floyd算法所“擅長”的。因此，本文在研究教育裝備中心的選址問題時，優選Floyd算法。

表1中每行的合計數表示教材配送中心建于該校區時，滿足所有校區每學期教學需要的大學英語教材運輸的冊千米數。從表中可以看出C列的合計數最小，表明當把教材配送中心建于C校區時，教材運輸的冊千米數最小，為107 500。

3 結論

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

參考文獻

[1]李慧.教育裝備運籌規劃[M].北京：北京大學出版社，2010：100-116.

[2]辛宇.基于運籌學圖論的物流網絡優化研究[J].中國外資，2011（6）：125-127.

[3]蔣智凱.淺談運籌學教學[J].重慶科技學院學報：社會科學版，2010（24）：176-177.

[4]徐俊明.圖論及其應用[M].3版.北京：中國科學技術大學出版社，2010：84-90.

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

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

[7]王櫻，徐雨明，王靜.校園道路網最短路徑的分析與實現[J].衡陽師范學院學報，2004，12（6）：77-79.