【正文】 等車時(shí)間、住宿時(shí)間（單位：小時(shí)）（i,j=1,2……11）Ti表示在景點(diǎn)i的觀光時(shí)間（i=1，2……10）則總時(shí)間，既目標(biāo)函數(shù)為：③約束條件的確定 由于每個(gè)景點(diǎn)只能有一條邊出去，所以對(duì)j景點(diǎn)Xij之和影等于1，既： i=1,2......11 同理，每個(gè)景點(diǎn)只能有一條邊進(jìn)去，所以對(duì)i景點(diǎn)Xij之和也應(yīng)等于1，既: i=1,2……11應(yīng)該注意的是，除了起點(diǎn)和終點(diǎn)（都是徐州）以外，各邊不構(gòu)成Hamilton圈。已經(jīng)分析，該問題屬于旅行商問題，這一過程中時(shí)間最省就是求最省時(shí)間路線的Hamilton圈。這一過程中我們盡量選擇高速的交通工，并且將在旅游景點(diǎn)停留的時(shí)間設(shè)為最短的符合要求的時(shí)間。 費(fèi)用(元)徐州常州青島北京祁縣洛陽黃山武漢西安九江舟山徐州062130154179122159158159118176常州62015014018012573361165120193青島1301500116120245360373363371422北京154140116094106182210210225493祁縣179180120940184248379109337569洛陽12212524510618402878733125546黃山159733601822482870205206120200武漢158361373210379872050267177674西安159165363210109332062670207313九江1181203712253371251201772070169舟山1761934224935692462006743131690根據(jù)建立的模型，我們利用LINGO軟件編程得到全局最優(yōu)解為3012元，最佳的旅游路線如下：徐州常州市恐龍園黃山市黃山舟山市普陀山九江市廬山武漢市黃鶴樓洛陽市龍門石窟西安市秦始皇兵馬俑祁縣喬家大院八達(dá)嶺長城青島市嶗山據(jù)此，我們?yōu)樵撀糜螑酆谜咴O(shè)計(jì)了詳細(xì)的行程表，：起止地點(diǎn)列車車次列車起止時(shí)間列車票價(jià)游覽行程徐州—常州13485月1日 21:43—03:3462元乘29路至常州市恐龍園，門票120元，在恐龍園大約停留9個(gè)小時(shí)常州—黃山K84185月2日20:02—5月3日06:5573元乘旅游班車至黃山，門票150元，在黃山大約停留10個(gè)小時(shí)黃山—鷹潭22395月3日20:56—5月4日03:3130元乘船至舟山市，轉(zhuǎn)乘27路公交車到達(dá)，門票160元，在普陀山大約停留7個(gè)小時(shí)鷹潭—寧波東K4745月4日23:04—5月5日06:4077元寧波—舟山乘船5月5日上午33元舟山—寧波乘船5月5日下午15:0033元乘102路至廬山，門票180元，在廬山大約停留9個(gè)小時(shí)寧波—杭州D31085月5日16:15—17:4246元杭州—九江K2535月5日18:03—5月6日03:4790元九江—十堰K10785月6日19:15—5月7日05:4353元乘10路車到武漢黃鶴樓，門票50元，大約停留5個(gè)小時(shí)十堰—武漢T2585月7日23:45—5月8日06:0664元武漢—洛陽K8625月9日00:30—09:2687元乘81路車至龍門石窟，門票80元，大約停留5個(gè)小時(shí)洛陽—西安10455月9日22:33—5月10日03:5733元乘306旅游專線至秦始皇兵馬俑，門票90元，大約停留6個(gè)小時(shí)西安—太原T425月10日18:20—5月11日03:3486元乘直達(dá)車至祁縣喬家大院，門票40元，大約停留4個(gè)小時(shí)太原—祁縣24625月11日05:00—06:0823元祁縣—北京26045月11日13:33—5月12日04:0094元乘地鐵2號(hào)線，再轉(zhuǎn)乘919快車，門票50元，大約停留6個(gè)小時(shí)北京—青島T255月12日22:48—5月13日07:38116元乘304路至嶗山，門票70元，在嶗山內(nèi)大約停留7個(gè)小時(shí)青島—徐州K705月13日19:10—5月14日05:06130元到家（注：該行程的設(shè)置使得夜間的住宿均在火車上）問題理解在費(fèi)用不受限制的情況下，可游覽完所有景點(diǎn)，要求所用的時(shí)間最短。模型建立綜上分析，建立Hamilton圈的線性規(guī)劃模型： min i=1,2......11 模型求解（注：上網(wǎng)查閱列車時(shí)刻表（），盡量保證車次是晚間發(fā)車并且到達(dá)下一個(gè)景點(diǎn)時(shí)不耽誤游玩，上網(wǎng)（）找到了滿足條件的賓館。我們把兩景點(diǎn)的最省路費(fèi)最為賦權(quán)值w（e），在一定程度上，各景點(diǎn)間的距離與兩點(diǎn)間的單程最省路費(fèi)是成正比的，所以把兩景點(diǎn)的最省路費(fèi)作為權(quán)值w（e）是可行的。現(xiàn)給出旅游景點(diǎn)門票費(fèi)用，每天基本費(fèi)用（吃飯等其它費(fèi)用60元），市內(nèi)交通（從火車站到旅游景點(diǎn)的雙程費(fèi)用））的最低費(fèi)。模型分析我們把各景點(diǎn)轉(zhuǎn)化為純數(shù)學(xué)形式的點(diǎn)線集合，利用圖論方面的知識(shí)求解。也就是說，從徐州出發(fā)，逐一觀賞各景點(diǎn)，不能重復(fù)，然后再回到徐州，使得這一過程中總的花費(fèi)最少。只是在實(shí)際的處理中，我們把兩景點(diǎn)的最省路費(fèi)（最短時(shí)間）最為賦權(quán)值w（e），在一定程度上，各景點(diǎn)間的距離與兩點(diǎn)間的單程最省路費(fèi)（單程最短時(shí)間）是成正比的，所以把兩景點(diǎn)的最省路（最短時(shí)間）作為權(quán)值w（e）是可行的。TSP問題是一個(gè)典型的組合優(yōu)化問題，其可能的搜索路徑隨著城市數(shù)目N的增加呈指數(shù)增長，屬于NP完全問題。用數(shù)學(xué)語言描述TSP，即給定一組N個(gè)城市和它們兩兩之間的直達(dá)距離，尋找一條閉合的旅程，使得每個(gè)城市剛好經(jīng)過一次且總的旅行距離最短。為了建立數(shù)學(xué)模型，首先應(yīng)該將各個(gè)景點(diǎn)轉(zhuǎn)化為純數(shù)學(xué)形式的點(diǎn)線的集合，進(jìn)行圖論方面的分析。第一方面根據(jù)對(duì)第一方面問題的分析可知，問題目的在于當(dāng)時(shí)間（費(fèi)用）不限的情況下求游完所有景點(diǎn)并回到出發(fā)地點(diǎn)所用的費(fèi)用（時(shí)間）的最小值。為了建立模型，首先應(yīng)將各景點(diǎn)線路轉(zhuǎn)化為純數(shù)學(xué)形式的點(diǎn)線集合，進(jìn)行圖論方面的分析。這就需要我們建立高效實(shí)用的數(shù)學(xué)模型來解決這些問題。二、問題分析對(duì)于人們生活水平不斷提高，越來越多的人會(huì)選擇在節(jié)假日游覽一下祖國的大好河山，領(lǐng)略一下各地的風(fēng)土人情和人文氣息。（D）假設(shè)景點(diǎn)的開放時(shí)間為8:00至18:00.根據(jù)以上條件考慮到旅游者的以下需求：在時(shí)間不限的情況下，游覽全部景點(diǎn)，旅游費(fèi)用最省；在旅游費(fèi)用不限的情況下，游覽全部景點(diǎn)，旅游時(shí)間最短；在旅游費(fèi)用一定的情況下，游覽盡可能多的景點(diǎn)；在時(shí)間一定的情況下，游覽盡可能多的景點(diǎn)；在時(shí)間和旅游費(fèi)用都一定的情況下，游覽盡可能多的景點(diǎn)。晚上20：:00至次日早晨7：:00之間，如果在某地停留超過6小時(shí)，必須住宿，住宿費(fèi)用不超過200元/天。（B）市內(nèi)交通出行可乘公交車（含專線大巴、小巴）、地鐵或出租車。由于跟團(tuán)旅游會(huì)受到限制，旅游者打算自己背包出游。在旅游的過程中，我們不僅可以感受大自然之美、放松心情，而且可以領(lǐng)略不同地方的文化氣息、拓寬視野。第二面要解決的問題是在費(fèi)用（時(shí)間）有限制或兩者都有限制的情況的情況下觀賞的景點(diǎn)近可能多，根據(jù)這種要求可從這種方案入手：建立多目標(biāo)規(guī)劃模型，通過適當(dāng)?shù)臄M合或線性加權(quán)，把多目標(biāo)轉(zhuǎn)化為單目標(biāo)（二）綜上所述，： 問題結(jié)果旅游路線（1）3012元（2）（3）1954元7個(gè)景點(diǎn)（4）5個(gè)景點(diǎn)（5）1201元 天3個(gè)景點(diǎn) 由于不同的網(wǎng)站公布的信息存在一定偏差，所以該結(jié)果僅依求解時(shí)提供的網(wǎng)站信息。用圖語言描述TSP：給出一個(gè)圖G=（V，E），每邊上有非負(fù)權(quán)值， 尋找G的Hamilton圈C，使得C的總權(quán)最小。根據(jù)對(duì)第一方面問題的分析可知，該問題屬于旅行商問題（Traveling Salesman Problem,TSP）。為了建立模型，首先應(yīng)將各景點(diǎn)線路轉(zhuǎn)化為純數(shù)學(xué)形式的點(diǎn)線集合，進(jìn)行圖論方面的分析。2012年安徽省建模競賽題 目 ： 旅游線路的優(yōu)化設(shè)計(jì)摘要本文考慮的是旅游時(shí)間（費(fèi)用）不受限制的情況下，如何安排旅游路線不重復(fù)且有返回的游覽完所有景點(diǎn)，使得費(fèi)用（時(shí)間）最少，以及費(fèi)用（時(shí)間）受限制或兩者都受限制時(shí)，如何安排不重復(fù)且有返回的路線使得游覽的景點(diǎn)最多。（一）對(duì)優(yōu)化模型的理解：路線優(yōu)化模型：首先我們知道本問題屬于旅游路線的優(yōu)化問題。本問題主要是解決兩方面的問題：（1）、（2）兩問是在時(shí)間或旅游費(fèi)用不限的情況下，游完十個(gè)景點(diǎn)怎樣才可以做到費(fèi)用最省或是時(shí)間最??；（3）、（4）、（5）問是在旅游時(shí)間或是旅游費(fèi)用或是兩者都有約束條件的情況下，怎樣才可以玩更多的地方。對(duì)旅行商問題的理解：一位銷售商從N個(gè)城市的某個(gè)城市出發(fā)，不重復(fù)的走完其余N1個(gè)城市并回到原出發(fā)點(diǎn)，在所有可能路徑中求出路徑長度最短的一條。在一定程度上，各景點(diǎn)間的距離與兩點(diǎn)間的單程最省路費(fèi)（單程最短時(shí)間）是成正比的，所以把兩景點(diǎn)的最省路（最短時(shí)間）作為權(quán)值是可行的。