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

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

2、010年1月8日 經(jīng)濟旅游線路優(yōu)化設計摘要：對給定的數(shù)據(jù)進行旅游線路優(yōu)化，設計出更經(jīng)濟的旅游線路。 針對問題：如何用簡潔的方法解決TSP商旅問題； 運用列舉法通過C語言編程將所有可能的路線所需費用計算出來，通過比較求出最經(jīng)濟的旅行路線。關鍵詞：經(jīng)濟，列舉法，C語言。1、 問題的提出現(xiàn)在有8個城市，已知兩個城市之間的路費如下表，現(xiàn)在有一個人從A城市出發(fā)旅行，應該選擇怎樣的路線才能剛好每個城市都到達一次又回到A城市，其總路費最少？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、條件的假設與符號的約定2.1條件的假設: 把該問題的每個解看作是一次“巡回”。在下述意義下，引入一些0-1整數(shù)變量：其目標只是使為最小。這里有兩個明顯的必須滿足的條件：訪問城市i后必須要有一個即將訪問的確切城市；訪問城市j前必須要有一個剛剛訪問過的確切城市。用下面的兩組約束分別實現(xiàn)上面的兩個條件。 。2.2符號約定： 循環(huán)路線（i=1，2···，n j=1,2,3···，n）從一個城市到另一個城市所需的費用。（i=1，2，···，n j=1，2，3，·

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

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

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

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

8、變量所帶表的含義money88二維數(shù)組（用來存放城市之間旅行的路費）all10000一維數(shù)組（用來存放每一條旅行線路的費用）sta2B城市sta3C城市sta4D城市sta5E城市sta6F城市sta7G城市sta8H城市L2最佳線路的第2個城市L3最佳線路的第3個城市L4最佳線路的第4個城市L5最佳線路的第5個城市L6最佳線路的第6個城市L7最佳線路的第7個城市L8最佳線路的第8個城市min最佳線路所需費用xuhaoall數(shù)組中最佳線路所需費用的序號解決該模型的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是通過首先運行程序得到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