線路的優(yōu)化模型

1、I加另就彳M A A與Shenyang Aerospace University數(shù)學(xué)模型課程結(jié)業(yè)論文線路的優(yōu)化模型任務(wù)書(shū)要求1、將所給的問(wèn)題翻譯成漢語(yǔ)；2、給論文起個(gè)題目（名字或標(biāo)題）3、根據(jù)任務(wù)來(lái)完成數(shù)學(xué)模型論文；4、論文書(shū)寫格式要求按給定要求書(shū)寫；5、態(tài)度要認(rèn)真，要獨(dú)立思考，獨(dú)立完成任務(wù)；6、論文上交時(shí)間：6月1日前（要求交紙質(zhì)論文和電子文檔）。7、嚴(yán)禁抄襲行為，若發(fā)現(xiàn)抄襲，則成績(jī)記為“不及格”。任務(wù)下圖為某縣的鄉(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)）、村巡視。巡視路線指從縣政府所

2、在地 出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線。若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡 視路線。假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間 t=1小時(shí)，汽車行駛速度V=35公里/小時(shí)。要在24小時(shí)內(nèi)完成巡 視，至少應(yīng)分幾組；給出這種分組下你認(rèn)為最佳的巡視路線。在上述關(guān)于T , t和V的假定下，如果巡視人員足夠多，完成巡 視的最短時(shí)間是多少；給出在這種最短時(shí)間完成巡視的要求下， 你認(rèn)為最佳的巡視路線。若巡視組數(shù)已定（如三組），要求盡快完成巡視，討論T，t和V 改變對(duì)最佳巡視路線的影響。成績(jī)?cè)u(píng)定單評(píng)語(yǔ)：成績(jī)?nèi)握n 年月日摘要本題是一個(gè)有深刻背景的NPC問(wèn)題

3、，文章分析了分組回路的拓?fù)浣Y(jié)構(gòu)，并構(gòu) 造了多個(gè)模型，從多個(gè)側(cè)面對(duì)具體問(wèn)題進(jìn)行求解，最短樹(shù)結(jié)構(gòu)模型給出了局部尋優(yōu) 的原則，算法模型體，算法模型體現(xiàn)了由簡(jiǎn)到繁，確保較優(yōu)的思想；而三個(gè)層次分 明的表述模型證明了這一類問(wèn)題共有的性質(zhì)。在此基礎(chǔ)上，我們的結(jié)果也是比較令 人滿意的，如對(duì)第一題給了總長(zhǎng)599.9，單項(xiàng)長(zhǎng)為216的分組，第二題給出了至少 分四組的證明。最后，我們還談到了模型的優(yōu)缺點(diǎn)及推廣思想。關(guān)鍵詞：關(guān)鍵詞1；關(guān)鍵詞2；關(guān)鍵詞3；關(guān)鍵詞4目錄1第1級(jí)標(biāo)題錯(cuò)誤！未定義書(shū)簽。1.1目錄1第1級(jí)標(biāo)題錯(cuò)誤！未定義書(shū)簽。1.1.1第3級(jí)標(biāo)題1.1.2第3級(jí)標(biāo)題1.2第2級(jí)標(biāo)題1.2.1第3級(jí)標(biāo)題1.2.

4、2第3級(jí)標(biāo)題1.2.3第3級(jí)標(biāo)題1.3第2級(jí)標(biāo)題錯(cuò)誤！未定義書(shū)簽。錯(cuò)誤！未定義書(shū)簽。錯(cuò)誤！未定義書(shū)簽。錯(cuò)誤！未定義書(shū)簽。錯(cuò)誤！未定義書(shū)簽。錯(cuò)誤！未定義書(shū)簽。錯(cuò)誤！未定義書(shū)簽。錯(cuò)誤！未定義書(shū)簽。錯(cuò)誤！未定義書(shū)簽。錯(cuò)誤！未定義書(shū)簽。錯(cuò)誤！未定義書(shū)簽。錯(cuò)誤！未定義書(shū)簽。附錄I程序清單錯(cuò)誤！未定義書(shū)簽。附錄I程序清單論文正文：正文所含內(nèi)容：標(biāo)題：?jiǎn)栴}提出（問(wèn)題重述）：模型假設(shè)模型的建立：模型求解（算法設(shè)計(jì)和計(jì)算機(jī)實(shí)現(xiàn)）：結(jié)果（數(shù)據(jù)、圖形）。結(jié)果分析和檢驗(yàn)（如誤差分析、統(tǒng)計(jì)檢驗(yàn)、靈敏性檢驗(yàn)）：優(yōu)缺點(diǎn)，改進(jìn)方向：參考文獻(xiàn)附錄（程序、更多的計(jì)算結(jié)果、復(fù)雜的推導(dǎo)、證明等）。1.1.標(biāo)題:線路的優(yōu)化模型問(wèn)題提出

