災情巡視的最短路-數(shù)學建模15頁

1、災情巡視路線的數(shù)學模型摘 要本文研究的是根據(jù)某縣的鄉(xiāng)（鎮(zhèn)）、村公路網(wǎng)示意圖，如何在不同條件下制定出最佳災情巡視方案的問題。針對問題一：首先將公路網(wǎng)轉(zhuǎn)化為一張無向賦權圖并構造其鄰接矩陣，然后根據(jù)Dijkstra算法求出任意兩點間的最短距離及O點到其余頂點的最短路，最短路構成了一棵以O為樹根的最小生成樹，將干枝分為三組，每組各頂點間的最短路構成一個完備加權圖，再建立混合整數(shù)規(guī)劃模型求其最佳H圈。再逐步調(diào)整，使三組中路程較長者減小，最后得到三個組路程分別為204.9km、208.8km和205.3km，最長路程為208.8km，路程均衡度為1.9%，總路程為619km。針對問題二:依題意至少需要4組

2、，根據(jù)問題一中得到的最小生成樹將頂點分為4組，利用問題一中的算法，求出每組的最佳H圈，然后逐步調(diào)整，使四組中用時較長者減小，最后得到四個組所用時間分別為21.9h、22.41h、22.12h和21.66h，最長時間為22.41h，時間均衡度為3.3%。針對問題三:根據(jù)O點到最遠點的距離確定時間上界，然后根據(jù)時間上界和到O點的距離由遠及近確定最優(yōu)巡視路線，得最優(yōu)方案為分23組，巡視時間為6.43h，具體路徑見問題三解答。針對問題四：以問題二中所得結果為例，固定T，t和V中的兩個量，改變一個量，求巡視時間與該變量間的關系，巡視時間與T，t和V的曲線圖見解答四。關鍵詞：Dijkstra算法、最小生成

3、樹、加權完備圖、最佳H圈、整數(shù)規(guī)劃1.問題重述1.1問題背景 今年夏天該縣遭受水災。為考察災情、組織自救，縣領導決定，帶領有關部門負責人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線。1.2需要解決的問題 問題一:若分三組（路）巡視，試設計總路程最短且各組盡可能均衡的巡視路線。 問題二:假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2小時，在各村停留時間t=1小時，汽車行駛速度V=35公里/小時。要在24小時內(nèi)完成巡視，至少應分幾組；給出這種分組下你認為最佳的巡視路線。 問題三:在上述關于T , t和V的假定下，如果巡視人員足夠多，完成巡視的最短時間

