走遍全中國(guó)__論文

《走遍全中國(guó)__論文》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、封一答卷編號(hào)（參賽學(xué)校填寫）:答卷編號(hào)（競(jìng)賽組委會(huì)填寫）:論文題目：B：走遍全中國(guó)組別:本科生參賽隊(duì)員信息（必填）:姓名專業(yè)班級(jí)及學(xué)號(hào)聯(lián)系電話參賽隊(duì)員1楊陽(yáng)84140101:2008041401008;15040226572參賽隊(duì)員2王默涵84010105:2008040101132;15040246437參賽隊(duì)員3梁利亮84010105；2008040101125；15040282018參賽學(xué)校：沈陽(yáng)航空航天大學(xué)封二答卷編號(hào)（參賽學(xué)校填寫:答卷編號(hào)（競(jìng)賽組委會(huì)填寫）：評(píng)閱情況（學(xué)校評(píng)閱專家填寫）:學(xué)校評(píng)閱1.學(xué)校評(píng)閱2.學(xué)校評(píng)閱3.評(píng)閱情況（聯(lián)賽評(píng)閱專

2、家填寫人聯(lián)賽評(píng)閱1.聯(lián)賽評(píng)閱2.聯(lián)賽評(píng)閱3論文題目：走遍全中國(guó)摘要旅行商問(wèn)題也叫貨郎擔(dān)問(wèn)題，其一般解釋為：有一個(gè)旅行推銷商要由某一城市出發(fā)，到若干個(gè)城市去銷貨，他只能經(jīng)侮一個(gè)城市一次且僅一次，最后冋到原來(lái)出發(fā)的城訓(xùn)，問(wèn)應(yīng)如何選擇旅行路線才能使得總的路線最短？這是運(yùn)籌學(xué)的一個(gè)非常著名的問(wèn)題。本題——走遍全中國(guó)，就可以歸結(jié)為這類問(wèn)題。這類問(wèn)題通常在多項(xiàng)式時(shí)間里無(wú)法求解，屬于NP完全問(wèn)題。尤其是隨著問(wèn)題規(guī)模的擴(kuò)大，問(wèn)題空間呈現(xiàn)組合爆炸特征，無(wú)法用常規(guī)的方法求解。本題要考慮到34個(gè)城山，已經(jīng)達(dá)到一定的規(guī)模了。為此，我們采用遺傳算法并對(duì)其進(jìn)行相應(yīng)的改進(jìn)來(lái)逐步運(yùn)算，

3、得到一個(gè)相對(duì)較最優(yōu)的出行路線。在求解最佳線路時(shí)，會(huì)涉及到圖論中的哈密爾頓路，即圖屮每個(gè)點(diǎn)經(jīng)過(guò)且僅經(jīng)過(guò)一次的一條路。題冃要求的是一條最優(yōu)的哈密爾頓路，即圖的最小生成樹。主要的算法有prim算法和kruska1算法。prim算法：依次從圖屮取最小的邊，共取N-1條邊（假設(shè)有N個(gè)點(diǎn)），但不能形成回路，若取的邊和已取的邊形成回路，則放棄該邊，去取圖中未取中的第二小的邊，若仍形成回路，則放棄,取第三小的邊，依次類推,直到取N-1條邊。kruskal算法:先在圖屮任取一點(diǎn)，再在已取的點(diǎn)屮找與這些點(diǎn)相連的最小的邊，取這條邊另一段的點(diǎn)，如此循環(huán)，直到取滿N個(gè)點(diǎn)。在模型三

4、建立過(guò)程屮，涉及到的最小費(fèi)用流問(wèn)題。在求解容量網(wǎng)絡(luò)的時(shí)候,由于管道的長(zhǎng)度、設(shè)施狀況不同，因而通過(guò)單位流量的費(fèi)用往往也會(huì)有差距。所以，一般除了要求通過(guò)的流量最大外，通常還希望通過(guò)一定流量大的費(fèi)用也能最小化。這就是最小費(fèi)用流問(wèn)題。在模型三中，除了要求費(fèi)用最小外，還希望旅行所需時(shí)間最小化，所以我們將此模型定義為最小費(fèi)用流問(wèn)題。最小費(fèi)用流問(wèn)題實(shí)際上也是一種線性規(guī)劃問(wèn)題我們將時(shí)間約束TSP問(wèn)題可以描述為：由一個(gè)旅行商訪問(wèn)n個(gè)城市。要求訪問(wèn)每個(gè)城市一次且僅有一次.盡可能在一定時(shí)間范圍內(nèi)訪問(wèn)，否則將產(chǎn)生等待或延遲損失，求成本最小的旅行線路。通過(guò)以上的算法，便可以給出理

