最短路程問題

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

2、=10;en ddatasets :cities/1.n/: F;!10 個(gè)城市;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,則點(diǎn)i到點(diǎn)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計(jì)算的部分結(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示兩個(gè)城市之間的距離(百公里)例3.5 (最短路問題)在縱橫交錯(cuò)的公路網(wǎng)中，貨

5、車司機(jī)希望找到一條從一個(gè)城市到另一城市的最短 路。假設(shè)圖3-1表示的是該公路網(wǎng)，節(jié)點(diǎn)表示貨車可以?？康某鞘?，弧上的權(quán)表o那么，貨車從城市 S出發(fā)到達(dá)城市T,如何選擇行駛路線，使所經(jīng)過的路程最短?假設(shè)從S到T的最優(yōu)行駛路線P經(jīng)過城市Ci,則P中從S到Ci的子路也一定是從S到Ci的最優(yōu)行 駛路線；假設(shè)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)行駛路線是很容易得到的(實(shí)際上，此例中S到Ai (i=i,2)只有唯一的道路)o也就是說，此例中我們可以把從S到T的行駛過程分成4個(gè)階段，即St Ai (i=i,2,3) AiT Bj (j=i,2) , Bjf Ck (k=i,2), CkTTo記d(Y,X)為城市丫與城市X之間的直接距離(若這兩個(gè)城市 之間沒有道路直接相連，則可以認(rèn)為直接距離為無窮大),用L(X)表示城市S到城市X的最優(yōu)行駛路線的路長(zhǎng)，則有L(S)=0L(X) minL(Y) d(Y,X), X S對(duì)本例的具體問題，可以直接計(jì)算如下：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)行駛路線的路長(zhǎng)為20o進(jìn)一步分析以上求解過程，可以得到從S到T的最優(yōu)行駛路線為St Ast B2T Cit T上面這種計(jì)算方法在數(shù)學(xué)上稱為動(dòng)態(tài)規(guī)劃(dynamic programming )，是最優(yōu)化的一個(gè)分支。作為一個(gè)例子，我們用LINGO來解

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

9、法。這里主要討論的是如何用LINGO軟件來解決最短路問題。例7在圖1中，用點(diǎn)表示城市，現(xiàn)有A, Bi, B2, Ci, Cz Ca, D共七個(gè)城市。點(diǎn)與點(diǎn)之 間的連線 表示城市間有道理相連。連線旁的數(shù)字表示道路的長(zhǎng)度。現(xiàn)計(jì)劃從城市A到城市D鋪設(shè)一條天然氣管道，請(qǐng)?jiān)O(shè)計(jì)出最小價(jià)格管道鋪設(shè)方案?！痉治觥看死谋举|(zhì)是求從城市 A到城市D的一條最短路。最短路問題的數(shù)學(xué)表達(dá)式假設(shè)圖有n個(gè)頂點(diǎn)，現(xiàn)需要求從頂點(diǎn) 1到頂點(diǎn)n的最短路，設(shè)決策變量為Xj,當(dāng)Xij=1說明弧(i,j)位于頂點(diǎn)1至頂點(diǎn)n的路上；否則Xij=Oo其數(shù)學(xué)規(guī)劃表達(dá)式為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ī)劃問題設(shè)計(jì)的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）是計(jì)算集cities的個(gè)數(shù)，這里的計(jì)算結(jié)果是 n=7,這只編寫的方法的目的在于提高程序的通用性。22行表示目標(biāo)函數(shù)（14）,即求道路的最小 權(quán)值。23、24行表示約束（15）中i=1的情形，即最短路中起點(diǎn)的約束。約束（15）中i=n的情形，也就是最短路中終點(diǎn)的情形，沒有列在程序中，因?yàn)榻K點(diǎn)的 約束方程與前門1個(gè)方程線性相關(guān)。當(dāng)然，如果將此方程列入LINGO程序中，計(jì)算時(shí)也不 會(huì)出現(xiàn)任 何問題，因?yàn)長(zhǎng)INGO軟件可以自動(dòng)刪除描述線性規(guī)劃