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

丁正陽

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

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

1 建模

1.1 數(shù)學模型

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

1.2 求解方法

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

根據(jù)前人對該方法的總結，我們可以將動態(tài)規(guī)劃法歸納為如下的表達式：

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

2 案例分析

2.1 案例

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

圖1 9個村莊之間的網(wǎng)絡圖

動態(tài)規(guī)劃法：

該問題有三個階段，第一階段從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 出發(fā)到E,F,G，再到終點K 的路程長度是：

0-1 整數(shù)規(guī)劃法：

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

表1 0-1整數(shù)規(guī)劃法求解最短路徑

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

2.2 求解過程

LINGO 軟件的程序：

1）動態(tài)規(guī)劃程序

得到的結果如表2 所示：

表2 動態(tài)規(guī)劃法求得結果

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

2）0-1 整數(shù)規(guī)劃程序

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

表3 0-1整數(shù)規(guī)劃法求得結果

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

3 結論

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