運籌學關于武漢旅游線路最佳

PAGEPAGE15目錄一. 學習運籌學的心得 3（一）線性規(guī)劃 3（二）對偶理論與靈敏度分析 3（三）運輸問題 4（四）整數(shù)規(guī)劃： 4二．旅游線路的優(yōu)化設計 4三.研究報告 41.問題描述 51.1背景描述 51.2研究意義 51.3對題目的理解 52.資料數(shù)據(jù)的收集和整理 63.數(shù)學模型的建立、計算 83.1模型建立背景 83.2模型假設 83.3符號說明 83.4模型的建立 93.4.1第一天旅游最優(yōu)路線影響消費的因素 93.4.2第一天旅游最優(yōu)路線目標函數(shù)的確定 93.4.3第一天旅游最優(yōu)路線約束條件的確定 103.4.4第二天旅游最優(yōu)路線影響景點數(shù)的因素 113.4.5第二天旅游最優(yōu)路線目標函數(shù)的確定 113.4.6第二天旅游最優(yōu)路線約束條件的確定 113.4.7第二天旅游最優(yōu)路線模型建立 123.4.8模型求解與結果分析 124.結果分析 135.結論 146.模型推廣與應用 147.參考文獻 148.附錄 15學習運籌學的心得大三上學期我們第一次學習了與運籌學相關的科目-線性規(guī)劃(運籌學的一個重要分支),這也是我們初次認識到運籌學這一課程,讓我們對運籌學有了初步了解并深入學習,大三下學期我們更進一步的學習了運籌學,從他的由來到發(fā)展,到更深入運用運籌學知識來解決生活中的實際問題,原料分配、收發(fā)平衡型的運輸問題、LP問題、ILP問題以及對偶問題?，F(xiàn)在的我們會用簡單的方法來處理一些問題,通過深入學習我們更希望獲得更多學習處理這一類問題的方法,從線性規(guī)劃問題到建立數(shù)學模型,這些都需要我們來細細學習,認真對待。綜合種種可以定義，從最直觀、明了的角度將運籌學定義為：“通過構建、求解數(shù)學模型，規(guī)劃、優(yōu)化有限資源的合理利用，為科學決策提供量化依據(jù)的系統(tǒng)知識體系?！?/p>

運籌學的具體內(nèi)容包括：規(guī)劃論（包括線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃和動態(tài)規(guī)劃）、庫存論、圖論、決策論、對策論、排隊論、、博弈論、可靠性理論等?！妒酚洝じ咦姹炯o》有云：“夫運籌帷幄之中，決勝千里之外”。運籌學的英文名原名為Operations

Research，由此可見運籌學主要在于“研究（Research）”，研究在經(jīng)營管理等活動中該如何行動，如何以盡可能小的代價，獲取盡可能好的結果，即所謂“最優(yōu)化”的問題。中國學者把這門學科意譯為“運籌學”，便是取自古語“運籌帷幄，決勝千里”之意，運算籌劃，出謀獻策，從而以最佳策略取勝。這就極其恰當?shù)馗爬诉@門學科的精髓。在現(xiàn)代商業(yè)社會中，人們更加講求運籌學的應用。作為一名數(shù)學院的學生，為了使自己未來的人生中更有勝算，讓自己步入社會后更具備優(yōu)勢競爭力，就更應該盡可能地去熟練地掌握、運用運籌學的精髓，用運籌學的思維去思考問題。那么，我就必須抓住運籌學的特點：利用數(shù)學、管理科學、計算機科學技術等研究事物的數(shù)量化規(guī)律，應用分析、試驗、量化的方法，對實際生活中人、財、物、時、空、信息等有限資源進行統(tǒng)籌安排和充分合理的運用。（一）線性規(guī)劃它是運籌學的一個重要分支。線性規(guī)劃解決的是：在資源有限的條件下，為達到預期目標最優(yōu)，而尋找資源消耗最少的方案。其數(shù)學模型由目標函數(shù)和約束條件組成。解決線性規(guī)劃問題的關鍵是找出它的目標函數(shù)和約束方程，并將它們轉化為標準形式。簡單的設計兩個變量的線性規(guī)劃問題可以直接運用圖解法得到。但是在現(xiàn)實生活中，線性規(guī)劃問題往往涉及到的變量很多，很難用作圖法實現(xiàn)，而運用單純形法卻比較方便。單純形法的發(fā)展很成熟，應用也很廣泛，在運用單純形法時，需要先將問題化為標準形式，求出基可行解，列出單純形表，進行單純形迭代，當所有的變量檢驗數(shù)不大于零，且基變量中不含人工變量時，計算就算結束。將所得的量的值代入目標函數(shù)，便可得出最優(yōu)值。

