優(yōu)選全國大學(xué)生數(shù)學(xué)建模競賽題

1、1998年全國大學(xué)生數(shù)學(xué)建模競賽題目B題災(zāi)情巡視路線下圖為某縣的鄉(xiāng)（鎮(zhèn)）、村公路網(wǎng)示意圖，公路邊的數(shù)字為該路段的公里數(shù)。今年夏天該縣遭受水災(zāi)。為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線。（1）若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線。假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2小時，在各村停留時間t=1小時，汽車行駛速度V=35公里/小時。要在24小時內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下你認(rèn)為最佳的巡視路線。在上述關(guān)于T,t和V的假定下，如果巡視人員足夠多，完成巡視

2、的最短時間是多少；給出在這種最短時間完成巡視的要求下，你認(rèn)為最佳的巡視路線。若巡視組數(shù)已定（如三組），要求盡快完成巡視，討論T,t和V改變對最佳巡視路線的影響。災(zāi)情巡視路線模型摘要本文將求最佳巡視路線問題轉(zhuǎn)化為圖論中求最佳推銷員回路（哈米爾頓回路）的問題,并用近似算法去尋求近似最優(yōu)解。對賦權(quán)圖中的路徑分組問題定義了均衡度用以衡量分組的均衡性。對問題1和問題2先定出幾個分的準(zhǔn)則進(jìn)行初步分組，并用近似算法求每一組的近似最佳推銷員回路，再根據(jù)均衡度進(jìn)行微調(diào)，得到較優(yōu)的均衡分組和每組的近似最佳推銷員回路。對問題1,運(yùn)用求任意兩點(diǎn)間最短路的Floyd算法，得出總路程較短且各組盡可能均衡的路線，各組的巡視

3、路程分別為公里，公里，公里，總路程公里。對問題2,證明了應(yīng)至少分為4組,并求出了分為4組時各組的較優(yōu)巡視路線，各組的巡視時間分別為小時，小時，小時，小時。對問題3,求出完成巡視的最短時間為小時，并用較為合理的分組的準(zhǔn)則，分成22個組對問題4,研究了在不影響分組的均衡條件下,T,t,V的允許變化范圍，并得出了這三個變量的關(guān)系式，并由此對分三個組的情況進(jìn)行了具體討論。關(guān)鍵詞：最佳推銷員回路問題哈米爾頓回路賦權(quán)圖近似算法均衡度一、問題重述1998年夏天某縣遭受水災(zāi)。為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各17個鄉(xiāng)（鎮(zhèn)）、35個村巡視。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、

4、村，又回到縣政府所在地的路線。（1）若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線。假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2小時，在各村停留時間t=1小時，汽車行駛速度V=35公里/小時。要在24小時內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下你認(rèn)為最佳的巡視路線。在上述關(guān)于T,t和V的假定下，如果巡視人員足夠多，完成巡視的最短時間是多少；給出在這種最短時間完成巡視的要求下，你認(rèn)為最佳的巡視路線。若巡視組數(shù)已定（如三組），要求盡快完成巡視，討論T,t和V改變對最佳巡視路線的影響。二、問題分析本題給出了某縣的公路網(wǎng)絡(luò)圖，要求的是在不同的條件下，災(zāi)情巡視的最分組方案和路線.將每個鄉(xiāng)（鎮(zhèn)）

5、或村看作一個圖的頂點(diǎn)，各鄉(xiāng)鎮(zhèn)、村之間的公路看作此圖對應(yīng)頂點(diǎn)間的邊，各條公路的長度（或行駛時間）看作對應(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)至少一次再回到點(diǎn)0,使得總權(quán)（路程或時間）最小.本題是旅行售貨員問題的延伸-多旅行售貨員問題.本題所求的分組巡視的最佳路線，也就是m條經(jīng)過同一點(diǎn)并覆蓋所有其他頂點(diǎn)又使邊權(quán)之和達(dá)到最小的閉鏈（閉跡）.如第一問是三個旅行售貨員問題，第二問是四個旅行售貨員問題.眾所周知，旅行售貨員問題屬于NP完全問題，即求解沒有多項(xiàng)式時間算法.顯然本問題更應(yīng)屬于NP完全問題.有鑒于

