哈密頓災情巡視模型

1、數(shù)學建模課 程 論 文學生 潘在裕 成績 災情巡視路線模型摘要本題所研究的分組巡視的最佳路線與多個旅行推銷員的問題相似，但也有不同，因為此題還有均衡性要求。這是一類圖上的點的遍歷性問題，即用若干條閉鏈覆蓋圖上所有的頂點，并使某些指標達到最優(yōu)。首先，將鄉(xiāng)村公路示意圖轉(zhuǎn)化為賦權連通圖，并通過最小生成樹法將原權圖劃分為若干個子圖，然后，利用Hamilon圈法分別求出各個子圖的最佳巡視路線。最后，利用本文中自定義的均衡度公式：，來衡量分組的均衡性，如果均衡度越小，那么分組的均衡性就越好，據(jù)此來判斷分組是否滿足題意。而題中，在基于最小生成樹法將原權圖劃分為若干個子圖的劃分情況下，就必然使得總巡視路程相對

2、較短，而均衡度不夠令人滿意，此時根據(jù)實際需要，若要使總巡視路程優(yōu)先，達到相對較短，則采用原劃分的子圖分組；若要使均衡度優(yōu)先，達到滿意要求，則我們可以對各分組部分邊界點進行重劃分調(diào)整。針對問題一，我們分別采用直觀分析法和最小生成樹法求解并得到不同的結果。若分三組巡視，最小生成樹法求解各組的巡視路程分別為159.3km、242.2km、186.4km，總路程為587.9km，路程均衡度為34%。此結果下的總路程相對較短，而均衡度偏高。如果要優(yōu)先考慮均衡度，在最小生成樹法求解發(fā)改進的基礎上得到：194.0km、205.3km、206.8km，總路程為606.1km，路程均衡度為6.2%。針對問題二，

3、基于計算可以發(fā)現(xiàn)至少分4組，并求出了各組的最佳巡視路線。各組巡視的路程和時間分別為125.5km19.6h、154.3km22.4h、203.9km23.8h、158.8km21.5h，時間均衡度為18%。針對問題三，我們選取了巡視離縣城最遠的鄉(xiāng)鎮(zhèn)（點H）所需的時間6.4小時作為最短巡視時間，當巡視比較偏僻的鄉(xiāng)村時，汽車從縣鎮(zhèn)府出發(fā)直至到達終點，中途不會停留，僅在終點站停留T（或t）小時，然后按原路返回，到達沿途各站接回巡視人員?；谧疃萄惨晻r間和制定的分組原則得到巡視人員至少需分成7組。針對問題四，實際上是一個變量討論問題。在分析鄉(xiāng)（鎮(zhèn)）停留時間T，村莊停留時間t和汽車行駛速度v的改變對最佳

4、巡視路線的影響時，我們通過控制不同變量的變化，初步的得出了當T與t變化時和v變化時對最佳巡視路線的影響。最后，我們對模型進行了評價和推廣，使其更具有實用價值?！娟P鍵詞】： 均衡度 最小生成樹 Hamilon圈 最佳巡視路線一、問題重述下圖為某縣的鄉(xiāng)（鎮(zhèn)）、村公路網(wǎng)示意圖，公路邊的數(shù)字為該路段的公里數(shù)。今年夏天該縣遭受水災。為考察災情、組織自救，縣領導決定，帶領有關部門負責人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線。問題一：若分三組（路）巡視，試設計總路程最短且各組盡可能均衡的巡視路線。 問題二：假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2小

