运筹学关于武汉旅游线路最佳

PAGEPAGE15目录一. 学习运筹学的心得 3（一）线性规划 3（二）对偶理论与灵敏度分析 3（三）运输问题 4（四）整数规划： 4二．旅游线路的优化设计 4三.研究报告 41.问题描述 51.1背景描述 51.2研究意义 51.3对题目的理解 52.资料数据的收集和整理 63.数学模型的建立、计算 83.1模型建立背景 83.2模型假设 83.3符号说明 83.4模型的建立 93.4.1第一天旅游最优路线影响消费的因素 93.4.2第一天旅游最优路线目标函数的确定 93.4.3第一天旅游最优路线约束条件的确定 103.4.4第二天旅游最优路线影响景点数的因素 113.4.5第二天旅游最优路线目标函数的确定 113.4.6第二天旅游最优路线约束条件的确定 113.4.7第二天旅游最优路线模型建立 123.4.8模型求解与结果分析 124.结果分析 135.结论 146.模型推广与应用 147.参考文献 148.附录 15学习运筹学的心得大三上学期我们第一次学习了与运筹学相关的科目-线性规划(运筹学的一个重要分支),这也是我们初次认识到运筹学这一课程,让我们对运筹学有了初步了解并深入学习,大三下学期我们更进一步的学习了运筹学,从他的由来到发展,到更深入运用运筹学知识来解决生活中的实际问题,原料分配、收发平衡型的运输问题、LP问题、ILP问题以及对偶问题。现在的我们会用简单的方法来处理一些问题,通过深入学习我们更希望获得更多学习处理这一类问题的方法,从线性规划问题到建立数学模型,这些都需要我们来细细学习,认真对待。综合种种可以定义，从最直观、明了的角度将运筹学定义为：“通过构建、求解数学模型，规划、优化有限资源的合理利用，为科学决策提供量化依据的系统知识体系。”

运筹学的具体内容包括：规划论（包括线性规划、非线性规划、整数规划和动态规划）、库存论、图论、决策论、对策论、排队论、、博弈论、可靠性理论等。《史记·高祖本纪》有云：“夫运筹帷幄之中，决胜千里之外”。运筹学的英文名原名为Operations

Research，由此可见运筹学主要在于“研究（Research）”，研究在经营管理等活动中该如何行动，如何以尽可能小的代价，获取尽可能好的结果，即所谓“最优化”的问题。中国学者把这门学科意译为“运筹学”，便是取自古语“运筹帷幄，决胜千里”之意，运算筹划，出谋献策，从而以最佳策略取胜。这就极其恰当地概括了这门学科的精髓。在现代商业社会中，人们更加讲求运筹学的应用。作为一名数学院的学生，为了使自己未来的人生中更有胜算，让自己步入社会后更具备优势竞争力，就更应该尽可能地去熟练地掌握、运用运筹学的精髓，用运筹学的思维去思考问题。那么，我就必须抓住运筹学的特点：利用数学、管理科学、计算机科学技术等研究事物的数量化规律，应用分析、试验、量化的方法，对实际生活中人、财、物、时、空、信息等有限资源进行统筹安排和充分合理的运用。（一）线性规划它是运筹学的一个重要分支。线性规划解决的是：在资源有限的条件下，为达到预期目标最优，而寻找资源消耗最少的方案。其数学模型由目标函数和约束条件组成。解决线性规划问题的关键是找出它的目标函数和约束方程，并将它们转化为标准形式。简单的设计两个变量的线性规划问题可以直接运用图解法得到。但是在现实生活中，线性规划问题往往涉及到的变量很多，很难用作图法实现，而运用单纯形法却比较方便。单纯形法的发展很成熟，应用也很广泛，在运用单纯形法时，需要先将问题化为标准形式，求出基可行解，列出单纯形表，进行单纯形迭代，当所有的变量检验数不大于零，且基变量中不含人工变量时，计算就算结束。将所得的量的值代入目标函数，便可得出最优值。

（二）对偶理论与灵敏度分析1、每一个线性规划问题都会有与之伴随的另一个问题，若一个问题称为原问题，则另一个称为其对偶问题，原问题和对偶问题有着非常密切的关系，以至于可以根据一个问题的最优解，得出另一个问题的最优解的全部信息。

