旅游路線的優(yōu)化模型

楚雄師范學(xué)院2011年數(shù)學(xué)建模培訓(xùn)第二次測試論文題目姓名系（院）數(shù)學(xué)系專業(yè)信息與計(jì)算科學(xué)2011年5月15日一、摘要云南風(fēng)光旖旎，四季如春，是旅游的天堂。本論文就是以到云南旅游的交通方式以及路線選擇為背景，通過構(gòu)建模型。實(shí)現(xiàn)以經(jīng)濟(jì)的方式玩轉(zhuǎn)云南的各大旅游景點(diǎn)。旅游的交通方式一般有自駕游覽和乘坐公共交通工具兩種方式。本論文通過比較用公共交通出行方式下所有旅游路線的費(fèi)用，得出最佳的旅游路線。為了方便進(jìn)行進(jìn)行比較，文中引入了帶權(quán)圖和最小生成樹的模型，為比較提供了可以參考的標(biāo)準(zhǔn)，模型中既要考慮路線最短，又要在規(guī)定的時(shí)間范圍完成旅程,且通過預(yù)訂旅游近點(diǎn)數(shù)最多，費(fèi)用較少。該模型以云南各大旅游景點(diǎn)為帶權(quán)圖的點(diǎn)，以采用交通方式來進(jìn)行旅游過程中在具體的兩個(gè)旅游景點(diǎn)的途中花去的費(fèi)用為權(quán)值，這樣，在該種旅游方式下的花費(fèi)就是各對應(yīng)的權(quán)值之和。當(dāng)然，選擇了公共交通的旅游方式，可能走的旅游路線也不盡相同。這樣就產(chǎn)生了同一個(gè)旅游方式下的多條路線費(fèi)用的比較，通過比較大小，就得到了較為經(jīng)濟(jì)的相應(yīng)旅游方式下的最佳路線了。本文作者充分調(diào)查了云南省目前的各種交通方式的收費(fèi)情況，并查找了相關(guān)的旅游路線，有利地確保了論文的真實(shí)性和可靠性。#關(guān)鍵字：最小生成樹、最佳路線、時(shí)間、路程。二、問題某旅客攜帶著家人想到云南旅游觀光，并且想玩遍云南的各大旅游景點(diǎn)。請為這一行旅客設(shè)計(jì)旅游路線，并為他們提供一個(gè)合理的旅游交通方式的建議。三、符號說明把各景點(diǎn)用數(shù)據(jù)代替如下：昆明市⑴楚雄市⑵大理市⑶麗江市⑷香格里拉⑸怒江⑹保山⑺德宏⑻臨滄⑼普洱市⑽西雙版納(11)玉溪市(⑵紅河(⑶文山市(⑷石林(15)曲靖(16)昭通(⑺權(quán)值表示景點(diǎn)之間的車票價(jià)

交通方式費(fèi)用時(shí)間昆明市T楚雄汽車/火車45/302小時(shí)市汽車/火車32/203小時(shí)昆明市T曲靖汽車251小時(shí)市汽車733.5小時(shí)昆明市T玉溪汽車1005小時(shí)昆明市T開遠(yuǎn)昆明市T昭通四、模型建立

