《數(shù)學(xué)建模優(yōu)秀論文-災(zāi)情巡視路線的數(shù)學(xué)模型.doc》由會員分享，可在線閱讀，更多相關(guān)《數(shù)學(xué)建模優(yōu)秀論文-災(zāi)情巡視路線的數(shù)學(xué)模型.doc（25頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

災(zāi)情巡視路線的數(shù)學(xué)模型 摘 要 本文解決的是災(zāi)情巡視路線的設(shè)計(jì)問題。由于路線圖可看成網(wǎng)絡(luò)圖因此此問題可轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)Ｏ出發(fā)行遍所有頂點(diǎn)至少一次再回到點(diǎn)Ｏ使得總權(quán)（路程或時間）最小的問題。然后針對具體問題，采用一些啟發(fā)式算法，建立模型進(jìn)行求解。 對于問題一：基于設(shè)計(jì)分三組巡視時使總路程最短且各組盡可能均衡的巡視路線的要求我們采用Dijkstra算法，通過對初始圈進(jìn)行二邊逐次修正,處理三組的巡視路線長度，用lingo軟件求解出較優(yōu)方案。定義分組的均衡度系數(shù)a檢驗(yàn)分組均衡度，在均衡度為a=0.0751時得到分三組（路）巡視時，總路程最短且各組盡可能均衡的巡視路線見附表1。 對于問題二：將問題轉(zhuǎn)化為圖論問題，運(yùn)用問題一的求解方法，得到分為四組的路線，在通過均衡度分析之后得出近似最優(yōu)巡視路線。利用lingo軟件求得，至少要分四組，且四組的近似最優(yōu)巡視路線見附表2。 對于問題三：基于問題一二中圖論的方法，考慮到從Ｏ點(diǎn)巡視H點(diǎn)的最短時間是所有巡視線路中用時最長的，將計(jì)算出的最長路線巡視所用的時間作為巡視路線的最短時間限定，在此限定下對路線進(jìn)行設(shè)計(jì)。求得的最短時間為6.43小時，最佳巡視路線分為23組。（具體分組見附錄二） 對于問題四：由于組數(shù)一定， T，t和V改變，對每組內(nèi)的最佳巡視路線是沒有影響的，但可能會影響到各組件的均衡性，因此問題實(shí)質(zhì)是討論T，t和V對分組的影響，即在不破壞原來分組均衡的條件下T，t和V允許的最大變化范圍。 關(guān)鍵詞：啟發(fā)式算法 Dijkstra算法 均衡度 圖論 二邊逐次修正 1. 問題重述 1.1問題背景 今年夏天某縣遭受水災(zāi)。為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線。附錄一中給出了該縣的鄉(xiāng)（鎮(zhèn)）、村公路網(wǎng)示意圖，公路邊的數(shù)字為該路段的公里數(shù)。 1.2本文需解決的問題 問題一：若分三組（路）巡視，試設(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改變對最佳巡視路線的影響。 2. 模型的假設(shè)與符號說明 2.1模型的假設(shè) 假設(shè)1：公路不考慮等級差別，不受災(zāi)情和交通情況的影響。 假設(shè)2：各條公路段上的汽車行駛速度均勻。 假設(shè)3：各巡視組巡視的鄉(xiāng)（鎮(zhèn)）、村不受行政區(qū)劃分的影響。 假設(shè)4：各巡視組行動統(tǒng)一，一個巡視組不可再分成若干小組。 假設(shè)5：巡視當(dāng)中在每個鄉(xiāng)（鎮(zhèn)）村的停留時間一定，不會出現(xiàn)特殊情況而延誤時間。 2.2符號說明 符號 符號說明 巡視小組在鄉(xiāng)（鎮(zhèn)）巡視的停留時間 巡視小組在村巡視的停留時間 汽車行駛速度 為導(dǎo)出子圖中的最佳Ｈ圈。（其中=1，2，3，…，n.） 為的權(quán)，（其中=1，2，3，…，n.） 最大允許均衡度 分組后的實(shí)際均衡度 第個點(diǎn)距起始點(diǎn)的路線長度 點(diǎn)的時間權(quán)重 分組數(shù) 第組巡視時要停留的鄉(xiāng)（鎮(zhèn)）數(shù) 第組巡視時要停留的村數(shù) 最短時間下限 第巡視路線的長度 第巡視所用的時間 3. 問題分析 此題研究的是某縣災(zāi)情巡視路線的設(shè)計(jì)問題。問題要求設(shè)計(jì)出最佳的巡視路線，即：保證總路程最短或時間最小而且各組盡可能均衡的巡視路線?；趫D論相關(guān)理論，借助于幾何直觀和生活體驗(yàn)的啟發(fā)作用，便于為計(jì)算機(jī)搜索制定行之有效的操作規(guī)則，接著利用圖論軟件包通過計(jì)算機(jī)求解出較精確的路線。再通過線路均衡性比較，對均衡性不好的線路進(jìn)行微調(diào)。以此方法確定最佳巡視路線。 針對問題一：基于對問題的分析，借助圖論知識，將所給公路網(wǎng)就轉(zhuǎn)化為圖論中的加權(quán)網(wǎng)絡(luò)圖，因此問題就轉(zhuǎn)化為一個圖論問題，即在給定的加權(quán)網(wǎng)絡(luò)圖中，尋找從給定點(diǎn)Ｏ出發(fā)，行遍所有頂點(diǎn)至少一次再回到Ｏ點(diǎn)，使得總權(quán)（路程或時間）最小。此即多個推銷員的最佳推銷員回路問題?；谝陨戏治?，運(yùn)用圖論知識和圖論軟件包進(jìn)行求解，再利用均衡度分析對得到的分組路線進(jìn)行微調(diào)，均衡度越小表示路線越均衡，微調(diào)后即可得到相對較優(yōu)的分組路線?？烧J(rèn)為這樣設(shè)計(jì)的分組方法和巡回路線能使總路線近似最短。 針對問題二：在問題一的基礎(chǔ)上添加了巡視組在各鄉(xiāng)鎮(zhèn)停留時間T=2小時，在各村停留時間t=1小時，汽車行駛速度V=35公里/小時等條件，要求在24小時內(nèi)完成巡視的最少分組數(shù)以及相應(yīng)的最佳巡視路線。首先，由圖中數(shù)據(jù)初步計(jì)算后判斷分成四組可行，再針對分組為四組的情況進(jìn)行線路設(shè)計(jì)，仍將問題轉(zhuǎn)化為圖論問題，運(yùn)用問題一的求解方法，得到分為四組的路線，在通過均衡度分析之后得出近似最優(yōu)巡視路線。 針對問題三：在問題二中關(guān)于T , t和V的假定下且巡視人員足夠多時，要求在最短時間完成巡視的要求下所得的最佳的巡視路線，此時考慮到從Ｏ點(diǎn)巡視H點(diǎn)的最短時間是所有巡視線路中用時最長的，將計(jì)算出的最長路線巡視所用的時間作為巡視路線的最短時間限定，在此限定下對路線進(jìn)行設(shè)計(jì)?；趩栴}一二中圖論的方法，從一些點(diǎn)的路線比較少的點(diǎn)開始，能夠使搜素容易進(jìn)行，因此選擇從距離Ｏ點(diǎn)一些較遠(yuǎn)的點(diǎn)（如12 10 15 22等點(diǎn)）開始搜索，每次搜索時都要對該點(diǎn)的巡視時間進(jìn)行判斷，直到找到近似最優(yōu)路線。 針對問題四：在巡視組數(shù)已定(如三組）的情況下，為盡快完成巡視就要求每組完成的巡視時間盡量均衡，因?yàn)榭偟耐瓿裳惨晻r間按線路最長的完成巡視時間計(jì)算，由于組數(shù)一定， T，t和V改變，對每組內(nèi)的最佳巡視路線是沒有影響的，但可能會影響到各組件的均衡性，因此問題實(shí)質(zhì)是討論T，t和V對分組的影響，即在不破壞原來分組均衡的條件下T，t和V允許的最大變化范圍。需要用控制單一變量的方法，分別討論T、t、V三個量中任意兩個量不變時第三個量的變化范圍。從而確定T，t和V的改變對最佳巡視路線的影響。 4. 數(shù)據(jù)分析 4.1問題一數(shù)據(jù)分析 基于對該縣公路圖的初步分析，可以統(tǒng)計(jì)出該縣有鄉(xiāng)（鎮(zhèn)）17個，村35個。（線路圖見附錄一） 應(yīng)用lingo軟件求解(具體程序見附錄三)得出巡視點(diǎn)距離縣政府所在地的最短距離，如表1所示： 表1：Ｏ點(diǎn)到其余各點(diǎn)的最短距離 P R 1 C 2 M 26 O 10.1 12.9 6 11.5 9.2 19.8 20.6 28 29 31 A B 3 5 O 22.2 20.8 22.1 16.3 11.9 14 17.5 N 25 20 L 6 7 D O 31.1 31.8 38.3 39 27.2 34.5 22.2 4 8 E 9 F 10 12 O 34.9 49.7 41.7 49.5 55.1 65.9 67.3 11 G H 13 14 J 19 O 55.9 62.7 77.5 64.1 72.7 54.3 46.2 18 I 15 16 17 22 K O 52.9 61.1 69.9 60.3 53.5 49 43.7 21 23 24 27 Q 30 32 O 39.6 39 44.3 28.4 28 35.7 30.2 33 35 34 O 23.7 36 27.8 由此表格畫出了最短路徑生成圖，如圖1 圖 1 由上圖便于在第一問分析得到分組情況。 4.2問題二數(shù)據(jù)分析 問題二中給出了巡視小組在鄉(xiāng)（鎮(zhèn)）村的停留時間和汽車行駛速度，分別為：巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2小時，在各村停留時間t=1小時，汽車行駛速度V=35公里/小時。對于要在24小時內(nèi)完成巡視，至少應(yīng)分幾組的問題，應(yīng)首先求出最長路線巡視所用的時間，用停留總時間加上行走時間除以4的結(jié)果與24進(jìn)行比較，以此判斷最少分組能否為4組。計(jì)算如下： (17*2+35+599.8/35)/4=21.5<24(小時) （其中路線長度估算為599.8公里）因此最少分組可定為4組。 5． 問題一的解答 本文研究的是災(zāi)情巡視路線的最優(yōu)設(shè)計(jì)問題，由于路線圖可看成網(wǎng)絡(luò)圖，因此此問題可轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找線路使總權(quán)（路程或時間）最小的問題。然后針對具體問題，采用一些啟發(fā)式算法，建立模型。 5.1模型一的建立 5.1.1模型一的準(zhǔn)備 經(jīng)對問題的初步分析，基于圖論的相關(guā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)Ｏ出發(fā)，行遍所有頂點(diǎn)至少一次再回到Ｏ點(diǎn)，使得總權(quán)（路程或時間）最小。 定義１　經(jīng)過圖Ｇ的每個頂點(diǎn)正好一次的圈，稱為Ｇ的哈密爾頓圈，簡稱Ｈ圈。 定義２ 在加權(quán)圖中 　　　?。ǎ保?quán)最小的哈密爾頓圈稱為Ｈ圈： （２）經(jīng)過每個頂點(diǎn)至少一次且權(quán)最小的閉通路稱為最佳推銷員回路。 由定義（2）可知本問題是一個尋求最佳推銷員回路的問題，最佳推銷員回路的問題可以轉(zhuǎn)化為最佳Ｈ圈的問題，方法是由給定的圖Ｇ＝（Ｖ，Ｅ）構(gòu)造一個以Ｖ為頂點(diǎn)集的完備圖Ｇ’=（Ｖ，Ｅ’）Ｅ’中每條邊（x y）權(quán)等于頂點(diǎn)x與y在圖Ｇ中最短路徑的權(quán)，即。 在圖論中有以下定理： 定理１ 加權(quán)圖Ｇ的最佳推銷員回路的權(quán)和Ｇ’的最佳Ｈ圈的權(quán)相同。 定理2 在加權(quán)完備圖中求最佳Ｈ圈的問題是NP——完全問題。 我們采用一種近似算法求出該問題的一個近似最優(yōu)解，來代替最優(yōu)解，算法如下： 算法一 求加權(quán)圖Ｇ＝（Ｖ，Ｅ）的最佳推銷員回路的近似算法： ⑴用圖論軟件包求出Ｇ中任意兩個頂點(diǎn)間的最短路，構(gòu)造出完備圖Ｇ’（Ｖ，Ｅ’） ⑵輸入圖Ｇ’的一個初始Ｈ圈； ⑶用對角線完全算法[2]產(chǎn)生一個初始Ｈ圈； ⑷隨機(jī)搜索出Ｇ’中若干個Ｈ圈，例如3000個； ⑸對⑵⑶⑷步所得的每個Ｈ圈用二邊逐次修正法[2]進(jìn)行優(yōu)化，得到近似最佳Ｈ圈； ⑹在第⑸步求出的所有Ｈ圈中，找出權(quán)最小的一個，此即要找的最佳Ｈ圈的近似解。（算法程序見附錄） 由于二邊主次修正法的結(jié)果與初始圈有關(guān)故本算法第⑵⑶⑷步分別用三種方法，產(chǎn)生初始圈，以保證能得到較優(yōu)的計(jì)算結(jié)果。 在此問題是多個推銷員的最佳推銷員回路問題，即在加權(quán)圖Ｇ中求頂點(diǎn)集Ｖ的劃分Ｖ1，Ｖ２，…，Ｖｎ 將G分成n 個生成子圖G[Ｖ１]， Ｇ［Ｖ２］，…，Ｇ[Vn]，使得： ⒈頂點(diǎn)ＯＶｉ，ｉ＝1,2,3，…，n. ⒉. ⒊，其中Ｃi 為導(dǎo)Ｖi的導(dǎo)出子圖G[Ｖ１]中的最佳Ｈ圈，w(Ci)為Ci 的權(quán)，i，j=1，2，3，…，n. ⒋. 定義3 稱為該分組的實(shí)際路線均衡度，為最大允許均衡度，顯然01，越小說明分組的均衡性越好，取定一個后，與滿足條件3的分組，條件4表示總巡視路程最短。 此問題包含兩個方面：第一，對點(diǎn)分組；第二，在每組中尋求最佳推銷員回路，即為單個推銷員的最佳推銷員問題，我們只能去尋求一種較合理的劃分準(zhǔn)則，對圖進(jìn)行初步劃分后，求出各部分的最佳推銷員回路的權(quán)，在進(jìn)一步進(jìn)行調(diào)整，使得各部分滿足均衡性條件3. 從Ｏ點(diǎn)出發(fā)去其它點(diǎn)，要使路程較小應(yīng)盡量走Ｏ點(diǎn)到該點(diǎn)的最短路，故用圖論軟件包求出Ｏ點(diǎn)到其余頂點(diǎn)的最短路，這些最短路構(gòu)成一棵以Ｏ為樹根的樹，將從Ｏ點(diǎn)出發(fā)的樹枝稱干枝，如圖2： 圖 2 從圖中可以看出，從Ｏ點(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)則三 盡量將的干枝與短的干枝分在同一組。 由上述分組原則，為我們找到兩組分組形式如下： 分組一：（⑥，①），（②，③），（⑤，④） 分組二：（①，②），（③，④），（⑤，⑥） 顯然由圖中可以直接看出分組一的方法極不均衡，故考慮分組二。 對分組二中每組頂點(diǎn)的生成子圖，用算法一求出近似最優(yōu)解及相應(yīng)的巡視路線，使用算法一時在每個子圖所構(gòu)造的完備圖中，取一個盡量包含圖1中樹上的邊的Ｈ圈作為其第二步輸入的初始圈。依次求解得到巡視路線的近似最優(yōu)解。 5.1.1綜上所述，問題一的優(yōu)化模型為： 5.2問題一的解答。 在本模型的基礎(chǔ)上，運(yùn)用lingo軟件求解出分三組巡視時近似最優(yōu)的巡視路線（具體程序見附錄三），如表2： 表2：分三組巡視的近似最優(yōu)路線圖 組號 路 線 路線長度 路線總長度 I OP282726N24232217 16I15I18K212025MO 191 589.8 II OR29Q303231333534 A1BC3D4D32O 192.3 III O256L19J11G1314 H12F10F9E8E765 2O 206.5 5.3問題一的結(jié)果分析 由以上分三組所得的路線結(jié)果可以看出， 第一組的巡視路線為： Ｏ－Ｐ－28－27―26―N―24―23―22―17―16―I―15―18―K―21―20―25―M―O 第二組巡視路線為： Ｏ－R－29－Q―30―32―31―33―35―34―A―1―B―C―3―D―4―D―3―2－O 第三組巡視路線為： Ｏ－2－5－6―L―19―J―11―G―13―14―H―12―F―10―F―9―E―8―E―7―6―5―2―O 將以上巡視線路的巡視距離進(jìn)行均衡度分析： =7.46%=0.0746 當(dāng)規(guī)定距離均衡度=0.1時，此三組的巡視路線的設(shè)計(jì)均符合要求。而且實(shí)際均衡度比0.1小得多，可見路線設(shè)計(jì)很合理。 6. 問題二的解答 6.1模型二的建立 6.1.1確定目標(biāo)函數(shù) 由于T=2小時，t=1小時，V=35公里/小時，需訪問的鄉(xiāng)（鎮(zhèn)）共有17個，村共有35個，計(jì)算出在鄉(xiāng)鎮(zhèn)的總停留時間為： 17*2+35=69（小時） 需要在24小時內(nèi)完成巡視，考慮行走時間有： (17*2+35+599.8/35)/4=21.5<24(小時) （其中最長路線長度估算為599.8公里）因此最少分組可定為4組。 由于該網(wǎng)絡(luò)的鄉(xiāng)（鎮(zhèn)）、村分布較均勻，故有可能找處停留時間計(jì)量均衡的分組，當(dāng)分四組時各組停留時間大約為： 69/4=17.25（小時） 則每組分配在路途的時間大約為： 24－17.25=6.75（小時） 問題分析時有分三組路線時，巡視總路線最長的是599.8公里，分四組時的總路程更不會比599.8公里大太多，不妨以599.8公里來計(jì)算，路途時間約為： （599.8/35)/4=4.25（小時） 由于4.25<6.75（小時）因此分成四組是可以辦到的。 現(xiàn)在嘗試將頂點(diǎn)分為四組，分組準(zhǔn)則為： 準(zhǔn)則一 盡量使同一干枝上及其分支上的點(diǎn)分在同一組； 準(zhǔn)則二 應(yīng)將相鄰的干枝上的點(diǎn)分在同一組； 準(zhǔn)則三 盡量將的干枝與短的干枝分在同一組； 準(zhǔn)則四 盡量使各組的停留時間相等。 以上原則將圖1中的頂點(diǎn)分為四組，同時計(jì)算各組的停留時間，然后用模型一中的算法算出各組的近似最佳推銷員巡回，得出路線長度及行走時間，從而得出完成巡視的近似最佳時間，用模型一的算法進(jìn)行計(jì)算時，初始圈的輸入與分三組時的處理方式一樣。 利用lingo軟件求解得出分為四組時的近近似最優(yōu)巡視路線。 6.1.1綜上所述，問題二的優(yōu)化模型為 6.2問題二的求解 在模型二的基礎(chǔ)上，運(yùn)用lingo軟件求解出分四組巡視時近似最優(yōu)的巡視路線（具體程序見附錄三），如表3： 表3：分四組巡視時的近似最優(yōu)路線 組號 路 線 巡視時間 路線長度 路線總長度 I ORA3331323534B1 CD4D32O 22.74 166 735 II OR29Q30Q282726N 242322171617K2223N 26PO 21.91 206.9 III OM252021K18I151413 J19L6MO 21.75 166.3 IV O2567E8E9F10F 12H12G11E7652O 21.59 195.8 6.3問題二結(jié)果分析 由以上分四組所得的路線結(jié)果可以看出， 第一組的巡視路線為： Ｏ－R－A－33―31―32―35―34―B―1―C―D―4―D―3―2―O 第二組巡視路線為： Ｏ－R－29－Q―30―Q―28―27―26―N―24―23―22―17―16―17―K―22―23―N－26―P―O 第三組巡視路線為： Ｏ－M－25－20―21―K―18―I―15―14―13―J―19―L―6―M―O 第四組的巡視路線為： Ｏ－2－5－6―7―E―8― E―9―F―10―F―12―H―12―G―11―E―7―6－5―2―O 對以上巡視線路的巡視距離進(jìn)行均衡度分析： =19.33%=0.1933 對以上巡視線路的巡視時間進(jìn)行均衡度分析： =5.06%=0.0506 由距離均衡度和時間均衡度可以看出，所分組的巡視路線的距離均衡度較好，時間均衡度也較好。 因此，所得路線可以認(rèn)為是分組的近似最優(yōu)解巡視線路。 7. 問題三的解答 7.1模型三的建立 7.1.1確定目標(biāo)函數(shù) 由于巡視人員足夠多，故單獨(dú)巡視所花的時間要小的多，所有組中完成的巡視時間最長的可看為完成巡視時間的下限tmin ，從最短生成樹上可以看出，點(diǎn)Ｈ距離點(diǎn)Ｏ最長，且Ｈ的權(quán)最大（為2），故巡視Ｈ的那組所花的時間為完成整個巡視時間的下限： =（小時） 于是問題變成在6.43小時內(nèi)完成巡視所需的最少分組和巡視方案。 則目標(biāo)函數(shù)： minn 7.1.2確定約束條件 即使人員足夠多，分組再細(xì)，完成巡視至少需要的時間不能超過巡視時間的下限，即： 7.1.3綜上所述，得到問題三的優(yōu)化模型 minn s.t 7.2問題三的求解 我們采用一種算法解決此問題，算法如下： ⑴ 令i=0； ⑵選最短樹形圖中違背標(biāo)號的點(diǎn)中離Ｏ點(diǎn)最近的點(diǎn)，設(shè)為Ｍ，Ｍ與Ｏ的距離記為lm ,設(shè)第i個巡視點(diǎn)集Vi ={Ｍ}，計(jì)算V最多還可增加的點(diǎn)的權(quán)之和 ⑶盡可能使并入Vi的點(diǎn)的權(quán)之和為[l’m]，同時滿足從Ｏ點(diǎn)出發(fā)，經(jīng)歷Vi中所有點(diǎn)并回到Ｏ點(diǎn)的路Li，使，為路Li的長度，分別為權(quán)為的點(diǎn)的個數(shù)。若同時存在幾種并入方式，先取并入的點(diǎn)到Ｏ點(diǎn)距離和最大的那一種。 ⑷在圖中把含有的點(diǎn)標(biāo)上號，若還有點(diǎn)未標(biāo)號，令i=i+1轉(zhuǎn)⑵，否則，停止。 通過這種算法利用lingo軟件包處理得到分組數(shù)為23組，（具體程序見附錄三）結(jié)果見表3： 表3：巡視人員足夠多時的近似最佳巡視路線 編號 巡視路徑 停留地 所需時間 時間差 1 O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-O H 6.43 0 2 O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-O 13,14 6.15 0.28 3 O-2-5-6-7-E-9-F-10-F-9-E-7-6-5-2-O 10,7 5.77 0.66 4 O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O 12,9 5.85 0.58 5 O-M-25-21-K-18-I-15-I-18-K-21-25-M-O 15,18 5.99 0.44 6 O-2-5-6-7-E-11-G-11-E-7-6-5-2-O G 5.58 0.55 7 OM-25-K-18-I-18-K-25-M-0-O I 5.49 0.94 8 O-M-25-21-K-17-16-17-K-21-25-M-O 16,17 5.45 0.98 9 O-2-5-6-7-E-11-E-7-6-5-2-O 11,E 6.19 0.24 10 O-2-5-6-7-E-9-F-9-E-7-6-5-2-O F 5.15 1.08 11 O-2-5-6-L-19-J-19-L-6-5-2-O J,19 6.10 0.33 12 O-P-26-N-23-22-23-N-26-P-O 22,23,26 5.80 0.63 13 O-2-5-6-7-E-8-E-7-6-5-2-O 8,5,2 5.80 0.63 14 O-P-26-N-24-N-26-P-O 24,N 5.53 0.90 15 O-M-25-21-K-21-25-M-O K,21 5.50 0.93 16 O-2-5-6-L-6-5-2-O L,6 5.23 1.02 17 OM-25-20-25-M-O 20,25,M 6.19 0.24 18 O-R-31-32-35-34-A-1-O 31,32,34,35 6.32 0.11 19 O-29-Q-30-29-R-O 30,Q,29 6.04 0.39 20 O-2-3-D-4-D-3-2-O 4,D,3 5.99 0.44 21 O-1-B-C-O 1,B,C 5.98 0.45 22 OP-26-27-28-P-O- 27,P,26,28 6.38 0.05 23 O-1-A-33-A-R-O A,33,R 6.41 0.02 7.3問題三的結(jié)果分析 由上求得最短巡視時間為6.43小時。 在問題二T , t和V的假定下，若果人員足夠多，甚至每個村鎮(zhèn)都可分配一組巡視人員，此時巡視的最短時間為所有組中完成的巡視時間最長的那個時間，故計(jì)算出離出發(fā)點(diǎn)最遠(yuǎn)的點(diǎn)所需的巡視時間作為完成巡視的最短時間是切合實(shí)際的。 上表是在6.43小時內(nèi)完成巡視所需的最少分組和巡視方案，可見，最少分組為23組，每組完成巡視的時間分別為： 6.43－6.15－5.77－5.85－5.99－5.58－5.49－5.45－6.19－5.15－6.10－5.80－5.53－5.50－5.23－6.19－6.32－6.04－5.99－5.98－6.38－6.41 可見以上各組完成巡視時間均在6.43小時內(nèi)。 且各個小組完成巡視的時間與最短時間下限之差很小，如表中所示，時差分別為： 0―0.28―0.66―0.58―0.44―0.55―0.94―0.98―0.24―1.08―0.33―0.63―0.63―0.90―0.93―1.02―0.24―0.11―0.39―0.44―0.45―0.05―0.02 由此可見最大時差為1.08最小時差為0，時差變化范圍較小。 接著利用時間均衡度來衡量分組的均衡性，得到時間均衡度為： =15.55%=0.1555 可見在這種分配方案下，巡視時間和所分組數(shù)均可以認(rèn)為是近似最優(yōu)解。 8. 問題四的解答 8.1模型四的建立 8.1.1確定目標(biāo)函數(shù) 8.1.1.1模型準(zhǔn)備 方法一： 正如問題三已經(jīng)提到的要盡快完成巡視即要求各組巡視時間的最大值也要最小，用數(shù)學(xué)表達(dá)式就是： 這里是給定的分組數(shù)，分別是第組停留的鄉(xiāng)（鎮(zhèn)）數(shù)和村數(shù)，是第組巡視路線的長度（=1，2，…,k） 在上述的表達(dá)式中，由于的作用完全相仿，所以為簡化起見對于任意給定的，不妨記，即，這里可簡記為 ⒈若t增大而V不變，為了使的最大值盡可能小就要求的最大值盡可能小。但是當(dāng)T和t的關(guān)系確定后，是定值（等于，其中是全縣的鄉(xiāng)（鎮(zhèn)）數(shù)17，是全縣的村數(shù)35）。上述要求就成為各組停留鄉(xiāng)村數(shù)（加權(quán)之后之和）盡可能均衡，用數(shù)學(xué)式子表示即為： 這里和分別表示數(shù)的上整數(shù)和下整數(shù)，當(dāng)然在調(diào)整各組的停留的鄉(xiāng)村數(shù)使之達(dá)到均衡時，自然會給各組的路線及其長度帶來影響，這時應(yīng)當(dāng)考慮進(jìn)行適當(dāng)調(diào)整。 ⒉若t不變而V增大，這種情況下，在中可能導(dǎo)致起主導(dǎo)作用。因此和1的結(jié)論類似，更應(yīng)使即各組的巡視路線盡可能均衡，又因?yàn)椴皇浅?shù)，而且的均衡性會帶來的增大，這對于盡快完成巡視會帶來負(fù)面影響，所以對具體情況應(yīng)做具體分析，比如可以考慮的前半部分對均衡性的修正，對路線較長的組盡量考慮停留較少的鄉(xiāng)村。 對于T , t和V之間的交互作用會使情況變得更復(fù)雜。 此方法有助于要討論T , t和V之間的變化，但是不能定量的求出T , t和V的變化范圍，因此我們在此方法上進(jìn)行改進(jìn)，如方法二。 方法二： 確定T , t和V允許的最大變化范圍。 在已確定組數(shù)的情況下，無論T , t和V如何改變，對每組內(nèi)的最佳尋視路線是沒有影響的，可能會影響各組間的均衡性，因此問題轉(zhuǎn)化為在不破壞原來分組均衡的條件下，T , t和V允許的最大變化范圍。 在分n組的情況下，設(shè) Si表示第i組的最佳推銷員回路路線總長度； Xi表示第i組所要停留的鄉(xiāng)鎮(zhèn)的數(shù)目； Yi表示第i組所要停留的村的數(shù)目； i=1，2，3，…，n. 顯然，當(dāng)Xi=Xj，Yi=Yj,Si=Sj，i，j=1，2，3，…，n.時即每組的鄉(xiāng)（鎮(zhèn)）數(shù)、村數(shù)最佳巡回的長度均相等，因而分組絕對均衡時，即=0，無論T , t和V如何改變都不會改變原來分組的均衡。 （一） 不影響分組的均衡時，T , t和V的最大允許范圍的討論： 對任意一個組i，其完成巡視的時間： 設(shè)均衡分組的最大允許時間均衡度為，即： 則有： 記，則表示均衡分組所允許的最大時間誤差，稱為最大允許時間誤差。則： 由上式我們得到 由此式可推出以下結(jié)果： 1當(dāng)Xi-Xj>0時，要保持原均衡分組不變，T必須滿足的條件為： 2.當(dāng)Yi-Yj>0時，要保持原均衡分組不變，t必須滿足的條件為： 3.當(dāng)Si-Sj>0時，有 （1）當(dāng)時，有 （2）當(dāng)時，有 由1.2.3.中的式子知，當(dāng)T 、t、V三個變量中任意兩個變量無論如何變化，都可計(jì)算出為保持均衡分組不變，三個變量所允許的最大變化范圍。 （二）分三組的實(shí)例討論。 現(xiàn)對分三組的情況進(jìn)行實(shí)際討論。對問題一中所得的三個分組，若考慮停留時間和行駛時間，且取T=T0=2小時，t=t0=1小時，V=V0=35公里/小時時，結(jié)果如下表4所示： 表4：分三組巡視相關(guān)表 編號 Xi Yi Si 行駛時間 總時間 I 5 13 191 5.46 28.46 II 6 11 192.3 5.49 28.49 III 6 12 206.5 5.9 29.9 由表可計(jì)算時間的實(shí)際均衡度為： ==4.8%=0.048 實(shí)際時間誤差=0.048*29.9=1.44（小時） 現(xiàn)分別規(guī)定均衡分組的最大允許均衡度為=4.8%和=9.6%,即最大允許的時間誤差分別為：1.44小時和2.88小時。 計(jì)算出T , t和V中三個參量中任意兩個固定時，要不破壞原平衡分組，另一個參量所要允許的變化范圍。計(jì)算結(jié)果如下表5： 表5：T ，t，V中三個參量的變化范圍 T，V不變 t，V不變 T，t不變 =4.8% =1.44 =9.6% =2.88 由上表可以看出： （1）當(dāng)實(shí)際均衡度=4.8%，剛好等于最大允許均衡度=4.8%時，要保持原均衡分組，當(dāng)： t，V不變時，T只能減小，且下界為1.25小時，上界為2小時。 T，V不變時，t只能增大，且上界為1.38小時，下界為1小時。 T，t不變時，V只能增大，且無上界，V的下界為35公里/小時。 （2）當(dāng)實(shí)際均衡度=4.8%，小于最大允許均衡度=9.6%時，要保持原均衡分組，當(dāng)： t，V不變時，T的變化上界為0.51小時，下界為2.74小時。 T，V不變時，t的變化上界為0.63小時，下界為1.75小時。 T，t不變時，V無上界，V的下界為17.3公里/小時。 9. 模型的評價、改進(jìn)及推廣 9.1模型評價 優(yōu)點(diǎn)： （1）本文提出的分組準(zhǔn)則簡便易行，可操作性強(qiáng)，且可逐步調(diào)整使分組達(dá)到均衡。 （2）引用均衡度的概念定量的刻畫了分組的均衡性。 （3）再用近似法求解最佳推銷員回路時采用了三種不同的方法產(chǎn)生初始圈，使得算法比較完善，得到了誤差很小的而近似最優(yōu)解。 （4）從理論上定量的討論了T，t和V的變化對均衡分組靈敏度的影響，得到了很好的結(jié)果。 缺點(diǎn)：使用的方法不能求得最優(yōu)解，只能求得近似最優(yōu)解。 9.2模型改進(jìn) （1）求解時可建立將多組路線轉(zhuǎn)化為一組路線來求解的思想，如果能夠找出一種準(zhǔn)則，使三個代表縣城點(diǎn)之間的距離盡量大，則在最好的情況下，將使兩個縣城點(diǎn)均分整個一條路線，這種改進(jìn)將簡化問題的求解，并可以得到較好的解。 （2）由于線路的設(shè)計(jì)是在假設(shè)條件下取得的近似最優(yōu)解，因此，需要減少假設(shè)更多的考慮實(shí)際情況下的最優(yōu)路線的設(shè)計(jì)。 9.3模型推廣 本文建立的模型可以廣泛它應(yīng)用于實(shí)際生活中涉及到圖論的有關(guān)問題，例如公交線路的而選擇問題，城市相關(guān)設(shè)施的布置等相關(guān)問題。 參考文獻(xiàn) [1] 運(yùn)籌學(xué)與實(shí)驗(yàn)/薛毅，耿美英編著?！本弘娮庸I(yè)出版社，2008.9 [2] 《運(yùn)籌學(xué)》教材編寫組編，運(yùn)籌學(xué)（3版），北京：清華大學(xué)出版社，2005.6 [3] 圖論算法及其MATLAB實(shí)現(xiàn)/王海英等編著. —北京：北京航空航天大學(xué)出版社，2010.2 附錄 附錄一：縣政府線路圖 附錄二： 編號 巡視路徑 停留地 所需時間 時間差 1 O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-O H 6.43 0 2 O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-O 13,14 6.15 0.28 3 O-2-5-6-7-E-9-F-10-F-9-E-7-6-5-2-O 10,7 5.77 0.66 4 O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O 12,9 5.85 0.58 5 O-M-25-21-K-18-I-15-I-18-K-21-25-M-O 15,18 5.99 0.44 6 O-2-5-6-7-E-11-G-11-E-7-6-5-2-O G 5.58 0.55 7 OM-25-K-18-I-18-K-25-M-0-O I 5.49 0.94 8 O-M-25-21-K-17-16-17-K-21-25-M-O 16,17 5.45 0.98 9 O-2-5-6-7-E-11-E-7-6-5-2-O 11,E 6.19 0.24 10 O-2-5-6-7-E-9-F-9-E-7-6-5-2-O F 5.15 1.08 11 O-2-5-6-L-19-J-19-L-6-5-2-O J,19 6.10 0.33 12 O-P-26-N-23-22-23-N-26-P-O 22,23,26 5.80 0.63 13 O-2-5-6-7-E-8-E-7-6-5-2-O 8,5,2 5.80 0.63 14 O-P-26-N-24-N-26-P-O 24,N 5.53 0.90 15 O-M-25-21-K-21-25-M-O K,21 5.50 0.93 16 O-2-5-6-L-6-5-2-O L,6 5.23 1.02 17 OM-25-20-25-M-O 20,25,M 6.19 0.24 18 O-R-31-32-35-34-A-1-O 31,32,34,35 6.32 0.11 19 O-29-Q-30-29-R-O 30,Q,29 6.04 0.39 20 O-2-3-D-4-D-3-2-O 4,D,3 5.99 0.44 21 O-1-B-C-O 1,B,C 5.98 0.45 22 OP-26-27-28-P-O- 27,P,26,28 6.38 0.05 23 O-1-A-33-A-R-O A,33,R 6.41 0.02 附錄三 最短路徑算法 % 求兩點(diǎn)間最短路的 Dijkstra 算法 function [d index1 index2] = Dijkf(a) % a 表示圖的權(quán)值矩陣; d 表示所求最短路的權(quán)和 % index1 表示標(biāo)號頂點(diǎn)順序； index2 表示標(biāo)號頂點(diǎn)索引 % 參數(shù)初始化 M = max( max(a) ); pb(1 : length(a)) = 0; pb(1) = 1; index1 = 1; index2 = ones(1, length(a)); d(1 : length(a)) = M; d(1) = 0; temp = 1; % 更新1(v), 同時記錄頂點(diǎn)順序和頂點(diǎn)索引 while sum(pb) < length(a) tb = find( pb == 0 ); d(tb) = min( d(tb), d(temp) + a(temp, tb) ); tmpb = find( d(tb) == min( d(tb) ) ); temp = tb( tmpb(1) ); pb(temp) = 1; index1 = [index1, temp]; index = index1( find( d(index1) == d(temp) - a( temp, index1 ) ) ); if length(index) >= 2 index = index(1); end index2(temp) = index; end d; index1; index2; 第一組路徑的程序 SETS: city/1, 2, 7, 8, 9, 16, 17, 18, 37, 38, 39,40, 41,42, 43, 44, 45, 46,47/:u; link(city, city):w, x; ENDSETS DATA: !w = @FILE('C:\Users\Administrator\Desktop\data51.txt'); w = 0 10.1 19.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10.1 0 10000 10.5 12.1 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 19.8 10000 0 10000 10000 14.2 12.0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10.5 10000 0 10000 10.5 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.8 10000 12.1 10000 10000 0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.9 10000 10000 14.2 10.5 10000 8.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.9 13.2 10000 10000 12.0 10000 10000 8.8 0 6.5 10000 10000 10000 10000 10000 10000 10000 7.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 6.5 0 10000 10000 10000 10000 10000 10000 10000 7.9 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 0 8.2 10000 10000 10000 10000 9.2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 8.2 0 8.8 11.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 8.8 0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 11.8 10000 0 6.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 6.8 0 6.7 9.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 6.7 0 10.1 10000 10.0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 9.2 10000 10000 10000 9.8 10.1 0 4.1 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.8 7.9 10000 10000 10000 10000 10000 10000 4.1 0 9.1 10000 10000 10000 10000 10000 10000 10000 7.9 10000 10000 10000 10000 10000 10000 10000 10.0 10000 9.1 0 8.9 10000 10000 10000 10000 10000 10000 13.2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 8.9 0 18.8 10000 10000 10000 7.8 7.9 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 18.8 0 ENDDATA n = @SIZE( city ); MIN = @SUM( link: w * x ); @FOR( city(k): @SUM( city(i) | i #ne# k : x(i,k) ) = 1; @SUM( city(j) | j #ne# k : x(k,j) ) = 1; ); @FOR( link(i,j) | i #gt# 1 #and# j #gt# 1 #and# i #ne# j: u(i) - u(j) + n * x(i,j) <= n - 1 ); @FOR( link: @BIN(x) ); 第二組路徑的程序 SETS: city/1, 3, 4, 5, 6, 10, 11, 12, 13, 14, 22, 23, 48, 49, 50, 51, 52, 53/:u; link(city, city):w, x; ENDSETS DATA: !w = @FILE('C:\Users\Administrator\Desktop\data51.txt'); w = 0 12.9 6 11.5 9.2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 12.9 0 10000 10000 10000 7.9 9.2 8.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 6 10000 0 11.2 10000 10000 10000 10.3 5.9 10000 10000 10000 10000 10000 10000 10000 10000 10000 11.5 10000 11.2 0 10000 10000 10000 10000 11 7.9 10000 10000 10000 10000 10000 10000 10000 10000 9.2 10000 10000 10000 0 10000 10000 10000 10000 4.8 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.9 10000 10000 10000 0 10000 10000 10000 10000 10000 10000 7.2 10000 10000 10000 10000 10000 10000 9.2 10000 10000 10000 10000 0 10000 10000 10000 10000 10000 10000 10000 8.1 7.3 10000 10000 10000 8.8 10.3 10000 10000 10000 10000 0 10000 10000 10000 10000 10000 10000 10000 7.4 10000 11.5 10000 10000 5.9 11 10000 10000 10000 10000 0 10000 10000 10000 10000 10000 10000 10000 10000 17.6 10000 10000 10000 7.9 4.8 10000 10000 10000 10000 0 8.2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 8.2 0 12.7 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 12.7 0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.2 10000 10000 10000 10000 10000 10000 0 7.7 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7.7 0 10.3 10000 10000 10000 10000 10000 10000 10000 10000 10000 8.1 10000 10000 10000 10000 10000 10000 10.3 0 19 14.9 10000 10000 10000 10000 10000 10000 10000 7.3 7.4 10000 10000 10000 10000 10000 10000 19 0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 14.9 10000 0 8.2 10000 10000 10000 10000 10000 10000 10000 11.5 17.6 10000 10000 10000 10000 10000 10000 10000 8.2 0; ENDDATA n = @SIZE( city ); MIN = @SUM( link: w * x ); @FOR( city(k): @SUM( city(i) | i #ne# k : x(i,k) ) = 1; @SUM( city(j) | j #ne# k : x(k,j) ) = 1; ); @FOR( link(i,j) | i #gt# 1 #and# j #gt# 1 #and# i #ne# j: u(i) - u(j) + n * x(i,j) <= n - 1 ); 第三組路徑的程序 SETS: city/1, 6, 15, 19, 20, 21, 24, 25, 26, 27, 28,29, 30,31, 32, 33, 34, 35,36/:u; link(city, city):w, x; ENDSETS DATA: !w = @FILE('C:\Users\Administrator\Desktop\data51.txt'); w = 0 9.2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 9.2 0 8.3 1000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 8.3 0 10000 9.7 1000 11.3 10000 10000 10000 10000 10000 10000 10000 100