5、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)分幾組；給出這種分組下你認(rèn)為最佳的巡視路線。（3）在上述關(guān)于T , t和V的假定下，如果巡視人員足夠多，完成巡視 的最短時(shí)間是多少；給出在這種最短時(shí)間完成巡視的要求下，你認(rèn)為最 佳的巡視路

6、線。（4）若巡視組數(shù)已定（如三組），要求盡快完成巡視，討論T，t和V改 變對(duì)最佳巡視路線的影響。問(wèn)題重述本題給出了某縣的公路網(wǎng)絡(luò)圖，要求的是在不同的條件下，災(zāi)情巡視的 最分組方案和路線.將每個(gè)鄉(xiāng)（鎮(zhèn)）或村看作一個(gè)圖的頂點(diǎn)，各鄉(xiāng)鎮(zhèn)、村之間的公 路看作此圖對(duì)應(yīng)頂點(diǎn)間的邊，各條公路的長(zhǎng)度（或行駛時(shí)間）看作對(duì)應(yīng)邊上的權(quán)， 所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問(wèn)題就轉(zhuǎn)化圖論中一類稱之為旅行售貨員問(wèn)題， 即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)O出發(fā)，行遍所有頂點(diǎn)至少一次再回到點(diǎn)0, 使得總權(quán)（路程或時(shí)間）最小.本題是旅行售貨員問(wèn)題的延伸一多旅行售貨員問(wèn)題.本題所求的分組巡視的最 佳路線，也就是m條經(jīng)過(guò)同一點(diǎn)并覆蓋所

7、有其他頂點(diǎn)又使邊權(quán)之和達(dá)到最小的閉鏈 （閉跡）.如第一問(wèn)是三個(gè)旅行售貨員問(wèn)題，第二問(wèn)是四個(gè)旅行售貨員問(wèn)題.眾所周知，旅行售貨員問(wèn)題屬于NP完全問(wèn)題，即求解沒(méi)有多項(xiàng)式時(shí)間算法.顯 然本問(wèn)題更應(yīng)屬于NP完全問(wèn)題.有鑒于此，一定要針對(duì)問(wèn)題的實(shí)際特點(diǎn)尋找簡(jiǎn)便 方法，想找到解決此類問(wèn)題的一般方法是不現(xiàn)實(shí)的，對(duì)于規(guī)模較大的問(wèn)題可使用近 似算法來(lái)求得近似最優(yōu)解.3.3.模型假設(shè)汽車在路上的速度總是一定，不會(huì)出現(xiàn)拋錨等現(xiàn)象；忽略天氣、故障等因素的 影響。巡視當(dāng)中，在每個(gè)鄉(xiāng)鎮(zhèn)、村的停留時(shí)間一定，不會(huì)出現(xiàn)特殊情況而延誤時(shí)間；每個(gè)小組的汽車行駛速度完全一樣；分組后，各小組只能走自己區(qū)內(nèi)的路，不能走其他小組的路，除公

8、共路外。4.模型的建立和模型求解及結(jié)果w（i,jw（i,j）.任意兩點(diǎn)i，j間的間距。七.各點(diǎn)的停留時(shí)間，即點(diǎn)權(quán)。v汽車行駛速度。d.從任意點(diǎn)i全點(diǎn)j的時(shí)間，則jd. = w（i, j）/V。j（2）模型的建立公路網(wǎng)圖中，每個(gè)鄉(xiāng)（鎮(zhèn)）或村看作圖中的一個(gè)節(jié)點(diǎn)，各鄉(xiāng)（鎮(zhèn)）、村之間的公 路看作圖中對(duì)應(yīng)節(jié)點(diǎn)間的邊，各條公路的長(zhǎng)度（或行駛時(shí)間）看作對(duì)應(yīng)邊上的權(quán)， 所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問(wèn)題就轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定 點(diǎn)O出發(fā)，行遍所有頂點(diǎn)至少一次再回到O點(diǎn)，使得總權(quán)（路程或時(shí)間）最小，此 即最佳推銷員回路問(wèn)題。在加權(quán)圖G中求最佳推銷員回路問(wèn)題是NP完全問(wèn)題，我們采用一種近似算法 求出

