.,1,1.問題引入與分析,1)98年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題“最佳災(zāi),今年(1998年)夏天某縣遭受水災(zāi).為考察災(zāi)情、,組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到,全縣各鄉(xiāng)（鎮(zhèn)）、村巡視.巡視路線指從縣政府,所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政,府所在地的路線.,情巡視路線”中的前兩個(gè)問題是這樣的：,.,2,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)分,幾組；給出這種分組下最佳的巡視路線.,.,3,公路邊的數(shù)字為該路段的公里數(shù).,.,4,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ò)圖，問題就轉(zhuǎn)化圖論中,一類稱之為旅行售貨員問題，即在給定的加權(quán)網(wǎng)絡(luò),圖中尋找從給定點(diǎn)O出發(fā)，行遍所有頂點(diǎn)至少一次,.,5,如第一問是三個(gè)旅行售貨員問題，第二問是四,本題是旅行售貨員問題的延伸,多旅行售貨員問題.,本題所求的分組巡視的最佳路線，也就是m條,眾所周知，旅行售貨員問題屬于NP完全問題，,顯然本問題更應(yīng)屬于NP完全問題.有鑒于此，,經(jīng)過同一點(diǎn)并覆蓋所有其他頂點(diǎn)又使邊權(quán)之和達(dá)到,最小的閉鏈（閉跡）.,個(gè)旅行售貨員問題.,即求解沒有多項(xiàng)式時(shí)間算法.,一定要針對(duì)問題的實(shí)際特點(diǎn)尋找簡(jiǎn)便方法，想找到,解決此類問題的一般方法是不現(xiàn)實(shí)的，對(duì)于規(guī)模較大,的問題可使用近似算法來求得近似最優(yōu)解.,.,6,6.最佳災(zāi)情巡視路線的模型的建立與求解,問題轉(zhuǎn)化為在,給定的加權(quán)網(wǎng),絡(luò)圖中尋找從,給定點(diǎn)O出發(fā),行遍所有頂點(diǎn),至少一次再回,回到點(diǎn)O,使得,總權(quán)(路程或時(shí),時(shí)間)最小,即,最佳旅行售貨,員問題.,.,7,最佳旅行售貨員問題是NP完全問題,采用一種,近似算法求其一個(gè)近似最優(yōu)解，來代替最優(yōu)解.,算法一求加權(quán)圖的最佳旅行售貨員回路近似算法:,1)用圖論軟件包求出G中任意兩個(gè)頂點(diǎn)間的最短路,構(gòu)造出完全圖,2)輸入圖的一個(gè)初始H圈；,3)用對(duì)角線完全算法（見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é)果.,.,8,問題一若分為三組巡視，設(shè)計(jì)總路程最短且各,組盡可能均衡的巡視路線.,此問題是多個(gè)售貨員的最佳旅行售貨員問題.,4),.,9,此問題包含兩方面：a)對(duì)頂點(diǎn)分組,b)在每組中,求(單個(gè)售貨員)最佳旅行售貨員回路.,因單個(gè)售貨員的最佳旅行售貨員回路問題不存,存在多項(xiàng)式時(shí)間內(nèi)的精確算法.,故多,也不,.,10,而圖中節(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ā)的樹枝稱為干枝.,.,11,從O點(diǎn)出發(fā)到其它點(diǎn)共有6條干枝，它們的名稱,分別為，.,在分組時(shí)應(yīng)遵從準(zhǔn)則：,準(zhǔn)則1盡量使同一干枝上及其分枝上的點(diǎn)分在同一組.,準(zhǔn)則2應(yīng)將相鄰的干枝上的點(diǎn)分在同一組；,準(zhǔn)則3盡量將長(zhǎng)的干枝與短的干枝分在同一組.,由上述分組準(zhǔn)則，我們找到兩種分組形式如下：,分組1:（，），（，），（，）,分組2:（，），（，），（，）,分組1極不均衡,故考慮分組2.,.,12,分組2:(,),(,),(,),對(duì)分組2中每組頂點(diǎn)的生成子圖,用算法一求出近似最優(yōu)解及相應(yīng)的巡視路線.,在每個(gè)子圖所構(gòu)造的完全圖中,取一個(gè)盡量包含上圖中樹上的邊的H圈作為其第2)步輸入的初始圈.,.,13,分組2的近似解,.,14,因?yàn)樵摲纸M的均衡度,.所以此分法的均衡性很差.,為改善均衡性，將第組中的頂點(diǎn)C,2,3,D,4,分給第組（頂點(diǎn)2為這兩組的公共點(diǎn)），重新分,分組后的近似最優(yōu)解見表2.,.,15,.,16,因該分組的均衡度,所以這種分法的均衡性較好.,問題二當(dāng)巡視人員在各鄉(xiāng)（鎮(zhèn)）、村的停留,停留時(shí)間一定,汽車的行駛速度一定,要在24小時(shí)內(nèi),完成巡視,至少要分幾組及最佳旅行的巡視路線.,.,17,由于T=2小時(shí),t=1小時(shí),V=35公里/小時(shí),需訪問,的鄉(xiāng)鎮(zhèn)共有17個(gè)，村共有35個(gè).計(jì)算出在鄉(xiāng)(鎮(zhèn))及,村的總停留時(shí)間為172+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í).而前面討,論過,分三組時(shí)有個(gè)總路程599.8公里的巡視路線，,分4組時(shí)的總路程不會(huì)比599.8公里大太多,不妨以,599.8公里來計(jì)算.路上約用599.8/35=17小時(shí),若平,均分配給4個(gè)組,每個(gè)組約需17/4=4.25小時(shí)6.75小,小時(shí),故分成4組是可能辦到的.,.,18,現(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í)，初始圈的