版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
第7章旅行商問題目錄第7章旅行商問題1問題概述2求解算法21下界和上界算法22分支定界法23動態(tài)規(guī)劃法25近似算法25競賽題§7-1問題概述數(shù)學(xué)模型1.標(biāo)準(zhǔn)TSP旅行商問題(簡稱TSP),也稱貨郎擔(dān)問題或旅行推銷員問題,是運籌學(xué)中一個著名的問題,其一般提法為:有一個旅行商從城市1出發(fā),需要到城市2、3n去推銷貨物,最后返回城市1,若任意兩個城市間的距離已知,則該旅行商應(yīng)如何選擇其最佳行走路線?TSP在圖論意義下又常常被稱為最小Hamilton圈問題Euler等人最早研究了該問題的雛形,后來由英國的Hamiltoni爵士作為一個懸賞問題而提出。但這個能讓普通人在幾分鐘內(nèi)就可理解的游戲之作,卻延續(xù)至今仍未能完全解決,成了一個世界難題。TSP有著明顯的實際意義,如,郵局里負(fù)責(zé)到各信箱開箱取信的郵遞員,以及去各分局送郵件的汽車等,都會遇到類似的問題。有趣的是,還有一些問題表面上看似乎與TSP無關(guān),而實質(zhì)上卻可以歸結(jié)為TSP來求解。已經(jīng)證明,TSP是個NP難題,除非P=NP,否則不存在有效算法。記為賦權(quán)圖G=(V,E),V為頂點集,E為邊集,各頂點間的距離已知。設(shè)若(i,j)在回路路徑上0其他則經(jīng)典的TSP可寫為如下的數(shù)學(xué)規(guī)劃模型:minz=∑∑dxj∈v(7-2)∑x≤|S|-1,MSc
溫馨提示
- 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 施工現(xiàn)場施工防噪隔音制度
- 現(xiàn)代家居設(shè)計中的綠植藝術(shù)實踐
- 醫(yī)療護(hù)理醫(yī)學(xué)培訓(xùn) 小麥病蟲害防治課件
- DB6528T 202-2024春玉米滴灌栽培技術(shù)規(guī)程
- 中小企業(yè)勞動合同模板大全
- 個人與工廠合作協(xié)議合同
- 個人借款合同條款解析
- 交通運輸行業(yè)勞動合同準(zhǔn)則
- 個人短期借款合同文本范例
- 臨時勞務(wù)用工合同協(xié)議
- 2025至2030年中國減肥肽數(shù)據(jù)監(jiān)測研究報告
- 2024內(nèi)蒙古公務(wù)員省直行測、行政執(zhí)法、省考行測考試真題（5套）
- 2025年安徽馬鞍山市兩山綠色生態(tài)環(huán)境建設(shè)有限公司招聘筆試參考題庫附帶答案詳解
- 山東省濱州市濱城區(qū)2024-2025學(xué)年九年級上學(xué)期期末考試化學(xué)試題
- 期末試卷：安徽省宣城市2021-2022學(xué)年七年級上學(xué)期期末歷史試題（解析版）
- 幼兒教師新年規(guī)劃
- 2024年湖南省公務(wù)員錄用考試《行測》真題及答案解析
- 2024新版（北京版）三年級英語上冊單詞帶音標(biāo)
- 第21課 活動課 從考古發(fā)現(xiàn)看中華文明的起源 教學(xué)課件
- 部編版《道德與法治》四年級下冊教材解讀與分析文檔
- PP、PVC-風(fēng)管制作安裝施工作業(yè)指導(dǎo)書
評論
0/150
提交評論