5、想的模型關(guān)鍵詞：旅行商問(wèn)題遺傳算法最小費(fèi)用流Hamilton回路多1=1標(biāo)函數(shù)規(guī)劃一.問(wèn)題重述本題目主要討論如何對(duì)周游先生的旅游制定出合理化的旅游方案，使周游先生的旅游兼顧既省時(shí)又省錢且方便，從而達(dá)到最理想的旅游計(jì)劃方案。周游先生退休后想到各地旅游。計(jì)劃走遍全國(guó)的省會(huì)城市、直轄市、香港、澳門、臺(tái)北。首先，考慮乘車的路線，按地理位置(經(jīng)緯度)設(shè)計(jì)岀最短路旅行方案。其次，考慮乘車的的方式及價(jià)格，乘車方式選擇航空、鐵路(快車臥鋪或動(dòng)車)，設(shè)計(jì)出最經(jīng)濟(jì)的旅行互聯(lián)網(wǎng)上訂票方案。最后，根據(jù)實(shí)際情況，要綜合考慮省錢、省時(shí)又方便，給出自己的評(píng)價(jià)準(zhǔn)則，如何將旅游問(wèn)題抽象成

6、一個(gè)明確完整的數(shù)學(xué)模型，指出求解方法，修訂你的方案，根據(jù)自己對(duì)所建立的模型的理解，對(duì)自己的模型進(jìn)行評(píng)價(jià)。二.問(wèn)題分析本問(wèn)題的難點(diǎn)是要同時(shí)考慮到旅行路程最短，乘車方式(動(dòng)車、快車臥鋪以及航空)的選擇，最經(jīng)濟(jì)旅行路線和出行方式，旅行所需時(shí)間等諸多因素。如果僅考慮旅行路線最短，則只要考慮如何實(shí)現(xiàn)遍歷的最短路程，運(yùn)用哈密頓回路方法以及遺傳算法就可以給出最佳方案。如果僅考慮最經(jīng)濟(jì)旅行路線，由于火車類票價(jià)和火車行駛距離存在一定關(guān)系，我們根據(jù)模型一屮求得的最短路線計(jì)算所需的費(fèi)用，最后再根據(jù)某些特殊因素加以改進(jìn)，便可以給出最佳方案。由實(shí)際情況綜合考慮，顯然這兩種方案都不

7、是最佳的方案，我們要兼顧時(shí)間，路線，花費(fèi)等方面。根據(jù)最小費(fèi)用流計(jì)算方法以及多Fl標(biāo)函數(shù)最優(yōu)化方法，給出一個(gè)比較完整的方案。一.符號(hào)說(shuō)明x(i)—將角度制轉(zhuǎn)化為弧度制后每個(gè)城市的弧度制橫坐標(biāo)Y(i)---將角度制轉(zhuǎn)化為弧度制后每個(gè)城市的弧度制縱坐標(biāo)M(i)—將弧度制轉(zhuǎn)化為二維平面后每個(gè)城市的橫坐標(biāo)N(i)—將弧度制轉(zhuǎn)化為二維平面后何:個(gè)城市的縱坐標(biāo)D——》［、N兩城市間距離Smn—m、N兩城市間旅行經(jīng)費(fèi)D遍歷后的最短距離S選取最經(jīng)濟(jì)路線后的總旅行經(jīng)費(fèi)四.模型假設(shè)(1)忽略火車軌道長(zhǎng)度與兩城市間直線距離的茅別，即火車軌道長(zhǎng)度為兩城市間直線距離。(2)“各

8、城市經(jīng)緯度統(tǒng)計(jì)表”，“各城市間最經(jīng)濟(jì)票價(jià)統(tǒng)計(jì)表”中數(shù)據(jù)來(lái)源準(zhǔn)確、可信、穩(wěn)定。(3