5、時，在各村停留時間t=1小時，汽車行駛速度v=35公里/小時。要在24小時內(nèi)完成巡視，至少應分幾組；給出這種分組下你認為最佳的巡視路線。 問題三：在上述關于T , t和v的假定下，如果巡視人員足夠多，完成巡視的最短時間是多少；給出在這種最短時間完成巡視的要求下，你認為最佳的巡視路線。 問題四：若巡視組數(shù)已定(如三組），要求盡快完成巡視，討論T，t和v改變對最佳巡視路線的影響。二、問題分析本題給出了某縣的道路交通網(wǎng)絡圖，要求的是在不同條件下，災情巡視的最佳分組方案和路線。這是一類圖上的點的遍歷性問題，也就是要用若干條閉鏈覆蓋圖上所有的頂點，并使某些指標達到最優(yōu)。點的遍歷性問題在圖論中屬于哈密頓問

6、題和旅行推銷員問題類似。如果巡視人員只分一組，巡視路線是指巡視人員從縣政府O出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村最后油回到縣鎮(zhèn)府。我們可以把該題抽象為圖論的賦權連通問題，即有一賦權無向連通圖，且。兩村之間的公路長度即為無向圖的邊權。尋找最佳巡視路線，即在圖中找到一條包含O點的回路，它至少經(jīng)過所有的頂點一次且使得總路程（總時間）最短。如果將巡視人員分成若干組，每組考察部分區(qū)域且所有鄉(xiāng)（鎮(zhèn)）、村都考察到，實際上就是將圖分為若干個連通的子圖，然后在每個子圖中尋找到一條含O點的最佳回路。完成巡視的時間應是各組巡視中最長的時間，要想提高巡視的效率則應盡量使各組的巡視時間接近，反映在圖分塊時應盡量均衡。三、模型假設1

7、、公路不考慮等級差別，也不受災情或交通情況的影響；2、各條公路段上汽車行駛的速度可以認為是均勻的；3、巡視人員在各鄉(xiāng)（鎮(zhèn)）、村停留的時間一定，不會出現(xiàn)特殊情況而延誤時間；4、各巡視組巡視的鄉(xiāng)（鎮(zhèn)）、村不受行政區(qū)劃的影響，即某鄉(xiāng)（鎮(zhèn)）與隸屬于它的村不一定要分在同一組內(nèi)5、忽略不計巡視人員上、下車所用的時間；6、當巡視比較偏僻的鄉(xiāng)村時，汽車從縣鎮(zhèn)府出發(fā)直至到達終點，中途不會停留，僅在終點站停留T（或t）小時，然后按原路返回，到達沿途各站接回巡視人員。四、符號約定: 巡視人員的分組數(shù);：賦權連通圖；：賦權連通圖的第個子圖;：子圖中的最佳回路；：最佳回路的各邊權之和；：最佳回路的巡視時間;：第個鄉(xiāng)、村

8、到第個鄉(xiāng)、村的距離；：巡視員在各鄉(xiāng)（鎮(zhèn)）的停留時間；：巡視人員在各村停留的時間；：汽車行駛的速度，單位公里小時。五、模型建立及模型求解5.1問題一模型的建立及求解：5.1.1模型一的建立與求解（直觀分析法）：根據(jù)題中所給的鄉(xiāng)（鎮(zhèn)）、村示意圖對地理位置進行粗略的劃組分析。很顯然，由于縣政府位置偏向東面，則若分成三組巡視，縣城遠離的一邊分為兩塊的可能性比鄰近縣城的一邊大得多，這樣就可以得到手工給出的三組巡視路線圖見表1： 表1編號路線路線長度/公里路線總長度/公里O-1-B-34-35-32-30-Q-28-27-26-P-29-R-31-33-A-1-O168.4O-M-25-N-24-23-2

9、1-K-22-17-16-I-15-I-18-J-19-20-L-6-5-2-O207.2 594.3 O-2-3-D-7-E-11-G-13-14-H-12-F-10-F-9-E-8-4-D-3-C-O218.7為了衡量分組的合理性，于是我們定義分組的路程均衡度公式 ：；顯然，值越小，說明分組的均衡性越好。由此我們可以得到采用直觀分析法時的均衡度。5.1.2模型二的建立與求解（基于最小生成樹法）現(xiàn)要分三組巡視，則需要把圖分成三個子圖，在每個子圖中尋找最佳回路。因為最小生成樹中能包含圖中所有的頂點，而且最小樹的邊權是相鄰兩頂點間的距離，它描述了頂點之間的相近程度，故可以采用最小生成樹進行分組。

10、本模型的主要思想是：首先采用Prim算法得到圖的最小生成樹，然后基于最小生成樹生成一個可行的巡視路線，求得路線的最優(yōu)總路程為。采用Prim算法求解最小生成樹步驟如下：（1）輸入加權連通圖的帶權鄰接矩陣；（2）建立初始候選邊表；（3）在候選邊表中選出最短邊；（4）調(diào)整候選邊表；（5）重復（2），（3），直到含有條邊。根據(jù)Prim算法進行編程求解（具體程序見附錄1），于是我們得到圖的最小生成樹如圖1。圖1現(xiàn)對已得到的最小生成樹進行分解，以獲得三個子圖并使得分解結果盡量均衡。由于在最小生成樹上，邊權接近可以近似認為均衡即各子圖包含的頂點數(shù)應接近。因此，各個子圖的頂點數(shù)應盡量接近17個，且遵循以下分解

11、原則。最小生成樹分解原則：(i)分解點為O點或盡可能地接近O點；（ii）分解所得的三個子圖的頂點數(shù)盡可能地接近17個；（iii）盡量是分解所得的子圖是連通圖；（iv）盡量使子圖與點O的最短路上的點在該子圖內(nèi)，且盡量使各子圖的點在子圖內(nèi)部形成環(huán)路。依據(jù)以上分解原則得到的分解結果如圖2。 圖2然后，采用哈密頓回路法求解每個子圖內(nèi)的最佳巡視路線。尋找最佳巡視路線實際上就是在賦權圖中尋找最優(yōu)的哈密頓圈，包含圖的每個頂點的圈陳為哈密頓圈。于是問題就可以轉(zhuǎn)化為：現(xiàn)已知三個子圖內(nèi)鄉(xiāng)、村與鄉(xiāng)、村之間的距離，從縣鎮(zhèn)府O出發(fā)，經(jīng)過子圖內(nèi)的所有鄉(xiāng)、村，最后又回到點O。現(xiàn)在討論如何將尋找最佳巡視路線問題表述成整數(shù)規(guī)劃

12、問題。但是，對于規(guī)模較大的尋找最佳巡視路線問題，這里的表述會顯得笨拙且效率低下。決策變量定義為:;其線性（整數(shù)）規(guī)劃模型目標函數(shù)為：。目標函數(shù)給出了哈密頓圈的總長度，并使其最小。約束式保證只能到達每個城市一次，約束式保證只能離開一個城市一次，約束式( 為自定義變量)是表述問題的關鍵，它確保：（1）由解得到的任何圈一定包含城市1（即縣鎮(zhèn)府點O）；（2）包含全部城市的圈是可行的。于是，約束條件概括為：按照上述思想寫出相應的Lingo程序（程序見附錄2）求解得到三組巡視路線圖見表2：表2編號路線路線長度/公里路線總長度/公里O-P-26-27-28-30-Q-29-R-A-33-31-32-35-3

13、4-B-1-O159.3O-25-20-L-19-18-J-13-14-H-15-I-16-17-22-K-21-23-24-N-M-O242.2 587.9 O-2-5-6-7-E-11-G-12-10-F-9-8-4-D-3-C-O186.4由此我們可以得到采用最小生成樹法時的路程均衡度。從上述圖表中不難看出，第二組走的路程過長而第一組走的路程過短，兩者之間的差值較大，也就是說這樣分組的均衡性較差。因此，我們需在基于最小生成樹的原則之上對原來的分組進行適當?shù)恼{(diào)整。為了縮小第一、二組間的路程差，首先，我們將第二組的28點和N點分到第一組；然后，再采用Hamilton圈法分別求解三個子圖內(nèi)的最

14、佳回路；最后，采用Lingo編程求解得到初步改進后三組巡視路線圖見表3。表3編號路線路線長度/公里路線總長度/公里O-P -26-N -24-27-28-Q-30-29-R-A-33-31-32-35-34-B-1-O194.0O-23-21-K-22-17-16-18-I-15-H-14-13-J-19-L- 20-25-M-O225.1 605.5 O-2-5-6-7-E-11-G-12-10-F-9-8-4-D-3-C-O186.4由此，可以計算出對模型二初步改進后的分組的均衡度為：。分析表3可知，第二組與第三組走的路程間的差值還是比較大，也就是說這樣分組的均衡性還有待改善。于是，我們在

15、基于最小生成樹的原則之上對初步改進后的分組進行適當?shù)恼{(diào)整。為了縮小第二、三組間的路程差，首先，我們將第二組的H點分到第三組；然后采用上述中同樣的方法求解得到最終改進后各組的巡視路線圖見表4。表4編號路線路線長度/公里路線總長度/公里O-P -26-N -24-27-28-Q-30-29-R-A-33-31-32-35-34-B-1-O194.0O-M-N-23-21-K-22-17-16-18-I-15-14-13-J-19-L- 20-25-M-O205.3 606.1 O-C-3-D-4-8-E-9-F-10-F-12-H-12-G-11-E-7-6-5-2-O206.8注：加有底紋的表示

16、只經(jīng)過此點但不停留。由此，可以計算出對模型二最終改進后的分組的均衡度為：。綜上所述，對比模型一和改進后模型二的結果可知，若分成三組巡視，雖然改進后模型二的巡視總路程比模型一的長，但是，改進后模型二分組的均衡性比模型一要好很多。此外，模型二的結果是經(jīng)過嚴謹科學的計算得到的，具有較高的可信度，相比之下，模型一的結果是人根據(jù)地理位置粗略劃分得到地，具有隨機性，可信度較低。經(jīng)上述分析可知，若分成三組巡視，則應該采用改進后模型二的巡視路線,見圖3。圖35.2問題二的模型建立及求解：此問添加了巡視組在各鄉(xiāng)（鎮(zhèn)）停留的時間小時，在各村停留的時間小時以及汽車的行駛速度公里小時的條件后，要求在24小時內(nèi)完成巡視

17、的最少分組數(shù)以及相應的最佳巡視路線。此時需訪問的鄉(xiāng)（鎮(zhèn)）共有17個，村共有35個，于是可以計算出巡視人員在鄉(xiāng)（鎮(zhèn)）及村停留的總時間為小時。此外，從問題一的結果中可知，巡視的總路程至少為500公里，則汽車行駛所需的時間和將超過14小時。由此可知，各組巡視所需的總時間之和超過83小時，要想在24小時內(nèi)完成巡視則應滿足： (i為分的組數(shù))。得i最小為4，故至少要分4組。 現(xiàn)在嘗試將頂點分成4組。分組的原則應建立在最小生成樹的分解原則之上，則分組應遵循以下原則：(i)分解點為O點或盡可能地接近O點；（ii）分解所得的4個子圖的頂點數(shù)盡可能地接近14個；（iii）盡量是分解所得的子圖是連通圖；（iv）盡

18、量使子圖與點O的最短路上的點在該子圖內(nèi)，且盡量使各子圖的點在子圖內(nèi)部形成環(huán)路；（v）盡量使各組的巡視時間相接近。采用上述原則將圖分為4個子圖，并運用哈密頓回路法找出各個組的最佳巡視路線。然后，計算出各組最佳巡視路線的總長度及汽車行駛所需時間，同時算出各組的停留時間,從而得到各組完成巡視的最佳時間?；诖?，可以采用Lingo軟件進行編程求解（程序見附錄3）得到4個組的巡視路線，并計算出各組巡視的總時間，具體數(shù)據(jù)見表3。表3（路程單位：公里；時間單位：小時）編號路線路線長度停留時間行駛時間總時間O-1-B-A-34-35-33-31-32-30-Q-29-R-O125.5163.619.6O-P-

19、28-27-26-N-24-23-22-17-16-17-K-21-25-M-O154.3184.422.4O-M-20-18-I-15-14-H-12-G-11-G-13-J-19-L-20-M-O203.9185.823.8O-2-5-6-7-E-9-F-10-F-9-E-8-4-D-3-C-O158.8174.521.5注：加有底紋的表示只經(jīng)過此點但不停留。從上述圖表中可以看出所分的四個組的巡視時間均小于24小時，符合題意。此外，計算得到該分組的時間均衡度公式為： ；此時，計算得到均衡度：。在此基礎上，我們可以得到有時間約束的最佳巡視路線如圖4。圖45.3問題三的模型建立及求解：此問題就

20、是要求如果有足夠多的巡視人員，怎樣確定最佳路線是完成巡視的時間最短。實際上，完成巡視的最短時間受到單獨巡視離縣城最遠的鄉(xiāng)（鎮(zhèn)）、村所需時間的制約，同時我們可以求出離縣城最遠的點是H點，距離為77.5公里。因此，單獨巡視返回該鄉(xiāng)所需的時間為小時。由此可知，即使巡視人員再多，分組再細，完成巡視至少需要6.4小時?；诖?，此題就可以轉(zhuǎn)化為求在6.4小時內(nèi)完成巡視的最少分組數(shù)和最佳巡視路線。為達到以上目標，我們制定了以下分組巡視原則：1、對圖中偏西且距縣政府較遠的鄉(xiāng)（鎮(zhèn)）、村：（1）在6.4小時內(nèi)，每組巡視人員盡可能走足夠多的鄉(xiāng)（鎮(zhèn)）、村。 （2）在巡視時，盡量按出發(fā)點到該次巡視終點最短路徑的路線巡視

21、，但在不超過6.4小時的原則下，為了能夠途經(jīng)更多的點，我們可以不走最短路線。（3）巡視車從縣政府出發(fā)，途中每到達一個鄉(xiāng)（鎮(zhèn)）、村，部分巡視人員下車巡視，車不停留（忽略不計巡視人員上、下車的時間）繼續(xù)開往下個站點，直到到達最遠點，車停下等待；然后按原路返回，依次到達每點接回巡視人員，直至出發(fā)點。2、由于第一種分組原則下，在最遠點必須要花1或者2個小時的停留時間，針對這一浪費時間的缺點，對圖中偏東且距縣政府較近的鄉(xiāng)、村，我們改進一種按圈巡視的方法，原則如下：（1）每組巡視人員巡視路線構成一個圈，且巡視兩圈。（2）第一圈巡視時，途中每到達一個鄉(xiāng)（鎮(zhèn)）、村，部分巡視人員下車巡視，車不停留（忽略不計巡視

22、人員上、下車的時間）繼續(xù)開往下個站點，直至出發(fā)點，仍不停留繼續(xù)第二圈巡視，到達每點依次接回巡視人員，直至回到出發(fā)點，結束。（3）在遵循不超過6.4小時原則下，按圈巡視時，總路線不能過長，不超過112公里；總路線也不能過短，避免車停留等待而浪費時間。依據(jù)以上原則，我們在6.4小時內(nèi)完成巡視，總共分成了7組，前5組遵循的第一種分組原則，后2組依據(jù)的第二種按圈分組原則。具體的分組巡視路線和所需時間見表4。表4（時間單位：小時）編號路線總時間O-2-5-6-7-E-9-F-12-H-14-H-12-F-9-E-7-6-5-2-O6.43O-M-25-20-21-K-18-I-15-I-18-K-21-

23、20-25-M-O5.87O-2-5-6-L-19-J-13-G-11-G-13-J-19-L-6-5-2-O6.15O-2-3-D-4-8-E-9-F-10-F-9-E-8-4-D-3-2-O6.38O-P-28-27-26-N-24-23-22-17-16-17-22-23-24-N-26-27-28-P-O6.37O-R-31-33-A-1-C-O-R-31-33-A-1-C-O4O-R-29-Q-30-32-35-34-B-1-O-O-R-29-Q-30-32-35-34-B-1-O5.64注：加有底紋的表示經(jīng)過此點但無巡視人員上、下車。由此可以計算出此種分組下的時間均衡度為：?；诖?/p>

24、，我們可以得到巡視人員足夠多的情況下分成7組的最佳巡視路線如圖5。圖55.4問題四的模型建立及求解：第四問要求在巡視組數(shù)已定的情況下盡快完成巡視，討論參數(shù)T，t和v的改變對最佳巡視路線的影響。前面我們已經(jīng)提到，要盡快完成巡視，即要求各組巡視時間的最大值也要最小。用數(shù)學式子表達為：；其中：是給定的分組數(shù)；：分別是第組停留的鄉(xiāng)(鎮(zhèn))數(shù)和村數(shù)；：第組巡視路線的總長度。在上述表達式中，由于T和t的作用完全相仿，所以為簡化討論起見，對于任意給定的T和t，不妨記。即這里可簡記為：；它是t和的的線性函數(shù)，將隨著t和增大(即v的減小)而增大.于是我們?nèi)菀椎玫揭韵陆Y論：（1）若t（T）增大而V不變，為了使最大值

