1、會計學(xué)1最短路徑問題最短路徑問題(wnt)-數(shù)學(xué)建模數(shù)學(xué)建模41111第一頁，共31頁。2Floyd算法(sun f)Dijkstra算法(sun f)兩個例子的求解引例2：最廉價航費表的制定引例1：最短運輸路線問題最短路徑問題的0-1規(guī)劃模型第1頁/共31頁第二頁，共31頁。31023741165981第2頁/共31頁第三頁，共31頁。4050402510500152025150102040201001025252010055102525550第3頁/共31頁第四頁，共31頁。5l定義(dngy)：設(shè)P(u,v)是加權(quán)圖G中從u到v的路徑,則該路徑上的邊權(quán)之和稱為該路徑的權(quán),記為w(P).

2、從u到v的路徑中權(quán)最小者 P*(u,v)稱為u到v的最短路徑.1023741165981第4頁/共31頁第五頁，共31頁。61023741165981第5頁/共31頁第六頁，共31頁。7S: 具有永久標號的頂點集;l(v): v的標記; f(v):v的父頂點,用以確定最短路徑; 輸入加權(quán)圖的帶權(quán)鄰接矩陣w=w(vi,vj)nxm.初始化 令l(v0)=0,S=; vv0 ,l(v)=;更新l(v), f(v) 尋找不在S中的頂點u,使l(u)為最小.把u加入到S中,然后對所有(suyu)不在S中的頂點v,如l(v)l(u)+w(u,v),則更新l(v),f(v), 即 l(v)l(u)+w(u

3、,v),f(v)u;重復(fù)步驟2), 直到所有(suyu)頂點都在S中為止.第6頁/共31頁第七頁，共31頁。8第7頁/共31頁第八頁，共31頁。9第8頁/共31頁第九頁，共31頁。101023741165981第9頁/共31頁第十頁，共31頁。11 d(i,j) : i到j(luò)的距離; path(i,j): i到j(luò)的路徑上i的后繼(huj)點; 輸入帶權(quán)鄰接矩陣a(i,j).1）賦初值 對所有i,j, d(i,j)a(i,j) , path(i,j)j,k=l.2）更新d(i,j) , path(i,j) 對所有i,j, 若d(i,k)+d(k,j)d(i,j),則 d(i,j)d(i,k)+d(

4、k,j) , path(i,j)path(i,k) , k k+13）重復(fù)2)直到k=n+1第10頁/共31頁第十一頁，共31頁。12第11頁/共31頁第十二頁，共31頁。13第12頁/共31頁第十三頁，共31頁。141023741165981第13頁/共31頁第十四頁，共31頁。15第14頁/共31頁第十五頁，共31頁。16050402510500152025150102040201001025252010055102525550第15頁/共31頁第十六頁，共31頁。17050402510500152025150102040201001025252010055102525550第16頁/共3

5、1頁第十七頁，共31頁。18最短路徑(ljng)問題的0-1規(guī)劃模型 設(shè)決策變量為設(shè)決策變量為xij , 當頂點當頂點1至頂點至頂點n的路上含弧的路上含弧(i,j) 時，時，xij=1；否則；否則xij=0. 其數(shù)學(xué)其數(shù)學(xué)(shxu)規(guī)劃表達式為規(guī)劃表達式為( , )11( , )( , )min ; 1,1,. . 1, ; 0,1, . 01,( , ). ijiji jEnnijjijji jEj iEijw xistxxininxi jE 或第17頁/共31頁第十八頁，共31頁。19最短路徑問題(wnt)的0-1規(guī)劃模型 例 （有向圖最短路問題） 在下圖中，用點表示城市，現(xiàn)有 共7個城

6、市.點與點之間的連線(lin xin)表示城市間有道路相連.連線(lin xin)旁的數(shù)字表示道路的長度.現(xiàn)計劃從城市 到城市 鋪設(shè)一條天然氣管道，請設(shè)計出最小價格管道鋪設(shè)方案. 12123, ,A B B C C C DAD本質(zhì)是求從城市 到城市 的一條最短路AD第18頁/共31頁第十九頁，共31頁。20最短路徑問題的0-1規(guī)劃(guhu)模型 解：寫出相應(yīng)(xingyng)的LINGO程序，MODEL: 1! We have a network of 7 cities. We want to find 2 the length of the shortest route from city

7、 1 to city 7; 3 4sets: 5 ! Here is our primitive set of seven cities; 6 cities/A, B1, B2, C1, C2, C3, D/; 7 8 ! The Derived set roads lists the roads that 9 exist between the cities; 第19頁/共31頁第二十頁，共31頁。21最短路徑問題(wnt)的0-1規(guī)劃模型 10 roads(cities, cities)/ 11 A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 1