1.當(dāng)兩點(diǎn)之間沒有直線連接時(shí)，應(yīng)改進(jìn)為使其兩點(diǎn)的距離最短（兩點(diǎn)之間可以經(jīng)過若干個(gè)點(diǎn)）.2.遇到兩點(diǎn)直間不直接連接，如果由這兩點(diǎn)組成的最短路徑與后面有重復(fù)，必須把后面的路徑中重復(fù)的部分刪除。五、模型求解5.1約束條件時(shí)間和消費(fèi)約束：不考慮旅游者在景點(diǎn)處的逗留時(shí)間和消費(fèi)；旅游方式約束：當(dāng)景點(diǎn)之間需分路時(shí)，先去了某個(gè)景點(diǎn)，如果原路返回去另一個(gè)景點(diǎn)比較合適，則可以原路返回；交通方式約束：為了旅游方便，盡量選擇客車。5.2模型求解從昆明出發(fā)，可選路線如下：(1)t(5)t(4)t(3)T(2)t(1):W(T)=197+58+38+32+44=369(1)t(2)t⑶t(4)t⑸t(1):W(T)=44+32+38+58+197=369(1)T(2)T(3)T(4)T(6)T(5)T(1):W(T)=44+32+38+58+197=369(1)T(2)T(3)T(7)T(6)T(5)T(1):W(T)=44+32+26+25+30+197=354(1)T(12)T(11)T(10)T(9)T(7)T(6)T(5)+(1)：W(T)=25+110+25+160+20+25+30+197=592(1)T(12)T(11)T(10)T(9)T(7)T(3)t(4)t(5)T(l)：W(T)=25+110+25+160+20+26+38+58+197=659(1)T(5)T(6)T(7)T(9)T(10)T(11)T(12)T(1):W(T)=197+30+25+20+160+25+110+25+197=789(1)T(5)T(6)T(7)T(9)T(10)T(11)T(12)T(13)T(14)T(16)T(1):W(T)=197+30+25+20+160+25+110+70+20+130+27+197=1011由昆明出發(fā)，進(jìn)行云南省內(nèi)旅游，根據(jù)游客的喜好，可以有很多種不同的路線供選擇。但是，從消費(fèi)者的角度看：a、選擇途經(jīng)最多的旅游景點(diǎn)，盡量不重復(fù)，節(jié)約開銷；b.每個(gè)景點(diǎn)都要旅游，盡管有路線的重復(fù)；C、通過尋找最小生成樹的方法，找到一條最優(yōu)線路。對已問題a：(1)T(5)T(6)T(4)T(3)T(7)T(9)T(10)T(11)T(12)T(13)T(14)T(16)T(1)，相應(yīng)權(quán)值之和為W(T)=197+30+25+38+26+20+160+25+110+70+20+130+27=878因此，滿足問題a的旅游線路如圖a所示。5)30⑹(11)（⑷對于問題b：Il:路線為：(1)T⑸T⑹T⑷T⑶T⑺T⑻T(7)T⑼T(10)T(11)T(12)T(13)T(14)T(16)T(17)T(16)T(1)T(15)T(1)T(2)T(1)W(T)=197+30+25+38+26+20+20+20+150+25+110+70+20+130+90+90+27+30+44+44=1206該無向圖的可達(dá)矩陣為:11001000000000110C：100110000110011010011000011001100001001101000000000000000000000000000000000000000000000000000100100010001000011101100101000100000000000000000000000000000000000000000000000000000000000010001100111001110011000100000000000001100000000000000000000000000000000000000000000010001100010010110011通過尋找最小生成樹的方法，找到一條最優(yōu)線路。W(T)=30+25+25+20+26+20+32+44+25+110+25+27+30+70+20+90=619綜上所述rW(T)=878選擇圖a的旅游路線最優(yōu)a.選擇途經(jīng)最多的旅游景點(diǎn)，盡量不重復(fù)，節(jié)約開銷。W(T)=1206選擇圖b的旅游路線最優(yōu)b.每個(gè)景點(diǎn)都要旅游，盡管有路線的重復(fù)。W(T)=619選擇圖c的旅游路線最優(yōu)c.通過尋找最小生成樹的方(法，找到一條最優(yōu)線路。五、模型推廣該模型可以推廣到解決用最節(jié)省的經(jīng)費(fèi)建立通信網(wǎng)絡(luò)的實(shí)際問題上。如：假設(shè)要在n個(gè)城市之間建立通信聯(lián)絡(luò)網(wǎng)，則聯(lián)通n個(gè)城市需要n-1條線路，那么怎樣才能用最節(jié)省的經(jīng)費(fèi)建立通信網(wǎng)絡(luò)？

注釋：圖中的①②③④⑤⑥為城市代號；圖中兩個(gè)城市代號之間的數(shù)字代表修通信網(wǎng)的經(jīng)費(fèi)比例上圖經(jīng)過模型變換后得到以下的模型：六、參考文獻(xiàn)1、數(shù)學(xué)模型引論，E.A。Bender著，朱堯辰、徐偉宣譯，科學(xué)普及出版社(1982).2、數(shù)學(xué)模型，［門］近藤次郎著，官榮章等譯，機(jī)械工業(yè)出版社，(1985).3、微分方程模型，(應(yīng)用數(shù)學(xué)模型叢書第1卷)，［美］W.F.Lucas主編，朱煜民等譯，國防科技大學(xué)出版社，(1988).4、政治及有關(guān)模型，(應(yīng)用數(shù)學(xué)模型叢書第2卷)，［美W.F.Lucas主編，王國秋等譯，國防科技大學(xué)出版社，(1996).5、離散與系統(tǒng)模型，(應(yīng)用數(shù)學(xué)模型叢書第3卷)，［美w.F.Lucas主編，成禮智等譯，國防科技大學(xué)出版社，(1996)．附錄］昆明景點(diǎn)石林,民族村,九鄉(xiāng)風(fēng)景區(qū),金殿,大觀公園,世界園藝博覽園,騰沖火山國家公園,西山森林公園,巖泉風(fēng)景區(qū)紅河景點(diǎn)建水燕子洞,朱家花園,彌勒白龍洞,煥文公園,元陽,建水古城,彌勒湖泉生態(tài)園,元陽梯田,紅河學(xué)院,元陽風(fēng)光大理景點(diǎn)崇圣寺三塔,南詔風(fēng)情島,新華民族村,天鏡閣,洱海公園,漾濞石門關(guān)，劍川滿賢林景區(qū),彌度縣東山森林公園,大理古城,蒼山麗江景點(diǎn)玉龍雪山,麗江古城,束河古鎮(zhèn),玉水寨,文筆山景區(qū),文海,瀘沽湖四方街,白水河迪慶景點(diǎn)梅里雪山,碩都湖,霞給藏族文化村旅游景,天生橋溫泉,納帕海,民族服飾旅游展演中心,中甸藏經(jīng)閣景點(diǎn),博物館,中甸,香格里拉?曲靖景點(diǎn)陸良彩色沙林,羅平多依河,珠江源,羅平,沾益海峰濕地,羅平油菜花海,九龍瀑布,南盤江,曲靖師范學(xué)院,爨寶子碑楚雄景點(diǎn)武定獅子山，元謀土林旅游景區(qū)，太陽歷公園，永仁方山景區(qū)，牟定化佛山,彝人古鎮(zhèn),元謀人遺址,紫溪山森林公園,祿豐恐龍博物館,盤龍寺西雙版納景點(diǎn)原始森林公園,傣族園,熱帶花卉園,中科院熱帶植物園,野象谷,勐景來旅游景區(qū),民族風(fēng)情園,曼聽公園,猴山景區(qū),打洛獨(dú)樹成林怒江景點(diǎn)六庫,三江并流,怒江大峽谷,丙中洛,貢山,三江并流風(fēng)景區(qū),秋那桶，怒江，碧羅雪山,蘭坪羅古箐保山景點(diǎn)騰沖熱海國家重點(diǎn)風(fēng)景...,騰沖和順景區(qū),龍陵邦臘掌度假區(qū),騰沖疊水河景區(qū),北廟湖公園,太保公園,沖云峰山景區(qū),和順僑鄉(xiāng),北海濕地，騰沖景區(qū)昭通景點(diǎn)大關(guān)黃連河,水富縣西部大峽谷溫泉…,大山包,鹽津豆沙關(guān),觀斗山石雕,僰［b6］人懸棺,鹽津火車站,昭通機(jī)場,孟孝琚碑,彝良火車站玉溪景點(diǎn)匯龍生態(tài)園,映月潭修閑文化中心通海秀山歷史文化公園,通海秀山公園，華寧象鼻溫泉度假村,易門龍泉森林公園,撫仙湖,紅塔山,李家山青銅器,聶耳故居思茅景點(diǎn)梅子湖公園，小黑江森林公園，墨江北回歸線標(biāo)志園，瀾滄江，哀勞山，梅子湖,思茅機(jī)場,白塔,遷糯佛寺臨滄景點(diǎn)滄源崖畫,云縣漫灣百里長湖景區(qū),西門公園,五老山國家森林公園鳳慶鳳山公園,茶文化風(fēng)景園,滄源佤山,臨滄機(jī)場,廣允緬寺德宏景點(diǎn)瑞麗市莫里熱帶雨林景…,潞西市勐巴娜西珍奇園,南甸宣撫司署,瑞麗旅游淘寶場,潞西市勐巴娜西大花園,盈江凱棒亞湖景區(qū),瑞麗,三仙洞,瑞麗姐勒佛塔文山景點(diǎn)邱北普者黑風(fēng)景區(qū),硯山浴仙湖,富寧馱娘江景區(qū),西華公園,麻栗坡烈士陵園,普者黑,麻栗坡老山,官寨附錄II最小生成樹的實(shí)現(xiàn)代碼如下：voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){struct{VerTypeadjvex;VRTypelowcost;}closedge[MAX_VERTEX_MUM];K=LocateVex(G,u);for(j=0;j<G.vexnum;j++)if(j!=k)closedge[j]={u,G.arcs[k][j].adj};closedge[k].lowcost=0;for(i=1;i<G.vexnum;++i){k=minimum(closedge);closedge[k].lowcost=MIN{closedge[v].lowcost|closedge[v].loiiwcost〉0,vWV-U}iprintf(closedge[k].adjvex,G.vexs[k]);closedge[k].lowcost=0;for(j=0;j<G.vexnum;++j)if(G.arcs[k][j].adj<closedge<[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj}}}

云尚的縣齡馬備W呑搭叫［也昴勒^llUllq.昌扁,缺/"雙版納棒族自治斟d云尚的縣齡馬備W呑搭叫［也昴勒^llUllq.昌扁,缺/"雙版納棒族自治斟d遜：江嘶可傑一輕ljn-s平逆茁甫歇?jiǎng)澨m坪白處豎￡y米護(hù)宜欷爲(wèi)）釧I豆帆床和嘶對4臨滄地氐?<7Joi&Sf