25、盡可能小，就要求的最大值盡可能小.但是當T和t的關系確定后，實際上就是定值，其中m是全縣的鄉(xiāng)(鎮(zhèn))數(shù)17，n是全縣的村數(shù)35。上述要求就成為各組停留在詢問鄉(xiāng)村的總時間盡可能均勻.用數(shù)學式子表示即為:；這里表示數(shù)的下整數(shù)和上整數(shù).當然，在調(diào)整各組停留的鄉(xiāng)村數(shù)使之達到均衡時，自然會給各組的路線及其長度帶來影響.這時應當考慮進行適當調(diào)整。（2）若t（T）不變而v增大.這種情況下，今起主導作用。那么，和（1）中的結論類似，我們更應使即各組的巡視路線盡可能均衡。誠然，因為不是常數(shù)，而且的均衡性會帶來的增大，這對于盡快完成巡視會帶來負面影響。所以對具體情況應作具體分析，比如可以考慮的前半部份對均衡性的修正

26、，對路程較長的組盡量考慮停留較少鄉(xiāng)村。六、模型的推廣在現(xiàn)實生活和生產(chǎn)中，有許多管理、組織與計劃中的優(yōu)化問題，如企業(yè)管理中，如何制訂管理計劃或設備購置計劃，使收益最大或費用最小；在生產(chǎn)管理中，如何使各工序銜接好，才能使生產(chǎn)任務完成的既快又好；在交通管理中，如何利用現(xiàn)有的交通網(wǎng)絡，使調(diào)用的物資數(shù)量多且費用最小等。這類問題都可以借助圖論知識得以解決。網(wǎng)絡模型就是一種應用圖論的理論與方法解決具有網(wǎng)絡性質(zhì)的管理決策問題的數(shù)學模型。由于它具有圖形直觀、方法簡便、容易掌握等特點，因此，近年來得到迅速發(fā)展，且廣泛地應用在各個領域，尤其是經(jīng)濟活動中許多管理決策的優(yōu)化問題?；镜木W(wǎng)絡優(yōu)化問題有：最短路徑問題、最小

