基于LINGO軟件的最短路線問題研究

丁正陽

目前，科技的發展越來越快，計算機和信息技術得到越來越廣泛的發展。既然要發展，我們就要選擇最優的方案，換句話說，也就是消耗資源最小的方案。這也是為了實現資源優化配置的一個主要途徑。因此最短路線問題就顯得尤為重要，它在交通運輸、網絡通訊、資源配置等方面有著極為廣泛的應用。前人也對這個問題做了大量的研究。參考文獻[1]對任意城市間的最短路徑問題進行了研究，簡單介紹了Dijkstra 算法和Floyd 算法，并且用用MATLAB 軟件編寫了一段簡單的程序Floyd 算法進行了進一步的驗證，證明了方法的正確性。參考文獻[2]對動態規劃的基本原理進行了介紹，并將動態規劃成功運用到了運輸問題的最短路徑當中，結合實例對該方法進行了說明，并且闡述了動態規劃整體最優思想和其在求解最短路徑問題中的獨特優越性。參考文獻[3]對大城市的公共交通網絡進行了分析，利用圖論方法對觀光旅游的乘車路徑問題進行了設計規劃，最后得到的結果能夠進行進一步推廣應用。

LINGO 軟件具有十分強大的功能，可以通過內部已有的函數對0-1 整數規劃問題進行求解，軟件求解精度高，速度快，并且小巧方便。

1 建模

1.1 數學模型

最短路徑問題旨在尋找圖中節點與節點之間的最短路徑，可以廣泛應用到人工智能，神經網絡，通信和計算機等學科當中，實際生活中的道路建設，電網鋪設，路線規劃等等問題也可以用最短路徑問題進行描述。最短路徑問題有多種類型，典型的任意一點到終點的最短路徑問題描述如下。首先給定一張網絡圖，圖中有點和線組成，或者線上還有方向箭頭。所有的個點另為，組成集合，集合中的任意一點到另一點的距離我們用表示，假設到沒有先進行連接，則令到的距離，并且當時，令，我們任意指定一個終點，求從點出發到的最短路線。

1.2 求解方法

首先介紹一種常用并且對于求解最短路徑十分有效的方法—動態規劃。動態規劃法不是一種局部最優的思想，而是一種全局最優的思想。按照一定的次序求得每個階段的結果，最終得到得到整個問題的最優化的解。

根據前人對該方法的總結，我們可以將動態規劃法歸納為如下的表達式：

除了常用的動態規劃法，我們也可以利用0-1整數規劃法來求解最短路徑問題。0-1 整數規劃問題具有廣泛的應用基礎，比如線路設計、工廠選址等問題時，都可以采用0-1 變量即邏輯變量，建立數學模型，在滿足條件的前提下，使目標解達到最優。應用0-1 整數規劃模型求解最短路徑問題的思路如下：

2 案例分析

2.1 案例

如圖1 所示，A，B，C，D，E，F，G，H，K 表示9 個不同的村莊，村莊之間的連線表示兩個村莊之間的距離，用表示?，F在有一個居民需要從村莊A 到村莊K，請求出兩村莊之間的最短路線。

圖1 9個村莊之間的網絡圖

動態規劃法：

該問題有三個階段，第一階段從A 到B 或C 到D，第二階段到E,F 或G 或H，第三階段到終點K，我們從終點往前倒退。對于第三階段：從集合E,F,G,H 到終點K 的路徑分別為30,26,21,22，只有唯一的一條路，這就是最短路，標記為，，，；對于第二階段：和集合E,F,G,H 相連的下一個階段的集合是B,C,D，則從B 出發到E,F,G，再到終點K 的路程長度是：

0-1 整數規劃法：

由于0-1 整數規劃模型在最短路中的算法是遍歷進行試湊，因此對于數據點一旦上升的情況沒有實用性，因此不采用人工手動求解的方式進行演示，將直接通過計算機編程進行求解。

表1 0-1整數規劃法求解最短路徑

利用0-1 整數規劃法進行最短路徑問題的手工計算主要是采用整數規劃的方法，按照約束條件對所有可能路徑進行0-1 試湊，求出某一目標函數值，并且對所有的可能的路徑組合的目標函數值進行比較，見表1。

2.2 求解過程

LINGO 軟件的程序：

1）動態規劃程序

得到的結果如表2 所示：

表2 動態規劃法求得結果

其中P(H,K)=1 就是最短路徑經過這條弧的意思；P(D,G)=0 就是最短路徑不經過這條弧的意思；因為P(A,D)=1，P(D,H)=1，P(H,K)=1，所以從A 點到K 點的最短路徑是從A 點經過D 點到H 點最后再到K 點。

2）0-1 整數規劃程序

得到的結果如下（見表3）：

表3 0-1整數規劃法求得結果

其中X(A,D)=1 表示從村莊A 到村莊K 的最短路徑經過了D 點，X(i,j)=0 表示從村莊A 到村莊K的最短路徑沒有經過某點或某條路徑。從表3 可知最短路徑為A-D-G-K，總的長度為46。

3 結論

本文講解了動態規劃法和0-1 整數規劃法以及LINGO 軟件對求解最短路徑問題的作用。同樣的經過對文章中的案例和生活中其他案例的分析計算，本文所采用的方法具有普適性?？梢越鉀Q諸如物流配送、道路建設、網絡鋪設等一系列問題，除此之外當然也要考慮人力資源配置和當地造價等一系列其他的因素。