2021年全國大學(xué)生數(shù)學(xué)建模競賽題

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è)計總路程最短且各組盡量均衡巡視路線。(2)假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2小時，在各村停留時間t=1小時，汽車行駛速度V=35公里/小時。要在24小時內(nèi)完畢巡視，至少應(yīng)分幾組；給出這種分組下你以為最佳巡視路線。(3)在上述關(guān)于T，t和V假定下，如果巡視人員足夠多，完畢巡視最短時間是多少；給出在這種最短時間完畢巡視規(guī)定下，你以為最佳巡視路線。(4)若巡視組數(shù)已定(如三組），規(guī)定盡快完畢巡視，討論T，t和V變化對最佳巡視路線影響。

災(zāi)情巡視路線模型摘要本文將求最佳巡視路線間題轉(zhuǎn)化為圖論中求最佳推銷員回路（哈米爾頓回路）問題,并用近似算法去謀求近似最優(yōu)解。對賦權(quán)圖半途徑分組問題定義了均衡度用以衡量分組均衡性。對問題1和問題2先定出幾種分準(zhǔn)則進(jìn)行初步分組,并用近似算法求每一組近似最佳推銷員回路,再依照均衡度進(jìn)行微調(diào),得到較優(yōu)均衡分組和每組近似最佳推銷員回路。對問題1，運(yùn)用求任意兩點(diǎn)間最短路Floyd算法,得出總路程較短且各組盡量均衡路線,各組巡視路程分別為216.4公里,191.1公里,192.3公里,總路程599.8公里。對問題2,證明了應(yīng)至少分為4組,并求出了分為4組時各組較優(yōu)巡視路線,各組巡視時間分別為22.74小時,22.59小時,21.69小時,22.54小時。對問題3,求出完畢巡視最短時間為6.43小時,并用較為合理分組準(zhǔn)則,提成22個組對問題4，研究了在不影響分組均衡條件下，T,t,V容許變化范疇,并得出了這三個變量關(guān)系式,并由此對分三個組狀況進(jìn)行了詳細(xì)討論。 核心詞：最佳推銷員回路問題哈米爾頓回路賦權(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)）、村，又回到縣政府所在地路線。(1)若分三組（路）巡視，試設(shè)計總路程最短且各組盡量均衡巡視路線。(2)假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2小時，在各村停留時間t=1小時，汽車行駛速度V=35公里/小時。要在24小時內(nèi)完畢巡視，至少應(yīng)分幾組；給出這種分組下你以為最佳巡視路線。(3)在上述關(guān)于T，t和V假定下，如果巡視人員足夠多，完畢巡視最短時間是多少；給出在這種最短時間完畢巡視規(guī)定下，你以為最佳巡視路線。(4)若巡視組數(shù)已定(如三組），規(guī)定盡快完畢巡視，討論T，t和V變化對最佳巡視路線影響。二、問題分析 本題給出了某縣公路網(wǎng)絡(luò)圖，規(guī)定是在不同條件下，災(zāi)情巡視最分組方案和路線.將每個鄉(xiāng)（鎮(zhèn)）或村看作一種圖頂點(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)O，使得總權(quán)（路程或時間）最小.本題是旅行售貨員問題延伸－多旅行售貨員問題.本題所求分組巡視最佳路線，也就是m條通過同一點(diǎn)并覆蓋所有其她頂點(diǎn)又使邊權(quán)之和達(dá)到最小閉鏈（閉跡）.如第一問是三個旅行售貨員問題，第二問是四個旅行售貨員問題.眾所周知，旅行售貨員問題屬于NP完全問題，即求解沒有多項式時間算法.顯然本問題更應(yīng)屬于NP完全問題.有鑒于此，一定要針對問題實(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)路，不能走其她小組路，除公共路外。四、符號闡明……..任意兩點(diǎn)，間間距?！?.各點(diǎn)停留時間，即點(diǎn)權(quán)。………汽車行駛速度?！瓘娜我恻c(diǎn)至點(diǎn)時間，則。五、模型建立與求解公路網(wǎng)圖中，每個鄉(xiāng)（鎮(zhèn)）或村看作圖中一種節(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)O出發(fā)，行遍所有頂點(diǎn)至少一次再回到O點(diǎn)，使得總權(quán)（路程或時間）最小，此即最佳推銷員回路問題。在加權(quán)圖G中求最佳推銷員回路問題是NP—完全問題，咱們采用一種近似算法求出該問題一種近似最優(yōu)解，來代替最優(yōu)解，算法如下：算法一求加權(quán)圖G（V，E）最佳推銷員回路近似算法：用圖論軟件包求出G中任意兩個頂點(diǎn)間最短路，構(gòu)造出完備圖，，；輸入圖一種初始H圈；用對角線完全算法（見[23]）產(chǎn)生一種初始H圈；隨機(jī)搜索出中若干個H圈，例如個；對第2、3、4步所得每個H圈，用二邊逐次修正法進(jìn)行優(yōu)化，得到近似最佳H圈；在第5步求出所有H圈中，找出權(quán)最小一種，此即要找最佳H圈近似解.由于二邊逐次修正法成果與初始圈關(guān)于，故本算法第2、3、4步分別用三種辦法產(chǎn)生初始圈，以保證能得到較優(yōu)計算成果。問題一：此問題是各種推銷員最佳推銷員回路問題.即在加權(quán)圖G中求頂點(diǎn)集V劃分，將G提成n個生成子圖，使得（1）頂點(diǎn)i=1，2，3……n（2）（3），其中為導(dǎo)出子圖中最佳推銷員回路，為權(quán)，i，j=1，2，3……n（4）定義稱為該分組實(shí)際均衡度。為最大容許均衡度。顯然，越小，闡明分組均衡性越好.取定一種后，與滿足條件（3）分組是一種均衡分組.條件（4）表達(dá)總巡視路線最短。此問題包括兩方面：第一、對頂點(diǎn)分組；第二、在每組中求最佳推銷員回路，即為單個推銷員最佳推銷員問題。由于單個推銷員最佳推銷員回路問題不存在多項式時間內(nèi)精準(zhǔn)算法，故各種推銷員問題也不存在多項式時間內(nèi)精準(zhǔn)算法.而圖中節(jié)點(diǎn)數(shù)較多，為53個，咱們只能去謀求一種較合理劃分準(zhǔn)則，對圖１1－9進(jìn)行粗步劃分后，求出各某些近似最佳推銷員回路權(quán)，再進(jìn)一步進(jìn)行調(diào)節(jié)，使得各某些滿足均衡性條件（3）。圖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ā)樹枝稱為干枝，見圖１１－１0，從圖中可以看出，從O點(diǎn)出發(fā)到其他點(diǎn)共有6條干枝，它們名稱分別為①，②，③，④，⑤，⑥。圖11-10O點(diǎn)到任意點(diǎn)最短路圖（單位：公里）依照實(shí)際工作經(jīng)驗(yàn)及上述分析，在分組時應(yīng)遵從如下準(zhǔn)則：準(zhǔn)則一：盡量使同一干枝上及其分枝上點(diǎn)分在同一組；準(zhǔn)則二：應(yīng)將相鄰干枝上點(diǎn)分在同一組；準(zhǔn)則三：盡量將長干枝與短干枝分在同一組.由上述分組準(zhǔn)則，咱們找到兩種分組形式如下：分組一：（⑥，①），（②，③），（⑤，④）分組二：（①，②），（③，④），（⑤，⑥）顯然分組一辦法極不均衡，故考慮分組二。對分組二中每組頂點(diǎn)生成子圖，用算法一求出近似最優(yōu)解及相應(yīng)巡視路線.使用算法一時，在每個子圖所構(gòu)造完備圖中，取一種盡量包括圖11-10中樹上邊H圈作為其第2步輸入初始圈。分組二近似解見表1。表1（單位：公里）小組名稱路線總路線長度路線總長度=1\*ROMANIO-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O191.1558.5=2\*ROMANIIO-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-7-E-8-4-D-3-C241.9=3\*ROMANIIIO-R-29-Q-30-32-31-33-35-34-A-B-1-O125.5由于該分組均衡度=54.2%因此此分法均衡性很差。為改進(jìn)均衡性，將第Ⅱ組中頂點(diǎn)C，2，3，D，4分給第Ⅲ組（頂點(diǎn)2為這兩組公共點(diǎn)），重新分組后近似最優(yōu)解見表2。表2（單位：公里）編號路線路線長度路線總長度=1\*ROMANIO—P—28—27—26—N—24—23—22—17—16—I—15—I—18—K—21—20—25—M—O191.1599.8=2\*ROMANIIO—2—5—6—7—E—8—E—9—F—10—F—12—H—14—13—G—11—J—19—L—6—5—2—O216.4=3\*ROMANIIIO—R—29—Q—30—32—31—33—35—34—A—1—B—C—3—D—4—D—3—2—O192.3因該分組均衡度11.69%因此這種分法均衡性較好。問題二由于T=2小時，t=1小時，V=35公里/小時，需訪問鄉(xiāng)鎮(zhèn)共有17個，村共有35個.計算出在鄉(xiāng)（鎮(zhèn)）及村總停留時間為172+35=69小時，要在24小時內(nèi)完畢巡回，若不考慮行走時間，有：(i為分組數(shù)).得i最小為4，故至少要分4組。由于該網(wǎng)絡(luò)鄉(xiāng)（鎮(zhèn)）、村分布較為均勻，故有也許找出停留時間盡量均衡分組，當(dāng)分4組時各組停留時間大概為小時，則每組分派在路途上時間大概為24-17.25=6.75小時.而前面討論過，分三組時有個總路程599.8公里巡視路線，分4組時總路程不會比599.8公里大太多，不妨以599.8公里來計算.路上時間約為小時，若平均分派給4個組，每個組約需=4.25小時〈6.75小時，故提成4組是也許辦到。當(dāng)前嘗試將頂點(diǎn)分為4組.分組原則：除遵從前面準(zhǔn)則一、二、三外，還應(yīng)遵從如下準(zhǔn)則：準(zhǔn)則四：盡量使各組停留時間相等。用上述原則在圖11-10上將圖分為4組，同步計算各組停留時間,然后用算法一算出各組近似最佳推銷員巡回，得出路線長度及行走時間，從而得出完畢巡視近似最佳時間.用算法一計算時，初始圈輸入與分三組時同樣解決。這4組近似最優(yōu)解見表3：表3（路程單位：公里；時間單位：小時）組名路線路線總長度停留時間行走時間完畢巡視總時間=1\*ROMANIO—2—5—6—7—E—8—E—11—G—12—H—12—F—10—F—9—E—7—6—5—2—O195.8175.5922.59=2\*ROMANIIO—R—29—Q—30—Q—28—27—26—N—24—23—22—17—16—17—K—22—23—N—26—P—O199.2165.6921.69=3\*ROMANIIIO—M—25—20—21—K—18—I—15—14—13—J—19—L—6—M—O159.1184.5422.54=4\*ROMANIVO—R—A—33—31—32—35—34—B—1—C—3—D—4—D—3—2—O166184.7422.74上表中符號闡明：加有底紋表達(dá)前面通過并停留過，本次只通過不需停留；加框表達(dá)此點(diǎn)只通過不斷留。該分組實(shí)際均衡度=4.62%可以看出，表3分組均衡度較好，且完全滿足24小時完畢巡視規(guī)定。問題三咱們發(fā)現(xiàn)從O點(diǎn)巡視H點(diǎn)最短時間是所有最短時間中最長，其距離為77.5公里。其時間為因而，T=2小時，t=1小時，V=35公里/小時。若巡視人員足夠多，完畢巡視最短時間為6.43小時。在最短時間內(nèi)限定一下，完畢巡視最優(yōu)路線應(yīng)滿足如下條件：每個組巡視總時間不能超過最短時間；所有點(diǎn)都必要訪問到，不能漏點(diǎn)；所需巡視組數(shù)要盡量少；在謀求最優(yōu)路線時，從距離O點(diǎn)較遠(yuǎn)某些點(diǎn)（如點(diǎn)12、10、15、22）開始搜索比較容易，由于到這些點(diǎn)路線比較少。詳細(xì)辦法如下：第一步：根據(jù)圖1算出從O點(diǎn)到每一種點(diǎn)最短距離;第二步：找出其中最大一種，算出從O點(diǎn)沿最短路巡視時間，并求出;第三步：若則這一組只能訪問這一點(diǎn)；若則在余下點(diǎn)找到距離O點(diǎn)最遠(yuǎn)點(diǎn)，依照條件看這一組能否巡視這一點(diǎn)；第四步：若能巡視，則算出，轉(zhuǎn)到第三步；第五步：若不能則依次判斷次遠(yuǎn)點(diǎn)、第三遠(yuǎn)點(diǎn)……,滿足總巡視時間不超過，就讓這組巡視到這一點(diǎn)，直到然后再從第二步開始。通過以上辦法，最后咱們找到最優(yōu)解是22個組，如下表所示：編號巡視途徑停留地點(diǎn)所需時間時間差1O-H-OH6.4302O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-013,146.150.283O-M-25-21-K-18-I-15-I-16-17-K-21-25-M-O15,166.310.124O-2-5-6-7-E-9-F-12-G-11-E-7-6-5-2-O12,115.940.495O-2-5-6-7-E-8-E-9-F-10-F-9-E-7-6-5-2-O8,106.220.216O-2-5-6-7-E-11-G-11-E-7-6-5-2-OG5.580.857O-2-5-6-7-E-9-F-9-E-7-6-5-2-O9,F6.140.298O-2-5-6-L-19-J-18-K-21-25-M-OJ,186.290.149O-M-25-21-K-18-I-18-K-21-25-M-OI5.490.9410O-M-25-21-K-17-22-23-N-26-P-O17,22,236.120.3111O-2-5-G-L-19-L-6-5-2-OL,195.640.7912O-M-25-20-21-23-24-N-26-P-O20,21,246.100.3313O-M-25-21-K-21-25-M-O25,K5.500.9314O-2-5-6-7-E-7-6-5-2-O6,7,E6.380.0515O-R-31-32-35-34-A-1-O31,32,35,346.320.1116O-R-29-Q-30-Q-28-P-OQ,30,286.110.3217O-P-26-27-26-N-26-P-O26,27,N6.230.2018O-2-3-D-4-D-3-2-O3,D,45.990.4419O-1-A-33-31-R-29-R-OA,33,295.970.4620O-2-5-M-O2,5,M5.401.0321O-1-B-C-O1,B,C5.980.4522O-P-O-R-OP,R5.321.11問題四巡視組數(shù)已定，規(guī)定盡快完畢巡視，討論T，t和V變化對最佳巡視路線影響。要盡快完畢巡視，就得規(guī)定每組完畢巡視時間盡量均衡，由于總完畢巡視時間按最長完畢巡視時間計算。當(dāng)前討論在均衡度容許范疇內(nèi)已提成n組后，變化T，t和V對最佳巡視路線影響。顯然在分組不變狀況下，無論了T,t、V如何變化，對每組內(nèi)最佳巡視路線是沒有影響，但也許會影響各組間均衡性。因而該問題事實(shí)上討論T，t和V對于分組影響，即在不破壞本來分組均衡條件下，T，t和V容許最大變化范疇。在分n組狀況下，設(shè)：表達(dá)第i組最佳推銷員回路路線總長度；：表達(dá)第i組所要停留鄉(xiāng)鎮(zhèn)數(shù)目；：表達(dá)第i組所要停留村數(shù)目；i=1,2,3,…,n顯然，當(dāng)時，即每組鄉(xiāng)（鎮(zhèn)）數(shù)、村數(shù)、最佳巡回長度均相等，因而分組絕對均衡時，即=0時，無論T，t和V如何變化都不會變化本來分組均衡。不影響分組均衡時，T，t和V最大容許變化范疇討論：對任意一種組i，其完畢巡視時間設(shè)均衡分組最大容許時間均衡度為，即則有記則表達(dá)均衡分組所容許最大時間誤差，則(1)由（1）式咱們得到（2）由式（2）可得當(dāng)>0時，要保持原均衡分組不變，T必要滿足條件為（3）2.當(dāng)時，要保持原均衡分組不變，t必要滿足條件為(4)3.當(dāng)>0時，由（2）式得當(dāng)有當(dāng)時，有（6）由（3）—（6）式，當(dāng)T,t,V三個變量中任意兩個變量無論如何變化，都可計算出為保持均衡性分組不變，三個變量所容許最大變化范疇。（二）分三組實(shí)例討論現(xiàn)對分三組狀況進(jìn)布寸論對問題一中所得三個分組若考慮停留時間和行駛時間且取小時，小時，公里/小時，成果如表5：表5（路程單位：公里；時間單位：小時）編號行駛時間總時間=1\*ROMANI513191.15.4628.46=2\*ROMANII611192.35.4928.49=3\*ROMANIII611216.46.1829.18實(shí)際均衡度為。實(shí)際時間誤差為小時?，F(xiàn)分別規(guī)定均衡分組最大容許均衡度和，即最大容許時間誤差分別為小時和小時，計算出T,t,V三個參量中固定任意兩個時，要不破壞原均衡分組，另一種參量所容許變化范疇，成果如下表：表6V,t不變T,V不變T,t不變上表可以看出：（1）當(dāng)實(shí)際均衡度剛好等于最大容許均衡度時，要保持原均衡分組，當(dāng)t，V不變時，T只能減小，且下界為1.25小時；T上界為小時；T，V不變時，t只能增大，且上界為1.38小時；t下界為小時；t，T不變時，V只能增大，且下界為35；無上界；（2）當(dāng)實(shí)際均衡度不大于最大容許均衡度時，即時要保持原均衡分組，當(dāng)t，V不變時，T變化下界為0.51小時；T上界為2.74小時；T，V不變時，t上界為1.75小時；t下界為0.63小時；t，T不變時，V增大但無上界，且下界為17.3公里/小時；（三）對實(shí)例成果分析上述實(shí)例均衡分組有一種特點(diǎn)，各組停留時間相等,即取小時，小時，公里/小時，在表5分組中定義4各組停留時間相等均衡分組稱為停留時間相等均衡分組，由（7）式得現(xiàn)討論對停留時間相等均衡分組,T,t,V變化規(guī)律，對停留時間相等均衡分組，分組實(shí)際時間誤差：其中，為使最大組標(biāo)號；為使最小組標(biāo)號。（*）當(dāng)T,t不變時,即,時，因由（6）式懂得，要保持平衡分組,V下界應(yīng)為取時，由（9）式得時，由（9）式得故有如下定