6、此，一定要針對問題的實(shí)際特點(diǎn)尋找簡便方法，想找到解決此類問題的一般方法是不現(xiàn)實(shí)的，對于規(guī)模較大的問題可使用近似算法來求得近似最優(yōu)解.三、模型假設(shè)1 .汽車在路上的速度總是一定，不會出現(xiàn)拋錨等現(xiàn)象；忽略天氣、故障等因素的影響。2 .巡視當(dāng)中，在每個鄉(xiāng)鎮(zhèn)、村的停留時間一定，不會出現(xiàn)特殊情況而延誤時間；3 .每個小組的汽車行駛速度完全一樣；4 .分組后，各小組只能走自己區(qū)內(nèi)的路，不能走其他小組的路，除公共路外。四、符號說明w（i,j）任意兩點(diǎn)i,j問的間距。q各點(diǎn)的停留時間，即點(diǎn)權(quán)。V汽車行駛速度。dj從任意點(diǎn)i至點(diǎn)j的時間，則djw（i,j）/V五、模型建立與求解公路網(wǎng)圖中，每個鄉(xiāng)（鎮(zhèn)）或村看作圖

7、中的一個節(jié)點(diǎn)，各鄉(xiāng)（鎮(zhèn)）、村之間的公路看作圖中對應(yīng)節(jié)點(diǎn)間的邊，各條公路的長度（或行駛時間）看作對應(yīng)邊上的權(quán)，所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問題就轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)0出發(fā)，行遍所有頂點(diǎn)至少一次再回到O點(diǎn)，使得總權(quán)（路程或時間）最小，此即最佳推銷員回路問題。在加權(quán)圖G中求最佳推銷員回路問題是N完全問題，我們采用一種近似算法求出該問題的一個近似最優(yōu)解，來代替最優(yōu)解，算法如下：算法一求加權(quán)圖G（V,E）的最佳推銷員回路的近似算法：1 .用圖論軟件包求出G中任意兩個頂點(diǎn)間的最短路，構(gòu)造出完備圖G（V,E）,x,yE,x,yMindgx,y;2 .輸入圖G的一個初始H圈；3 .用對角線

8、完全算法（見23）產(chǎn)生一個初始H圈；4 .隨機(jī)搜索出G中若干個H圈，例如2000個；5 .對第2、3、4步所得的每個H圈，用二邊逐次修正法進(jìn)行優(yōu)化，得到近似最佳H圈；6 .在第5步求出的所有H圈中，找出權(quán)最小的一個，此即要找的最佳H圈的近似解.由于二邊逐次修正法的結(jié)果與初始圈有關(guān)，故本算法第2、3、4步分別用三種方法產(chǎn)生初始圈，以保證能得到較優(yōu)的計(jì)算結(jié)果。問題一：此問題是多個推銷員的最佳推銷員回路問題.即在加權(quán)圖G中求頂點(diǎn)集V的劃分MM,Vn,將G分成n個生成子圖GV|,GV2,GVn,使得（1）頂點(diǎn)OVJ=1,2,3nUViVGi1（3） MaxwCiwCj，其中Ci為Vi的導(dǎo)出子圖GVi中

9、的最佳推銷員回MaxwCi路，G為Ci的權(quán)，i,j=1,2,3nn（4） wCiMin1 1定義稱MaxIwCiwCjI為該分組的實(shí)際均衡度。為最大容許均衡度。0MaxwCi顯然001,0越小，說明分組的均衡性越好.取定一個后，0與滿足條件（3）的分組是一個均衡分組.條件（4）表示總巡視路線最短。此問題包含兩方面：第一、對頂點(diǎn)分組；第二、在每組中求最佳推銷員回路，即為單個推銷員的最佳推銷員問題。由于單個推銷員的最佳推銷員回路問題不存在多項(xiàng)式時間內(nèi)的精確算法，故多個推銷員的問題也不存在多項(xiàng)式時間內(nèi)的精確算法.而圖中節(jié)點(diǎn)數(shù)較多，為53個，我們只能去尋求一種較合理的劃分準(zhǔn)則，對圖11-9進(jìn)行粗步劃分

