案例：最佳災(zāi)情巡視路線課件

1、1. 問(wèn)題引入與分析 1) 98年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題“最佳災(zāi) 今年(2019年)夏天某縣遭受水災(zāi). 為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視. 巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線.情巡視路線”中的前兩個(gè)問(wèn)題是這樣的： 1）若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線. 2）假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t=1小時(shí)，汽車行駛速度V=35公里/小時(shí). 要在24小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下最佳的巡視路線.公路邊的數(shù)字為該路段的公里數(shù).2) 問(wèn)題分析：本題給

2、出了某縣的公路網(wǎng)絡(luò)圖，要求的是在不同的條件下，災(zāi)情巡視的最佳分組方案和路線. 將每個(gè)鄉(xiāng)（鎮(zhèn)）或村看作一個(gè)圖的頂點(diǎn)，各鄉(xiāng)鎮(zhèn)、村之間的公路看作此圖對(duì)應(yīng)頂點(diǎn)間的邊，各條再回到點(diǎn)O，使得總權(quán)（路程或時(shí)間）最小.公路的長(zhǎng)度（或行駛時(shí)間）看作對(duì)應(yīng)邊上的權(quán)，所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問(wèn)題就轉(zhuǎn)化圖論中一類稱之為旅行售貨員問(wèn)題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)O出發(fā)，行遍所有頂點(diǎn)至少一次 如第一問(wèn)是三個(gè)旅行售貨員問(wèn)題，第二問(wèn)是四本題是旅行售貨員問(wèn)題的延伸多旅行售貨員問(wèn)題. 本題所求的分組巡視的最佳路線，也就是m條眾所周知，旅行售貨員問(wèn)題屬于NP完全問(wèn)題，顯然本問(wèn)題更應(yīng)屬于NP完全問(wèn)題. 有鑒于此，經(jīng)過(guò)同一

3、點(diǎn)并覆蓋所有其他頂點(diǎn)又使邊權(quán)之和達(dá)到最小的閉鏈（閉跡）.個(gè)旅行售貨員問(wèn)題.即求解沒(méi)有多項(xiàng)式時(shí)間算法.一定要針對(duì)問(wèn)題的實(shí)際特點(diǎn)尋找簡(jiǎn)便方法，想找到解決此類問(wèn)題的一般方法是不現(xiàn)實(shí)的，對(duì)于規(guī)模較大的問(wèn)題可使用近似算法來(lái)求得近似最優(yōu)解.6. 最佳災(zāi)情巡視路線的模型的建立與求解問(wèn)題轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)O出發(fā),行遍所有頂點(diǎn)至少一次再回回到點(diǎn)O ,使得總權(quán)(路程或時(shí)時(shí)間)最小,即最佳旅行售貨員問(wèn)題.最佳旅行售貨員問(wèn)題是NP完全問(wèn)題,采用一種近似算法求其一個(gè)近似最優(yōu)解，來(lái)代替最優(yōu)解.算法一 求加權(quán)圖的最佳旅行售貨員回路近似算法: 1) 用圖論軟件包求出G中任意兩個(gè)頂點(diǎn)間的最短路, 構(gòu)造出完全

4、圖2) 輸入圖 的一個(gè)初始H圈；3) 用對(duì)角線完全算法（見(jiàn)23）產(chǎn)生一個(gè)初始圈;4) 隨機(jī)搜索出 中若干個(gè)H圈，例如2000個(gè)；5) 對(duì)第2)，3)，4)步所得的每個(gè)H圈，用二邊逐次修正法進(jìn)行優(yōu)化，得到近似最優(yōu)H圈；6) 在第5)步求出的所有H圈中，找出權(quán)最小的一個(gè), 此即要找的最優(yōu)H圈的近似解.因二邊逐次修正法的結(jié)果與初始圈有關(guān),故本算法第2)，3)，4)步分別用三種方法產(chǎn)生初始圈，以保證能得到較優(yōu)的計(jì)算結(jié)果. 問(wèn)題一 若分為三組巡視，設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線. 此問(wèn)題是多個(gè)售貨員的最佳旅行售貨員問(wèn)題.4) 此問(wèn)題包含兩方面：a)對(duì)頂點(diǎn)分組, b)在每組中求(單個(gè)售貨員)最佳

