最佳災情巡視路線
頁數(shù) 17 字數(shù) 7672
摘要：（建議最后寫很多需要改）本題是一類圖上點的行遍性問題，也就是要用若干條閉鏈覆蓋圖上所有的頂點（本題為鄉(xiāng)村所在地），并使得某些指標達到最優(yōu)（本題為使路程最近，耗時最短，各小組盡量均衡），也就是在圖論和組合最優(yōu)化中分別稱為哈密爾頓問題和旅行商問題。針對此：本文首先利用兩點間的最短路長度作為該兩點邊的權(quán)構(gòu)造了一個完全圖，然后根據(jù)完全圖形狀和各頂點分布，將完全圖分為三個區(qū)域。接著，本文給出了對各個區(qū)域分別運用解哈密爾頓圈的局部回路搜索法（3-代換法）和逐次改進法求解最短路徑的方法。為給出均衡的多路巡視路線，先將圖分劃為均衡的多個子圖，再在各個子圖中分別求最優(yōu)解，從而得到整體的均衡最優(yōu)解。
第三問我們首先使用Dijkstra單源最短路徑算法求出O中各點到O最短路徑。然后用近似解法得出分組的最佳情況。
在模型的進一步分析中，考慮到模型的針對性太強，我們給出了運用最小生成樹的新的求解方法從而能使模型普遍適應各種不同情況的災情巡視問題。
根據(jù)偏差程度的大小來衡量巡視路線的均衡性, 最后得到了均衡性較好的分組路線。在所給條件下, 找出完成巡視的最短時間為6. 43 小時, 在這個時間限制下, 采用較為合理的分組方法, 找出22 個組。最后, 討論了在組數(shù)一定的情況下, 將T、t 視為時間因素X ,V 視為速度因素Y , 分析X 、Y 變化對最佳巡視路線的影響。


關鍵字：
哈密爾頓問題和旅行商問題,完全圖,最短路,局部回路搜索法（3-代換法）,最鄰近算法,逐次修正法,最小生成樹


參考書籍：

（1） 杜端甫，運籌圖論（圖、網(wǎng)絡理論中的運籌問題）北京航空航天大學 1990
（2） 肖位樞 圖論及其算法 航空工業(yè)出版社 1993
（3） 趙靜，但琦.數(shù)學建模與數(shù)學實驗（第二版）.[M]北京：高等教育出版社