10、后，求出各部分的近似最佳推銷員回路的權(quán)，再進(jìn)一步進(jìn)行調(diào)整，使得各部分滿足均衡性條件（3）o圖11-10O點(diǎn)到任意點(diǎn)的最短路圖（單位：公從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ā)的樹枝稱為干枝，見圖1110,從圖中可以看出，從O點(diǎn)出發(fā)到其它點(diǎn)共有6條干枝，它們的名稱分別為，。根據(jù)實(shí)際工作的經(jīng)驗(yàn)及上述分析，在分組時應(yīng)遵從以下準(zhǔn)則：準(zhǔn)則一：盡量使同一干枝上及其分枝上的點(diǎn)分在同一組；準(zhǔn)則二：應(yīng)將相鄰的干枝上的點(diǎn)分在同一組；準(zhǔn)則三：盡量將長的干枝與短的干枝分在同一組.由上述分組準(zhǔn)則，我們找到兩種分組形

11、式如下：分組一：（，），（，），（，）分組二：（，），（，），（，）顯然分組一的方法極不均衡，故考慮分組二。對分組二中每組頂點(diǎn)的生成子圖，用算法一求出近似最優(yōu)解及相應(yīng)的巡視路線.使用算法一時，在每個子圖所構(gòu)造的完備圖中，取一個盡量包含圖11-10中樹上的邊的H圈作為其第2步輸入的初始圈。分組二的近似解見表1。表1（單位：公里）小組名稱路線總路線長度路線的總長度IO-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-OIIO-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-7-E-8-4-D-3-CIIIO-R-

12、29-Q-30-32-3A-B-1-O因?yàn)樵摲纸M的均衡度0=CiC2241.9125.5%MaxCi241.9i1,2.3所以此分法的均衡性很差。為改善均衡性，將第R組中的頂點(diǎn)C,2,3,D,4分給第田組（頂點(diǎn)2為這兩組的公共點(diǎn)），重新分組后的近似最優(yōu)解見表2。表2（單位：公里）編號路線路線長度路線總長度IO-P282726N-2423221716I15I18212025MHOIIO2567E8E9F10F12H-1413G-11J19L65-2OIIIO-R-29Q-303231333534A-1BC3D4D-32O因該分組的均衡度oC豆216.4191.1%MaxCi216.4i1,2,3

13、所以這種分法的均衡性較好。問題二由于T=2小時，t=1小時，V=35公里/小時，需訪問的鄉(xiāng)鎮(zhèn)共有17個，村共有35個.計(jì)算出在鄉(xiāng)（鎮(zhèn)）及村的總停留時間為172+35=69小時，要在24小時內(nèi)完成巡回，若不考慮行走時間，有：6924（i為分的組數(shù)）.得i最小為4,故至少要分4i組。由于該網(wǎng)絡(luò)的鄉(xiāng)（鎮(zhèn)）、村分布較為均勻，故有可能找出停留時間盡量均衡的分組，69.一.當(dāng)分4組時各組停留時間大約為6917.25小時，則每組分配在路途上的時間大約為4=小時.而前面討論過，分三組時有個總路程公里的巡視路線，分4組時的總路程不會比公里大太多，不妨以公里來計(jì)算.路上時間約為599817小時，若平均分配給435

14、17個組，每個組約需上=小時小時，故分成4組是可能辦到的。4現(xiàn)在嘗試將頂點(diǎn)分為4組.分組的原則：除遵從前面準(zhǔn)則一、二、三外，還應(yīng)遵從以下準(zhǔn)則：準(zhǔn)則四：盡量使各組的停留時間相等。用上述原則在圖11-10上將圖分為4組，同時計(jì)算各組的停留時間，然后用算法一算出各組的近似最佳推銷員巡回，得出路線長度及行走時間，從而得出完成巡視的近似最佳時間.用算法一計(jì)算時，初始圈的輸入與分三組時同樣處理。這4組的近似最優(yōu)解見表3:表3（路程單位：公里；時間單位：小時）組名路線路線總長度停留時間一時間完成巡視的總時間IO2567E8E11G-1212F10F9E7652O17IIO-R-29Q-30Q-28-2726