9、該問(wèn)題的一個(gè)近似最優(yōu)解，來(lái)代替最優(yōu)解，算法如下：算法一求加權(quán)圖G （V，E）算法一求加權(quán)圖G （V，E）的最佳推銷員回路的近似算法：用圖論軟件包求出G中任意兩個(gè)頂點(diǎn)間的最短路，構(gòu)造出完備圖Gr（V,E），V（x, y ）e E， s G, y）= MindgG, y）；輸入圖G的一個(gè)初始H圈；用對(duì)角線完全算法（見(jiàn)23）產(chǎn)生一個(gè)初始H圈；隨機(jī)搜索出G中若十個(gè)H圈，例如2000個(gè)；對(duì)第2、3、4步所得的每個(gè)H圈，用二邊逐次修正法進(jìn)行優(yōu)化，得到近似最佳H圈；在第5步求出的所有H圈中，找出權(quán)最小的一個(gè)，此即要找的最佳H圈的 近似解.1.2.3.4.5.6.由于二邊逐次修正法的結(jié)果與初始圈有關(guān)，故本算法

10、第2、3、4步分別用三種 方法產(chǎn)生初始圈，以保證能得到較優(yōu)的計(jì)算結(jié)果。模型求解及結(jié)果問(wèn)題一：此問(wèn)題是多個(gè)推銷員的最佳推銷員回路問(wèn)題.即在加權(quán)圖G中求頂點(diǎn)集V的劃分 匕,匕， 匕，將G分成n個(gè)生成子圖0gV2.gv 使得（1） 頂點(diǎn) O eVi=1，2，3ni（2）n Vi = v （g ）（3）y （q 1 心L，其中C為v.的導(dǎo)出子圖gV中的最佳推銷員tf- W aC iiiMaxw （C ）i回路，sCJ為q的權(quán)，i, j=1, 2, 3n（4）葺 w （C ） = Mini定義 稱以MaX （Ci ） w（CJ為該分組的實(shí)際均衡度。a為最大容許均a =。 Max w （C ）ii衡度。顯

11、然。a。 1，a0越小，說(shuō)明分組的均衡性越好.取定一個(gè)a后，a。與a滿足 條件（3）的分組是一個(gè)均衡分組.條件（4）表示總巡視路線最短。此問(wèn)題包含兩方面：第一、對(duì)頂點(diǎn)分組；第二、在每組中求最佳推銷員回路， 即為單個(gè)推銷員的最佳推銷員問(wèn)題。由于單個(gè)推銷員的最佳推銷員回路問(wèn)題不存在多項(xiàng)式時(shí)間內(nèi)的精確算法，故多 個(gè)推銷員的問(wèn)題也不存在多項(xiàng)式時(shí)間內(nèi)的精確算法.而圖中節(jié)點(diǎn)數(shù)較多，為53個(gè)， 我們只能去尋求一種較合理的劃分準(zhǔn)則，對(duì)圖1 1 9進(jìn)行粗步劃分后，求出各部分 的近似最佳推銷員回路的權(quán)，再進(jìn)一步進(jìn)行調(diào)整，使得各部分滿足均衡性條件（3）。2 (1)9322 (1)932302712/色1平8d-31