对偶问题分为对称形式和非对称形式两种。非对称形式的对偶问题需要将原问题变为标准形式，然后找出标准形式的对偶问题，因为对偶问题存在特殊的基本性质，所以在解决实际问题比较困难时，可以将其转化为对偶问题进行求解；

2、灵敏度分析是分析在线性规划问题中，一个或几个参数的变化对最优解的影响问题。可以分析目标函数中变量系数、约束条件的右端项、增加一个约束变量、增加一个约束条件、约束条件的系数矩阵中的参数值等的变化。如果将问题转化为研究参数值在保持最优解或最优基不变时的允许范围或改变到某一值时对问题最优解的影响时，就属于参数线性规划的内容。

（三）运输问题是解决多个产地和多个销地之间的同品种物品的规划问题。根据运输问题的独特性，一般采用一种简单而有效的方法：表上作业法。表上作业法先找出运输问题的基可行解，方法有：最小元素法、西北角法、沃格尔法。其中沃格尔法得出的解最接近最优解。然后利用闭回路法或对偶变量法对得到解进行最优性判别。当检验的结果为非最优解时，进行解的改进，然后再进行最优性判别，直到所有的非基变量检验数全非负，得到最优解。在解决运输问题时会遇到产销不平衡的情况，在该情况下，要将该问题转化为产销平衡问题，只需增加一个假象的产地或销地，并将表示该地的变量在目标函数中的系数设为零即可。

（四）整数规划：是解决决策变量只能取整数的规划问题，整数规划的解法有割平面法和分支定界法。整数规划中的0-1规划整数问题是一个非常有用的方法。在实际问题中，该方法能够解决很多问题。0-1整数规划的解决方法有枚举法和隐枚举法。指派问题是0-1整数规划中的特例，现在采用的解法一般为匈牙利法，由于指派问题的特殊性，使用匈牙利法可以有效的减少计算量。