15、N-2423221716172223N-26P-O16IIIO-IVH252021K18I151413J19L一6MO18IVO-RA3331323534B1C3D4D32-o16618上表中符號說明：加有底紋的表示前面經(jīng)過并停留過，此次只經(jīng)過不需停留；加框的表示此點(diǎn)只經(jīng)過不停留。該分組實(shí)際均衡度。=22.7421.69%22.74可以看出，表3分組的均衡度很好，且完全滿足24小時完成巡視的要求。問題三我們發(fā)現(xiàn)從O點(diǎn)巡視H點(diǎn)的最短時間是所有最短時間中最長的，具距離為公里。其時間為因此，T=2小時，t=1小時，V=35公里/小時。若巡視人員足夠多，完成巡視的最短時間為小時。在最短時間內(nèi)限定一下，

16、完成巡視的最優(yōu)路線應(yīng)滿足如下條件：(1)每個組巡視的總時間不能超過最短時間儲6.43小時；(2)所有點(diǎn)都必須訪問到，不能漏點(diǎn)；(3)所需巡視組數(shù)要盡量少；在尋求最優(yōu)路線時，從距離O點(diǎn)較遠(yuǎn)的一些點(diǎn)(如點(diǎn)12、10、15、22)開始搜索比較容易，因?yàn)榈竭@些點(diǎn)的路線比較少。具體方法如下：第一步：依據(jù)圖1算出從O點(diǎn)到每一個點(diǎn)的最短距離；第二步：找出其中最大的一個，算出從O點(diǎn)沿最短的路巡視的時間3,并求出VttHti；第三步：若t1,則這一組只能訪問這一點(diǎn)；若t1,則在余下的點(diǎn)找到距離O點(diǎn)最遠(yuǎn)的點(diǎn)，根據(jù)條件看這一組能否巡視這一點(diǎn)；第四步：若能巡視，則算出t,轉(zhuǎn)到第三步；第五步：若不能則依次判斷次遠(yuǎn)點(diǎn)、第

17、三遠(yuǎn)點(diǎn)，滿足總巡視時間不超過tH,就讓這組巡視到這一點(diǎn)，直到t1,然后再從第二步開始。通過以上方法，最后我們找到的最優(yōu)解是22個組，如下表所示:編號巡視路徑停留地點(diǎn)所需時間時間差1O-H-OH012O-2-5-6-L-19-J-13-1413,14-13-J-19-L-6-5-2-03O-M-25-21-K-18-I-15-I-16-17-K-21-25-M-O15,164O-2-5-6-7-E-9-F-12-G-11-E-7-6-5-2-O12,115O-2-5-6-7-E-8-E-9-F-10-F-9-E-7-6-5-2-O8,106O-2-5-6-7-E-11-G-11-E-7-6-5-

18、2-OG7O-2-5-6-7-E-9-F-9-E-7-6-5-2-O9,F8O-2-5-6-L-19-J-18-K-21-25-M-OJ,189O-M-25-21-K-18-I-18-K-21-25-M-OI10O-M-25-21-K-17-22-23-N-26-P-O17,22,2311O-2-5-G-L-19-L-6-5-2-OL,1912O-M-25-20-21-23-24-N-26-P-O20,21,2413O-M-25-21-K-21-25-M-O25,K14O-2-5-6-7-E-7-6-5-2-O6,7,E15O-R-3A-1-O31,32,35,3416O-R-29-Q-30-

19、Q-28-P-OQ,30,2817O-P-26-27-26-N-26-P-O26,27,N18O-2-3-D-4-D-3-2-O3,D,419O-1-A-33-31-R-29-R-OA,33,2920O-2-5-M-O2,5,M21O-1-B-C-O1,B,C22O-P-O-R-OP,R問題四巡視組數(shù)已定,要求盡快完成巡視，討論T,t和V的改變對最佳巡視路線的影響。要盡快完成巡視，就得要求每組完成巡視時間盡量均衡，因?yàn)榭偟耐瓿裳惨晻r間按最長的完成巡視時間計(jì)算?，F(xiàn)在討論在均衡度允許的范圍內(nèi)已分成n組后，改變T,t和V對最佳巡視路線的影響。顯然在分組不變的情況下，無論了T,t、V如何改變，對每組內(nèi)

