1、摘要隨著人們生活水平的不斷提高，作為“無(wú)煙工業(yè)”旅游活動(dòng)便成為人們生活水平的重要指標(biāo)。本文圍繞五一黃金周的旅游問(wèn)題進(jìn)行了定量的評(píng)估，對(duì)即有時(shí)間限制又有時(shí)間限制的旅游質(zhì)量問(wèn)題建立了數(shù)學(xué)模型，對(duì)求解結(jié)果進(jìn)行了分析。問(wèn)題要求在只有1000元的旅游費(fèi)用且在7天之內(nèi)的條件下游覽盡可能多的城市。首先，我們對(duì)預(yù)選的旅游景點(diǎn)之間消耗的費(fèi)用和時(shí)間進(jìn)行了分析。由于約束條件不僅要求費(fèi)用不大于1000而且旅游時(shí)間在7天之內(nèi)，因此，我們從長(zhǎng)途汽車(chē)站和火車(chē)車(chē)次中選取費(fèi)用最低且最節(jié)約時(shí)間的路線并記錄了最優(yōu)行程費(fèi)用表。另外，由于時(shí)間的限制，因此，需引入0-1變量表示是否游覽某個(gè)景點(diǎn)，根據(jù)求解最優(yōu)Hamilton回路算法三邊交

2、換調(diào)整法，以費(fèi)用和時(shí)間為參考量，我們建立了一個(gè)適用于本問(wèn)題最優(yōu)規(guī)劃模型，得出最優(yōu)旅游路線。關(guān)鍵詞：三邊交換調(diào)整法 最優(yōu)旅游路線 Matlab程序 01模型問(wèn)題重述旅游路線安排計(jì)劃黃金周又到了，希望安排出外旅游。你要考慮的因素很多。首先，你得考慮時(shí)間有限（天）；其次要考慮費(fèi)用問(wèn)題：根據(jù)有限的費(fèi)用安排你的交通方式。當(dāng)然，還要考慮出游的樂(lè)趣，希望多走幾個(gè)景點(diǎn)。還要考慮勞逸結(jié)合，如較遠(yuǎn)的地方如坐火車(chē)需乘坐臥鋪，晚上休息。如何安排你的假期。假設(shè)一個(gè)景點(diǎn)一天的平均費(fèi)用為100元，你手中恰有剛剛發(fā)下來(lái)的獎(jiǎng)學(xué)金1000元。要制定合理的旅行路線，需要考慮的因素很多，如交通方式，盡可能去多個(gè)景點(diǎn)，休息住宿等。假設(shè)

3、一個(gè)景點(diǎn)一天的平均費(fèi)用為100元。那么如何安排你的假期？預(yù)選的九個(gè)市旅游景點(diǎn)市景點(diǎn)名稱(chēng)在景點(diǎn)的最短停留時(shí)間忻州盧芽山5小時(shí)呂梁北武當(dāng)山7小時(shí)太原晉祠6小時(shí)陽(yáng)泉藏山6小時(shí)晉中平遙古城5小時(shí)長(zhǎng)治上黨門(mén)7小時(shí)運(yùn)城五老峰4小時(shí)晉城九女仙湖4小時(shí)三門(mén)峽豫西大峽谷7小時(shí)模型假設(shè)與符號(hào)說(shuō)明模型假設(shè)1、所有的車(chē)票均預(yù)訂；2、在每個(gè)城市中停留時(shí)，難免會(huì)遇到等車(chē)、堵車(chē)等延時(shí)情況，在此問(wèn)題中我們不做考慮；3、平均每個(gè)城市的交通費(fèi)用30元(如公交車(chē)、出租車(chē)等)；4、景點(diǎn)的開(kāi)放，列車(chē)和汽車(chē)的運(yùn)營(yíng)不受天氣的影響；5、每天的伙食費(fèi)達(dá)到最高標(biāo)準(zhǔn)40元/天；6、景點(diǎn)停留時(shí)間超過(guò)六小時(shí)必須住宿，住宿費(fèi)每晚60元；7、在時(shí)間的認(rèn)識(shí)