27、支撐樹問題、最大流問題和最小費用問題。在圖論這個數(shù)學分支中已經(jīng)有有效的算法來解決這些問題，當然這當中有很多問題都可以建立線性規(guī)劃的模型，但有時若變量特別多、約束也特別多，用線性規(guī)劃的方法求解效率不高甚至不能在忍受的時間內(nèi)解決。根據(jù)這些問題的特點，采用網(wǎng)絡分析的方法去求解可能會非常有效。七、模型的評價優(yōu)點：本文多處使用圖表，增強了文章的可讀性，使建模思想更加清晰易懂。在問題三的求解中，我們假定當巡視比較偏僻的鄉(xiāng)村時，汽車從縣鎮(zhèn)府出發(fā)直至到達終點，中途不會停留，僅在終點站停留T（或t）小時，然后按原路返回，到達沿途各站接回巡視人員，這樣考慮可以避免車停留等待而浪費時間，提高巡視效率。缺點：采用最小

28、生成樹求解最小回路，并采用Hmilton圈法求解各子圖內(nèi)的最佳回路，雖然分組的均衡度比較理想，但求的不是全局最優(yōu)解。當頂點數(shù)目比較多（大于等于20）時，采用Lingo軟件針對Hailton圈法編程時，程序執(zhí)行的速度較慢，效率不高。(3) 本文僅僅是針對具體問題具體分析，有一定的局限性；雖然也是采用圖論法解決，但與圖論中的經(jīng)典旅行推銷員模型有所區(qū)別，在實際應用中，應對各種情況作進一步分析不斷對模型加以優(yōu)化，才會使其更具適用性。八、參考文獻及附錄【1】數(shù)學建模原理與方法，蔡鎖章，海洋出版社，2000.6【2】運籌學與實驗，薛毅，耿美英，電子工業(yè)出版社，2008.9【3】數(shù)學的實踐與認識（第29卷第