二．旅游线路的优化设计武汉市旅游景点路线的设计摘要旅游线路设计是旅游规划设计的一部分，当今旅游线路设计的成果研究还比较少，大部分重实际，轻理论。对于一个旅游者而言，对旅游路线的期望是最大化的满足其消费需要，即时间最短，成本最小，玩得开心。本文着重围绕运筹学在旅游线路规划中的运用来发掘运筹学在旅游规划设计中的潜力，探讨旅游路线的优化问题。本文主要研究最佳旅游路线的设计问题。在满足相关约束条件的情况下，花最少的钱游览尽可能多的景点是我们追求的目标。基于对此的研究，建立数学模型，设计出最佳的旅游路线。本问题主要是解决两方面的问题：（1）、（2）两问是在时间或旅游费用不限的情况下，游完十个景点怎样才可以做到费用最省或是时间最省；（3）、（4）、（5）问是在旅游时间或是旅游费用或是两者都有约束条件的情况下，怎样才可以玩更多的地方。关键词：运筹学；旅游线路规划；最短时间三.研究报告正文问题描述随着人们生活水平的提高，旅游逐渐成为最热门的户外活动之一。在旅游的过程中，我们不仅可以感受大自然之美、放松心情，而且可以领略不同地方的文化气息、拓宽视野。旅游者在今年五月一日8点之后从武昌火车站出发，到武汉市一些著名景点旅游，最后回到出发点。由于跟团旅游会受到限制，旅游者打算自己背包出游。出行路途中有以下几个条件：（A）跨区交通出行可以乘公汽、长途汽车或地铁（不允许包车或包及），并且车票可预定到。（B）市内交通出行可乘公交车（含专线大巴、小巴）、地铁或出租车。（C）旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票（第一门票）。晚上20：:00至次日早晨7：:00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。（D）假设景点的开放时间为8:00至18:00.根据以上条件考虑到旅游者的以下需求：1、在时间不限的情况下，游览全部景点，旅游费用最省；2、在旅游费用不限的情况下，游览全部景点，旅游时间最短；3、在旅游费用一定的情况下，游览尽可能多的景点；4、在时间一定的情况下，游览尽可能多的景点； 5、在时间和旅游费用都一定的情况下，游览尽可能多的景点。针对以上几种情况，建立相关的数学模型并为该旅行者设计详细的行程表，行程表中应包括具体的交通信息（车次、起止时间、票价等）、宾馆地点和名称，门票费用，在景点的停留时间等信息。1.1背景描述现如今社会发展迅速，生活节奏不断加快，对于大多数旅游者来说，在舒适度不受影响或者体力许可的前提下，能花费较少的费用和较少的时间而尽可能游览更多的风景名胜，是他们的最大愿望。一个旅游区域内的若干景点各在不同的空间位置，对这些景点游览或活动参与的先后顺序与连接方式，可有多种不同的串连方式，由此产生组合成不同的旅游线路。于是，我们如何解决让游客实现最大愿望这个问题可以转化为如何实现旅游成本最小化和路线最优化的问题。1.2研究意义武汉市是中国西部最大的城市，具有独天得厚的自然人文资源。对于这样一个优秀的旅游城市，其景点很多，交通路线复杂，如果就这样盲目的进行游玩，则很有可能造成费用高，游览景点少，且玩不尽兴的遗憾。如果我们运用运筹学的方法将其旅游路线进行规划，并结合实际背景，寻求出最佳方案，这样可以充分满足一个旅游者的需求，达到旅游路线最优化的目的。1.3对题目的理解首先我们知道本问题属于旅游路线的优化问题。为了建立模型，首先应将各景点线路转化为纯数学形式的点线集合，进行图论方面的分析。本问题主要是解决两方面的问题：（1）、（2）两问是在时间或旅游费用不限的情况下，游完十个景点怎样才可以做到费用最省或是时间最省；（3）、（4）、（5）问是在旅游时间或是旅游费用或是两者都有约束条件的情况下，怎样才可以玩更多的地方。第一方面根据对第一方面问题的分析可知，问题目的在于当时间（费用）不限的情况下求游完所有景点并回到出发地点所用的费用（时间）的最小值。该问题属于旅行商问题（TravelingSalesmanProblem,TSP）。为了建立数学模型，首先应该将各个景点转化为纯数学形式的点线的集合，进行图论方面的分析。下面给出旅行商问题的定义：旅行商问题：一位销售商从N个城市的某个城市出发，不重复的走完其余N-1个城市并回到原出发点，在所有可能路径中求出路径长度最短的一条。用数学语言描述TSP，即给定一组N个城市和它们两两之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。用图语言描述TSP：给出一个图G=（V，E），每边上有非负权值w（e），寻找G的Hamilton圈C，使得C的总权最小。TSP问题是一个典型的组合优化问题，其可能的搜索路径随着城市数目N的增加呈指数增长，属于NP完全问题。了解了以上只是后，我们更加确定了该问题就是旅行商问题。只是在实际的处理中，我们把两景点的最省路费（最短时间）最为赋权值w（e），在一定程度上，各景点间的距离与两点间的单程最省路费（单程最短时间）是成正比的，所以把两景点的最省路（最短时间）作为权值w（e）是可行的。第二方面这一方面要解决的问题是在费用（时间）有限制或两者都有限制的情况的情况下观赏的景点近可能多，根据这种要求可从以下方案入手：建立多目标规划模型，通过适当的拟合或线性加权，把多目标转化为单目标资料数据的收集和整理（1）以下为各个景点间的直达公交路线。起点终点公交路线票价耗时所经站次步行距离武昌火车站黄鹤楼101.5103604022932061193105291.51262407172135720561282510722182590905581420556282530电车4119860武昌火车站归元寺61125650072212739805362233960武昌火车站晴川阁561236740武昌火车站江汉路步行街4022348680武昌火车站湖北省博物馆4022802150武昌火车站东湖磨山4022113314500武昌火车站光谷步行街5932351226073824120220901内环3307680592331164051813513220武昌火车站武汉大学5641248160901内环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数学模型的建立、计算3.1模型建立背景根据武汉地图，相关旅游资料及以上数据分析，可把武汉旅游路线分两天进行，第一天以长江大桥为中心，游玩四周景点，且因黄鹤楼与红楼毗邻，步行几百米就可到达，故把红楼归纳为黄鹤楼景点；第二天以武大为中心，游览附近景点。资料显示的公交路线仅考虑景点间的直达路线，未有换乘现象，表上选取的数据均综合考虑各线路的票价，运行时间及步行距离而得。3.2模型假设1、在旅游期间，天气晴朗，列车和航班没有延误并且准时到站，市内交通也没有出现长时间的堵塞2、该旅游者是成年人，不考虑学生票的问题3、旅游者在两地旅游来回时间和路上花的费用是相同的3.3符号说明图1V1代表武昌火车站，V2代表黄鹤楼，V3代表归元寺，V4代表晴川阁，V5代表江汉路步行街图2：V1代表武昌火车站，V2代表武大，V3代表省博物馆，V4代表东湖磨山，V5代表光谷3.4模型的建立第一天游玩的路线如图1表示，弧旁数字代表通过该段路线所需的最短时间Min。现有五个旅游景点V1、V2…..V5，现在我们从V1出发到V5;对于第二天，游玩的路线如图2所示，求在两天中哪条路所花费的时间最短，并且能玩较多的景点。图1图23.4.1第一天旅游最优路线影响消费的因素路费路费住宿费基本消费门票费总费用3.4.2第一天旅游最优路线目标函数的确定用Lij表示i景点到j景点的途中花费，并引入路线决策变量Xij1经过i到j的路段0不经过i到j的路段Xij=1经过i到j的路段0不经过i到j的路段用Pj表示j地区景点的第一门票费用，T表示在景点所在地区停留的时间则总费用，则目标函数为：3.4.3第一天旅游最优路线约束条件的确定