（二）對偶理論與靈敏度分析1、每一個線性規(guī)劃問題都會有與之伴隨的另一個問題，若一個問題稱為原問題，則另一個稱為其對偶問題，原問題和對偶問題有著非常密切的關系，以至于可以根據(jù)一個問題的最優(yōu)解，得出另一個問題的最優(yōu)解的全部信息。

對偶問題分為對稱形式和非對稱形式兩種。非對稱形式的對偶問題需要將原問題變?yōu)闃藴市问剑缓笳页鰳藴市问降膶ε紗栴}，因為對偶問題存在特殊的基本性質(zhì)，所以在解決實際問題比較困難時，可以將其轉化為對偶問題進行求解；

2、靈敏度分析是分析在線性規(guī)劃問題中，一個或幾個參數(shù)的變化對最優(yōu)解的影響問題?？梢苑治瞿繕撕瘮?shù)中變量系數(shù)、約束條件的右端項、增加一個約束變量、增加一個約束條件、約束條件的系數(shù)矩陣中的參數(shù)值等的變化。如果將問題轉化為研究參數(shù)值在保持最優(yōu)解或最優(yōu)基不變時的允許范圍或改變到某一值時對問題最優(yōu)解的影響時，就屬于參數(shù)線性規(guī)劃的內(nèi)容。

（三）運輸問題是解決多個產(chǎn)地和多個銷地之間的同品種物品的規(guī)劃問題。根據(jù)運輸問題的獨特性，一般采用一種簡單而有效的方法：表上作業(yè)法。表上作業(yè)法先找出運輸問題的基可行解，方法有：最小元素法、西北角法、沃格爾法。其中沃格爾法得出的解最接近最優(yōu)解。然后利用閉回路法或?qū)ε甲兞糠▽Φ玫浇膺M行最優(yōu)性判別。當檢驗的結果為非最優(yōu)解時，進行解的改進，然后再進行最優(yōu)性判別，直到所有的非基變量檢驗數(shù)全非負，得到最優(yōu)解。在解決運輸問題時會遇到產(chǎn)銷不平衡的情況，在該情況下，要將該問題轉化為產(chǎn)銷平衡問題，只需增加一個假象的產(chǎn)地或銷地，并將表示該地的變量在目標函數(shù)中的系數(shù)設為零即可。

（四）整數(shù)規(guī)劃：是解決決策變量只能取整數(shù)的規(guī)劃問題，整數(shù)規(guī)劃的解法有割平面法和分支定界法。整數(shù)規(guī)劃中的0-1規(guī)劃整數(shù)問題是一個非常有用的方法。在實際問題中，該方法能夠解決很多問題。0-1整數(shù)規(guī)劃的解決方法有枚舉法和隱枚舉法。指派問題是0-1整數(shù)規(guī)劃中的特例，現(xiàn)在采用的解法一般為匈牙利法，由于指派問題的特殊性，使用匈牙利法可以有效的減少計算量。

