最佳旅游線路的數(shù)學(xué)模型

【摘要】本文通過(guò)對(duì)自駕游云南的幾個(gè)旅游景點(diǎn)，求出了最正確旅游線路的數(shù)學(xué)模型，為旅游者設(shè)計(jì)旅游線路提供有一定價(jià)值的參考。首先，本文對(duì)所求問(wèn)題做出合理假設(shè)，然后運(yùn)用“分枝定界法”建立并尋找最正確旅游線路的圖論模型使問(wèn)題簡(jiǎn)單明了，并充分利用線性規(guī)劃建立模型，得出了最優(yōu)的線路設(shè)計(jì)，最后提出該模型的算法及求解過(guò)程?！娟P(guān)鍵字】分枝定界法Floyd〔弗勞德〕算法哈密頓圈旅游線路一、問(wèn)題重述云南是我國(guó)的旅游大省，擁有豐富的旅游資源，吸引了大批的省外游客，旅游業(yè)正在成為云南的支柱產(chǎn)業(yè)。隨著越來(lái)越多的人選擇到云南旅游，旅行社也推出了各種不同類型的旅行路線，使得公眾的面臨多條線路的選擇問(wèn)題。某一個(gè)從沒(méi)有到過(guò)云南的人準(zhǔn)備在假期帶家人到云南旅游，預(yù)計(jì)從昆明出發(fā)，并最終返回昆明，且旅行者采取自駕游的旅行方式。二、符號(hào)說(shuō)明1、，：加權(quán)圖的頂點(diǎn)即云南各旅游景點(diǎn)；2、：各景點(diǎn)間的距離構(gòu)成的矩陣；3、：各景點(diǎn)間的距離構(gòu)成的矩陣中每一行減去該行的最小的元素及每一列減去該列的最小元素后所構(gòu)成的矩陣；4、：加權(quán)圖的邊，即權(quán)，表示兩景點(diǎn)間的距離；5、：為任意兩頂點(diǎn)與頂點(diǎn)在圖中最短路徑長(zhǎng)度。三、模型假設(shè)1、假設(shè)旅游者在各景點(diǎn)的逗留時(shí)間、花費(fèi)等都相同；2、旅游者最終要返回昆明，假設(shè)昆明是旅游者要去的一個(gè)旅游景點(diǎn)；3、假設(shè)旅游者所經(jīng)過(guò)的公路是同一等級(jí)公路，在汽車恒速及單位路程所耗油量相同的條件下，各景點(diǎn)的路程與時(shí)間及耗油量成正比，即在較短時(shí)間及較低耗油量?jī)?nèi)，旅游較多景點(diǎn)，為此我們制定一條路線使得路程最短，這樣就能使旅游者花費(fèi)時(shí)間最短而耗油量又最低得情況下旅游相同的景點(diǎn)。四、模型建立與求解1、根據(jù)旅游者采取的是自駕游的旅行方式，我們可以得到云南省局部旅游景點(diǎn)的交通路線中〔自駕游可以自選路線，每?jī)蓚€(gè)旅游景點(diǎn)間都有可行路程〕每?jī)删包c(diǎn)間的路程，任意兩旅游景點(diǎn)間的路程如下表所示〔單位：公里〕：昆明大理麗江石林西雙版納瀘沽湖香格里拉昆明031950285542567629大理3190183397854448314麗江50218305811037260178石林853975810603654707西雙版納5428541037603012261164瀘沽湖56744826065412260434香格里拉62931417870711644340表1各旅游景點(diǎn)間的路程表下列圖是云南省旅游景點(diǎn)地圖：圖1云南省旅游景點(diǎn)圖由上面的地圖可畫(huà)出所給旅游景點(diǎn)的路線圖如下：香格里拉麗江大理香格里拉麗江大理瀘沽湖昆明石林西雙版納由表1和圖1可得到加權(quán)無(wú)向圖圖2如下：71712345662931954256785314397854448183581103717826060370765412261164434502注：1.昆明2.大理3.麗江4.石林5.西雙版納6.瀘沽湖7.香格里拉2、“分枝定界法”模型：用階矩陣中的各個(gè)元素來(lái)表示各個(gè)景點(diǎn)之間的距離，且各個(gè)景點(diǎn)之間的距離是沒(méi)有方向的，那么階矩陣是對(duì)稱型矩陣,中的所有元素減去該行的最小非零元素，得到新的矩陣，再抽取矩陣每列的最小非零元素，并令矩陣各列的所有元素減去該列的最小非零元素，得到新的矩陣，這樣得到矩陣是每行每列都至少有一個(gè)零元素存在。然后，選擇起點(diǎn)與某景點(diǎn)之間距離為零的元素，把這個(gè)元素所在的行和列從矩陣中劃去，得到新的矩陣，同時(shí)，把起點(diǎn)與某景點(diǎn)組成一條路。對(duì)矩陣重復(fù)矩陣變化到矩陣的步驟操作，得到新的景點(diǎn)參加到最近路的末頂點(diǎn)的后面，使其成為一條新路。直到得到的最后矩陣是，且這條路包含所有的景點(diǎn)，所有的景點(diǎn)在這條路上只能出現(xiàn)一次，這樣操作才算停止，否那么重復(fù)上面的步驟。3、“分枝定界法”模型求解，用“分枝定界法”尋找近似最正確旅游線路的算法如下：步驟1：用Floyd算法求任意兩景點(diǎn)之間的距離，構(gòu)建一個(gè)加權(quán)無(wú)向圖，每條邊的權(quán)叫為頂點(diǎn)與頂點(diǎn)在圖中最短路徑長(zhǎng)度。步驟2：隨機(jī)搜索加權(quán)無(wú)向圖中已指定的起點(diǎn)的假設(shè)干個(gè)哈密頓圈，或者找出它的任意一個(gè)初始的哈密頓圈。步驟3：用二邊逐次修改法對(duì)步驟2中的哈密頓圈進(jìn)行優(yōu)化，從而得到近似最正確的哈密頓圈。步驟4：比擬上述哈密頓圈，找出權(quán)值最小的一個(gè)，即為所要找的最正確哈密頓的近似解。4、“分枝定界法”模型求解的具體過(guò)程：123456712345671234567由“分枝定界法”的模型建立和矩陣算法，選擇一條路，并令再把矩陣的第一行，第四列劃去，得到矩陣:123567123567123567從矩陣中，可以選擇頂點(diǎn)5添加在路中，那么有路，將第一行，第四列劃去，令得：123671236712367從矩陣中，選擇將頂點(diǎn)2添加到路，即得到路，將第一行，第二列劃去，令得1367將頂點(diǎn)3添加到路上得路，將第一行，第二列劃去并令得：167將頂點(diǎn)7添加到路上得路，將第一行第三列劃去，并令得：16最后將頂點(diǎn)6添加得，從而可得總權(quán)數(shù)最小的哈密頓圈，即總權(quán)數(shù)為2904。所以最正確的旅游路線是：昆明石林西雙版納大理麗江香格里拉瀘沽湖昆明。五、模型推廣在模型求解過(guò)程中，我們可以應(yīng)用“最鄰近插入法”，0-1變量等方法尋找近似的最正確旅游線路，對(duì)景點(diǎn)較少而言，具體操作過(guò)程簡(jiǎn)單，但對(duì)有較多的景點(diǎn)時(shí)，具體操作過(guò)程比擬復(fù)雜，因此用這種方法尋找近似最正確的旅游線路存在一定的缺陷。而用“分枝定界法”尋找近似的最正確旅游線路，能在有限的時(shí)間內(nèi)根據(jù)個(gè)人條件盡可能游覽較多的景點(diǎn)，是游客所關(guān)心的問(wèn)題。該模型能尋找出較多景點(diǎn)的最正確旅游線路，并用Floyd〔弗勞德〕算法更簡(jiǎn)單快捷的求解問(wèn)題。六、模型評(píng)價(jià)為了尋找最正確旅游路線的問(wèn)題，在“最鄰近插入法”，0-1變量法和“分枝定界法”中，0-1變量法是用代數(shù)的方法轉(zhuǎn)化為lindo或lingo中求解，“最鄰近插入法”和“分枝定界法”均是將其轉(zhuǎn)化為在給定加權(quán)無(wú)向圖中尋找總權(quán)數(shù)最小的哈密頓圈。但由于求解的模型和算法不同，“最鄰近插入法”的求解過(guò)程更為直觀、便于理解，而“分枝定界法”在景點(diǎn)較多的情況下，可通過(guò)計(jì)算機(jī)編程求解。所以，在實(shí)踐中運(yùn)用“分枝定界法”來(lái)尋找近似的最正確旅游線路更有優(yōu)勢(shì)。一般來(lái)說(shuō)，一個(gè)整數(shù)規(guī)劃問(wèn)題的可行解或是無(wú)限或是有限的。對(duì)于有限的可行解來(lái)說(shuō)，我們自然想到列舉法〔或稱枚舉法〕，把所有可能的整數(shù)可行解組合列出來(lái)，然后得到目標(biāo)函數(shù)的最優(yōu)值和最優(yōu)解。但是如果斷策變量很多或整數(shù)可行解組合多得驚人時(shí)，列舉法就沒(méi)有實(shí)用價(jià)值了。因此，就要尋求一種可行方法，使之僅檢查局部整數(shù)可行解組合，從而得出最優(yōu)的整數(shù)解。分枝定界法〔branchandboundmethod〕就是其中一種，它靈活且便于用計(jì)算機(jī)求解，是解整數(shù)規(guī)劃的重要方法。七、參考文獻(xiàn)[1]周溪召主編.運(yùn)籌學(xué)及應(yīng)用.——北京：化學(xué)工業(yè)出版社，2009.1[2]王文平等編著.運(yùn)籌學(xué).——北京：科學(xué)出版社，2007[3]栗雪娟，崔尚森，張柯．最正確旅游路線選擇的神經(jīng)網(wǎng)絡(luò)方法[J]．交通與計(jì)算機(jī)，2006[4]張杰，周碩主編；邢麗娟等編寫(xiě).運(yùn)籌學(xué)模型與實(shí)驗(yàn).——北京：中國(guó)電力出版社，2007