12、(7.9l2.1覆j嵯!7.4趴 X1IL1(7.9i-l.J工 7.3M.8 L從O點(diǎn)出發(fā)去其它點(diǎn)，要使路程較小應(yīng)盡量走O點(diǎn)到該點(diǎn)的最短路.故用圖論軟件包求出O點(diǎn)到其余頂點(diǎn)的最短路，這些最短路構(gòu)成一棵O為樹(shù)根的樹(shù)，將從O點(diǎn)出發(fā)的樹(shù)枝稱為十枝，見(jiàn)圖11 1 0，從圖中可以看出，從O點(diǎn)出發(fā)到其它點(diǎn)共有6條十枝，它們的名稱分別為，。根據(jù)實(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)則，我們找到兩種分組形式如下：分組一：（，），（，），（，）分組二：（

13、，），（，），（，）顯然分組一的方法極不均衡，故考慮分組二。對(duì)分組二中每組頂點(diǎn)的生成子圖，用算法一求出近似最優(yōu)解及相應(yīng)的巡視路線. 使用算法一時(shí)，在每個(gè)子圖所構(gòu)造的完備圖中，取一個(gè)盡量包含圖11-10中樹(shù)上的 邊的H圈作為其第2步輸入的初始圈。所以此分法的均衡性很差。為改善均衡性，將第II組中的頂點(diǎn)所以此分法的均衡性很差。為改善均衡性，將第II組中的頂點(diǎn)C，2, 3, D，4分給第III組（頂點(diǎn)2為這兩 組的公共點(diǎn)），重新分組后的近似最優(yōu)解見(jiàn)表2。小組名稱路線總路線長(zhǎng) 度路線 的總 長(zhǎng)度IO-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-

14、O191.1558.5IIO-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-7-E-8-4-D-3-C241.9IIIO-R-29-Q-30-32-31-33-35-34-A-B-1-O125.5表1 （單位：公里）因?yàn)樵摲纸M的均衡度a廣打以-8（C 2）= 241.9 - 125.5 = 54.2%Max （C. ） 一 241 .9i=1,2,31表2 （單位：公里）編號(hào)路線路線長(zhǎng)度路線總 長(zhǎng)度IOP282726N24232217 16I15I18K212025MO191.1599.8IIO2567E8E9F10F 12H 1413G 11J 19L65

15、2O216.4IIIOR29Q303231333534A 1BC3D4D32O192.3因該分組的均衡度a 0Max因該分組的均衡度a 0MaxW（C 216.4 191.1216.4=11.69%i=1,2,3 所以這種分法的均衡性較好。問(wèn)題二由于T=2小時(shí)，t=1小時(shí)，V=35公里/小時(shí)，需訪問(wèn)的鄉(xiāng)鎮(zhèn)共有17個(gè)，村共有 35個(gè).計(jì)算出在鄉(xiāng)（鎮(zhèn)）及村的總停留時(shí)間為17x 2+35=69小時(shí)，要在24小時(shí)內(nèi)完 .一，. 69 一，.,成巡回，若不考慮行走時(shí)間，有：69 24 （i為分的組數(shù)）.得i最小為4,故全i少要分4組。由于該網(wǎng)絡(luò)的鄉(xiāng)（鎮(zhèn)）、村分布較為均勻，故有可能找出停留時(shí)間盡量均衡的6

16、9分組，當(dāng)分4組時(shí)各組停留時(shí)間大約為69 = 17.25小時(shí)，則每組分配在路途上的時(shí)4間大約為24-17.25=6.75小時(shí).而前面討論過(guò)，分三組時(shí)有個(gè)總路程599.8公里的 巡視路線，分4組時(shí)的總路程不會(huì)比599.8公里大太多，不妨以599.8公里來(lái)計(jì)算.599 817,路上時(shí)間約為-99 = 17小時(shí)，若平均分配給4個(gè)組，每個(gè)組約需一=4.25小時(shí)6.75354小時(shí)，故分成4組是可能辦到的?，F(xiàn)在嘗試將頂點(diǎn)分為4組.分組的原則：除遵從前面準(zhǔn)則一、二、三外，還應(yīng)遵 從以下準(zhǔn)則：準(zhǔn)則四：盡量使各組的停留時(shí)間相等。用上述原則在圖11-10上將圖分為4組，同時(shí)計(jì)算各組的停留時(shí)間，然后用算法 一算出各

17、組的近似最佳推銷員巡回，得出路線長(zhǎng)度及行走時(shí)間，從而得出完成巡視 的近似最佳時(shí)間.用算法一計(jì)算時(shí)，初始圈的輸入與分三組時(shí)同樣處理。這4組的近似最優(yōu)解見(jiàn)表3：表3 （路程單位：公里；時(shí)間單位：小時(shí)）組名路線路線 總長(zhǎng)度停留時(shí)間行走 時(shí)間完成巡視 的總時(shí)間IO G- 9.2567E8E11 12H 12F 10F E7652O195.8175.5922.59IIO 2 16一 P（R29Q30Q2827 6N242322 17 -17 K2223N26 O199.2165.6921.69IIIOM252021K 18 1514 13J 19L MOI6159.1184.5422.54IVO 34一

18、 2RA33313235- _B1C3D4D O一3166184.7422.74上表中符號(hào)說(shuō)明：加有底紋的表示前面經(jīng)過(guò)并停留過(guò)，此次只經(jīng)過(guò)不需停留;加框的表示此點(diǎn)只經(jīng)過(guò)不停留。該分組實(shí)際均衡度 = 22.74 21.69 = 4.62%022.74可以看出，表3分組的均衡度很好，且完全滿足24小時(shí)完成巡視的要求。問(wèn)題二我們發(fā)現(xiàn)從O點(diǎn)巡視H點(diǎn)的最短時(shí)間是所有最短時(shí)間中最長(zhǎng)的，其距離為77.5 公里。其時(shí)間為775.t =x2 + 2 = 6.43 小時(shí) H 35因此，T=2小時(shí)，t=1小時(shí)，V=35公里/小時(shí)。若巡視人員足夠多，完成巡視的 最短時(shí)間為6.43小時(shí)。在最短時(shí)間內(nèi)限定一下，完成巡視的

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

20、讓這組巡視到這一點(diǎn)，直到At 1,然后再?gòu)牡诙介_(kāi)始。H通過(guò)以上方法，最后我們找到的最優(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

21、-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-

22、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

23、-OP,R5.321.11問(wèn)題四巡視組數(shù)已定，要求盡快完成巡視，討論T, t和V的改變對(duì)最佳巡視路線的 影響。要盡快完成巡視，就得要求每組完成巡視時(shí)間盡量均衡，因?yàn)榭偟耐瓿裳惨?時(shí)間按最長(zhǎng)的完成巡視時(shí)間計(jì)算?，F(xiàn)在討論在均衡度允許的范圍內(nèi)已分成 n組后，改變T，t和V對(duì)最佳巡視路線的影響。顯然在分組不變的情況下，無(wú)論了 T,t、V如何改變，對(duì)每組內(nèi)的最佳巡視路線是沒(méi)有影響的，但可能會(huì)影響各組間 的均衡性。因此該問(wèn)題實(shí)際上討論T，t和V對(duì)于分組的影響，即在不破壞原來(lái)分 組均衡的條件下，T，t和V允許的最大變化范圍。在分n組的情況下，設(shè)S：表示第i組的最佳推銷員回路路線總長(zhǎng)度；X :表示第i組所要停

