數(shù)學(xué)建模路線優(yōu)化問(wèn)題

1、選路的優(yōu)化模型摘要:本題是一個(gè)有深刻背景的NPC問(wèn)題，文章分析了分組回路的拓?fù)浣Y(jié)構(gòu)，并構(gòu)造了多個(gè)模型，從多個(gè)側(cè)面對(duì)具體問(wèn)題進(jìn)行求解。最短樹結(jié)構(gòu)模型給出了局部尋優(yōu)的準(zhǔn)則算法模型體現(xiàn)了由簡(jiǎn)到繁，確保較優(yōu)的思想而三個(gè)層次分明的表述模型證明了這一類問(wèn)題共有的性質(zhì)。在此基礎(chǔ)上我們的結(jié)果也是比較令人滿意的。如對(duì)第一題給出了總長(zhǎng)為599.9，單項(xiàng)長(zhǎng)為216的分組，第二題給出了至少分四組的證明。最后，我們還談到了模型的優(yōu)缺點(diǎn)及推廣思想。一、問(wèn)題描述“水大無(wú)情，人命關(guān)天”為考察災(zāi)情，縣領(lǐng)導(dǎo)決定派人及早將各鄉(xiāng)（鎮(zhèn)），村巡視一遍。巡視路線為從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)），村又回到縣政府所在地的路線。1. 若分三

2、組巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線。2. 假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間為T=2小時(shí)，在各村停留時(shí)間為 t =1 小時(shí)， 汽車行駛速度為V=35公里/時(shí)，要在24小時(shí)內(nèi)巡視完，至少分成幾組；給出這種分組下你認(rèn)為最佳的巡視路線。3. 上述關(guān)于T，t和V的假定下，如果巡視人員足夠多，完成巡視的最短時(shí)間是多少？給出在這種最短時(shí)間完成巡視的要求下，你認(rèn)為最佳的巡視路線。 4. 巡視組數(shù)已定（如三組）要求盡快完成巡視，討論T，t和V改變時(shí)最佳路線的影響（圖見(jiàn)附錄）。二、問(wèn)題假設(shè)1、鄉(xiāng)（鎮(zhèn)）村只考察一次，多次經(jīng)過(guò)時(shí)只計(jì)算一次停留時(shí)間。 2、非本縣村不限制通過(guò)。3、汽車的行駛速度始終一致

3、。三、符號(hào)說(shuō)明符號(hào)表示意義Ti第i 人走的回路Ti=vvi(i) v2(i) vn(i) Ti=00表示第i人在0點(diǎn)沒(méi)移動(dòng)ViTi的點(diǎn)集SiTi的長(zhǎng)度Hi(v)在V上定義的特殊函數(shù)僅當(dāng)V被第i 人走過(guò)且停留時(shí)Hi(v)=1,否則為0四、模型建立在這一節(jié)里，我們將提出若干個(gè)模型及其特點(diǎn)分析，不涉及對(duì)題目的求解。 最簡(jiǎn)樹結(jié)構(gòu)模型 在這個(gè)模型中我們依靠利用最短樹的特殊結(jié)構(gòu)所給出的準(zhǔn)則，進(jìn)行局部尋優(yōu)，在一個(gè)不大的圖里，我們較易得到較優(yōu)解。(a) 分片 準(zhǔn)則1利用最短樹的長(zhǎng)度可大致的估算出路程長(zhǎng)，在具體操作中，各片中的最短路程長(zhǎng)度不宜相差太大。 準(zhǔn)則 2 盡可能將最短樹連成一個(gè)回路，這可保證局部上路程是

4、較短的。(b) 片內(nèi)調(diào)整 細(xì)準(zhǔn)1對(duì)于右圖的最短樹結(jié)構(gòu)，最好的走法是 a1 a2 a3 a4 a5 a6假設(shè) a3 a4有路相連若 a3 a4 進(jìn)去重復(fù)走的話，它與上述的走法路程差w(a3, a2)+w(a2 ,a5)+w(a4, a5)w(a3, a4)。由兩點(diǎn)間最小原則上式是大于0的優(yōu)劣可見(jiàn) 細(xì)準(zhǔn)2若有如圖所示結(jié)構(gòu)，一般思想是：將中間樹枝上的點(diǎn)串到兩旁樹枝，以便連成回路。五、模型求解問(wèn)題一 該問(wèn)題完全可以用均衡模型表述 用算法模型 1 經(jīng)過(guò)局部?jī)?yōu)化 手工多次比較 我們能夠給出的最佳結(jié)果為第一組路徑為0P282726N242322-1716115118K212025M-0 長(zhǎng) 191.1 經(jīng)

5、5 鎮(zhèn) 6 村 第二組路徑為 0256L19J11-G1314H12F10F9E8E76520 長(zhǎng) 216.5 經(jīng) 6 鎮(zhèn)11 村第三組路徑為 O23D4D3CB1A343533313230Q29R 長(zhǎng) 192.3 經(jīng) 6 鎮(zhèn)11 村 總長(zhǎng) S=599.9 公里 由算法 2 給出的為 1 組0P29R3133A34353230Q282726N24332223N26P05 鄉(xiāng) 13 村長(zhǎng) 215.2 公里 2 組 0M2521K1716I15I18K212520L19J11G1314O5 鄉(xiāng) 11 村長(zhǎng) 256.2 公里 3 組 O2567E9-F12-H-12F10F9E-84076M5-23

6、L13108 鄉(xiāng) 11 村長(zhǎng) 256.3 公里 總長(zhǎng) 727.7 公里問(wèn)題二 利用最小時(shí)模型所給結(jié)論 應(yīng)分組 ntt*+1=2429.83+1=4 當(dāng)分 4 組時(shí) 1 算法模型 1 給出的解為 組號(hào) 長(zhǎng)度 公里 經(jīng)鄉(xiāng)鎮(zhèn) 村 耗時(shí) 小時(shí) 1 154.2 4 11 23.4 2 140.1 5 8 22.0 3 167.2 3 8 18.8 4 201.2 5 7 22.8 2 算法模型 2 給出的為 組號(hào) 時(shí)間 路徑 1 23.0 2 01A3331R29Q303235 3413C32-0 9村5鄉(xiāng)140.7公里 2 23.1 8 25M67048-E9F10120 9村4鄉(xiāng)216.3公里 3

7、22.9 3 H1413G11J19L202521K0 7 村 5 鄉(xiāng) 207.55 公里 4 21.2 7 18L15I1617-2218-24N26272854-0 10 村 3 鄉(xiāng) 184.45 公里 注 以上每一路徑是含 0 的回路 如果兩點(diǎn)之間沒(méi)有公共邊 則走連接兩點(diǎn)之間的最短路徑因篇幅有限不能將途徑的所有點(diǎn)都羅列 問(wèn)題三 可以這樣認(rèn)為 往每個(gè)點(diǎn)都派一個(gè)巡視組去訪問(wèn) 并且都走最短路徑 這時(shí)所花時(shí)間最少由于點(diǎn)的個(gè)數(shù)有限 時(shí)間是容易求的 從地圖上看 H 是最短路徑最長(zhǎng)的點(diǎn) 且停留時(shí)間最長(zhǎng)它所花的時(shí)間即為所求:E=77.1 2/35 +2=6.43(小時(shí)) 我們認(rèn)為在這個(gè)時(shí)間限制下 最佳路線指派出人數(shù)最少路線 依靠最小時(shí)模型結(jié)論 可以給出估