最短路程問題

1、例7.4最短路問題 給定N個點蟻1,打組成集合P",由集合中任一點p到另一點R的距離用6表示，如果“到巧沒有弧聯(lián)結(jié)，則規(guī)定G，又規(guī)定cwiN),指定一個終點Pn,要求從R點出發(fā)到Pn的最短路線。這里我們用動 態(tài)規(guī)劃方法來做。用所在 的點H表示狀態(tài)，決策集合就是除A以外的點，選定一個點巧以后，得到效益4并轉(zhuǎn)入新狀態(tài)當狀 態(tài)是PN時，過程停止。顯然這是一個不定期多階 段決策過程。定義f(i)是由Pi點出發(fā)至終點PN的最短路程，由最優(yōu)化原理可得f(i)mijnCij f(j), i1,2,N 1f(N)O這是一個函數(shù)方程，用LINGO可以方便的解決。!最短路問題；model:data :n

2、=10;en ddatasets :cities/1.n/: F;!10 個城市;roads(cities,cities)/1,2 1,32.4 2,5 2,63.4 3,5 3,64.7 4,85.7 5,8 5,96.8 6,97.108.109,10/： D, P；en dsetsdata :D=6 53697 5 119 18 754 10579；en ddataF(n)=0;for(cities(i) | i #lt# n:F(i)= min(roads(i,j): D(i,j)+F(j);)；!顯然，如果P(i,j)=d,則點i到點n的最短路徑的第一步是i -> j ,否則就

3、不是。由此，我們就可方便的確定出最短路徑；for(roads(i,j):P(i,j)= jf (F(i) #eq# D(ij)+F(j),1,0)Variable NF(1)F( 2)F( 3) F( 4)F( 5) F( 6)F( 7) F( 8)F( 9) F(10)P(1,2)P(1,3)P( 2, 4)P( 2, 5)P( 2, 6)P( 3, 4)P( 3, 5)P( 3, 6)P( 4, 7)P( 4, 8)P( 5, 7)P( 5, 8)P( 5, 9)P(6, 8)P(6, 9)P( 7,10)P( 8,10)P(9, 10)；end計算的部分結(jié)果為:Feasible solu

4、tion found at iteration:Value10.0000017.0000011.0000015.000008.00000013.0000011.000005.0000007.0000009.0000000.0000001.0000000.0000001.0000000.0000000.0000001.0000000.0000000.0000000.0000001.0000001.0000000.0000000.0000001.0000000.0000001.0000001.0000001.000000示兩個城市之間的距離(百公里)例3.5 (最短路問題)在縱橫交錯的公路網(wǎng)中，貨

5、車司機希望找到一條從一個城市到另一城市的最短 路。假設圖3-1表示的是該公路網(wǎng)，節(jié)點表示貨車可以停靠的城市，弧上的權(quán)表o那么，貨車從城市 S出發(fā)到達城市T,如何選擇行駛路線，使所經(jīng)過的路程最短?假設從S到T的最優(yōu)行駛路線P經(jīng)過城市Ci,則P中從S到Ci的子路也一定是從S到Ci的最優(yōu)行 駛路線；假設P經(jīng)過城市C2,貝U P中從S到C2的子路也一定是從S到C2的最優(yōu)行駛路線。因 此，為了得到從S到T的最優(yōu)行駛路線，我們只需要先求出從S到Ck( k=i,2)的最優(yōu)行駛路線，只需要先求出從S到Bj (j=i,2)的最優(yōu)行駛路線；只需要先求出從S到Ai (i=i,2 )的最優(yōu)行駛路線。而從S到Ai(i=

6、i,2,3)的最優(yōu)行駛路線是很容易得到的(實際上，此例中S到Ai (i=i,2)只有唯一的道路)o也就是說，此例中我們可以把從S到T的行駛過程分成4個階段，即St Ai (i=i,2,3) AiT Bj (j=i,2) , Bjf Ck (k=i,2), CkTTo記d(Y,X)為城市丫與城市X之間的直接距離(若這兩個城市 之間沒有道路直接相連，則可以認為直接距離為無窮大),用L(X)表示城市S到城市X的最優(yōu)行駛路線的路長，則有L(S)=0L(X) minL(Y) d(Y,X), X S對本例的具體問題，可以直接計算如下：L(Ai)6 丄(A?) 3 丄(A3)7L(Bi) min L(AJ

7、6 丄施)8 ±(As) 7 IO L(As) 7屈)min L( Ai) 5 丄(AR 6 丄(乓)4 7 L(Aa)4;L(Ci) min L(B() 6 丄偲)815 L(BQ 8,g)min L(Bi)7 丄(B» 916 L(BQ 9;L(T) min L(Ci) 5 丄 G) 620 L(Ci) 5.所以，從S到T的最優(yōu)行駛路線的路長為20o進一步分析以上求解過程，可以得到從S到T的最優(yōu)行駛路線為St Ast B2T Cit T上面這種計算方法在數(shù)學上稱為動態(tài)規(guī)劃(dynamic programming )，是最優(yōu)化的一個分支。作為一個例子，我們用LINGO來解

8、這個最短路問題。我們可以編寫如下的LINGOS序。集合段 定義的“CITIES” （城市）是一個基本集合（元素通過枚舉給出），L是其對應的屬性變量（我們要求的 最短路長）；“ROADS （道路）是由CITIES導出的一個派生集合（請?zhí)貏e注意其用法），由于只有 一部分城市之間有道理相連，所以不應該把它定義成稠密集合，我們進一步將其元素通過枚舉給 出，這就是一個稀疏集合。D是稀疏集合ROAD對應的屬性變量（給定的距離）最短路程問題最短路程問題(shortest path problems)是圖論另一類與優(yōu)化有關的問題，對于這個問題，圖論中已有 解決的方法，如最短路問題的求解方法有Dijkstra算

9、法。這里主要討論的是如何用LINGO軟件來解決最短路問題。例7在圖1中，用點表示城市，現(xiàn)有A, Bi, B2, Ci, Cz Ca, D共七個城市。點與點之 間的連線 表示城市間有道理相連。連線旁的數(shù)字表示道路的長度?，F(xiàn)計劃從城市A到城市D鋪設一條天然氣管道，請設計出最小價格管道鋪設方案。【分析】此例的本質(zhì)是求從城市 A到城市D的一條最短路。最短路問題的數(shù)學表達式假設圖有n個頂點，現(xiàn)需要求從頂點 1到頂點n的最短路，設決策變量為Xj,當Xij=1說明弧(i,j)位于頂點1至頂點n的路上；否則Xij=Oo其數(shù)學規(guī)劃表達式為min ij 州；1,1 1,1, in,0, i1,n;(i，j) EX

10、i Xji j 1 (i,j) E j1 (j,i) ES. t.Xij o,(i J) E.LINGO程序，程序名 exam0708.lg4下面介紹的方法是按照規(guī)劃問題設計的MODEL:1 ! We have a n etwork of 7 cities. We want to find2 the len gth of the shortest route from city 1 to city 7;33 sets:4 ! Here is our primitive set of seven cities;5 cities/A, B1, B2, C1, C2, C3, D/;78 ! The

11、 Derived set "roads" lists the roads that9 exist between the cities;10 roads(cities, cities)/11 A, B1 A, B2 B1, C1 B1, C2 B1, C3 B2, C1 B2, C2 B2, C312 C1, DC2, DC3, D/: w,x;13 endsets1414 data:15 ! Here are the idstances that correspond16 to above links;17 w = 24331231 13 4;18 enddata2019

12、 n = size(cites); ! The number of cities;20 min = sum(roads: w * x);21 for(cities(i)|i # ne # 1 # and # i # ne # n:22 sum(roads(i,j): x(i,j) = sum(roads(j,i): x(j,i);23 sum(rads(i,j)|i # eq # 1 : x(i,j) = 1;END在上述程序中，21行中的n=size （cities）是計算集cities的個數(shù)，這里的計算結(jié)果是 n=7,這只編寫的方法的目的在于提高程序的通用性。22行表示目標函數(shù)（14）,即求道路的最小 權(quán)值。23、24行表示約束（15）中i=1的情形，即最短路中起點的約束。約束（15）中i=n的情形，也就是最短路中終點的情形，沒有列在程序中，因為終點的 約束方程與前門1個方程線性相關。當然，如果將此方程列入LINGO程序中，計算時也不 會出現(xiàn)任 何問題，因為LINGO軟件可以自動刪除描述線性規(guī)劃