經(jīng)濟(jì)旅游線路優(yōu)化設(shè)計(jì)-數(shù)學(xué)建模

1、2009-2010學(xué)年第一學(xué)期數(shù)學(xué)建模論文論文題目經(jīng)濟(jì)旅游線路優(yōu)化設(shè)計(jì)姓 名學(xué) 號班 級論文分?jǐn)?shù)(教師填寫)1、論文的創(chuàng)新點(diǎn)綜合運(yùn)用了列舉法結(jié)合C語言解決TSP簡單問題；程序運(yùn)行環(huán)境 visual C+6.0;2、各成員的分工豐田 搜索材料和編程 陳曦 撰寫一部分論文 徐俊 撰寫一部分論文 3、各成員的貢獻(xiàn)豐田 35%；陳曦 35%；徐俊 30%；4、論文的原創(chuàng)性聲明本人鄭重聲明：所呈交的論文，是在論文小組成員討論下，獨(dú)立進(jìn)行研究工作所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫過的作品成果。論文如有抄襲嫌疑，后果由本人承擔(dān)。 各成員簽字： 日 期： 2

2、010年1月8日 經(jīng)濟(jì)旅游線路優(yōu)化設(shè)計(jì)摘要：對給定的數(shù)據(jù)進(jìn)行旅游線路優(yōu)化，設(shè)計(jì)出更經(jīng)濟(jì)的旅游線路。 針對問題：如何用簡潔的方法解決TSP商旅問題； 運(yùn)用列舉法通過C語言編程將所有可能的路線所需費(fèi)用計(jì)算出來，通過比較求出最經(jīng)濟(jì)的旅行路線。關(guān)鍵詞：經(jīng)濟(jì)，列舉法，C語言。1、 問題的提出現(xiàn)在有8個(gè)城市，已知兩個(gè)城市之間的路費(fèi)如下表，現(xiàn)在有一個(gè)人從A城市出發(fā)旅行，應(yīng)該選擇怎樣的路線才能剛好每個(gè)城市都到達(dá)一次又回到A城市，其總路費(fèi)最少？A B C D E F G HABCDEFG0 56 35 21 51 60 43 39 21 57 78 70 64 49 36 68 - 70 60 51 61 65

3、 26 13 45 62 53 26 502、條件的假設(shè)與符號的約定2.1條件的假設(shè): 把該問題的每個(gè)解看作是一次“巡回”。在下述意義下，引入一些0-1整數(shù)變量：其目標(biāo)只是使為最小。這里有兩個(gè)明顯的必須滿足的條件：訪問城市i后必須要有一個(gè)即將訪問的確切城市；訪問城市j前必須要有一個(gè)剛剛訪問過的確切城市。用下面的兩組約束分別實(shí)現(xiàn)上面的兩個(gè)條件。 。2.2符號約定： 循環(huán)路線（i=1，2···，n j=1,2,3···，n）從一個(gè)城市到另一個(gè)城市所需的費(fèi)用。（i=1，2，···，n j=1，2，3，·

4、;··，n）：額外變量旅行完8個(gè)城市所需總路費(fèi)3、問題分析 從A市出發(fā)選擇合適的路線旅游每一個(gè)城市一次，使路費(fèi)最少，其本質(zhì)是一個(gè)TSP商旅問題。我們可以對已有的TSP商旅模型進(jìn)行修改，通過編程將所有路線所需費(fèi)用列舉出來，找出最經(jīng)濟(jì)的路線。關(guān)于TSP旅行商問題：旅行商問題（Traveling Saleman Problem，TSP）是VRP的特例，由于Gaery1已證明TSP問題是NP難題，因此，VRP也屬于NP難題。 旅行商問題（TSP）又譯為旅行推銷員問題、貨郎擔(dān)問題，簡稱為TSP問題，是最基本的路線問題，該問題是在尋求單一旅行者由起點(diǎn)出發(fā)，通過所有給定的需求點(diǎn)之后，最后

5、再回到原點(diǎn)的最小路徑成本。最早的旅行商問題的數(shù)學(xué)規(guī)劃是由Dantzig（1959）等人提出。 TSP問題在物流中的描述是對應(yīng)一個(gè)物流配送公司，欲將n個(gè)客戶的訂貨沿最短路線全部送到。如何確定最短路線。 TSP問題最簡單的求解方法是枚舉法。它的解是多維的、多局部極值的、趨于無窮大的復(fù)雜解的空間，搜索空間是n個(gè)點(diǎn)的所有排列的集合，大小為（n-1）?？梢孕蜗蟮匕呀饪臻g看成是一個(gè)無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解TSP，則是在此不能窮盡的丘陵地帶中攀登以達(dá)到山頂或谷底的過程。TSP旅行商問題常見算法：枚舉法，蟻群算法，模擬退火柴法。4、模型的建立與求解由2.1所給的條件與假設(shè)可以建