二．旅游線路的優(yōu)化設計武漢市旅游景點路線的設計摘要旅游線路設計是旅游規(guī)劃設計的一部分，當今旅游線路設計的成果研究還比較少，大部分重實際，輕理論。對于一個旅游者而言，對旅游路線的期望是最大化的滿足其消費需要，即時間最短，成本最小，玩得開心。本文著重圍繞運籌學在旅游線路規(guī)劃中的運用來發(fā)掘運籌學在旅游規(guī)劃設計中的潛力，探討旅游路線的優(yōu)化問題。本文主要研究最佳旅游路線的設計問題。在滿足相關約束條件的情況下，花最少的錢游覽盡可能多的景點是我們追求的目標?；趯Υ说难芯?，建立數(shù)學模型，設計出最佳的旅游路線。本問題主要是解決兩方面的問題：（1）、（2）兩問是在時間或旅游費用不限的情況下，游完十個景點怎樣才可以做到費用最省或是時間最省；（3）、（4）、（5）問是在旅游時間或是旅游費用或是兩者都有約束條件的情況下，怎樣才可以玩更多的地方。關鍵詞：運籌學；旅游線路規(guī)劃；最短時間三.研究報告正文問題描述隨著人們生活水平的提高，旅游逐漸成為最熱門的戶外活動之一。在旅游的過程中，我們不僅可以感受大自然之美、放松心情，而且可以領略不同地方的文化氣息、拓寬視野。旅游者在今年五月一日8點之后從武昌火車站出發(fā)，到武漢市一些著名景點旅游，最后回到出發(fā)點。由于跟團旅游會受到限制，旅游者打算自己背包出游。出行路途中有以下幾個條件：（A）跨區(qū)交通出行可以乘公汽、長途汽車或地鐵（不允許包車或包及），并且車票可預定到。（B）市內(nèi)交通出行可乘公交車（含專線大巴、小巴）、地鐵或出租車。（C）旅游費用以網(wǎng)上公布為準，具體包括交通費、住宿費、景點門票（第一門票）。晚上20：:00至次日早晨7：:00之間，如果在某地停留超過6小時，必須住宿，住宿費用不超過200元/天。吃飯等其它費用60元/天。（D）假設景點的開放時間為8:00至18:00.根據(jù)以上條件考慮到旅游者的以下需求：1、在時間不限的情況下，游覽全部景點，旅游費用最??；2、在旅游費用不限的情況下，游覽全部景點，旅游時間最短；3、在旅游費用一定的情況下，游覽盡可能多的景點；4、在時間一定的情況下，游覽盡可能多的景點； 5、在時間和旅游費用都一定的情況下，游覽盡可能多的景點。針對以上幾種情況，建立相關的數(shù)學模型并為該旅行者設計詳細的行程表，行程表中應包括具體的交通信息（車次、起止時間、票價等）、賓館地點和名稱，門票費用，在景點的停留時間等信息。1.1背景描述現(xiàn)如今社會發(fā)展迅速，生活節(jié)奏不斷加快，對于大多數(shù)旅游者來說，在舒適度不受影響或者體力許可的前提下，能花費較少的費用和較少的時間而盡可能游覽更多的風景名勝，是他們的最大愿望。一個旅游區(qū)域內(nèi)的若干景點各在不同的空間位置，對這些景點游覽或活動參與的先后順序與連接方式，可有多種不同的串連方式，由此產(chǎn)生組合成不同的旅游線路。于是，我們?nèi)绾谓鉀Q讓游客實現(xiàn)最大愿望這個問題可以轉化為如何實現(xiàn)旅游成本最小化和路線最優(yōu)化的問題。1.2研究意義武漢市是中國西部最大的城市，具有獨天得厚的自然人文資源。對于這樣一個優(yōu)秀的旅游城市，其景點很多，交通路線復雜，如果就這樣盲目的進行游玩，則很有可能造成費用高，游覽景點少，且玩不盡興的遺憾。如果我們運用運籌學的方法將其旅游路線進行規(guī)劃，并結合實際背景，尋求出最佳方案，這樣可以充分滿足一個旅游者的需求，達到旅游路線最優(yōu)化的目的。1.3對題目的理解首先我們知道本問題屬于旅游路線的優(yōu)化問題。為了建立模型，首先應將各景點線路轉化為純數(shù)學形式的點線集合，進行圖論方面的分析。本問題主要是解決兩方面的問題：（1）、（2）兩問是在時間或旅游費用不限的情況下，游完十個景點怎樣才可以做到費用最省或是時間最省；（3）、（4）、（5）問是在旅游時間或是旅游費用或是兩者都有約束條件的情況下，怎樣才可以玩更多的地方。第一方面根據(jù)對第一方面問題的分析可知，問題目的在于當時間（費用）不限的情況下求游完所有景點并回到出發(fā)地點所用的費用（時間）的最小值。該問題屬于旅行商問題（TravelingSalesmanProblem,TSP）。為了建立數(shù)學模型，首先應該將各個景點轉化為純數(shù)學形式的點線的集合，進行圖論方面的分析。下面給出旅行商問題的定義：旅行商問題：一位銷售商從N個城市的某個城市出發(fā)，不重復的走完其余N-1個城市并回到原出發(fā)點，在所有可能路徑中求出路徑長度最短的一條。用數(shù)學語言描述TSP，即給定一組N個城市和它們兩兩之間的直達距離，尋找一條閉合的旅程，使得每個城市剛好經(jīng)過一次且總的旅行距離最短。用圖語言描述TSP：給出一個圖G=（V，E），每邊上有非負權值w（e），尋找G的Hamilton圈C，使得C的總權最小。TSP問題是一個典型的組合優(yōu)化問題，其可能的搜索路徑隨著城市數(shù)目N的增加呈指數(shù)增長，屬于NP完全問題。了解了以上只是后，我們更加確定了該問題就是旅行商問題。只是在實際的處理中，我們把兩景點的最省路費（最短時間）最為賦權值w（e），在一定程度上，各景點間的距離與兩點間的單程最省路費（單程最短時間）是成正比的，所以把兩景點的最省路（最短時間）作為權值w（e）是可行的。第二方面這一方面要解決的問題是在費用（時間）有限制或兩者都有限制的情況的情況下觀賞的景點近可能多，根據(jù)這種要求可從以下方案入手：建立多目標規(guī)劃模型，通過適當?shù)臄M合或線性加權，把多目標轉化為單目標資料數(shù)據(jù)的收集和整理（1）以下為各個景點間的直達公交路線。起點終點公交路線票價耗時所經(jīng)站次步行距離武昌火車站黃鶴樓101.5103604022932061193105291.51262407172135720561282510722182590905581420556282530電車4119860武昌火車站歸元寺61125650072212739805362233960武昌火車站晴川閣561236740武昌火車站江漢路步行街4022348680武昌火車站湖北省博物館4022802150武昌火車站東湖磨山4022113314500武昌火車站光谷步行街5932351226073824120220901內(nèi)環(huán)3307680592331164051813513220武昌火車站武漢大學5641248160901內(nèi)環(huán)3184100090721841100593219611005921961100518118713006612081300黃鶴樓歸元寺4012184170黃鶴樓晴川閣108122530黃鶴樓江漢路步行街40222555306412768206081274420晴川閣歸元寺55921055704511155605321115560711210568055321056505351.510567080321056805311137660561284100010819410006481115910晴川閣江漢路步行街5532145110532116555055911128104511138107112113870歸元寺江漢路步行街7272175520241175520598216454055912074704512184707072186550711223957055322310460武漢大學湖北省博物館810221920湖北省博物館東湖磨山402234104500湖北省博物館光谷步行街70914616580東湖磨山光谷步行街4012178680景點名稱開放時間票價建議游玩時間黃鶴樓夏：7：00~18:30804冬：7:30~17:30紅樓9:00~17:0002晴川閣9:00~16:3002歸元寺8:00~17:00101.5江漢路步行街全天03武漢大學全天03湖北省博物館9:00~17:0005東湖7:00~19:00406光谷步行街全天03數(shù)學模型的建立、計算3.1模型建立背景根據(jù)武漢地圖，相關旅游資料及以上數(shù)據(jù)分析，可把武漢旅游路線分兩天進行，第一天以長江大橋為中心，游玩四周景點，且因黃鶴樓與紅樓毗鄰，步行幾百米就可到達，故把紅樓歸納為黃鶴樓景點；第二天以武大為中心，游覽附近景點。資料顯示的公交路線僅考慮景點間的直達路線，未有換乘現(xiàn)象，表上選取的數(shù)據(jù)均綜合考慮各線路的票價，運行時間及步行距離而得。3.2模型假設1、在旅游期間，天氣晴朗，列車和航班沒有延誤并且準時到站，市內(nèi)交通也沒有出現(xiàn)長時間的堵塞2、該旅游者是成年人，不考慮學生票的問題3、旅游者在兩地旅游來回時間和路上花的費用是相同的3.3符號說明圖1V1代表武昌火車站，V2代表黃鶴樓，V3代表歸元寺，V4代表晴川閣，V5代表江漢路步行街圖2：V1代表武昌火車站，V2代表武大，V3代表省博物館，V4代表東湖磨山，V5代表光谷3.4模型的建立第一天游玩的路線如圖1表示，弧旁數(shù)字代表通過該段路線所需的最短時間Min。現(xiàn)有五個旅游景點V1、V2…..V5，現(xiàn)在我們從V1出發(fā)到V5;對于第二天，游玩的路線如圖2所示，求在兩天中哪條路所花費的時間最短，并且能玩較多的景點。圖1圖23.4.1第一天旅游最優(yōu)路線影響消費的因素路費路費住宿費基本消費門票費總費用3.4.2第一天旅游最優(yōu)路線目標函數(shù)的確定用Lij表示i景點到j景點的途中花費，并引入路線決策變量Xij1經(jīng)過i到j的路段0不經(jīng)過i到j的路段Xij=1經(jīng)過i到j的路段0不經(jīng)過i到j的路段用Pj表示j地區(qū)景點的第一門票費用，T表示在景點所在地區(qū)停留的時間則總費用，則目標函數(shù)為：3.4.3第一天旅游最優(yōu)路線約束條件的確定

