丁正陽

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

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

1 建模

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

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

1.2 求解方法

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

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

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

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

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

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

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

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

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

2.2 求解過程

LINGO 軟件的程序：

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

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

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

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

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

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

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

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

3 結(jié)論

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