6、立一個(gè)模型：最小費(fèi)用=它是一個(gè)指派問題的整數(shù)規(guī)劃模型。為了證明該約束條件有預(yù)期的效果，必須證明：（1）任何含子巡回的路線都不滿足該約束條件；（2）全部巡回都滿足該約束條件。首先證明（1），用反證法。假設(shè)還存在子巡回，也就是說至少有兩個(gè)子巡回。那么至少存在一個(gè)子巡回中不含城市1。把該子巡回記為，則必有把這k個(gè)式子相加，有，矛盾！故假設(shè)不正確，結(jié)論（1）得證。下面證明（2），采用構(gòu)造法。對于任意的總巡回，可取訪問城市i的順序數(shù)，取值范圍為。因此，。下面來證明總巡回滿足該約束條件。()總巡回上的邊（）非總巡回上的邊從而結(jié)論（2）得證。這樣我們把此問題轉(zhuǎn)化成了一個(gè)混合整數(shù)線性規(guī)劃問題。我們通過用C語言

7、編程得到編譯結(jié)果的截屏圖像結(jié)論：最佳路線A->G->E->F->C->B->H->D->A。5、模型的評價(jià)與改進(jìn)5.1、模型的優(yōu)點(diǎn)： 該模型構(gòu)造簡潔，易于理解，思路清楚。通過列舉法與C語言的結(jié)合使解決該問題更為快速?？紤]到了各種情況。為消費(fèi)者提供了一個(gè)好方法。5.2、模型的推廣： 該模型適合在旅行城市個(gè)數(shù)較少的時(shí)候推廣。當(dāng)城市個(gè)數(shù)較大（大于30）時(shí)，該混合整數(shù)線性規(guī)劃問題的規(guī)模會很大，從而給求解帶來很大問題。TSP已被證明是NP難問題，目前還沒有發(fā)現(xiàn)多項(xiàng)式時(shí)間的算法。對于小規(guī)模問題，我們求解這個(gè)混合整數(shù)線性規(guī)劃問題的方式還是有效的。附錄：程序中的

8、變量所帶表的含義money88二維數(shù)組（用來存放城市之間旅行的路費(fèi)）all10000一維數(shù)組（用來存放每一條旅行線路的費(fèi)用）sta2B城市sta3C城市sta4D城市sta5E城市sta6F城市sta7G城市sta8H城市L2最佳線路的第2個(gè)城市L3最佳線路的第3個(gè)城市L4最佳線路的第4個(gè)城市L5最佳線路的第5個(gè)城市L6最佳線路的第6個(gè)城市L7最佳線路的第7個(gè)城市L8最佳線路的第8個(gè)城市min最佳線路所需費(fèi)用xuhaoall數(shù)組中最佳線路所需費(fèi)用的序號解決該模型的C語言程序：#include "stdio.h"void main ()Long int money88=0,5

9、6,35,21,51,60,43,39,56,0,21,57,78,70,64,49,35,21,0,36,68,0,70,60,21,57,36,0,51,61,65,26,51,78,68,51,0,13,45,62,60,70,0,61,13,0,53,26,43,64,70,65,45,53,0,50,39,49,60,26,62,26,50,0;Long int sta2,sta3,sta4,sta5,sta6,sta7,sta8,i=0,x=0,y=0,min=0,xuhao=0;long int all10000,l2,l3,l4,l5,l6,l7,l8;printf("

10、;all case:n");for(sta2=1;sta2<=7;sta2+)for(sta3=1;sta3<=7;sta3+)for(sta4=1;sta4<=7;sta4+)for(sta5=1;sta5<=7;sta5+)for(sta6=1;sta6<=7;sta6+)for(sta7=1;sta7<=7;sta7+)for(sta8=1;sta8<=7;sta8+) if(sta3!=sta2&&sta4!=sta3&&sta4!=sta2&&sta5!=sta4&&s

11、ta5!=sta3&&sta5!=sta2&&sta6!=sta5&&sta6!=sta4&&sta6!=sta3&&sta6!=sta2&&sta7!=sta6&&sta7!=sta5&&sta7!=sta4&&sta7!=sta3&&sta7!=sta2&&sta8!=sta7&&sta8!=sta6&&sta8!=sta5&&sta8!=sta4&&s

12、ta8!=sta3&&sta8!=sta2) alli=s0sta2+ssta2sta3+ssta3sta4+ssta4sta5+ssta5sta6+ssta6sta7+ssta7sta8+ssta80;i+;if(i=4039)/此處的i是通過首先運(yùn)行程序得到xuhao值后確定的/l2=sta2;l3=sta3;l4=sta4;l5=sta5;l6=sta6;l7=sta7;l8=sta8; for(x=0;x<i;x+) printf("%5d",allx); if(x!=0&&x%10=0)printf("n");printf("n");min=a