由于每個景點只能有一條邊出去，所以對j景點Xij之和影等于1，既：i=1,211同理，每個景點只能有一條邊進去，所以對i景點Xij之和也應等于1，既:i=1,2……11應該注意的是，除了起點和終點（都是武昌火車站）以外，各邊不構成Hamilton圈。通過對武漢的一些旅行社進行咨詢，我們得出在第個景點的最佳逗留時間和在第個景點總消費：t1t2t3t4t5t6t7t8t9t10t1172418123630129152417(單位：小時)c1c2c3c4c5c6c7c8c9c10c1112042330013537839017590148303241(單位：元)從而根據(jù)模型，使用Lingo編程，得出結果如下表：旅游景點數(shù)n234每人總花費m（單位：元）250406623路線1→8→11→9→8→11→4→8→9→1旅游景點數(shù)n56每人總花費m（單位：元）9491207路線1→8→9→7→4→11→4→11→7→9→8→1旅游景點數(shù)n7每人總花費m（單位：元）1534路線1→4→10→11→7→9→8→1（其中數(shù)字1—11分別表示武昌火車站、黃鶴樓、歸元寺、晴川閣、江漢路步行街、武大、省博物館、光谷、東湖磨山）變量是1的變就是最短時間通過的邊，即V1-V3-V5，最短時間是38分鐘。3.4.4第二天旅游最優(yōu)路線影響景點數(shù)的因素旅途坐車費用旅途坐車費用住宿、基本費用門票費用不多于200元的費用費用3.4.5第二天旅游最優(yōu)路線目標函數(shù)的確定假設總費用未知，但滿足條件（<=2000元），用M表示用Pij表示i景點和j景點的門票費用之和，（單位：元）（i=1，2……10）用Lij表示i景點到j景點的途中花費，并引入路線決策變量Xij1經(jīng)過i到j的路段1經(jīng)過i到j的路段0不經(jīng)過i到j的路段Xij=用C表示旅游的景點數(shù)目則最多景點數(shù)，既目標函數(shù)為：C=3.4.6第二天旅游最優(yōu)路線約束條件的確定由于M=車費+基本費用+門票費，因此用函數(shù)表示為：M=由于每個景點只能有一條邊出去，所以對j景點Xij之和影等于1，既：或0i=1,211同理，每個景點只能有一條邊進去，所以對i景點Xij之和也應等于1，既：或0i=1,2……11應該注意的是，除了起點和終點（都是徐州）以外，各邊不構成Hamilton圈。3.4.7第二天旅游最優(yōu)路線模型建立 綜上所述，我們可以得到總的模型為：Min約束條件：+360（，=1，2，……，11）（，=1，2，……，11）（，=2，3，……，11）3.4.8模型求解與結果分析旅游景點數(shù)n234每人總花費c（單位：元）229370573路線1→8→11→8→9→11→9→8→4→1旅游景點數(shù)n56每人總花費c（單位：元）9271160路線1→4→8→9→7→11→4→8→9→7→11→1旅游景點數(shù)n7每人總花費c（單位：元）1412路線1→8→9→7→11→10→4→1（其中數(shù)字1—11分別表示武昌火車站、黃鶴樓、歸元寺、晴川閣、江漢路步行街、武大、省博物館、光谷、東湖磨山）圖中變量是1的變就是最短時間通過的邊，即V1-V2-V3-V5，最短時間是91分鐘。4.結果分析分析第一天旅游路線：由計算結果可知，最短時間路徑為從武昌火車站（以下簡稱火車站）出發(fā)經(jīng)歸元寺最后到達江漢路步行街（以下簡稱江漢路），途中僅游玩了歸元寺一個景點，這顯然不能滿足旅游者的要求?，F(xiàn)在從實際要求出發(fā)：若游完表一所有景點，大概需要12.5h（不考慮乘車時間，堵車購票時間），時間相對緊張，而各景點開門時間均在7:00~9:00這個時間段，故8:00開始游玩第一個景點。1.1）黃鶴樓為武漢第一景點，“不登此樓非好漢”。由表可知，黃鶴樓相距火車站最近，且相對各景點開放時間最早，故一站先到達黃鶴樓，乘坐61路公交，歷時9min,建議游玩3~4小時。1.2)紅樓與黃鶴樓毗鄰，從黃鶴樓可步行百來米參觀紅樓，紅樓建議游玩時間為2h.1.3)從黃鶴樓出發(fā)，相距最近的景點為歸元寺，且歸元寺的素菜很出名，可到歸元寺就餐，解決午餐問題。其中，可乘坐401公交，歷時18min到達歸元寺，建議游玩時間1.5h.1.4)考慮到晴川閣的關閉時間，從歸元寺出發(fā)，乘坐559公交，歷時10min到達晴川閣，建議游玩2h.1.5)乘坐553公交，歷時14min,從晴川閣到達江漢路。江漢路為本天的旅游終點，且全天開放，故游客可根據(jù)自身的疲倦程度選擇在江漢路的游玩時間。建議游玩3h.分析第二天旅游路線：由計算結果可知，最短時間路徑為火車站途徑武漢大學（以下簡稱武大），湖北省博物館（以下簡稱博物館）最后到達關谷步行街（以下簡稱光谷）。這條路線幾乎囊括了表二的所有景點，若時間緊急可按此路線行走，若想感受下武漢著名景點之一東湖，則需要從實際進一步安排。2.1）由圖二可知，武大相距火車站最近，故從火車站出發(fā)乘坐564公交，歷時24min到達武大，建議游玩2~3h.2.2)武大相距博物館最近，故乘坐810公交，歷時21min到達博物館。建議游玩時間3~5h。2.3）大概15:00從博物館出發(fā)，若時間緊急可乘坐709公交歷時46min直接到達光谷游玩本旅程的最后一個景點，若時間充?？沙俗?02公交歷時34min到達東湖景區(qū)。因東湖為一大景區(qū)，關閉時間為19:00，故此僅擇磨山一景點作為游玩。2.4)乘坐401公交，歷時17min到達光谷。光谷全天開放，故游客可根據(jù)個人需要安排游玩時間。至此，武漢兩日游全部結束。5.結論建模計算出的結果盡管符合題目要求，但是不一定滿足實際需要，故還需結合實際調(diào)整路線。武漢市經(jīng)典旅游路線兩日游安排如下：第一天，武昌火車站—黃鶴樓—歸元寺—晴川閣—江漢路步行街。第二天，武昌火車站—武漢大學—湖北省博物館—東湖—光谷步行街。6.模型推廣與應用很多的游客往往會因為沒有安排好合理的路線而玩不盡興，尤其在經(jīng)費和時間有限制的條件下不能去更多的景點欣賞更美得風景，這就要我們制定合理的路線，滿足自己的旅游需求，玩到更多的景點。對于學生、工薪階層來講，費用因素在旅行中占有較大的比重，因此要選擇合適的省錢路線旅行。對于領導階層而言，時間因素在旅行中占有很大比重，因此要選擇合理的省時路線旅行。旅游線路的優(yōu)化設計，不僅在省時、省錢方面做到最優(yōu)考慮，而且為在時間，金錢方面有制約的設計旅游線路最優(yōu)化和最大化。真正是站在旅行者角度思考問題，為旅行者設計最合適最經(jīng)濟最省時的旅游線路。7.參考文獻【1】吳祈宗.《運籌學》【M】.北京.機械工業(yè)出版社，2003【2】孔造杰.《運籌學上機指導書》（第五版）（EXCEl部分）【M】.河北工業(yè)大學出版【3】武漢勘測設