TSP問題知識分享_第1頁
TSP問題知識分享_第2頁
TSP問題知識分享_第3頁
全文預覽已結束

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、TSP 問 題有一個推銷員，從城市1出發，要遍訪城市2, 3,，n各一次，最后返 回城市1。已知從城市i到j的旅費為Cij，問他應按怎樣的次序訪問這些城 市，使得總旅費最少？可以用多種方法把TSP表示成整數規劃模型。這里介紹的一種建立模型的 方法，是把該問題的每個解（不一定是最優的）看作是一次 “巡回”。在下述意義下，引入一些0-1整數變量：1， 巡回路線是從i到j ,且i jnXj 0， 其它情況cij xij其目標只是使1為最小。這里有兩個明顯的必須滿足的條件：訪問城市i后必須要有一個即將訪問的確切城市；訪問城市 j前必須要有一 個剛剛訪問過的確切城市。用下面的兩組約束分別實現上面的兩個條

2、件。Xij1,j 1i 1,2, ,nnXij 1, j 1,2, ni 1到此我們得到了一個模型，它是一個指派問題的整數規劃模型。但以上兩個條 件對于TSP來說并不充分，僅僅是必要條件。例如：以上兩個條件都滿足，但它顯然不是 TSP的解，它存在兩個子巡回。 這里，我們將敘述一種在原模型上附加充分的約束條件以避免產生子巡回的方法。把額外變量Ui （i 2,3,n）附加到問題中。可把這些變量看作是連續的（最然這些變量在最優解中取普通的整數值）。現在附加下面形式的約束條 件ui Uj n Xjj n 1,2 i j n。為了證明該約束條件有預期的效果，必須證明：（1）任何含子巡回的路線 都不滿足該

3、約束條件；（2）全部巡回都滿足該約束條件。首先證明（1），用反證法。假設還存在子巡回，也就是說至少有兩個子巡 回。那么至少存在一個子巡回中不含城市 1。把該子巡回記為i1i2 iki1，則必有 （對于所有的ik都滿足大于2的限制條件）uhUi21Ui2n n 1Ui3n n 1UikUi1n n 1把這k個式子相加，有故假設不正確，結論（1）得證。下面證明（2）,采用構造法。對于任意的總巡回1i1 in 11，可取 Ui訪問城市i的順序數。下面來證明總巡回滿足該約束條件。（i）總巡回上的邊Ui1Ui2 n n1 n 1Ui2遲 n n1 n 1U-Uimnn 1 n 1（ii）非總巡回上的邊Uirun 2n 1,r 1,2,n 2, j 2,3,n ir,iUin1Uj n 2n 1,j 2,3,n ir從而結論（2）得證這樣我們把TSP轉化成了一個混合整數線性規劃問題。nmin z q x”i,j 1i jns.t.Xij 1, j 1,2, ni 1nXij1, i 1,2, , nj 15 Uj n Xjjn 1, 2 i j nXij 0,1, i, j 1,2, ,nui 0, i 2, 3, n顯然，當城市個數較大（大于 30）時，該混合整數線性規劃問題的規模會 很大，從而給求解帶來很大問題。TSP已

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論