基于LINGO軟件的最短路線問(wèn)題研究

丁正陽(yáng)

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

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

1 建模

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

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

1.2 求解方法

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

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

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

2 案例分析

2.1 案例

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

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

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

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

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

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

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

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

2.2 求解過(guò)程

LINGO 軟件的程序：

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

得到的結(jié)果如表2 所示：

表2 動(dòng)態(tài)規(guī)劃法求得結(jié)果

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

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

得到的結(jié)果如下（見(jiàn)表3）：

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

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

3 結(jié)論

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