數(shù)學建模經(jīng)典問題——旅行商問題

《數(shù)學建模經(jīng)典問題——旅行商問題》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、1第7章旅行商問題2第7章旅行商問題1.問題概述2.求解算法2.1.下界和上界算法2.2.分支定界法目錄2.5.競賽題2.3.動態(tài)規(guī)劃法2.5.近似算法3§7-1問題概述一、數(shù)學模型1.標準TSP旅行商問題（簡稱TSP），也稱貨郎擔問題或旅行推銷員問題，是運籌學中一個著名的問題，其一般提法為：有一個旅行商從城市1出發(fā)，需要到城市2、3、…、n去推銷貨物，最后返回城市1，若任意兩個城市間的距離已知，則該旅行商應如何選擇其最佳行走路線？4TSP在圖論意義下又常常被稱為最小Hamilton圈問題，Euler等人最早研究了該問題的雛形，后來由英

2、國的Hamilton爵士作為一個懸賞問題而提出。但這個能讓普通人在幾分鐘內(nèi)就可理解的游戲之作，卻延續(xù)至今仍未能完全解決，成了一個世界難題。TSP有著明顯的實際意義，如，郵局里負責到各信箱開箱取信的郵遞員，以及去各分局送郵件的汽車等，都會遇到類似的問題。有趣的是，還有一些問題表面上看似乎與TSP無關，而實質(zhì)上卻可以歸結為TSP來求解。已經(jīng)證明，TSP是個NP難題，除非P=NP，否則不存在有效算法。5記為賦權圖G=(V,E)，V為頂點集，E為邊集，各頂點間的距離dij已知。設則經(jīng)典的TSP可寫為如下的數(shù)學規(guī)劃模型：6模型中，為集合中所含圖的

3、頂點數(shù)。約束（7－1）和（7－2）意味著對每個點而言，僅有一條邊進和一條邊出；約束（7－3）則保證了沒有任何子回路解的產(chǎn)生。于是，滿足約束（7－1）、（7－2）和（7－3）的解構成了一條Hamilton回路。7當dij=dji(i,j∈V)時，問題被稱為對稱型TSP，否則稱為非對稱型TSP。若對所有1≤i,j,k≤n，有不等式dij+djk≥dik成立，則問題被稱為是滿足三角形不等式的，簡稱為ΔTSP。82.擴展TSP(1)瓶頸TSP瓶頸問題是最早從TSP延伸出來的一種擴展型TSP，其含義與經(jīng)典的TSP類似，僅目標不同，要求巡回路線中經(jīng)

4、過的最長距離最短，即最小化瓶頸距離。該情形體現(xiàn)了那些并不追求總巡回路線最短，而只希望在巡回路線中每次從一個地點至另一個地點的單次行程盡可能短的實際應用問題的特征。9從嚴格的數(shù)學意義而言，瓶頸TSP（簡稱BTSP）并沒有降低問題的難度，也未能提供任何特殊的解決辦法。瓶頸TSP的數(shù)學模型與標準TSP類似，僅目標函數(shù)不同：由于目標函數(shù)為瓶頸值，故求得的最佳巡回路線與標準TSP的往往截然不同。10(2)最小比率TSP最小比率TSP（簡稱MRTSP）是從經(jīng)典TSP引申出來的另一個變形問題，假定從一個城市走到另一個城市可得到某種收益（記為），則MR

5、TSP的目標就是確定最佳行走路線，使得回路的總行程與總收益之比最小。這種優(yōu)化目標的思想類似于人們?nèi)粘Ｉ钪薪?jīng)常使用的費用效益比，與單純的總行程最短相比，往往更具實際意義。11假定收益的數(shù)學性質(zhì)與相同，則最小比率TSP的數(shù)學模型也與標準TSP類似，僅目標函數(shù)不同：毫無疑問，由于目標函數(shù)中的非線性因素，最小比率TSP的求解比之標準TSP顯得更為困難。12(3)多人TSP若標準TSP中，出發(fā)點有多個推銷員同時出發(fā)，各自行走不同的路線，使得所有的城市都至少被訪問過一次，然后返回出發(fā)點，要求所有推銷員的總行程最短，則問題就成為一個多人的旅行商問題

6、（簡記MTSP）。令決策變量則MTSP的數(shù)學模型為：13假定原問題為對稱型MTSP，V={v0,v1,…vn-1}，v0為名推銷員出發(fā)點，記V‘={v01,v02,…v0m;v0,v1,…vn-1}，擴大的m-1個頂點稱為“人造頂點”，其距離矩陣也相應擴大，其中，位于出發(fā)點的m個頂點相互間的距離設定為∞，其他數(shù)值不變。14二、多面體理論從上世紀70年代開始的關于算法復雜性的研究表明，要想為TSP找到一個好的算法，也即多項式算法，似乎是不可能的。由于推銷員的每條路線可以用一個以1開始的排列來表示，因此所有可能的路線有條。這樣，若用枚舉法來

7、解決這一問題，即使不太大，例如n＝30，用目前最快的計算機，也要化幾百萬年才能求出一條最短的路線。15早在1954年，Dantzig等人就曾提出過一種方法（非多項式算法），并且求出了一個42城市的TSP最優(yōu)解。到了1960年代，不少人用分支定界法解決了許多有幾十個城市的TSP。還有人提出了一些近似方法，也解決了許多有幾十個城市甚至上百個城市的TSP（有時找到的僅是近似解）。更值得注意的是，從1970年代中期開始，Grotschel與Padberg等人深入研究了TS多面體的最大面（facet），并從所得結果出發(fā)獲得了一種解TSP的新算法，

8、可以解決一些有100多個城市的TSP，且都在不長的時間內(nèi)找到了最優(yōu)解。16考慮個頂點的完全圖Kn，則解TSP就相當于在中求一條總長度最短的Hamilton回路?，F(xiàn)在，對每條邊ej，定義一個變量xj與之對應，