4、是多少；給出在這種最短時間完成巡視的要求下，你認為最佳的巡視路線。 問題四:若巡視組數(shù)已定(如三組），要求盡快完成巡視，討論T，t和V改變對最佳巡視路線的影響。2.模型的假設假設一:各組在巡視過程中，路途通暢，無任何延誤時間。假設二:各組行駛車速都相同，并且勻速行駛。假設三:非本組巡視的鄉(xiāng)（鎮(zhèn)）或村只是路過，不作停留。3.符號的說明符號符號說明T在鄉(xiāng)(鎮(zhèn))的停留時間t在村的停留時間V汽車的速度wij兩相鄰點i和j的距離dij點i和點j的最短距離Zk第k組的最佳H圈的路程L第一問三個組中路程最大者路程均衡度sjk第k組的巡視時間sj幾個組巡視時間的最大者，即完成巡視任務所需時間4.問題分析針對問

5、題一:問題一是多個推銷員問題，我們首先考慮對鄉(xiāng)(鎮(zhèn)）、村這些點進行分組，然后安排三組人進行巡視，將多個推銷員問題轉(zhuǎn)化為單個推銷員問題。首先根據(jù)公路網(wǎng)圖建立一個鄰接矩陣儲存相鄰頂點間的距離，然后根據(jù)所得的鄰接矩陣用Dijkstra算法求出任意兩個頂點間的最短距離及O點到其余頂點間的最短路，再根據(jù)O點到其余頂點的最短路用Matlab畫出以O為樹根的最小生成樹(程序見附錄一)，由最小生成樹的樹枝將頂點分為三組，根據(jù)每組各點間的最短距離，構造一個完備加權圖，即在一個完備加權圖里面求最佳H圈，為TSP問題。再建立一個整數(shù)規(guī)劃模型表示TSP問題，求解得出最佳H圈的路程和其對應的路徑，最后逐步調(diào)整，是三組中

6、巡視路程最長的減小，可得到一個近似最優(yōu)解。針對問題二，首先根據(jù)單個組的最小巡視路程和在各個停留點所需的總的停留時間計算出至少應分4個組，考慮到該圖中鄉(xiāng)(鎮(zhèn))和村分布均勻，故首先將52個要巡視的頂點平分為4組，然后如問題一求出每個組的最佳H圈的路程，根據(jù)改組的最佳H圈的路程和停留的時間可算出其巡視時間，然后逐步調(diào)整，使四個組中巡視時間最大的減小，可得到一個近似最優(yōu)解。針對問題三，在巡視人員充足的前提下，設計最佳巡視路線。先根據(jù)問題一中 得到的O點到最遠點的距離確定巡視時間上界，然后再不超過時間上界的前提下，由遠及近設計巡視路線，使巡視時間盡可能接近時間上界。針對問題四，可以第二問的結果為例進行分

7、析，固定T,t和V中的兩個量，改變一個量，繪制出完成巡視任務所需時間隨各個量得變化曲線圖，觀察其對完成巡視任務所需時間的影響，并進行分析。5.數(shù)據(jù)分析首先根據(jù)題目所給公路網(wǎng)圖建立一個鄰接矩陣，然后根據(jù)鄰接矩陣用Dijkstra算法算出O點到其余頂點間的最短路，根據(jù)最短路可用Matlab函數(shù)畫出以O為樹根的最小生成樹(程序見附錄一)，如下圖，將樹枝從左至右依次編號為、，6.問題一的解答 6.1模型一的建立 問題一是多個推銷員問題，可以轉(zhuǎn)化為最佳H圈問題，再建立整數(shù)規(guī)劃模型求解最佳H圈的路程及路徑。首先根據(jù)鄰接舉證用Dijkstra算法求出任意兩點間的最短距離及O點到其余頂點間的最短路，根據(jù)最短路

8、畫出以O為樹根的最小生成樹。Dijkstra算法如下：Dijkstra算法：求G中從頂點u0到其預定點的最短路。S：具有永久標號的頂點集。對每一個頂點，定義兩個標記(l(v),z(v),其中：L(v):表示從頂點u0到v的一條路的權。Z(v):v的父親點，用以確定最短路的路線。算法的過程就是在每一步改進這兩個標記，使最終的l(v)為從頂點u0到v的最短路的權。輸入為帶權鄰接矩陣W。用上述算法求出的l(v)就是u0到v的最短路的權，從v的父親點標記z(v)追溯到u0，就得到u0到v的最短路的路線。如上圖，可看出從O出發(fā)的共有六個干枝，將這六個干枝進行分組，分組時遵循以下三個準則。準則一:盡量使長

9、的干枝和短的干枝分為一組。準則二:盡量把相鄰干枝上的點分為一組。準則三:盡量使使同一枝干及其分支上的點分為一組根據(jù)該原則確定一個分組形式：(),(),()。然后分別求每個組的最佳H圈。為求最佳H圈，應首先由給定的圖G=(V,E)構造一個以V為頂點集的完備圖,的每條邊(x,y)的權等于頂點x與y在途中最短路的權，即，這樣就把在G中尋找最佳推銷員回路問題轉(zhuǎn)化為在完備加權圖G中尋找最佳H圈，即TSP問題，我們將其轉(zhuǎn)化為混合整數(shù)規(guī)劃模型，建立了模型一。 6.1.1確定目標函數(shù)6.1.1.3建立整數(shù)規(guī)劃模型尋找最佳H圈 首先引入0-1整數(shù)變量:，則目標函數(shù)為: 6.1.2確定約束條件巡視i后必須要有一個

10、即將巡視的確切鄉(xiāng)(鎮(zhèn))或村；巡視j前必須要有一個剛剛巡視過的確切鄉(xiāng)(鎮(zhèn))或村。用下面的兩組約束分別實現(xiàn)上面的兩個條件。 到此得到一個指派問題的整數(shù)規(guī)劃模型，但這兩個條件對于TSP來說并不充分，只是必要條件。因此要在原模型的基礎上附加充分的條件以避免產(chǎn)生子巡回的方法。把額外變量附加到問題中，可把這些變量看作是連續(xù)的（這些變量在最優(yōu)解中取整數(shù)值）?，F(xiàn)附加下面形式的約束條件 綜上所述，有以下約束條件: 6.1.3綜上所述，得到問題一的最優(yōu)化模型 6.2模型一的求解由以上模型得到調(diào)整前和經(jīng)過兩次調(diào)整后的結果，整理如下表： (單位：km) 第1組第2組第3組總路程均衡度最長路程調(diào)整前237.5191.1

11、125.5554.147.2%237.5第一次調(diào)整216.5191.1188.7596.312.8%216.5第二次調(diào)整204.9208.8205.36191.9%208.8 得到的第二次調(diào)整后的路線及各組路程，總路程，均衡度整理如下表： (單位：km)組別路線(用紅色標記的點為停留點)路程總路程均衡度最長路程1O-2-5-6-7-E-11-G-13-14-H-12-F-10-F-9-E-8-E-7-6-5-2-O204.96191.9%208.82O-M-N-25-20-L-19-J-18-I-15-I-16-17-22-K-21-23-24-27-26-P-O208.83O-2-3-D-4

12、-D-3-C-B-34-35-32-30-Q-28-Q-29-R-31-33-A-1-O205.37.問題二的解答7.1模型二的建立 由題知，有17個鄉(xiāng)鎮(zhèn)，35個村，巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2小時，在各村停留時間t=1小時，汽車行駛速度V=35公里/小時，所以，總停留時間為(小時),計算得出單個組的巡視時最小H圈的路程為508.2km，為設有x個分組，則有，得x3.43，故取x=4，即分四組進行巡視， 分組時遵循以下四項準則:準則一:盡量使長的干枝和短的干枝分為一組。準則二:盡量讓各組的停留時間相同。準則三:盡量把相鄰干枝上的點分為一組。準則四:盡量將同一干枝上的點分在一組，且能形成環(huán)

13、路。7.1.1確定目標函數(shù)完成巡視的時間取決于四個組中最長的巡視時間，故目標函數(shù)為 min sj=（max（sjk）,k=1,2,32,47.1.2確定約束條件 sjk24,k=1,2,3,47.13綜上所述，得到問題二的最優(yōu)化模型min（max（sjk）,k=1,2,32,4 sjk24,k=1,2,3,47.2模型二的求解由以上模型求得調(diào)整前和調(diào)整后的結果整理如下表：第一組第二組第三組第四組總路程(km)時間均衡度最長時間（h）調(diào)整前鄉(xiāng)鎮(zhèn)的停留點個數(shù)5354663.612.30%23.12村的停留點數(shù)81089路程(km)136.5149.7179.2198.2巡視所用時間(h)21.92

14、0.27723.1222.663調(diào)整后鄉(xiāng)鎮(zhèn)的停留數(shù)5444668.23.33%22.409村的停留數(shù)81098路程(km)136.5154.3179.2198.2巡視所需時間（h）21.922.40922.1221.663 所得調(diào)整后的四組路線，巡視時間等整理如下表： 組別路線(用紅色標記的點為停留點)路程（km)停留時間（h）行駛時間（h）巡視時間(h）1O-1-A-33-31-R-29-Q-30-32-35-34-B-C-O136.5183.9021.92O-M-25-21-K-17-16-17-22-23-24-N-26-27-28-P-O154.3184.4122.413O-M-25-

15、20-L-19-J-18-I-15-14-13-G-11-E-7-6-5-2-O179.2175.1222.124O-2-3-D-4-8-E-9-F-12-H-12-F-10-F-9-E-7-6-5-2-O198.2165.6621.668.問題三的解答8.1從O點巡視H點的最短時間是所有最短時間中最長的，其距離為77.5km，算出時間為小時，因此，T=2h，t=1h，V=35km/h時，若巡視人員足夠多，完成巡視的最短時間為6.43小時。在最短時間的限制下，完成巡視的最佳路線應滿足以下條件：（1）每個組巡視的總時間不能超過最短時間小時，（2）所有的點都必須訪問到，不能漏點，（3）所需巡視組數(shù)

16、要盡量小。在尋求最優(yōu)路線時，從距離O點較遠的點開始搜索比較容易，因為到這些點的路線比較少。具體方法如下：第一步：依據(jù)最小生成樹算出從O點到每一點的最短距離。第二步：找出其中最大的一個，算出從O點到最短路巡視所需時間ti，并求 。第三步：若，則這一組只能訪問這一點；若，則在余下的點中找出 距離O點最遠的點，根據(jù)條件看這一組能否巡視這一點。第四步：若能巡視則算出，轉(zhuǎn)到第三步。第五步：若不能，則依次判斷次遠點、第三遠點滿足總巡視時間不超過， 就讓這組巡視這一點，直到，然后再從第二步開始。通過以上方法找到最優(yōu)解是23組，如下表：8.2模型三的求解路線(用紅色標記的點為停留點)時間第1組O-2-5-6-

17、7-E-9-F-12-H-12-F-9-E-7-6-5-2-06小時26分第2組O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-06小時9分第3組O-M-25-21-K-18-I-15-I-18-K-17-16-17-K-21-25-M-06小時19分第4組O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O5小時51分第5組O-2-5-6-7-E-9-F-10-F-9-E-8-E-7-6-5-2-O6小時13分第6組O-2-5-6-7-E-11-G-11-E-7-6-5-2-O5小時35分第7組O-M-25-21-K-18-I-18-K-21-25-

18、M-O5小時29分第8組O-2-5-6-7-E-11-E-7-6-5-2-O6小時12分第9組O-2-5-6-L-E-9-F-9-E-7-6-5-2-O6小時9分第10組O-2-5-6-L-19-J-19-L-6-5-2-O6小時6分第10組O-M-25-21-K-17-16-17-K-21-25-M-O6小時3分第12組O-M-25-21-K-18-K-21-25-20-25-M-O6小時13分第13組O-P-26-N-23-22-23-N-24-N-26-P-O5小時12分第14組O-2-5-6-7-E-8-E-7-6-5-2-3-D-4-D-3-2-O6小時0分第15組O-2-5-6-L

19、-6-5-2-O-M-O6小時17分第16組O-1-A-34-35-34-A-33-A-1-O5小時29分第17組O-R-29-Q-30-Q-29-R-O6小時2分第18組O-M-25-M-O-P-26-N-26-P-O6小時3分第19組O-R-31-32-31-R-O5小時44分第20組O-P-26-27-26-P-28-P-O5小時40分第21組O-2-3-D-3-2-O-C-O5小時25分第22組O-1-A-1-B-1-O6小時9分第23組O-2-3-2-5-2-O-M-O-P-26-N-23-N-26-P-O5小時51分 9.問題四的解答9.1模型四的建立根據(jù)題意，假設巡視組數(shù)定為四組

20、，以問題二中的分組方案為例，固定T，t和V中的兩個量，改變其中一個量，求巡視時間與該變量間的關系，通過MATLAB求解得到如下巡視時間隨三個變量的變化而變化的圖(程序見附錄一):圖中三個紅色的點位于一條直線上，分別代表T=2小時，t=1小時，V=35千米/小時時，對應問題二的巡視時間22.409h，即為問題二的解。顯然，由下圖得出以下結論： (1)當固定t、V時，巡視時間隨T的增大而增大(2)當固定T、V時，巡視時間隨t的增大而增大，且隨t增大得比隨T增大地快(3)當固定T、t時，巡視時間隨V的增大而減小更進一步分析，可看出，當V低于20km/h后，巡視時間急劇增加，當V高于50km/h后，再

21、增加對減小巡視時間作用很小，故從效率和安全兩個角度綜合考慮，汽車速度V應不低于20km/h，應不高于50km/h11.模型的模型的評價、改進及推廣11.1模型評價模型優(yōu)點：(1) 用均衡度量化分組的均衡性。(2) 綜合多種算法的思想進行求解，使所得模型在災情巡視方面有科學的指導意義。模型缺點：第三問用經(jīng)驗來調(diào)整的，如果可以通過編程求解則更好。11.2模型改進 由于實際情況中，各個鄉(xiāng)（鎮(zhèn)）、村的受災情況不同，故應根據(jù)受災的嚴重程度來分配巡視時的停留時間，可先將每個巡視點的受災程度量化，建立T，t關于受災程度的函數(shù)，然后分組巡視，求最佳巡視路線。11.3模型推廣所建模型還可用于公安執(zhí)勤人員的最優(yōu)巡

22、回路線、流水作業(yè)、生產(chǎn)線的順序問題以及老師任課班級負荷分配等問題。12.參考文獻1 趙靜,但琦,數(shù)學建模與數(shù)學實驗,北京:高等教育出版社,2008.2 薛定宇，陳陽泉，高等應用數(shù)學問題的MATLAB求解，北京：清華大學出版社，2008.13.附錄附錄一：Matlab程序%dijkstra.mfunction d,path=dijkstra(b,s,t)n,m=size(b);ix=(b=0);visited(1:n)=0;dist(1:n)=inf;parent(1:n)=0;dist(s)=0;d=inf;for i=1:(n-1) ix=(visited=0);vec(1:n)=inf;v

23、ec(ix)=dist(ix); a,u=min(vec);visited(u)=1; for v=1:n if (b(u,v)+dist(u)1 zdjl(m,n) p=dijkstra(b,m,n); path(n,1:length(p)=p; end endendjl_path=1:53 zdjl(:,1) pathzdjl%畫最小生成樹的程序a1=1;b1=4;w1=11.5;a2=1 20 21 5 20 23 24 13 37 11 31 24 25 6 6 29 6 27 7 7 30;b2=20 21 5 22 23 24 13 37 11 31 32 25 6 26 29 8

24、 27 7 28 30 9;w2=9.2 4.8 8.2 12.7 8.3 9.7 11.8 7.2 8.1 9.8 8.6 7.3 7.2 8.0 14.2 6.8 7.8 5.6 10.8 12.2 10.2;a3=1 14 43 43 39 12 35 12 36 10;b3=14 43 38 39 12 35 34 36 10 33;w3=19.8 12.0 6.5 7.8 4.1 9.8 6.8 9.2 8.2 8.8;a4=1 16 16 44 44 15 15 41 ;b4=16 46 44 45 15 42 41 40;w4=10.1 12.1 10.5 7.9 10.5 13

25、.2 7.9 10.0;a5=1 18 47 17 18 49;b5=18 47 17 48 49 50;w5=7.9 7.9 7.2 7.7 9.2 8.1;a6=1 19 19 2 2 52;b6=19 3 2 51 52 53;w6=6.0 7.9 10.3 7.4 11.5 8.2;R=sparse(a1 a2 a3 a4 a5 a6,b1 b2 b3 b4 b5 b6,w1 w2 w3 w4 w5 w6);R(53,53)=0;h=view(biograph(R,ShowWeights,on);%第一問程序zdjl_12=zdjl(1 4 5 6 7 8 9 11 13 20:32

26、37,1 4 5 6 7 8 9 11 13 20:32 37);zdjl_34=zdjl(1 10 12 14 15 16 33:36 38:46,1 10 12 14 15 16 33:36 38:46);zdjl_56=zdjl(1 2 3 17 18 19 47:53,1 2 3 17 18 19 47:53);zdjl_12_1=zdjl(1 6 7 8 9 11 13 20 23:32 37,1 6 7 8 9 11 13 20 23:32 37);zdjl_56_1=zdjl(1 2 3 4 5 17 18 19 21 22 47:53,1 2 3 4 5 17 18 19 21

27、 22 47:53);zdjl_12_tzh=zdjl(1 6 7 8 9 20 23:32,1 6 7 8 9 20 23:32);zdjl_34_tzh=zdjl(1 10 11 12 13 14 15 16 33:37 38:45,1 10 11 12 13 14 15 16 33:37 38:45);zdjl_56_tzh=zdjl(1 2 3 4 5 17 18 19 21 22 46:53,1 2 3 4 5 17 18 19 21 22 46:53);%第二問程序zdjl_1=zdjl(1 2 3 4 17 18 19 47:53,1 2 3 4 17 18 19 47:53);

28、zdjl_2=zdjl(1 12 15 16 34 35 39:46,1 12 15 16 34 35 39:46);zdjl_3=zdjl(1 8 10 11 13 14 24 29 31 32 33 36 37 38,1 8 10 11 13 14 24 29 31 32 33 36 37 38);zdjl_4=zdjl(1 5 6 7 9 20:23 25:28 30,1 5 6 7 9 20:23 25:28 30);zdjl_1_tzh=zdjl(1 2 3 4 17 18 19 47:53,1 2 3 4 17 18 19 47:53);zdjl_2_tzh=zdjl(1 12 1

29、4 15 16 34 35 39:46,1 12 14 15 16 34 35 39:46);zdjl_3_tzh=zdjl(1 8 10 11 13 23 24 29 31 32 33 36 37 38,1 8 10 11 13 23 24 29 31 32 33 36 37 38);zdjl_4_tzh=zdjl(1 5 6 7 9 20:22 25:28 30,1 5 6 7 9 20:22 25:28 30);%第三問程序jl index=sort(zdjl(:,1);jl_index=jl indexsj=2*77.5/35+2;2*72.7/35+1+1;(69.9+8.8+11.

30、8+60.3)/35+1+1;(67.3+12.2+5.6+49.5)/35+1+1; (65.9+10.8+5.6+7.8+8.0+49.7)/35+1+1;2*62.7/35+2;2*61.1/35+2;2*55.9/35+1+1+1; 2*55.1/35+2+1;2*54.3/35+1+2;2*53.5/35+1+2;(52.9+9.2+4.1+7.9+38.3)/35+1+1+1;(49+10.0+8.9+44.3)/35+1+1; (41.7+8+12.3+8.1+34.9)/35+2+1;(39+11.8+9.5+19.8)/35+2+2;(36+8.2+11.5+7.4+23.7)/35+1+1+1;2*35.7/35+1+2+1;(31.8+8.8+10.5+20.6)/35+1+2+1; (30.2+8.1+9.2+12.9)/35+1+1+2;(28.4+7.9+12.1+10.1)/35+1+1+2;(