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

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

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

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

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

5、或村看作一個圖的頂點，各鄉(xiāng)鎮(zhèn)、村之間的公路看作此圖對應(yīng)頂點間的邊，各條公路的長度（或行駛時間）看作對應(yīng)邊上的權(quán)，所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問題就轉(zhuǎn)化圖論中一類稱之為旅行售貨員問題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點O出發(fā)，行遍所有頂點至少一次再回到點0,使得總權(quán)（路程或時間）最小.本題是旅行售貨員問題的延伸-多旅行售貨員問題.本題所求的分組巡視的最佳路線，也就是m條經(jīng)過同一點并覆蓋所有其他頂點又使邊權(quán)之和達到最小的閉鏈（閉跡）.如第一問是三個旅行售貨員問題，第二問是四個旅行售貨員問題.眾所周知，旅行售貨員問題屬于NP完全問題，即求解沒有多項式時間算法.顯然本問題更應(yīng)屬于NP完全問題.有鑒于

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

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

8、完全算法（見23）產(chǎn)生一個初始H圈；4 .隨機搜索出G中若干個H圈，例如2000個；5 .對第2、3、4步所得的每個H圈，用二邊逐次修正法進行優(yōu)化，得到近似最佳H圈；6 .在第5步求出的所有H圈中，找出權(quán)最小的一個，此即要找的最佳H圈的近似解.由于二邊逐次修正法的結(jié)果與初始圈有關(guān)，故本算法第2、3、4步分別用三種方法產(chǎn)生初始圈，以保證能得到較優(yōu)的計算結(jié)果。問題一：此問題是多個推銷員的最佳推銷員回路問題.即在加權(quán)圖G中求頂點集V的劃分MM,Vn,將G分成n個生成子圖GV|,GV2,GVn,使得（1）頂點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為該分組的實際均衡度。為最大容許均衡度。0MaxwCi顯然001,0越小，說明分組的均衡性越好.取定一個后，0與滿足條件（3）的分組是一個均衡分組.條件（4）表示總巡視路線最短。此問題包含兩方面：第一、對頂點分組；第二、在每組中求最佳推銷員回路，即為單個推銷員的最佳推銷員問題。由于單個推銷員的最佳推銷員回路問題不存在多項式時間內(nèi)的精確算法，故多個推銷員的問題也不存在多項式時間內(nèi)的精確算法.而圖中節(jié)點數(shù)較多，為53個，我們只能去尋求一種較合理的劃分準則，對圖11-9進行粗步劃分

10、后，求出各部分的近似最佳推銷員回路的權(quán)，再進一步進行調(diào)整，使得各部分滿足均衡性條件（3）o圖11-10O點到任意點的最短路圖（單位：公從O點出發(fā)去其它點，要使路程較小應(yīng)盡量走O點到該點的最短路.故用圖論軟件包求出O點到其余頂點的最短路，這些最短路構(gòu)成一棵O為樹根的樹，將從O點出發(fā)的樹枝稱為干枝，見圖1110,從圖中可以看出，從O點出發(fā)到其它點共有6條干枝，它們的名稱分別為，。根據(jù)實際工作的經(jīng)驗及上述分析，在分組時應(yīng)遵從以下準則：準則一：盡量使同一干枝上及其分枝上的點分在同一組；準則二：應(yīng)將相鄰的干枝上的點分在同一組；準則三：盡量將長的干枝與短的干枝分在同一組.由上述分組準則，我們找到兩種分組形

11、式如下：分組一：（，），（，），（，）分組二：（，），（，），（，）顯然分組一的方法極不均衡，故考慮分組二。對分組二中每組頂點的生成子圖，用算法一求出近似最優(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因為該分組的均衡度0=CiC2241.9125.5%MaxCi241.9i1,2.3所以此分法的均衡性很差。為改善均衡性，將第R組中的頂點C,2,3,D,4分給第田組（頂點2為這兩組的公共點），重新分組后的近似最優(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個.計算出在鄉(xiāng)（鎮(zhèn)）及村的總停留時間為172+35=69小時，要在24小時內(nèi)完成巡回，若不考慮行走時間，有：6924（i為分的組數(shù)）.得i最小為4,故至少要分4i組。由于該網(wǎng)絡(luò)的鄉(xiāng)（鎮(zhèn)）、村分布較為均勻，故有可能找出停留時間盡量均衡的分組，69.一.當分4組時各組停留時間大約為6917.25小時，則每組分配在路途上的時間大約為4=小時.而前面討論過，分三組時有個總路程公里的巡視路線，分4組時的總路程不會比公里大太多，不妨以公里來計算.路上時間約為599817小時，若平均分配給435

14、17個組，每個組約需上=小時小時，故分成4組是可能辦到的。4現(xiàn)在嘗試將頂點分為4組.分組的原則：除遵從前面準則一、二、三外，還應(yīng)遵從以下準則：準則四：盡量使各組的停留時間相等。用上述原則在圖11-10上將圖分為4組，同時計算各組的停留時間，然后用算法一算出各組的近似最佳推銷員巡回，得出路線長度及行走時間，從而得出完成巡視的近似最佳時間.用算法一計算時，初始圈的輸入與分三組時同樣處理。這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)過不需停留；加框的表示此點只經(jīng)過不停留。該分組實際均衡度。=22.7421.69%22.74可以看出，表3分組的均衡度很好，且完全滿足24小時完成巡視的要求。問題三我們發(fā)現(xiàn)從O點巡視H點的最短時間是所有最短時間中最長的，具距離為公里。其時間為因此，T=2小時，t=1小時，V=35公里/小時。若巡視人員足夠多，完成巡視的最短時間為小時。在最短時間內(nèi)限定一下，

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

17、三遠點，滿足總巡視時間不超過tH,就讓這組巡視到這一點，直到t1,然后再從第二步開始。通過以上方法，最后我們找到的最優(yōu)解是22個組，如下表所示:編號巡視路徑停留地點所需時間時間差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的改變對最佳巡視路線的影響。要盡快完成巡視，就得要求每組完成巡視時間盡量均衡，因為總的完成巡視時間按最長的完成巡視時間計算?，F(xiàn)在討論在均衡度允許的范圍內(nèi)已分成n組后，改變T,t和V對最佳巡視路線的影響。顯然在分組不變的情況下，無論了T,t、V如何改變，對每組內(nèi)

20、的最佳巡視路線是沒有影響的，但可能會影響各組間的均衡性。因此該問題實際上討論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顯然，當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.當XiXj>0時，要保持原均衡分組不變，T必須滿足的條件為MaxXiXj02 .當YYj0時,MaxYY.0ij(YYj)tSiSjV(YiYj)tMinSiSjVXiXjXiXj0XiXj3 3)要保持原均衡分組不變,t必須滿足的條件為SSj(XiXj)tYjMinYY.0ijSSj(XiXj)tJYYj3.當§

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

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

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