29、1期），田家國等，1999.1附錄1：D=xlsread('shuju.xls')n=53;T=;l=0;%l記錄T的列數(shù)q(1)=-1;for i=2:n p(i)=1;q(i)=D(i,1);endk=1;while 1 if k>=n disp(T); break; else min=inf; for i=2:n if q(i)>0&q(i)<min min=q(i); h=i; end end end l=l+1; T(1,l)=h;T(2,l)=p(h); q(h)=-1; for j=2:n if D(h,j)<q(j) q(j)=D

30、(h,j); p(j)=h; end end k=k+1;end附錄2：sets:c/1.17/:u;link(c,c):w,x;endsetsdata:w=ole('第一組數(shù)據(jù).xls','dier');enddatan=size(c);min=sum(link:w*x);for(c(k):sum(c(i)|i#ne#k:x(i,k)=1;sum(c(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:b

31、in(x);endsets:c/1.17/:u;link(c,c):w,x;endsetsdata:w=ole('第二組數(shù)據(jù).xls','dier');enddatan=size(c);min=sum(link:w*x);for(c(k):sum(c(i)|i#ne#k:x(i,k)=1;sum(c(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);endsets:c/1.17/:u;link(c,c):w,x;endsetsdata:w=ole('第三組數(shù)據(jù).xls','dier');enddatan=size(c);min=sum(link:w*x);for(c(k):sum(c(i)|i#ne#k:x(i,k)=1;sum(c(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);end附錄3：sets:c/1.13/:u;link(c,c):w,x;en