由于每个景点只能有一条边出去，所以对j景点Xij之和影等于1，既：i=1,211同理，每个景点只能有一条边进去，所以对i景点Xij之和也应等于1，既:i=1,2……11应该注意的是，除了起点和终点（都是武昌火车站）以外，各边不构成Hamilton圈。通过对武汉的一些旅行社进行咨询，我们得出在第个景点的最佳逗留时间和在第个景点总消费：t1t2t3t4t5t6t7t8t9t10t1172418123630129152417(单位：小时)c1c2c3c4c5c6c7c8c9c10c1112042330013537839017590148303241(单位：元)从而根据模型，使用Lingo编程，得出结果如下表：旅游景点数n234每人总花费m（单位：元）250406623路线1→8→11→9→8→11→4→8→9→1旅游景点数n56每人总花费m（单位：元）9491207路线1→8→9→7→4→11→4→11→7→9→8→1旅游景点数n7每人总花费m（单位：元）1534路线1→4→10→11→7→9→8→1（其中数字1—11分别表示武昌火车站、黄鹤楼、归元寺、晴川阁、江汉路步行街、武大、省博物馆、光谷、东湖磨山）变量是1的变就是最短时间通过的边，即V1-V3-V5，最短时间是38分钟。3.4.4第二天旅游最优路线影响景点数的因素旅途坐车费用旅途坐车费用住宿、基本费用门票费用不多于200元的费用费用3.4.5第二天旅游最优路线目标函数的确定假设总费用未知，但满足条件（<=2000元），用M表示用Pij表示i景点和j景点的门票费用之和，（单位：元）（i=1，2……10）用Lij表示i景点到j景点的途中花费，并引入路线决策变量Xij1经过i到j的路段1经过i到j的路段0不经过i到j的路段Xij=用C表示旅游的景点数目则最多景点数，既目标函数为：C=3.4.6第二天旅游最优路线约束条件的确定由于M=车费+基本费用+门票费，因此用函数表示为：M=由于每个景点只能有一条边出去，所以对j景点Xij之和影等于1，既：或0i=1,211同理，每个景点只能有一条边进去，所以对i景点Xij之和也应等于1，既：或0i=1,2……11应该注意的是，除了起点和终点（都是徐州）以外，各边不构成Hamilton圈。3.4.7第二天旅游最优路线模型建立 综上所述，我们可以得到总的模型为：Min约束条件：+360（，=1，2，……，11）（，=1，2，……，11）（，=2，3，……，11）3.4.8模型求解与结果分析旅游景点数n234每人总花费c（单位：元）229370573路线1→8→11→8→9→11→9→8→4→1旅游景点数n56每人总花费c（单位：元）9271160路线1→4→8→9→7→11→4→8→9→7→11→1旅游景点数n7每人总花费c（单位：元）1412路线1→8→9→7→11→10→4→1（其中数字1—11分别表示武昌火车站、黄鹤楼、归元寺、晴川阁、江汉路步行街、武大、省博物馆、光谷、东湖磨山）图中变量是1的变就是最短时间通过的边，即V1-V2-V3-V5，最短时间是91分钟。4.结果分析分析第一天旅游路线：由计算结果可知，最短时间路径为从武昌火车站（以下简称火车站）出发经归元寺最后到达江汉路步行街（以下简称江汉路），途中仅游玩了归元寺一个景点，这显然不能满足旅游者的要求。现在从实际要求出发：若游完表一所有景点，大概需要12.5h（不考虑乘车时间，堵车购票时间），时间相对紧张，而各景点开门时间均在7:00~9:00这个时间段，故8:00开始游玩第一个景点。1.1）黄鹤楼为武汉第一景点，“不登此楼非好汉”。由表可知，黄鹤楼相距火车站最近，且相对各景点开放时间最早，故一站先到达黄鹤楼，乘坐61路公交，历时9min,建议游玩3~4小时。1.2)红楼与黄鹤楼毗邻，从黄鹤楼可步行百来米参观红楼，红楼建议游玩时间为2h.1.3)从黄鹤楼出发，相距最近的景点为归元寺，且归元寺的素菜很出名，可到归元寺就餐，解决午餐问题。其中，可乘坐401公交，历时18min到达归元寺，建议游玩时间1.5h.1.4)考虑到晴川阁的关闭时间，从归元寺出发，乘坐559公交，历时10min到达晴川阁，建议游玩2h.1.5)乘坐553公交，历时14min,从晴川阁到达江汉路。江汉路为本天的旅游终点，且全天开放，故游客可根据自身的疲倦程度选择在江汉路的游玩时间。建议游玩3h.分析第二天旅游路线：由计算结果可知，最短时间路径为火车站途径武汉大学（以下简称武大），湖北省博物馆（以下简称博物馆）最后到达关谷步行街（以下简称光谷）。这条路线几乎囊括了表二的所有景点，若时间紧急可按此路线行走，若想感受下武汉著名景点之一东湖，则需要从实际进一步安排。2.1）由图二可知，武大相距火车站最近，故从火车站出发乘坐564公交，历时24min到达武大，建议游玩2~3h.2.2)武大相距博物馆最近，故乘坐810公交，历时21min到达博物馆。建议游玩时间3~5h。2.3）大概15:00从博物馆出发，若时间紧急可乘坐709公交历时46min直接到达光谷游玩本旅程的最后一个景点，若时间充裕可乘坐402公交历时34min到达东湖景区。因东湖为一大景区，关闭时间为19:00，故此仅择磨山一景点作为游玩。2.4)乘坐401公交，历时17min到达光谷。光谷全天开放，故游客可根据个人需要安排游玩时间。至此，武汉两日游全部结束。5.结论建模计算出的结果尽管符合题目要求，但是不一定满足实际需要，故还需结合实际调整路线。武汉市经典旅游路线两日游安排如下：第一天，武昌火车站—黄鹤楼—归元寺—晴川阁—江汉路步行街。第二天，武昌火车站—武汉大学—湖北省博物馆—东湖—光谷步行街。6.模型推广与应用很多的游客往往会因为没有安排好合理的路线而玩不尽兴，尤其在经费和时间有限制的条件下不能去更多的景点欣赏更美得风景，这就要我们制定合理的路线，满足自己的旅游需求，玩到更多的景点。对于学生、工薪阶层来讲，费用因素在旅行中占有较大的比重，因此要选择合适的省钱路线旅行。对于领导阶层而言，时间因素在旅行中占有很大比重，因此要选择合理的省时路线旅行。旅游线路的优化设计，不仅在省时、省钱方面做到最优考虑，而且为在时间，金钱方面有制约的设计旅游线路最优化和最大化。真正是站在旅行者角度思考问题，为旅行者设计最合适最经济最省时的旅游线路。7.参考文献【1】吴祈宗.《运筹学》【M】.北京.机械工业出版社，2003【2】孔造杰.《运筹学上机指导书》（第五版）（EXCEl部分）【M】.河北工业大学出版【3】武汉勘测设