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


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


參考書籍：

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