數(shù)學(xué)建模優(yōu)秀論文-災(zāi)情巡視路線的數(shù)學(xué)模型.doc

災(zāi)情巡視路線的數(shù)學(xué)模型摘 要本文解決的是災(zāi)情巡視路線的設(shè)計(jì)問(wèn)題。由于路線圖可看成網(wǎng)絡(luò)圖因此此問(wèn)題可轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)出發(fā)行遍所有頂點(diǎn)至少一次再回到點(diǎn)使得總權(quán)（路程或時(shí)間）最小的問(wèn)題。然后針對(duì)具體問(wèn)題，采用一些啟發(fā)式算法，建立模型進(jìn)行求解。對(duì)于問(wèn)題一：基于設(shè)計(jì)分三組巡視時(shí)使總路程最短且各組盡可能均衡的巡視路線的要求我們采用Dijkstra算法，通過(guò)對(duì)初始圈進(jìn)行二邊逐次修正,處理三組的巡視路線長(zhǎng)度，用lingo軟件求解出較優(yōu)方案。定義分組的均衡度系數(shù)a檢驗(yàn)分組均衡度，在均衡度為a=0.0751時(shí)得到分三組（路）巡視時(shí)，總路程最短且各組盡可能均衡的巡視路線見(jiàn)附表1。對(duì)于問(wèn)題二：將問(wèn)題轉(zhuǎn)化為圖論問(wèn)題，運(yùn)用問(wèn)題一的求解方法，得到分為四組的路線，在通過(guò)均衡度分析之后得出近似最優(yōu)巡視路線。利用lingo軟件求得，至少要分四組，且四組的近似最優(yōu)巡視路線見(jiàn)附表2。對(duì)于問(wèn)題三：基于問(wèn)題一二中圖論的方法，考慮到從點(diǎn)巡視H點(diǎn)的最短時(shí)間是所有巡視線路中用時(shí)最長(zhǎng)的，將計(jì)算出的最長(zhǎng)路線巡視所用的時(shí)間作為巡視路線的最短時(shí)間限定，在此限定下對(duì)路線進(jìn)行設(shè)計(jì)。求得的最短時(shí)間為6.43小時(shí)，最佳巡視路線分為23組。（具體分組見(jiàn)附錄二）對(duì)于問(wèn)題四：由于組數(shù)一定， T，t和V改變，對(duì)每組內(nèi)的最佳巡視路線是沒(méi)有影響的，但可能會(huì)影響到各組件的均衡性，因此問(wèn)題實(shí)質(zhì)是討論T，t和V對(duì)分組的影響，即在不破壞原來(lái)分組均衡的條件下T，t和V允許的最大變化范圍。關(guān)鍵詞：?jiǎn)l(fā)式算法 Dijkstra算法 均衡度 圖論 二邊逐次修正1. 問(wèn)題重述1.1問(wèn)題背景今年夏天某縣遭受水災(zāi)。為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門(mén)負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線。附錄一中給出了該縣的鄉(xiāng)（鎮(zhèn)）、村公路網(wǎng)示意圖，公路邊的數(shù)字為該路段的公里數(shù)。1.2本文需解決的問(wèn)題問(wèn)題一：若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線。問(wèn)題二：假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t=1小時(shí)，汽車(chē)行駛速度V=35公里/小時(shí)。要在24小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下你認(rèn)為最佳的巡視路線。問(wèn)題三：在上述關(guān)于T , t和V的假定下，如果巡視人員足夠多，完成巡視的最短時(shí)間是多少；給出在這種最短時(shí)間完成巡視的要求下，你認(rèn)為最佳的巡視路線。問(wèn)題四：若巡視組數(shù)已定(如三組），要求盡快完成巡視，討論T，t和V改變對(duì)最佳巡視路線的影響。 2. 模型的假設(shè)與符號(hào)說(shuō)明2.1模型的假設(shè)假設(shè)1：公路不考慮等級(jí)差別，不受災(zāi)情和交通情況的影響。假設(shè)2：各條公路段上的汽車(chē)行駛速度均勻。假設(shè)3：各巡視組巡視的鄉(xiāng)（鎮(zhèn)）、村不受行政區(qū)劃分的影響。假設(shè)4：各巡視組行動(dòng)統(tǒng)一，一個(gè)巡視組不可再分成若干小組。假設(shè)5：巡視當(dāng)中在每個(gè)鄉(xiāng)（鎮(zhèn)）村的停留時(shí)間一定，不會(huì)出現(xiàn)特殊情況而延誤時(shí)間。2.2符號(hào)說(shuō)明符號(hào)符號(hào)說(shuō)明巡視小組在鄉(xiāng)（鎮(zhèn)）巡視的停留時(shí)間巡視小組在村巡視的停留時(shí)間汽車(chē)行駛速度為導(dǎo)出子圖中的最佳圈。（其中=1，2，3，n.）為的權(quán)，（其中=1，2，3，n.）最大允許均衡度分組后的實(shí)際均衡度第個(gè)點(diǎn)距起始點(diǎn)的路線長(zhǎng)度點(diǎn)的時(shí)間權(quán)重分組數(shù)第組巡視時(shí)要停留的鄉(xiāng)（鎮(zhèn)）數(shù)第組巡視時(shí)要停留的村數(shù)最短時(shí)間下限第巡視路線的長(zhǎng)度第巡視所用的時(shí)間3. 問(wèn)題分析此題研究的是某縣災(zāi)情巡視路線的設(shè)計(jì)問(wèn)題。問(wèn)題要求設(shè)計(jì)出最佳的巡視路線，即：保證總路程最短或時(shí)間最小而且各組盡可能均衡的巡視路線?；趫D論相關(guān)理論，借助于幾何直觀和生活體驗(yàn)的啟發(fā)作用，便于為計(jì)算機(jī)搜索制定行之有效的操作規(guī)則，接著利用圖論軟件包通過(guò)計(jì)算機(jī)求解出較精確的路線。再通過(guò)線路均衡性比較，對(duì)均衡性不好的線路進(jìn)行微調(diào)。以此方法確定最佳巡視路線。針對(duì)問(wèn)題一：基于對(duì)問(wèn)題的分析，借助圖論知識(shí)，將所給公路網(wǎng)就轉(zhuǎn)化為圖論中的加權(quán)網(wǎng)絡(luò)圖，因此問(wèn)題就轉(zhuǎn)化為一個(gè)圖論問(wèn)題，即在給定的加權(quán)網(wǎng)絡(luò)圖中，尋找從給定點(diǎn)出發(fā)，行遍所有頂點(diǎn)至少一次再回到點(diǎn)，使得總權(quán)（路程或時(shí)間）最小。此即多個(gè)推銷(xiāo)員的最佳推銷(xiāo)員回路問(wèn)題。基于以上分析，運(yùn)用圖論知識(shí)和圖論軟件包進(jìn)行求解，再利用均衡度分析對(duì)得到的分組路線進(jìn)行微調(diào)，均衡度越小表示路線越均衡，微調(diào)后即可得到相對(duì)較優(yōu)的分組路線?？烧J(rèn)為這樣設(shè)計(jì)的分組方法和巡回路線能使總路線近似最短。針對(duì)問(wèn)題二：在問(wèn)題一的基礎(chǔ)上添加了巡視組在各鄉(xiāng)鎮(zhèn)停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t=1小時(shí)，汽車(chē)行駛速度V=35公里/小時(shí)等條件，要求在24小時(shí)內(nèi)完成巡視的最少分組數(shù)以及相應(yīng)的最佳巡視路線。首先，由圖中數(shù)據(jù)初步計(jì)算后判斷分成四組可行，再針對(duì)分組為四組的情況進(jìn)行線路設(shè)計(jì)，仍將問(wèn)題轉(zhuǎn)化為圖論問(wèn)題，運(yùn)用問(wèn)題一的求解方法，得到分為四組的路線，在通過(guò)均衡度分析之后得出近似最優(yōu)巡視路線。針對(duì)問(wèn)題三：在問(wèn)題二中關(guān)于T , t和V的假定下且巡視人員足夠多時(shí)，要求在最短時(shí)間完成巡視的要求下所得的最佳的巡視路線，此時(shí)考慮到從點(diǎn)巡視H點(diǎn)的最短時(shí)間是所有巡視線路中用時(shí)最長(zhǎng)的，將計(jì)算出的最長(zhǎng)路線巡視所用的時(shí)間作為巡視路線的最短時(shí)間限定，在此限定下對(duì)路線進(jìn)行設(shè)計(jì)。基于問(wèn)題一二中圖論的方法，從一些點(diǎn)的路線比較少的點(diǎn)開(kāi)始，能夠使搜素容易進(jìn)行，因此選擇從距離點(diǎn)一些較遠(yuǎn)的點(diǎn)（如12 10 15 22等點(diǎn)）開(kāi)始搜索，每次搜索時(shí)都要對(duì)該點(diǎn)的巡視時(shí)間進(jìn)行判斷，直到找到近似最優(yōu)路線。針對(duì)問(wèn)題四：在巡視組數(shù)已定(如三組）的情況下，為盡快完成巡視就要求每組完成的巡視時(shí)間盡量均衡，因?yàn)榭偟耐瓿裳惨晻r(shí)間按線路最長(zhǎng)的完成巡視時(shí)間計(jì)算，由于組數(shù)一定， T，t和V改變，對(duì)每組內(nèi)的最佳巡視路線是沒(méi)有影響的，但可能會(huì)影響到各組件的均衡性，因此問(wèn)題實(shí)質(zhì)是討論T，t和V對(duì)分組的影響，即在不破壞原來(lái)分組均衡的條件下T，t和V允許的最大變化范圍。需要用控制單一變量的方法，分別討論T、t、V三個(gè)量中任意兩個(gè)量不變時(shí)第三個(gè)量的變化范圍。從而確定T，t和V的改變對(duì)最佳巡視路線的影響。4. 數(shù)據(jù)分析4.1問(wèn)題一數(shù)據(jù)分析基于對(duì)該縣公路圖的初步分析，可以統(tǒng)計(jì)出該縣有鄉(xiāng)（鎮(zhèn)）17個(gè)，村35個(gè)。（線路圖見(jiàn)附錄一）應(yīng)用lingo軟件求解(具體程序見(jiàn)附錄三)得出巡視點(diǎn)距離縣政府所在地的最短距離，如表1所示：表1：點(diǎn)到其余各點(diǎn)的最短距離PR1C2M26O10.112.9611.59.219.820.6282931AB35O22.220.822.116.311.91417.5N2520L67DO31.131.838.33927.234.522.248E9F1012O34.949.741.749.555.165.967.311GH1314J19O55.962.777.564.172.754.346.218I15161722KO52.961.169.960.353.54943.721232427Q3032O39.63944.328.42835.730.2333534O23.73627.8由此表格畫(huà)出了最短路徑生成圖，如圖1圖 1由上圖便于在第一問(wèn)分析得到分組情況。4.2問(wèn)題二數(shù)據(jù)分析問(wèn)題二中給出了巡視小組在鄉(xiāng)（鎮(zhèn)）村的停留時(shí)間和汽車(chē)行駛速度，分別為：巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t=1小時(shí)，汽車(chē)行駛速度V=35公里/小時(shí)。對(duì)于要在24小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組的問(wèn)題，應(yīng)首先求出最長(zhǎng)路線巡視所用的時(shí)間，用停留總時(shí)間加上行走時(shí)間除以4的結(jié)果與24進(jìn)行比較，以此判斷最少分組能否為4組。計(jì)算如下：(17*2+35+599.8/35)/4=21.524(小時(shí))（其中路線長(zhǎng)度估算為599.8公里）因此最少分組可定為4組。 5 問(wèn)題一的解答本文研究的是災(zāi)情巡視路線的最優(yōu)設(shè)計(jì)問(wèn)題，由于路線圖可看成網(wǎng)絡(luò)圖，因此此問(wèn)題可轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找線路使總權(quán)（路程或時(shí)間）最小的問(wèn)題。然后針對(duì)具體問(wèn)題，采用一些啟發(fā)式算法，建立模型。5.1模型一的建立5.1.1模型一的準(zhǔn)備經(jīng)對(duì)問(wèn)題的初步分析，基于圖論的相關(guān)知識(shí)，將公路網(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)化為一個(gè)圖論問(wèn)題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從定點(diǎn)出發(fā)，行遍所有頂點(diǎn)至少一次再回到點(diǎn)，使得總權(quán)（路程或時(shí)間）最小。定義經(jīng)過(guò)圖的每個(gè)頂點(diǎn)正好一次的圈，稱(chēng)為的哈密爾頓圈，簡(jiǎn)稱(chēng)圈。定義 在加權(quán)圖中（）權(quán)最小的哈密爾頓圈稱(chēng)為圈：（）經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次且權(quán)最小的閉通路稱(chēng)為最佳推銷(xiāo)員回路。由定義（2）可知本問(wèn)題是一個(gè)尋求最佳推銷(xiāo)員回路的問(wèn)題，最佳推銷(xiāo)員回路的問(wèn)題可以轉(zhuǎn)化為最佳圈的問(wèn)題，方法是由給定的圖（，）構(gòu)造一個(gè)以為頂點(diǎn)集的完備圖=（，）中每條邊（x y）權(quán)等于頂點(diǎn)x與y在圖中最短路徑的權(quán)，即。在圖論中有以下定理：定理 加權(quán)圖的最佳推銷(xiāo)員回路的權(quán)和的最佳圈的權(quán)相同。定理2 在加權(quán)完備圖中求最佳圈的問(wèn)題是NP完全問(wèn)題。我們采用一種近似算法求出該問(wèn)題的一個(gè)近似最優(yōu)解，來(lái)代替最優(yōu)解，算法如下：算法一 求加權(quán)圖（，）的最佳推銷(xiāo)員回路的近似算法：用圖論軟件包求出中任意兩個(gè)頂點(diǎn)間的最短路，構(gòu)造出完備圖（，）輸入圖的一個(gè)初始圈；用對(duì)角線完全算法2產(chǎn)生一個(gè)初始圈；隨機(jī)搜索出中若干個(gè)圈，例如3000個(gè)；對(duì)步所得的每個(gè)圈用二邊逐次修正法2進(jìn)行優(yōu)化，得到近似最佳圈；在第步求出的所有圈中，找出權(quán)最小的一個(gè)，此即要找的最佳圈的近似解。（算法程序見(jiàn)附錄）由于二邊主次修正法的結(jié)果與初始圈有關(guān)故本算法第步分別用三種方法，產(chǎn)生初始圈，以保證能得到較優(yōu)的計(jì)算結(jié)果。在此問(wèn)題是多個(gè)推銷(xiāo)員的最佳推銷(xiāo)員回路問(wèn)題，即在加權(quán)圖中求頂點(diǎn)集的劃分1，將G分成n 個(gè)生成子圖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 稱(chēng)為該分組的實(shí)際路線均衡度，為最大允許均衡度，顯然01，越小說(shuō)明分組的均衡性越好，取定一個(gè)后，與滿(mǎn)足條件3的分組，條件4表示總巡視路程最短。此問(wèn)題包含兩個(gè)方面：第一，對(duì)點(diǎn)分組；第二，在每組中尋求最佳推銷(xiāo)員回路，即為單個(gè)推銷(xiāo)員的最佳推銷(xiāo)員問(wèn)題，我們只能去尋求一種較合理的劃分準(zhǔn)則，對(duì)圖進(jìn)行初步劃分后，求出各部分的最佳推銷(xiāo)員回路的權(quán)，在進(jìn)一步進(jìn)行調(diào)整，使得各部分滿(mǎn)足均衡性條件3.從點(diǎn)出發(fā)去其它點(diǎn)，要使路程較小應(yīng)盡量走點(diǎn)到該點(diǎn)的最短路，故用圖論軟件包求出點(diǎn)到其余頂點(diǎn)的最短路，這些最短路構(gòu)成一棵以為樹(shù)根的樹(shù)，將從點(diǎn)出發(fā)的樹(shù)枝稱(chēng)干枝，如圖2：圖 2從圖中可以看出，從點(diǎn)出發(fā)到其它點(diǎn)共有6條干枝，他們的名稱(chēng)分別為，。根據(jù)實(shí)際工作的經(jīng)驗(yàn)及上述分析，在分組時(shí)應(yīng)遵循以下準(zhǔn)則：準(zhǔn)則一 盡量使同一干枝上及其分支上的點(diǎn)分在同一組；準(zhǔn)則二 應(yīng)將相鄰的干枝上的點(diǎn)分在同一組；準(zhǔn)則三 盡量將的干枝與短的干枝分在同一組。由上述分組原則，為我們找到兩組分組形式如下：分組一：（，），（，），（，）分組二：（，），（，），（，）顯然由圖中可以直接看出分組一的方法極不均衡，故考慮分組二。對(duì)分組二中每組頂點(diǎn)的生成子圖，用算法一求出近似最優(yōu)解及相應(yīng)的巡視路線，使用算法一時(shí)在每個(gè)子圖所構(gòu)造的完備圖中，取一個(gè)盡量包含圖1中樹(shù)上的邊的圈作為其第二步輸入的初始圈。依次求解得到巡視路線的近似最優(yōu)解。5.1.1綜上所述，問(wèn)題一的優(yōu)化模型為：5.2問(wèn)題一的解答。在本模型的基礎(chǔ)上，運(yùn)用lingo軟件求解出分三組巡視時(shí)近似最優(yōu)的巡視路線（具體程序見(jiàn)附錄三），如表2：表2：分三組巡視的近似最優(yōu)路線圖組號(hào)路 線路線長(zhǎng)度路線總長(zhǎng)度IOP282726N2423221716I15I18K212025MO191589.8IIOR29Q303231333534A1BC3D4D32O192.3IIIO256L19J11G1314H12F10F9E8E7652O206.55.3問(wèn)題一的結(jié)果分析由以上分三組所得的路線結(jié)果可以看出，第一組的巡視路線為：282726N2423221716I1518K212025MO 第二組巡視路線為：R29Q303231333534A1BC3D4D32O第三組巡視路線為：256L19J11G1314H12F10F9E8E7652O將以上巡視線路的巡視距離進(jìn)行均衡度分析：=7.46%=0.0746當(dāng)規(guī)定距離均衡度=0.1時(shí)，此三組的巡視路線的設(shè)計(jì)均符合要求。而且實(shí)際均衡度比0.1小得多，可見(jiàn)路線設(shè)計(jì)很合理。6. 問(wèn)題二的解答6.1模型二的建立6.1.1確定目標(biāo)函數(shù)由于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í)間為：17*2+35=69（小時(shí)）需要在24小時(shí)內(nèi)完成巡視，考慮行走時(shí)間有： (17*2+35+599.8/35)/4=21.524(小時(shí))（其中最長(zhǎng)路線長(zhǎng)度估算為599.8公里）因此最少分組可定為4組。由于該網(wǎng)絡(luò)的鄉(xiāng)（鎮(zhèn)）、村分布較均勻，故有可能找處停留時(shí)間計(jì)量均衡的分組，當(dāng)分四組時(shí)各組停留時(shí)間大約為：69/4=17.25（小時(shí)）則每組分配在路途的時(shí)間大約為：2417.25=6.75（小時(shí)）問(wèn)題分析時(shí)有分三組路線時(shí)，巡視總路線最長(zhǎng)的是599.8公里，分四組時(shí)的總路程更不會(huì)比599.8公里大太多，不妨以599.8公里來(lái)計(jì)算，路途時(shí)間約為：（599.8/35)/4=4.25（小時(shí)）由于4.250時(shí)，要保持原均衡分組不變，T必須滿(mǎn)足的條件為：2.當(dāng)Yi-Yj0時(shí)，要保持原均衡分組不變，t必須滿(mǎn)足的條件為：3.當(dāng)Si-Sj0時(shí)，有（1）當(dāng)時(shí)，有（2）當(dāng)時(shí)，有由1.2.3.中的式子知，當(dāng)T 、t、V三個(gè)變量中任意兩個(gè)變量無(wú)論如何變化，都可計(jì)算出為保持均衡分組不變，三個(gè)變量所允許的最大變化范圍。（二）分三組的實(shí)例討論?，F(xiàn)對(duì)分三組的情況進(jìn)行實(shí)際討論。對(duì)問(wèn)題一中所得的三個(gè)分組，若考慮停留時(shí)間和行駛時(shí)間，且取T=T0=2小時(shí)，t=t0=1小時(shí)，V=V0=35公里/小時(shí)時(shí)，結(jié)果如下表4所示：表4：分三組巡視相關(guān)表編號(hào)XiYiSi行駛時(shí)間總時(shí)間I5131915.4628.46II611192.35.4928.49III612206.55.929.9由表可計(jì)算時(shí)間的實(shí)際均衡度為：=4.8%=0.048實(shí)際時(shí)間誤差=0.048*29.9=1.44（小時(shí)）現(xiàn)分別規(guī)定均衡分組的最大允許均衡度為=4.8%和=9.6%,即最大允許的時(shí)間誤差分別為：1.44小時(shí)和2.88小時(shí)。計(jì)算出T , t和V中三個(gè)參量中任意兩個(gè)固定時(shí)，要不破壞原平衡分組，另一個(gè)參量所要允許的變化范圍。計(jì)算結(jié)果如下表5：表5：T ，t，V中三個(gè)參量的變化范圍T，V不變t，V不變T，t不變=4.8% =1.44=9.6% =2.88由上表可以看出：（1）當(dāng)實(shí)際均衡度=4.8%，剛好等于最大允許均衡度=4.8%時(shí)，要保持原均衡分組，當(dāng)：t，V不變時(shí)，T只能減小，且下界為1.25小時(shí)，上界為2小時(shí)。T，V不變時(shí)，t只能增大，且上界為1.38小時(shí)，下界為1小時(shí)。T，t不變時(shí)，V只能增大，且無(wú)上界，V的下界為35公里/小時(shí)。（2）當(dāng)實(shí)際均衡度=4.8%，小于最大允許均衡度=9.6%時(shí)，要保持原均衡分組，當(dāng)：t，V不變時(shí)，T的變化上界為0.51小時(shí)，下界為2.74小時(shí)。T，V不變時(shí)，t的變化上界為0.63小時(shí)，下界為1.75小時(shí)。T，t不變時(shí)，V無(wú)上界，V的下界為17.3公里/小時(shí)。9. 模型的評(píng)價(jià)、改進(jìn)及推廣9.1模型評(píng)價(jià)優(yōu)點(diǎn)：（1）本文提出的分組準(zhǔn)則簡(jiǎn)便易行，可操作性強(qiáng)，且可逐步調(diào)整使分組達(dá)到均衡。（2）引用均衡度的概念定量的刻畫(huà)了分組的均衡性。（3）再用近似法求解最佳推銷(xiāo)員回路時(shí)采用了三種不同的方法產(chǎn)生初始圈，使得算法比較完善，得到了誤差很小的而近似最優(yōu)解。（4）從理論上定量的討論了T，t和V的變化對(duì)均衡分組靈敏度的影響，得到了很好的結(jié)果。缺點(diǎn)：使用的方法不能求得最優(yōu)解，只能求得近似最優(yōu)解。9.2模型改進(jìn)（1）求解時(shí)可建立將多組路線轉(zhuǎn)化為一組路線來(lái)求解的思想，如果能夠找出一種準(zhǔn)則，使三個(gè)代表縣城點(diǎn)之間的距離盡量大，則在最好的情況下，將使兩個(gè)縣城點(diǎn)均分整個(gè)一條路線，這種改進(jìn)將簡(jiǎn)化問(wèn)題的求解，并可以得到較好的解。（2）由于線路的設(shè)計(jì)是在假設(shè)條件下取得的近似最優(yōu)解，因此，需要減少假設(shè)更多的考慮實(shí)際情況下的最優(yōu)路線的設(shè)計(jì)。9.3模型推廣本文建立的模型可以廣泛它應(yīng)用于實(shí)際生活中涉及到圖論的有關(guān)問(wèn)題，例如公交線路的而選擇問(wèn)題，城市相關(guān)設(shè)施的布置等相關(guān)問(wèn)題。參考文獻(xiàn)1 運(yùn)籌學(xué)與實(shí)驗(yàn)/薛毅，耿美英編著。北京：電子工業(yè)出版社，2008.9 2 運(yùn)籌學(xué)教材編寫(xiě)組編，運(yùn)籌學(xué)（3版），北京：清華大學(xué)出版社，2005.63 圖論算法及其MATLAB實(shí)現(xiàn)/王海英等編著. 北京：北京航空航天大學(xué)出版社，2010.2附錄附錄一：縣政府線路圖附錄二：編號(hào)巡視路徑停留地所需時(shí)間時(shí)間差1O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-OH6.4302O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-O13,146.150.283O-2-5-6-7-E-9-F-10-F-9-E-7-6-5-2-O10,75.770.664O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O12,95.850.585O-M-25-21-K-18-I-15-I-18-K-21-25-M-O15,185.990.446O-2-5-6-7-E-11-G-11-E-7-6-5-2-OG5.580.557OM-25-K-18-I-18-K-25-M-0-OI5.490.948O-M-25-21-K-17-16-17-K-21-25-M-O16,175.450.989O-2-5-6-7-E-11-E-7-6-5-2-O11,E6.190.2410O-2-5-6-7-E-9-F-9-E-7-6-5-2-OF5.151.0811O-2-5-6-L-19-J-19-L-6-5-2-OJ,196.100.3312O-P-26-N-23-22-23-N-26-P-O22,23,265.800.6313O-2-5-6-7-E-8-E-7-6-5-2-O8,5,25.800.6314O-P-26-N-24-N-26-P-O24,N5.530.9015O-M-25-21-K-21-25-M-OK,215.500.9316O-2-5-6-L-6-5-2-OL,65.231.0217OM-25-20-25-M-O20,25,M6.190.2418O-R-31-32-35-34-A-1-O31,32,34,356.320.1119O-29-Q-30-29-R-O30,Q,296.040.3920O-2-3-D-4-D-3-2-O4,D,35.990.4421O-1-B-C-O1,B,C5.980.4522OP-26-27-28-P-O-27,P,26,286.380.0523O-1-A-33-A-R-OA,33,R6.410.02附錄三最短路徑算法% 求兩點(diǎn)間最短路的 Dijkstra 算法function d index1 index2 = Dijkf(a)% a 表示圖的權(quán)值矩陣; d 表示所求最短路的權(quán)和% index1 表示標(biāo)號(hào)頂點(diǎn)順序； index2 表示標(biāo)號(hà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), 同時(shí)記錄頂點(diǎn)順序和頂點(diǎn)索引while sum(pb) = 2 index = index(1); end index2(temp) = index;endd;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;ENDSETSDATA:!w = FILE(C:UsersAdministratorDesktopdata51.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 0ENDDATAn = 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;ENDSETSDATA:!w = FILE(C:UsersAdministratorDesktopdata51.txt);w = 012.9611.59.21000010000100001000010000100001000010000100001000010000100001000012.901000010000100007.99.28.810000100001000010000100001000010000100001000010000610000011.210000100001000010.35.910000100001000010000100001000010000100001000011.51000011.2010000100001000010000117.910000100001000010000100001000010000100009.21000010000100000100001000010000100004.81000010000100001000010000100001000010000100007.910000100001000001000010000100001000010000100007.21000010000100001000010000100009.2100001000010000100000100001000010000100001000010000100008.17.31000010000100008.810.3100001000010000100000100001000010000100001000010000100007.41000011.510000100005.911100001000010000100000100001000010000100001000010000100001000017.61000010000100007.94.81000010000100001000008.2100001000010000100001000010000100001000010000100001000010000100001000010000100008.2012.7100001000010