8、2 C1,D C2,D C3,D/: w, x; 13 endsets 14 15 data: 16 ! Here are the distances that correspond 17 to above links; 18 w = 2 4 3 3 1 2 3 1 1 3 4; 19 enddata 第20頁/共31頁第二十一頁，共31頁。22最短路徑問題的0-1規(guī)劃(guhu)模型 20 21 n=size(cities); ! The number of cities; 22 min=sum(roads: w*x); 23 for(cities(i) | i #ne# 1 #and# i

9、 #ne# n: 24 sum(roads(i,j): x(i,j) = sum(roads(j,i): x(j,i); 25 sum(roads(i,j)|i #eq# 1 : x(i,j)=1; END第21頁/共31頁第二十二頁，共31頁。23最短路徑(ljng)問題的0-1規(guī)劃模型 在上述程序中， 21句中的n=size(cities)是計算集cities的個數(shù)，這里的計算結(jié)果是 , 這樣編寫方法目的在于提高程序的通用性.22句表示目標函數(shù), 即求道路的最小權(quán)值.23, 24句表示約束中 的情況，即最短路中中間點的約束條件.25句表示約束中 的情況，即最短路中起點的約束.7n 1,ii

10、n1i 約束中 的情況，也就是最短路中終點的情況，沒有列在程序中，因為終點的約束方程與前個方程相關(guān).當然，如果你將此方程列入到LINGO程序中，計算時也不會出現(xiàn)任何問題，因為LINGO軟件可以自動刪除描述線性規(guī)劃可行解中的多余方程.in第22頁/共31頁第二十三頁，共31頁。24最短路徑問題(wnt)的0-1規(guī)劃模型 LINGO軟件計算結(jié)果（僅保留非零變量(binling)）如下Global optimal solution found at iteration: 0 Variable Value Reduced Cost 即最短路(dunl)是 , 最短路(dunl)長為6個單位.11ABC

11、D第23頁/共31頁第二十四頁，共31頁。25最短路徑問題的0-1規(guī)劃(guhu)模型 例（無向(w xin)圖的最短路問題）求下圖中 到 的最短路.1v11v 本例是處理無向圖的最短路(dunl)問題，在處理方式上與有向圖的最短路(dunl)有一些差別.第24頁/共31頁第二十五頁，共31頁。26最短路徑問題(wnt)的0-1規(guī)劃模型 解： 對于無向圖的最短路問題，可以這樣理解，從點 到點 和點 到點 的邊看成有向弧，其他各條邊均看成有不同方向的雙弧，因此，可以按照前面介紹有向圖的最短路問題來編程序，但按照這種方法編寫LINGO程序相當于邊（?。┰黾恿艘槐?這里選擇鄰接矩陣和賦權(quán)矩陣的方法編

12、寫LINGO程序.1viviv11vMODEL: 1 sets: 2 cities/1.11/; 3 roads(cities, cities): p, w, x; 4 endsets 第25頁/共31頁第二十六頁，共31頁。27最短路徑(ljng)問題的0-1規(guī)劃模型 5 data: 6 p = 0 1 1 1 0 0 0 0 0 0 0 7 0 0 1 0 1 0 0 0 0 0 0 8 0 1 0 1 1 1 1 0 0 0 0 9 0 0 1 0 0 0 1 0 0 0 0 10 0 1 1 0 0 1 0 1 1 0 0 11 0 0 1 0 1 0 1 0 1 0 0 12 0 0

13、 1 1 0 1 0 0 1 1 0 13 0 0 0 0 1 0 0 0 1 0 1 14 0 0 0 0 1 1 1 1 0 1 1 15 0 0 0 0 0 0 1 0 1 0 1 16 0 0 0 0 0 0 0 0 0 0 0;第26頁/共31頁第二十七頁，共31頁。28最短路徑問題(wnt)的0-1規(guī)劃模型 17 w = 0 2 8 1 0 0 0 0 0 0 0 18 2 0 6 0 1 0 0 0 0 0 0 19 8 6 0 7 5 1 2 0 0 0 0 20 1 0 7 0 0 0 9 0 0 0 0 21 0 1 5 0 0 3 0 2 9 0 0 22 0 0 1 0

14、 3 0 4 0 6 0 0 23 0 0 2 9 0 4 0 0 3 1 0 24 0 0 0 0 2 0 0 0 7 0 9 25 0 0 0 0 9 6 3 7 0 1 2 26 0 0 0 0 0 0 1 0 1 0 4 27 0 0 0 0 0 0 0 9 2 4 0; 28 enddata第27頁/共31頁第二十八頁，共31頁。29最短路徑問題(wnt)的0-1規(guī)劃模型 29n=size(cities); 30min=sum(roads:w*x); 31for(cities(i) | i #ne# 1 #and# i #ne# n: 32 sum(cities(j): p(i,j)*x(i,j) 33 =sum(cities(j): p(j,i)*x(j,i); 34sum(cities(j): p(1,j)*x(1,j)=1; END第28頁/共31頁第二十九頁，共31頁。30最短路徑問題的0-1規(guī)劃(guhu)模型 在上述程序中，第6行到第16行給出了圖的鄰接矩陣 ， 到 和 到 的邊按單向計算，其余邊雙向計算.第17行到第27行給出了圖的賦權(quán)矩陣 , 注意：由于有了鄰接矩陣 ，兩點無道路連接時，權(quán)值可以定義為0. 其它的處理方法基本上與有向圖相同.P1v234,vvv8910,vvv11v