24、留的鄉(xiāng)鎮(zhèn)的數(shù)目；丫；表示第i組所要停留的村的數(shù)目；ii=1,2,3,，n顯然，當(dāng)X = X , Y = Y, S = S ; i, j = 1,2,3,員，即每組的鄉(xiāng)（鎮(zhèn)）數(shù)、村數(shù)、I j i j i j最佳巡回的長(zhǎng)度均相等，因而分組絕對(duì)均衡時(shí)，即a 0 =0時(shí)，無(wú)論T，t和V如何改變都不會(huì)改變?cè)瓉?lái)分組的均衡。（一）不影響分組的均衡時(shí)，T, t和V的最大允許變化范圍的討論: 對(duì)任意一個(gè)組i，其完成巡視的時(shí)間S 一T = X T+Yt + r, i 1,2,3,.,n設(shè)均衡分組的最大允許時(shí)間均衡度為a，即-一i - a i, j = 123 nMax T 1，2,3,ni=i,2,3,. ,n貝

25、臨 T -T a x MaxTi=1,2,3,. n記8 =ax MaxT，則e表示均衡分組所允許的最大時(shí)間誤差，則ii=1,2,3,., n TOC o 1-5 h z S S,、(X- X )T + (Y- Y )t + i j 8(1)由(1)式我們得到8 (X X )T + (Y Y )t + Si -Sj e(2)i j i j VMax -8-（匕- j+十 1 T Min8Max -8-（匕- j+十 1 T 0X XX X 0X X1 j .1 j .由式(2)可得1.當(dāng)X X 0時(shí)，要保持原均衡分組不變，T必須滿足的條件為i j2.當(dāng)Y Y 0時(shí)，要保持原均衡分組不變，t必須