5、旅行售貨員回路. 因單個(gè)售貨員的最佳旅行售貨員回路問(wèn)題不存存在多項(xiàng)式時(shí)間內(nèi)的精確算法.故多也不 而圖中節(jié)點(diǎn)數(shù)較多，為53個(gè)，我們只能去尋求一種較合理的劃分準(zhǔn)則，對(duì)圖1進(jìn)行粗步劃分后,求出各部分的近似最佳旅行售貨員回路的權(quán),再進(jìn)一進(jìn)一步進(jìn)行調(diào)整，使得各部分滿足均衡性條件3). 從O點(diǎn)出發(fā)去其它點(diǎn)，要使路程較小應(yīng)盡量走O點(diǎn)到該點(diǎn)的最短路. 故用軟件包求出O點(diǎn)到其余頂點(diǎn)的最短路. 這些最短路構(gòu)成一棵O為樹根的樹.將從O點(diǎn)出發(fā)的樹枝稱為干枝.從O點(diǎn)出發(fā)到其它點(diǎn)共有6條干枝，它們的名稱分別為，. 在分組時(shí)應(yīng)遵從準(zhǔn)則： 準(zhǔn)則1 盡量使同一干枝上及其分枝上的點(diǎn)分在同一組.準(zhǔn)則2 應(yīng)將相鄰的干枝上的點(diǎn)分在同一

6、組； 準(zhǔn)則3 盡量將長(zhǎng)的干枝與短的干枝分在同一組.由上述分組準(zhǔn)則，我們找到兩種分組形式如下：分組1:（，），（，），（，）分組2:（，），（，），（，）分組1極不均衡,故考慮分組2.分組2:(,),(,),(,) 對(duì)分組2中每組頂點(diǎn)的生成子圖,用算法一求出近似最優(yōu)解及相應(yīng)的巡視路線. 在每個(gè)子圖所構(gòu)造的完全圖中,取一個(gè)盡量包含上圖中樹上的邊的H圈作為其第2)步輸入的初始圈.分組2的近似解 因?yàn)樵摲纸M的均衡度.所以此分法的均衡性很差. 為改善均衡性，將第組中的頂點(diǎn)C,2,3,D,4分給第組（頂點(diǎn)2為這兩組的公共點(diǎn)），重新分分組后的近似最優(yōu)解見(jiàn)表2.因該分組的均衡度 所以這種分法的均衡性較好. 問(wèn)

7、題二 當(dāng)巡視人員在各鄉(xiāng)（鎮(zhèn)）、村的停留停留時(shí)間一定,汽車的行駛速度一定,要在24小時(shí)內(nèi)完成巡視,至少要分幾組及最佳旅行的巡視路線. 由于T=2小時(shí),t=1小時(shí),V=35公里/小時(shí),需訪問(wèn)的鄉(xiāng)鎮(zhèn)共有17個(gè)，村共有35個(gè). 計(jì)算出在鄉(xiāng)(鎮(zhèn))及村的總停留時(shí)間為17 2+35=69小時(shí)，要在24小時(shí)內(nèi)完成巡回，若不考慮行走時(shí)間，有: 69/i24(i為分的組數(shù)). 得i最小為4，故至少要分4組. 由于該網(wǎng)絡(luò)的鄉(xiāng)(鎮(zhèn))、村分布較為均勻,故有可能找出停留時(shí)間盡量均衡的分組,當(dāng)分4組時(shí)各組停停留時(shí)間大約為69/4=17.25小時(shí)，則每組分配在路路途上的時(shí)間大約為24-17.25=6.75小時(shí).而前面討論過(guò),分三組時(shí)有個(gè)總路程599.8公里的巡視路線，分4組時(shí)的總路程不會(huì)比599.8公里大太多,不妨以599.8公里來(lái)計(jì)算.路上約用599.8/35=17小時(shí),若平均分配給4個(gè)組,每個(gè)組約需17/4=4.25小時(shí)6.75小小時(shí),故分成4組是可能辦到的. 現(xiàn)在嘗試將頂點(diǎn)分為4組.分組的原則：除遵從前面準(zhǔn)則1、2、3外，還應(yīng)遵從以下準(zhǔn)則：準(zhǔn)則4 盡量使各組的停留時(shí)間相等. 用上述原則在下圖上將圖分為4組，同時(shí)計(jì)算各組的停留時(shí)間,然后用算法一算出各組的近似最最佳旅行售貨員巡回，得出路線長(zhǎng)度及行走時(shí)間,從而得出完成巡視的近似最佳時(shí)間. 用算法一計(jì)計(jì)算時(shí)，初始圈的