2021年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題

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

災(zāi)情巡視路線模型摘要本文將求最佳巡視路線間題轉(zhuǎn)化為圖論中求最佳推銷員回路（哈米爾頓回路）問題,并用近似算法去謀求近似最優(yōu)解。對(duì)賦權(quán)圖半途徑分組問題定義了均衡度用以衡量分組均衡性。對(duì)問題1和問題2先定出幾種分準(zhǔn)則進(jìn)行初步分組,并用近似算法求每一組近似最佳推銷員回路,再依照均衡度進(jìn)行微調(diào),得到較優(yōu)均衡分組和每組近似最佳推銷員回路。對(duì)問題1，運(yùn)用求任意兩點(diǎn)間最短路Floyd算法,得出總路程較短且各組盡量均衡路線,各組巡視路程分別為216.4公里,191.1公里,192.3公里,總路程599.8公里。對(duì)問題2,證明了應(yīng)至少分為4組,并求出了分為4組時(shí)各組較優(yōu)巡視路線,各組巡視時(shí)間分別為22.74小時(shí),22.59小時(shí),21.69小時(shí),22.54小時(shí)。對(duì)問題3,求出完畢巡視最短時(shí)間為6.43小時(shí),并用較為合理分組準(zhǔn)則,提成22個(gè)組對(duì)問題4，研究了在不影響分組均衡條件下，T,t,V容許變化范疇,并得出了這三個(gè)變量關(guān)系式,并由此對(duì)分三個(gè)組狀況進(jìn)行了詳細(xì)討論。 核心詞：最佳推銷員回路問題哈米爾頓回路賦權(quán)圖近似算法均衡度 一、問題重述1998年夏天某縣遭受水災(zāi)。為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)關(guān)于部門負(fù)責(zé)人到全縣各17個(gè)鄉(xiāng)（鎮(zhèn)）、35個(gè)村巡視。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhè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)分幾組；給出這種分組下你以為最佳巡視路線。(3)在上述關(guān)于T，t和V假定下，如果巡視人員足夠多，完畢巡視最短時(shí)間是多少；給出在這種最短時(shí)間完畢巡視規(guī)定下，你以為最佳巡視路線。(4)若巡視組數(shù)已定(如三組），規(guī)定盡快完畢巡視，討論T，t和V變化對(duì)最佳巡視路線影響。二、問題分析 本題給出了某縣公路網(wǎng)絡(luò)圖，規(guī)定是在不同條件下，災(zāi)情巡視最分組方案和路線.將每個(gè)鄉(xiāng)（鎮(zhèn)）或村看作一種圖頂點(diǎn)，各鄉(xiāng)鎮(zhèn)、村之間公路看作此圖相應(yīng)頂點(diǎn)間邊，各條公路長(zhǎng)度（或行駛時(shí)間）看作相應(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)（路程或時(shí)間）最小.本題是旅行售貨員問題延伸－多旅行售貨員問題.本題所求分組巡視最佳路線，也就是m條通過同一點(diǎn)并覆蓋所有其她頂點(diǎn)又使邊權(quán)之和達(dá)到最小閉鏈（閉跡）.如第一問是三個(gè)旅行售貨員問題，第二問是四個(gè)旅行售貨員問題.眾所周知，旅行售貨員問題屬于NP完全問題，即求解沒有多項(xiàng)式時(shí)間算法.顯然本問題更應(yīng)屬于NP完全問題.有鑒于此，一定要針對(duì)問題實(shí)際特點(diǎn)尋找簡(jiǎn)便辦法，想找到解決此類問題普通辦法是不現(xiàn)實(shí)，對(duì)于規(guī)模較大問題可使用近似算法來求得近似最優(yōu)解.三、模型假設(shè)1．汽車在路上速度總是一定，不會(huì)浮現(xiàn)拋錨等現(xiàn)象；忽視天氣、故障等因素影響。2．巡視當(dāng)中，在每個(gè)鄉(xiāng)鎮(zhèn)、村停留時(shí)間一定，不會(huì)浮現(xiàn)特殊狀況而延誤時(shí)間；3．每個(gè)小組汽車行駛速度完全同樣；4．分組后，各小組只能走自己區(qū)內(nèi)路，不能走其她小組路，除公共路外。四、符號(hào)闡明……..任意兩點(diǎn)，間間距?！?.各點(diǎn)停留時(shí)間，即點(diǎn)權(quán)?！囆旭偹俣??！瓘娜我恻c(diǎn)至點(diǎn)時(shí)間，則。五、模型建立與求解公路網(wǎng)圖中，每個(gè)鄉(xiāng)（鎮(zhèn)）或村看作圖中一種節(jié)點(diǎn)，各鄉(xiāng)（鎮(zhèn)）、村之間公路看作圖中相應(yīng)節(jié)點(diǎn)間邊，各條公路長(zhǎng)度（或行駛時(shí)間）看作相應(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)（路程或時(shí)間）最小，此即最佳推銷員回路問題。在加權(quán)圖G中求最佳推銷員回路問題是NP—完全問題，咱們采用一種近似算法求出該問題一種近似最優(yōu)解，來代替最優(yōu)解，算法如下：算法一求加權(quán)圖G（V，E）最佳推銷員回路近似算法：用圖論軟件包求出G中任意兩個(gè)頂點(diǎn)間最短路，構(gòu)造出完備圖，，；輸入圖一種初始H圈；用對(duì)角線完全算法（見[23]）產(chǎn)生一種初始H圈；隨機(jī)搜索出中若干個(gè)H圈，例如個(gè)；對(duì)第2、3、4步所得每個(gè)H圈，用二邊逐次修正法進(jìn)行優(yōu)化，得到近似最佳H圈；在第5步求出所有H圈中，找出權(quán)最小一種，此即要找最佳H圈近似解.由于二邊逐次修正法成果與初始圈關(guān)于，故本算法第2、3、4步分別用三種辦法產(chǎn)生初始圈，以保證能得到較優(yōu)計(jì)算成果。問題一：此問題是各種推銷員最佳推銷員回路問題.即在加權(quán)圖G中求頂點(diǎn)集V劃分，將G提成n個(gè)生成子圖，使得（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á)總巡視路線最短。此問題包括兩方面：第一、對(duì)頂點(diǎn)分組；第二、在每組中求最佳推銷員回路，即為單個(gè)推銷員最佳推銷員問題。由于單個(gè)推銷員最佳推銷員回路問題不存在多項(xiàng)式時(shí)間內(nèi)精準(zhǔn)算法，故各種推銷員問題也不存在多項(xiàng)式時(shí)間內(nèi)精準(zhǔn)算法.而圖中節(jié)點(diǎn)數(shù)較多，為53個(gè)，咱們只能去謀求一種較合理劃分準(zhǔn)則，對(duì)圖１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)及上述分析，在分組時(shí)應(yīng)遵從如下準(zhǔn)則：準(zhǔn)則一：盡量使同一干枝上及其分枝上點(diǎn)分在同一組；準(zhǔn)則二：應(yīng)將相鄰干枝上點(diǎn)分在同一組；準(zhǔn)則三：盡量將長(zhǎng)干枝與短干枝分在同一組.由上述分組準(zhǔn)則，咱們找到兩種分組形式如下：分組一：（⑥，①），（②，③），（⑤，④）分組二：（①，②），（③，④），（⑤，⑥）顯然分組一辦法極不均衡，故考慮分組二。對(duì)分組二中每組頂點(diǎn)生成子圖，用算法一求出近似最優(yōu)解及相應(yīng)巡視路線.使用算法一時(shí)，在每個(gè)子圖所構(gòu)造完備圖中，取一種盡量包括圖11-10中樹上邊H圈作為其第2步輸入初始圈。分組二近似解見表1。表1（單位：公里）小組名稱路線總路線長(zhǎng)度路線總長(zhǎng)度=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（單位：公里）編號(hào)路線路線長(zhǎng)度路線總長(zhǎng)度=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小時(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í)間，有：(i為分組數(shù)).得i最小為4，故至少要分4組。由于該網(wǎng)絡(luò)鄉(xiāng)（鎮(zhèn)）、村分布較為均勻，故有也許找出停留時(shí)間盡量均衡分組，當(dāng)分4組時(shí)各組停留時(shí)間大概為小時(shí)，則每組分派在路途上時(shí)間大概為24-17.25=6.75小時(shí).而前面討論過，分三組時(shí)有個(gè)總路程599.8公里巡視路線，分4組時(shí)總路程不會(huì)比599.8公里大太多，不妨以599.8公里來計(jì)算.路上時(shí)間約為小時(shí)，若平均分派給4個(gè)組，每個(gè)組約需=4.25小時(shí)〈6.75小時(shí)，故提成4組是也許辦到。當(dāng)前嘗試將頂點(diǎn)分為4組.分組原則：除遵從前面準(zhǔn)則一、二、三外，還應(yīng)遵從如下準(zhǔn)則：準(zhǔn)則四：盡量使各組停留時(shí)間相等。用上述原則在圖11-10上將圖分為4組，同步計(jì)算各組停留時(shí)間,然后用算法一算出各組近似最佳推銷員巡回，得出路線長(zhǎng)度及行走時(shí)間，從而得出完畢巡視近似最佳時(shí)間.用算法一計(jì)算時(shí)，初始圈輸入與分三組時(shí)同樣解決。這4組近似最優(yōu)解見表3：表3（路程單位：公里；時(shí)間單位：小時(shí)）組名路線路線總長(zhǎng)度停留時(shí)間行走時(shí)間完畢巡視總時(shí)間=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上表中符號(hào)闡明：加有底紋表達(dá)前面通過并停留過，本次只通過不需停留；加框表達(dá)此點(diǎn)只通過不斷留。該分組實(shí)際均衡度=4.62%可以看出，表3分組均衡度較好，且完全滿足24小時(shí)完畢巡視規(guī)定。問題三咱們發(fā)現(xiàn)從O點(diǎn)巡視H點(diǎn)最短時(shí)間是所有最短時(shí)間中最長(zhǎng)，其距離為77.5公里。其時(shí)間為因而，T=2小時(shí)，t=1小時(shí)，V=35公里/小時(shí)。若巡視人員足夠多，完畢巡視最短時(shí)間為6.43小時(shí)。在最短時(shí)間內(nèi)限定一下，完畢巡視最優(yōu)路線應(yīng)滿足如下條件：每個(gè)組巡視總時(shí)間不能超過最短時(shí)間；所有點(diǎn)都必要訪問到，不能漏點(diǎn)；所需巡視組數(shù)要盡量少；在謀求最優(yōu)路線時(shí)，從距離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)沿最短路巡視時(shí)間，并求出;第三步：若則這一組只能訪問這一點(diǎn)；若則在余下點(diǎn)找到距離O點(diǎn)最遠(yuǎn)點(diǎn)，依照條件看這一組能否巡視這一點(diǎn)；第四步：若能巡視，則算出，轉(zhuǎn)到第三步；第五步：若不能則依次判斷次遠(yuǎn)點(diǎn)、第三遠(yuǎn)點(diǎn)……,滿足總巡視時(shí)間不超過，就讓這組巡視到這一點(diǎn)，直到然后再從第二步開始。通過以上辦法，最后咱們找到最優(yōu)解是22個(gè)組，如下表所示：編號(hào)巡視途徑停留地點(diǎn)所需時(shí)間時(shí)間差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變化對(duì)最佳巡視路線影響。要盡快完畢巡視，就得規(guī)定每組完畢巡視時(shí)間盡量均衡，由于總完畢巡視時(shí)間按最長(zhǎng)完畢巡視時(shí)間計(jì)算。當(dāng)前討論在均衡度容許范疇內(nèi)已提成n組后，變化T，t和V對(duì)最佳巡視路線影響。顯然在分組不變狀況下，無論了T,t、V如何變化，對(duì)每組內(nèi)最佳巡視路線是沒有影響，但也許會(huì)影響各組間均衡性。因而該問題事實(shí)上討論T，t和V對(duì)于分組影響，即在不破壞本來分組均衡條件下，T，t和V容許最大變化范疇。在分n組狀況下，設(shè)：表達(dá)第i組最佳推銷員回路路線總長(zhǎng)度；：表達(dá)第i組所要停留鄉(xiāng)鎮(zhèn)數(shù)目；：表達(dá)第i組所要停留村數(shù)目；i=1,2,3,…,n顯然，當(dāng)時(shí)，即每組鄉(xiāng)（鎮(zhèn)）數(shù)、村數(shù)、最佳巡回長(zhǎng)度均相等，因而分組絕對(duì)均衡時(shí)，即=0時(shí)，無論T，t和V如何變化都不會(huì)變化本來分組均衡。不影響分組均衡時(shí)，T，t和V最大容許變化范疇討論：對(duì)任意一種組i，其完畢巡視時(shí)間設(shè)均衡分組最大容許時(shí)間均衡度為，即則有記則表達(dá)均衡分組所容許最大時(shí)間誤差，則(1)由（1）式咱們得到（2）由式（2）可得當(dāng)>0時(shí)，要保持原均衡分組不變，T必要滿足條件為（3）2.當(dāng)時(shí)，要保持原均衡分組不變，t必要滿足條件為(4)3.當(dāng)>0時(shí)，由（2）式得當(dāng)有當(dāng)時(shí)，有（6）由（3）—（6）式，當(dāng)T,t,V三個(gè)變量中任意兩個(gè)變量無論如何變化，都可計(jì)算出為保持均衡性分組不變，三個(gè)變量所容許最大變化范疇。（二）分三組實(shí)例討論現(xiàn)對(duì)分三組狀況進(jìn)布寸論對(duì)問題一中所得三個(gè)分組若考慮停留時(shí)間和行駛時(shí)間且取小時(shí)，小時(shí)，公里/小時(shí)，成果如表5：表5（路程單位：公里；時(shí)間單位：小時(shí)）編號(hào)行駛時(shí)間總時(shí)間=1\*ROMANI513191.15.4628.46=2\*ROMANII611192.35.4928.49=3\*ROMANIII611216.46.1829.18實(shí)際均衡度為。實(shí)際時(shí)間誤差為小時(shí)?，F(xiàn)分別規(guī)定均衡分組最大容許均衡度和，即最大容許時(shí)間誤差分別為小時(shí)和小時(shí)，計(jì)算出T,t,V三個(gè)參量中固定任意兩個(gè)時(shí)，要不破壞原均衡分組，另一種參量所容許變化范疇，成果如下表：表6V,t不變T,V不變T,t不變上表可以看出：（1）當(dāng)實(shí)際均衡度剛好等于最大容許均衡度時(shí)，要保持原均衡分組，當(dāng)t，V不變時(shí)，T只能減小，且下界為1.25小時(shí)；T上界為小時(shí)；T，V不變時(shí)，t只能增大，且上界為1.38小時(shí)；t下界為小時(shí)；t，T不變時(shí)，V只能增大，且下界為35；無上界；（2）當(dāng)實(shí)際均衡度不大于最大容許均衡度時(shí)，即時(shí)要保持原均衡分組，當(dāng)t，V不變時(shí)，T變化下界為0.51小時(shí)；T上界為2.74小時(shí)；T，V不變時(shí)，t上界為1.75小時(shí)；t下界為0.63小時(shí)；t，T不變時(shí)，V增大但無上界，且下界為17.3公里/小時(shí)；（三）對(duì)實(shí)例成果分析上述實(shí)例均衡分組有一種特點(diǎn)，各組停留時(shí)間相等,即取小時(shí)，小時(shí)，公里/小時(shí)，在表5分組中定義4各組停留時(shí)間相等均衡分組稱為停留時(shí)間相等均衡分組，由（7）式得現(xiàn)討論對(duì)停留時(shí)間相等均衡分組,T,t,V變化規(guī)律，對(duì)停留時(shí)間相等均衡分組，分組實(shí)際時(shí)間誤差：其中，為使最大組標(biāo)號(hào)；為使最小組標(biāo)號(hào)。（*）當(dāng)T,t不變時(shí),即,時(shí)，因由（6）式懂得，要保持平衡分組,V下界應(yīng)為取時(shí)，由（9）式得時(shí)，由（9）式得故有如下定