26、滿足的條件為ij（3）Max 01S S 18 (X X )t _j一 T 0Y Y1 j8 (X X )t Si - S ji j VY Yij3.當(dāng)S -S 0時(shí)，由(2)式得(X X )T + (Y Y )t 8 Si -Sj 8(X X )T (Y Y )ti j i jVi j i j 當(dāng)(X. -X )T + (Y Y )t max 8 時(shí)，有8V max 0（5）(j) j ()8-W X ) T - Y Y ) ti j i jX )& Y ) t 8i ji j V min 0（6）由（3）（6）式，當(dāng)T,t,V三個(gè)變量中任意兩個(gè)變量無(wú)論如何變化，都可計(jì)算出 為保持均衡性分組

27、不變，三個(gè)變量所允許的最大變化范圍。（二）分三組的實(shí)例討論論 對(duì)問(wèn)題一中所得的三個(gè)分組 若考慮停留時(shí)間和 t 論 對(duì)問(wèn)題一中所得的三個(gè)分組 若考慮停留時(shí)間和 t = t = 1小時(shí)，V =匕=35公里/小時(shí)，結(jié)果如表5：行駛時(shí)間且取T = T = 2小時(shí)編號(hào)XYS行駛時(shí)間總時(shí)間I513191.15.4628.46II611192.35.4928.49III611216.46.1829.18o一一表5 （路程單位：公里；時(shí)間單位：小時(shí)）29.18 28.46實(shí)際均衡度為a = 2.5%。29.18實(shí)際時(shí)間誤差為 = 2.5% x29.18 = 0.72小時(shí)?，F(xiàn)分別規(guī)定均衡分組的最大允許均衡度a

28、= 2.5%和a = 5%，即最大容許的時(shí)間 誤差分別為 = 0.72小時(shí)和 = 1.44小時(shí)，計(jì)算出T,t,V三個(gè)參量中固定任意兩個(gè)時(shí)， 要不破壞原均衡分組，另一個(gè)參量所容許的變化范圍，結(jié)果如下表：表6V,t不變T,V不變T,t不變a = 2.5% = 0.72小時(shí)1.25 T 21 t 35a= 5% = 1.44小時(shí)0.51 T 2.740.63 t 17.3上表可以看出：（1）當(dāng)實(shí)際均衡度a0 = 2.5%剛好等于最大容許均衡度a = 2.5%時(shí)，要保持原 均衡分組，當(dāng)t，V不變時(shí)，T只能減小，且下界為1.25小時(shí)；T的上界為T0 = 2小 時(shí)；T，V不變時(shí)，t只能增大，且上界為1.3

29、8小時(shí)；t的下界為t = 1小時(shí)；0t，T不變時(shí)，V只能增大，且下界為35；無(wú)上界；（2）當(dāng)實(shí)際均衡度a = 2.5%小于最大容許均衡度a = 5%時(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增大但無(wú)上界，且下界為17.3公里/小時(shí)；（三）對(duì)實(shí)例結(jié)果的分析上述實(shí)例的均衡分組有一個(gè)特點(diǎn)，各組的停留時(shí)間相等，即取T = T = 2小時(shí)，t = t0 = 1小時(shí)，V = V = 35公里/小時(shí)，、在表5的分組中G X）.T - Y Y）t = 0, i, j = 1,2

30、,3（7）i j 0 i j 0定義4各組的停留時(shí)間相等的均衡分組稱為停留時(shí)間相等的均衡分組，由（7）式 得T = % -1 , X - X。0,i, j = 1,2,3（8）0 X X 0 i j現(xiàn)討論對(duì)停留時(shí)間相等的均衡分組，T,t,V的變化規(guī)律，對(duì)停留時(shí)間相等的均衡分 組，分組的實(shí)際時(shí)間誤差： = = max0i, jx).t +YQ. t + H TOC o 1-5 h z =max JI i j = S S（9）i,j I V J V 00其中，i為使S,最大的組的標(biāo)號(hào)；j為使.最小的組的標(biāo)號(hào)。（*）當(dāng) T,t 不變時(shí)，即 T = T , t = t 時(shí)，因 & X）.T +Y Y） t = 0 0sX)T Yi jiY ) tj