4、上，我們把當(dāng)天的8點(diǎn)至次日8點(diǎn)作為一天；8、由于旅游者攜帶學(xué)生證，所有門(mén)票按半價(jià)計(jì)算。符號(hào)說(shuō)明、i,j表示第i個(gè)城市(景點(diǎn))或第j個(gè)城市(景點(diǎn))，i、j=1,210；、Z表示計(jì)劃行程中的總費(fèi)用；、W表示各城市(景點(diǎn))之間的交通費(fèi)用的總和，表示各城市(景點(diǎn))之間的交通費(fèi)用；、A表示在景點(diǎn)所在城市的總花費(fèi)，其中包括表示第i個(gè)城市(景點(diǎn))內(nèi)的交通費(fèi)用，表示第i個(gè)城市(景點(diǎn))內(nèi)的食宿費(fèi)用，表示第i個(gè)城市的景點(diǎn)的門(mén)票費(fèi)用， 表示第i個(gè)城市(景點(diǎn))內(nèi)總費(fèi)用，故=+；、表示在第i個(gè)城市(景點(diǎn))的逗留時(shí)間，表示從第i個(gè)景點(diǎn)到第j個(gè)景點(diǎn)路途中所需時(shí)間，T表示本次旅游的總時(shí)間；、問(wèn)題分析問(wèn)題背景分析根據(jù)對(duì)題目的理

5、解，我們知道旅游時(shí)的總費(fèi)用包含交通費(fèi)用、住宿費(fèi)用和在景點(diǎn)旅游時(shí)的費(fèi)用，在研究確定旅游路線和選用的交通工具后，我們的目標(biāo)是在所有的約束情況下，求出所求目標(biāo)的最優(yōu)解。對(duì)問(wèn)題分析問(wèn)題要求是在7天的時(shí)間內(nèi)、不大于1000元的旅游費(fèi)用的情況下使游客游覽盡可能多的景點(diǎn)數(shù)。模型的準(zhǔn)備 先給11個(gè)旅游城市分別進(jìn)行編號(hào)，臨汾、忻州、呂梁、太原、陽(yáng)泉、晉中、長(zhǎng)治、運(yùn)城、晉城、三門(mén)峽分別編號(hào)為、。則這10個(gè)城市和其交通路線構(gòu)成了一個(gè)網(wǎng)絡(luò)圖。這些城市可看作該網(wǎng)絡(luò)圖的節(jié)點(diǎn)。 各城市距離（單位：公里）臨汾忻州呂梁太原陽(yáng)泉晉中長(zhǎng)治運(yùn)城晉城三門(mén)峽臨汾0347.1380262440241315.5148594192.1忻州34

6、7.10269.981.3183.7108.4304.1500462519.9呂梁380269.90184.8275.3194.7377.8376.06457.9436.3太原26281.3184.80118.137.5223.8392.9322.3437.1陽(yáng)泉440183.7275.3118.1097.9313.3412439527.6晉中241108.4194.737.597.90197.9398280.8444.8長(zhǎng)治315.5304.1377.8223.8313.3197.90360518384運(yùn)城148500376.06392.9412398360017957.8晉城5944624

7、57.9322.3439280.85181790240三門(mén)峽192.1519.9436.3437.1527.6444.838457.8240001模型目標(biāo)函數(shù)的確立：旅游總費(fèi)用由2部分組成，分別為交通總費(fèi)用和在旅游景點(diǎn)的花費(fèi)。我們已經(jīng)定義：Z旅游總花費(fèi)；W交通總費(fèi)用；A旅游景點(diǎn)的花費(fèi)；從而得到目標(biāo)函數(shù)： Z=W+A(1)、交通總花費(fèi)因?yàn)楸硎镜趇個(gè)景點(diǎn)到第j個(gè)景點(diǎn)所需的交通費(fèi)用，而是判斷游客們是否從第i個(gè)景點(diǎn)到第j個(gè)景點(diǎn)的01變量，因此我們可以很容易的得到交通總費(fèi)用為：(2)、旅游景點(diǎn)的花費(fèi)因?yàn)楸硎居慰驮趇個(gè)景點(diǎn)的總消費(fèi)，也可以表示出是否到達(dá)過(guò)第i個(gè)和第j個(gè)景點(diǎn)，而整個(gè)旅游路線又是一個(gè)環(huán)形，因此

8、實(shí)際上將所到景點(diǎn)的花費(fèi)計(jì)算了兩遍，從而我們可以得到旅游景點(diǎn)的花費(fèi)為：從而我們可以得到目標(biāo)函數(shù)為： 約束條件:時(shí)間約束：旅游時(shí)間應(yīng)該不超過(guò)5天，而這些時(shí)間包括在路途中的時(shí)間和在旅游景點(diǎn)逗留的時(shí)間。因?yàn)楸硎緩牡趇個(gè)景點(diǎn)到第j個(gè)景點(diǎn)路途中所需時(shí)間，所以路途中所需的總時(shí)間為；表示在第i個(gè)景點(diǎn)的逗留時(shí)間，故在旅游景點(diǎn)的總逗留時(shí)間為因此，總的時(shí)間約束為：旅游景點(diǎn)數(shù)約束： 根據(jù)假設(shè)，整個(gè)旅游路線是環(huán)形，即最終要回到臨汾，因此即表示旅游的景點(diǎn)數(shù)，這里我們假定要旅游的景點(diǎn)數(shù)為n（n=1，2，3，9）。因此旅游景點(diǎn)數(shù)約束為： 01變量約束：我們可以把所有的景點(diǎn)連成一個(gè)圈，而把妹一個(gè)景點(diǎn)看做圈上一個(gè)點(diǎn)。對(duì)于每個(gè)景點(diǎn)