20、的最佳巡視路線是沒有影響的，但可能會影響各組間的均衡性。因此該問題實(shí)際上討論T,t和V對于分組的影響，即在不破壞原來分組均衡的條件下，T,t和V允許的最大變化范圍。在分n組的情況下，設(shè)S：表示第i組的最佳推銷員回路路線總長度；Xi：表示第i組所要停留的鄉(xiāng)鎮(zhèn)的數(shù)目；Y:表示第i組所要停留的村的數(shù)目；i=1,2,3,n顯然，當(dāng)XiXj,YYj,SSj；i,j1,2,3,K,n時，即每組的鄉(xiāng)(鎮(zhèn))數(shù)、村數(shù)、最佳巡回的長度均相等，因而分組絕對均衡時，即0=0時，無論T,t和V如何改變都不會改變原來分組的均衡。(一)不影響分組的均衡時，T,t和V的最大允許變化范圍的討論：對任意一個組i,其完成巡視的時間

21、設(shè)均衡分組的最大允許時間均衡度為，即則有TTjMaxTii1,2,3,K,n記MaxTi,則表示均衡分組所允許的最大時間誤差，則i1,2,3,K,nSSj(XiXj)T(YYj)tF_j(1)由(1)式我們得到SiSj(XiXj)T(YiYj)t(2)由式(2)可得1.當(dāng)XiXj>0時，要保持原均衡分組不變，T必須滿足的條件為MaxXiXj02 .當(dāng)YYj0時,MaxYY.0ij(YYj)tSiSjV(YiYj)tMinSiSjVXiXjXiXj0XiXj3 3)要保持原均衡分組不變,t必須滿足的條件為SSj(XiXj)tYjMinYY.0ijSSj(XiXj)tJYYj3.當(dāng)§

22、;Sj>0時，由當(dāng)(XiXj)T(Yi當(dāng)XiXjTYi(2)式得Yj)t時，有Yjt時，有VSmSn0SiSjXiXjTYiYjt(6)由(3)(6)式，當(dāng)T,t,V三個變量中任意兩個變量無論如何變化，都可計(jì)算出為保持均衡性分組不變，三個變量所允許的最大變化范圍。(二)分三組的實(shí)例討論現(xiàn)對分三組的情況進(jìn)布寸論對問題一中所得的三個分組若考慮停留時間和行駛時間且取TT02小時，tt01小時，VV035公里/小時，結(jié)果如表5:表5(路程單位：公里；時間單位：小時)編號行駛時間總時間I513II611III611實(shí)際均衡度為。29828462.5%。29.18實(shí)際時間誤差為02.5%29.180

23、.72小時。現(xiàn)分別規(guī)定均衡分組的最大允許均衡度2.5%和5%,即最大容許的時間誤差分別為0.72小時和1.44小時，計(jì)算出T,t,V三個參量中固定任意兩個時,要不破壞原均衡分組，另一個參量所容許的變化范圍，結(jié)果如下表：表6V,t/、艾T,V/、艾T,t/、艾上表可以看出：（1）當(dāng)實(shí)際均衡度°2.5%剛好等于最大容許均衡度2.5%時，要保持原均衡分組，當(dāng)t,V不變時，T只能減小，且下界為小時；T的上界為T02小時；T,V不變時，t只能增大，且上界為小時；t的下界為t01小時；t,T不變時，V只能增大，且下界為35;無上界；（2）當(dāng)實(shí)際均衡度02.5%小于最大容許均衡度5%時，即0時要保

24、持原均衡分組，當(dāng)t,V不變時，T變化的下界為小時；T的上界為小時；T,V不變時，t的上界為小時；t的下界為小時；t,T不變時，V增大但無上界，且下界為公里/小時；（三）對實(shí)例結(jié)果的分析上述實(shí)例的均衡分組有一個特點(diǎn)，各組的停留時間相等，即取TT02小時，tt。1小時，VV035公里/小時，在表5的分組中定義4各組的停留時間相等的均衡分組稱為停留時間相等的均衡分組，由（7）式得現(xiàn)討論對停留時間相等的均衡分組,T,t,V的變化規(guī)律，對停留時間相等的均衡分組，分組的實(shí)際時間誤差：»».'.'.其中，i為使Si最大的組的標(biāo)號；j為使Sj最小的組的標(biāo)號。（*）當(dāng)T,t不變時，即TT0,tt0時，因XiXjT0YiYjt00，由（6）式知道，要保持平衡分組,V的下界應(yīng)為取0時，由（9）式得0時，由（9）式得故有以