9、來(lái)說(shuō)，只允許最多一條邊進(jìn)入，同樣只允許最多一條邊出來(lái)，并且有一條邊進(jìn)入就要有一條邊出去。因此可得約束：當(dāng)i=1時(shí)，因?yàn)榕R汾是出發(fā)點(diǎn)，所以；j=1時(shí)，因?yàn)樽罱K要回到徐州，所以。綜上所述，我們可以得到總的模型為：約束條件 各大景點(diǎn)門(mén)票信息4景點(diǎn)盧芽山 北武當(dāng)山 晉祠 藏山風(fēng)平遙古城 上黨門(mén) 五老峰九女仙湖豫西大峽谷門(mén)票15元25元35元40元60元65元30元32元30元 *所有票價(jià)按學(xué)生票均半價(jià)*模型的建立與求解建立既有時(shí)限又有費(fèi)限的旅游質(zhì)量Hamilton回路模型，由于規(guī)定了費(fèi)用1000元和時(shí)間7天，所以這是一個(gè)完整的01模型，通過(guò)對(duì)綜合模型和結(jié)合Hamilton回路模型的運(yùn)算 最優(yōu)通行費(fèi)用表

10、最少旅費(fèi)臨汾忻州呂梁太原陽(yáng)泉晉中長(zhǎng)治運(yùn)城晉城三門(mén)峽臨汾03740254524.535205523忻州3702618221934524653呂梁4026022.526.523383745.545太原251822.50181624413645陽(yáng)泉455226.518018.5354345.553.5晉中24.519231618.5023.5412754長(zhǎng)治353438243523.503652.539運(yùn)城2052374143413602117晉城554645.53645.52752.521024.5三門(mén)峽2353454553.554391724.50編寫(xiě)基于Hamilton回路算法的C語(yǔ)言程序，輸

11、入上表數(shù)據(jù)，運(yùn)行得出有時(shí)間限制又有費(fèi)用限制的情況下，最優(yōu)城市順序?yàn)椋骸３鞘兄g的交通費(fèi)=24.5+18.5+18+22.5+37+17+23=160.5(元)市內(nèi)的交通費(fèi) M=(元)餐飲費(fèi)S=(元)住宿費(fèi)N=2=120(元)景點(diǎn)門(mén)票費(fèi) =60+40+35+25+30+30=220（元）所以總旅行費(fèi)用 =160.5+180+120+280+220=960.5（元）模型結(jié)果分析針對(duì)該問(wèn)題推薦最優(yōu)旅游路線：。旅游景點(diǎn)數(shù)：6 旅游總費(fèi)用：960.5元旅游總耗時(shí)：6天12小時(shí)（156小時(shí)）本文通過(guò)建立基于三邊交換調(diào)整法的旅游路線模型和引入01模型進(jìn)行規(guī)劃，在一定的約束條件下為游客設(shè)計(jì)了近似最優(yōu)旅行路線。

12、由于用了01模型進(jìn)行簡(jiǎn)化，建模和編程得以順利完成；經(jīng)后期檢驗(yàn)，所得結(jié)果能滿(mǎn)足題目的要求，最大程度減少了時(shí)間或資金的消耗，具有較好的實(shí)際意義。但由于數(shù)據(jù)量過(guò)于龐大，模型中為了方便研究又有一些假設(shè)，所以所得結(jié)果只是近似最優(yōu)解。模型的評(píng)價(jià)本文根據(jù)游客的旅行路線進(jìn)行了合理假設(shè)，簡(jiǎn)化了次要因素，把問(wèn)題轉(zhuǎn)化為圖論上最佳旅行商回路問(wèn)題解決，思路比較清晰，模型恰當(dāng)，得出的方案相對(duì)合理,使問(wèn)題得到了比較合理的解決；成功的使用了01變量，使模型的建立和求解得以順利進(jìn)行。但是，由于數(shù)據(jù)龐大，對(duì)程序的要求很高，盡管經(jīng)過(guò)了檢驗(yàn)，但結(jié)果依然比較粗糙，有待進(jìn)一步的改進(jìn)。實(shí)際情況中，兩景點(diǎn)之間的交通方式比較復(fù)雜，如公路、鐵路、航班之間可以轉(zhuǎn)換，增加這些考慮后，結(jié)果會(huì)更加合理。且數(shù)據(jù)資料搜集的不完整，有一定