数学建模论文——最佳旅游路线.doc

数学建模论文最佳旅游路线设计院系:信息科学与技术学院保证书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则，我们完全明白在竞赛开始后不能以任何方式与队外的任何人讨论有关竞赛试题的求解内容，抄袭别人的成果也是违反竞赛规则的，如被发现将会受到严肃处置。我们也知道如果引用别人的成果或其他公开的资料（包括网上查到的资料）必须按照规定的参考文献的表述方式在正文和参考文献中明确列出。为了确保竞赛的公正、公平性，我们保证严格遵守竞赛规则。参赛院系：信息科学与技术学院 参赛队员： 20 年6月 28 日 最佳旅游路线设计摘 要 为了提出合适的旅游线路，从实际情况出发考虑，本文建立了合适的线路选择模型，并给出了一些结果。问题一为既考虑旅游消费，又考虑旅游的景点数的旅游线路选择问题。本文对去各景点间的路费、景点门票、在景点内每天的平均消费加以考虑，建立了规划模型。对于多目标模型，我们采用适当的拟合将多目标转化为单目标。并使用lingo软件编程得出最优旅游线路及合适的旅游时间为: 二号线：成都乐山峨嵋，最合适的旅游时间均为1天；三号线：成都四姑娘山丹巴，最合适的旅游时间均为1天；四号线：成都都江堰青城山，最合适的旅游时间为都江堰2天，青城山1天；五号线：成都康定, 最合适的旅游时间为1天。并对最优线路给出了详细的评价。问题二，在代表时间充裕的条件下仅考虑旅游的交通费用，我们把各景点看成是纯数学中的点，利用图论的知识求解。在建模中，我们把各景点间的路费作为巡回图边的邻接矩阵权，使原题巧妙的转化为了图论中旅行商问题（即最短路问题），建立了线性规划模型，利用lingo软件求解得到最少的交通费用为427.00元，最佳的旅游路线为：成都青城山都江堰四姑娘山丹巴黄龙九寨沟海螺沟康定峨眉乐山成都。问题三在问题一的基础上增加了对代表旅游意向的考虑，建模思路与问题一大致相同。我们把代表的旅游意向刻画为代表对旅游路线的满意度，然后在问题一的基础上增加一个目标函数，即在整个旅游线路中满意度最高。建立了多目标优化模型，采用同样的方法把多目标规划问题转化为单目标问题利用lingo软件求解得到：旅游的景点总数是7个，总的满意度是4.08，各条路线的满意度分别为0.2，0.78，0.85，0.80，0.85。下面是求得的最佳旅游路线以及最合适的旅游时间：二号线：成都乐山峨嵋，最合适的旅游时间为前者2天，后者1天；三号线：成都四姑娘山丹巴，最合适的旅游时间为前者1天，后者2天；四号线：成都都江堰，最合适的旅游时间为2天； 五号线：成都海螺沟康定，最合适的旅游时间均为1天。最后，我们对整个过程进行了科学性的评价。并提出了使用Dijkstra算法和遗传算法解题的思路。关键词：规划 线性规划 多目标规划 lingo 遗传算法 Dijkstra算法1 问题重述随着生活水平的提高，旅游逐渐成为最热门的户外活动之一。在旅游的过程中，我们不仅可以感受大自然的美，而且可以领略不同地方的文化气息，乡土风情。在这里考虑到旅游者的以下需求：1.旅游的费用尽可能最省；2.观赏的旅游景点尽可能多；3.旅游者对旅游路线的满意度尽可能高。设计合适的旅游线路方案来满足旅游者的各种需求，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足旅游者的各种不同需求。在这里只针对将要来参加西南交通大学数学系召开的“学术会议”的来自国内外的许多著名学者，为其设计合适的旅游路线。需要解决如下问题：1.根据提供的五条线路，要求设计出合适的旅游路线，使得会议代表能在10天内花最少的钱，游最多的地方。2.上面考虑的是只有十天时间的情况，当代表时间非常充裕（比如一个月）时，可以游完所有的景点才离开，设计合适的旅游路线，使在四川境内的交通费用尽量地节省。3.根据主办方对代表的游意调查，充分考虑这些代表的意愿，为设计代表们合适的旅游路线，使他们在会议结束后的10天时间内花最少的钱游尽可能多的地方。2 条件假设1假设查阅的数据基本符合事实。2假设各景点间的路费及各景点的门票长期基本保持不变。3假设在问题一中不考虑每一条路线的最优，而是考虑整个旅游过程的最优问题。4假设代表在某景点旅游的最长时间不超过3天 。3 符号说明模型一中：第条线路中第个景点（变量）第条路线第个景点的门票（单位：元）在第条路线第个景点平均每天的基本消费（单位：元） 第条路线的平均路费（单位：元） 10天中旅游的景点总数 10天中的总消费（单位：元） 在第条线路第个景点观赏的总时间（单位：天）模型二中：路线决策变量（变量）景点到景点间的路费（单位：元） 总路费（单位：元）模型三中： 去第条线路的满意度 去第条线路的满意度上限 去第条线路的满意度下限 整个旅游过程中的满意度之和4 问题分析题目背景：随着我国经济实力的提高，人们的生活水平也不断的提高。旅游也随之成为很热门的户外活动。旅游不仅可以释放心情，也可以感受到大自然的美，不同的风土人情，不同的人文气息。所以越来越多的人把旅游作为一种享受。在旅游的时候，人们往往会想，怎样才能花最少的钱游最多的地方，怎样的旅游路线才能够使自己最满意。这样就要求我们建立适当的数学模型来解决这些问题。首先我们知道本问题属于旅游线路的优化问题。为了建立模型，首先应该将各景点线路转化为纯数学形式的点线的集合，进行图论方面的分析。 1.本问题要解决两方面的问题：在10天的旅游时间内，满足（1）旅游的费用尽可能少；（2）观赏的旅游景点尽可能多。根据这些需求，可以从以下两种方案入手：（1）建立多目标优化模型，考虑分层序列法，以旅游费用尽可能少为第一目标，观赏的景点尽可能多作为第二目标。在第一目标求得的可行解集里搜索满足第二目标的路线，将该路线作为最合适的旅游路线。（2）同样建立多目标规划模型，通过适当的拟合或线性加权，把多目标转化为单目标。在这里还把各景点的门票和每天的平均消费考虑进去，以增加模型的实用性。分析上面的两种方案可知，方案一求出来的旅游线路不一定是最佳线路，因为当在满足旅游费用尽可能少时，得到的线路不一定就满足第二个条件，即观赏的景点尽可能多。所以方案一存在一定的问题，我们选择方案二，用通过适当的拟合把多目标转化为一个单目标求解模型。下面给出各条线路的平均路费，各景点的门票，以及各景点平均每天的基本消费： 线路 价格（元）项目线路一线路二线路三线路四线路五九寨沟黄龙乐山峨眉四姑娘山丹巴都江堰青城山海螺沟康定平均路费1083510520100门票22020090120905090909040每天平均消费120801001201009010010013090表二各条线路平均路费、各景点的门票、各景点平均每天的基本消费（单位：元）2在代表的时间比较充裕的条件下，可以把所有的景区参观完，要求建立合适的模型，使得交通费用尽量最省。这时代表就是从成都出发，逐一到达各个景点（不能重复到达），观赏完所有景点之后返回成都。根据上面分析可知，该问题属于旅行商问题（Traveling Salesman Problem, TSP）。为了建立模型，首先应该将各景点转化为纯数学形式的点线的集合，进行图论方面的分析。下面给出旅行商问题的定义：旅行商问题: 一位销售商从N个城市中的某一城市出发, 不重复地走完其余N-1个城市并回到原出发点, 在所有可能路径中求出路径长度最短的一条.用数学语言描述TSP，即给定一组N 个城市和它们两两之间的直达距离, 寻找一条闭合的旅程, 使得每个城市刚好经过一次且总的旅行距离最短。用图语言来描述TSP: 给出一个图G=(V, E) , 每边eE 上有非负权值w(e), 寻找G 的Hamilton 圈C, 使得C的总权最小。TSP 问题是一个典型的组合优化问题, 其可能的搜索路径随着城市数目N 的增加呈指数增长, 属于NP完全问题。 了解了以上知识后，我们更加确定了该问题就是旅行商问题。只是在实际的处理中，我们把两景点的路费作为赋权值w(e),在一定程度上，各景点间的距离与这两点间的单程路费是成正比的，所以把两景点的路费作为权值w(e)是可行的。下表给出的是任意两景点间的单程车费。路费 地名地名成都九寨黄龙乐山峨眉山四姑娘山丹巴都江堰青城山海螺沟康定成都01081004235105110122010090九寨108015200130100120100100220200黄龙100150180190901109090210190乐山422001800201501706060100120峨眉山3513019020015018080885070四姑娘山105100901501500603038150120丹巴110120110170180600909813080都江堰12100906088309008160140青城山20100906080389880170150海螺沟11022021010050150130160170030康定902001901207012080140150300表二 各景点间的单程路费（单位：元）3.本题与问题一基本一样，只是在问题一的基础上充分考虑了代表对各条旅游路线的旅游意向。为了建立合适的数学模型，我们首先根据附件一在SPSS软件中统计出100位代表对各条线路的旅游意向。100位代表对各条旅游路线的旅游意向见下表：线路百分比意向一号线二号线三号线四号线五号线去20%12%15%20%15%不去14%22%15%15%15%无所谓66%66%70%65%70%表三 100位代表对各条旅游路线的旅游意向从上面的数据分析可知，持“无所谓”态度的代表大约占65%-70%，持“去”态度的代表约占12%-20%,持“不去”态度的代表约占14%-22%。对一号路线来说，“去”的有20%，“无所谓”的有66%，即是这部分人有可能参加这条路线也有可能不参加这条路线。也就是说如果去一号路线，那么就至少有20%的人满意。我们在这里把变量看作是去一号线的满意度，即是0.20.86，反之，要是不去一号线，就会使得14%-80%的人满意，即不去一号线的满意度为1-，则0.141-0.80。同理：对于第二条线路，“去”的满意度满足0.120.78，“不去”的满意度1-满足0.221-0.78;对于第三条线路，“去”的满意度满足0.150.85，“不去”的满意度1-满足0.151-0.85;对于第四条线路，“去” 的满意度满足0.200.85，“不去”的满意度1-满足0.151-0.80;对于第五条线路，“去”的满意度满足0.150.85，“不去”的满意度1-满足0.151-0.85;通过上面的分析，我们可以把每条线路“去”与“无所谓”的百分比之和作为去该条线路时的满意度范围。所以，我们要设计合适的旅游路线使尽可能多的人满意。也就是在整个旅游线路中，总的满意度要求达到最高。这样就只需要在问题一的基础上增加一个目标。如果去路线，那么路线的代表们的满意度为，如果不去路线，则代表们的满意度为1-。总之，该目标就是使得代表们满意度累计求和最大。5 模型建立模型一：在代表只有10天时间的情况下，不能观赏完所有的景点，只能观赏其中几景点，并且要求花的钱要少观赏的景点的个数要多。分析可知该问题是一个双目标规划问题，即（1）花的钱要最少；（2）观赏的景点数要多。1.目标函数的确定：（1）消费最省去各线路的费用：在这里由于每条线路的两个景点基本上都很接近，所以只考虑去两景点的平均路费。增加线路决策变量，表示第条线路中第个景点则到第条线路中第个景点可以表示为则总路费为总的基本消费为所以目标函数一，即消费最省：（2）观赏的景点数尽可能多不难知道，目标函数二，即观赏的景点数尽可能多：2约束条件的确定：代表的旅游时间只有10天，所以 并且为了满足观赏的景点数多，我们假设代表在每一个景点的旅游时间不超过三天，则： 为整数线路决策变量为变量：综上分析，建立多目标规划模型：目标一： 目标二:约束条件：模型二： 在代表有充裕的时间的情况下，可以将景点观赏完，要求交通费用尽量的节省。也即是说，代表从成都出发，逐一观赏各景点，但是不能重复观赏同一个景点，然后再回到成都，使得在这一过程中交通费用最省。 我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解。 仔细分析可知，该问题是一旅行商问题，这一过程中交通费用最省就是求最小交通费用的Hamilton圈。1.目标函数的确定：用表示，并引入线路判断决策变量，则总路费，即目标函数为 ，2.约束条件的确定由于每一个景点只能有一条边出去，所以对景点之和应等于1.即：同理，每一个景点只能有一条边进去，所以对景点之和也应等于1.即：但是应该主要的是，除了起点和终点（都是成都）以外，各边不构成Hamilton圈。 综上分析，建立能够解决Hamilton圈的线性规划模型： 模型三： 在充分考虑代表对各条路线的旅游意愿的条件下，要求花最少的钱游尽可能多的地方。也就是说，在这里我们要同时考虑三个目标，即（1）10天时间内旅游所花的费用要最少；（2）观赏的景点总数要最多；（3）代表对整个旅游过程中的满意度最高。通过上面的分析，我们建立一个三目标规划模型。1.目标函数的确定：（1）消费最省 和模型一类似，仍然引入线路决策变量，表示第条线路中第个景点 则可以直接得到目标函数一，即消费最省：（2）观赏的景点数尽可能多 由问题一知，目标函数二，即观赏的景点数尽可能多： （3）整个旅游过程中的满意度最高 经过上面的分析可知，去第条线路中第个景点可以表示为不去第条线路中第个景点可以表示为则去该条路线的满意度为 所以目标函数三，即在整个旅游过程中的满意度最高：2.约束条件的确定 （1）代表的旅游时间只有10天，所以（2）并且为了满足观赏的景点数多，我们假设代表在每一个景点的旅游时间不超过三天，则： 为整数（3）线路决策变量为变量： （4）去每一条路线的满意度范围综上分析，建立三目标优化模型：目标一：目标二：目标三： 约束条件： 6 模型求解模型一：根据上面的分析，我们建立的是一个多目标规划模型，由于多目标规划模型的求解较困难，所以我们把该多目标函数转化为一单目标函数。由于要求使得总消费尽量的少，而旅游的景点尽可能多，所以旅游过的景点总数除以总消费就应该尽量的大。转化为数学语言即是：所以简化的单目标模型为： 目标函数： 约束条件：转化为单目标函数以后，求解就比较方便了。我们使用lingo软件编程得到，观赏的景点最大总数为8个，最小总消费为2408元。满足“花最少的钱游尽可能多的地方”的最佳旅游路线及最合适的旅游时间为：二号线：成都乐山、峨嵋，最合适的旅游时间均为1天；三号线：成都四姑娘山、丹巴，最合适的旅游时间均为1天；四号线：成都都江堰、青城山，最合适的旅游时间为都江堰2天，青城山1天；五号线：成都海螺沟、康定, 最合适的旅游时间均为1天。模型二：根据建立的模型，我们利用lingo软件编程得到全局最优解为427.00元，也就是说游完所有景点的最少交通费用是427.00元。最佳的旅游路线如下：模型三：上面建立的模型是一个三目标规划模型，由于多目标规划模型的求解较困难，所以我们把该多目标规划模型转化为一单目标模型。由于三个目标分别是求（1）10天时间内旅游所花的费用要最少；（2）观赏的景点总数要最多；（3）代表对整个旅游过程中的满意度最高。所以我们可以将观赏的景点总数加上整个旅游过程中的满意度，除以总的消费就可以将该多目标规划问题转化为一个单目标规划问题。转化为数学语言即是：所以简化的单目标模型为：目标函数： 约束条件： 通过上面的简化，我们通过lingo编程得到：旅游的景点总数是7个，总的满意度是4.08，各条路线的满意度分别为0.2，0.78，0.85，0.80，0.85。下面是求得的最佳旅游路线以及最合适的旅游时间：二号线：成都乐山、峨嵋，最合适的旅游时间为前者2天，后者1天；三号线：成都四姑娘山、丹巴，最合适的旅游时间为前者1天，后者2天；四号线：成都都江堰，最合适的旅游时间为2天； 五号线：成都海螺沟、康定，最合适的旅游时间均为1天。7 模型检验与评价1模型一评价：对于模型一，根据我们求得的旅游路线可知，不包括一号线。从地图及查阅的资料显示，成都离九寨、黄龙相对较远而且消费也较高。所以求出的旅游路线不包括一号线是很符合实际的。而且旅游的景点总数为8个，也基本符合题目要求。所以，该模型在一定程度上是符合实际的。改进：对于问题一，有许多不明确的地方。所以不同的假设会有不同的结果。下面给出另一种理解及建模思路。对每一条路线来说，如果单独考虑每一条路线的交通费用最省，则该问题可以先求得去每一条路线的最小费用，然后再考虑旅游景点的总数，同样建立多目标规划求解。下面给出求解每一条路线的交通费用最省的模型：首先，把各景点看作是纯数学中的点，即将该问题转化为图论中的最短路问题。设任一景点为图的一个顶点，连接任意景点的公路作为图的边，记为，记（即去任意两景点间的交通费用）为图的边之长。对任意的顶点,寻求轨道，使得，即从到的所有轨道长中寻求最小的一个。若，当不相邻，则。采用迪克斯特拉（Dijkstra）算法求解。步骤如下：（1）令=0，；（2）对每个，用代替；设是使取最小的中的顶点，令（3）若，则停止；若由上述算法知，中各顶点都之标志即为到的距离，又，故经有限步后中每个顶点都标志了与的距离，从而可以找到到各顶点的最短路径。求最短路径的方法还有弗洛伊德算法（Floyd），在这里不作讨论。2模型二评价：对于问题二，由于只考虑交通费用，所以我们直接把两景点间的交通费用作为边到的赋权值，构成了有向赋权图，巧妙地将原问题转化为图论的旅行商问题（最短路问题）。改进：上面模型中，我们是利用lingo软件求解的，我们还可以利用解决旅行商问题的经典算法遗传算法求解。下面给出遗传算法的基本概念以及算法步骤：遗传算法是通过借鉴生物界自然选择和自然遗传机制而产生的一种计算方法, 与其他的优化算法一样, 遗传算法也是一种迭代算法. 从选定的初始解出发, 通过不断地迭代, 逐步改进当前解, 直到最后搜索到最优解或满意解。遗传算法的一般步骤：（1）初始化。令, 给出正整数 (最大迭代次数) , 交叉概率及变异概率, 随机生成个个体作为初始群体； （2）个体评价。计算中各个体的适应度； （3）选择。 对群体进行选择操作, 得到中间群体；（4）交叉。 把交叉操作作用于中间群体；（5）变异.。把变异操作作用于交叉之后所得到的群体, 则得到第代群体；（6） 若，则令，转（2）；若, 则以进化过程中所得到的具有最大适应度的个体作为最优解, 运算停止。3.模型三评价：在模型一的基础上，增加了代表对旅游路线意向的考虑，通过建立的模型，求得了合适的旅游路线。得到的总的满意度是4.08，各条路线的满意度分别为0.78，0.85，0.80，0.85，从各条路线的满意度显示，基本能够达到要求。改进：可以考虑更多因素，比如说可以加以考虑每路线上两个风景点点间的相互影响，以及两者之间是否是具有相似的特点，并加以考虑是否参加其一即可，改变中的路线。8 参考文献1谢金星，薛毅，优化建模与LINDO/LINGO软件，北京：清华大学出版社，2005年7月2韩中庚，数学建模方法及其应用，北京：高等教育出版社，2006年7月3 中北大学学报(自然科学版)，用遗传算法求解旅行商问题，2007 年第28 卷第1期9 附录模型一源程序：max=c/n;n=n1+n2;n1=L1+L2+L3+L4+L5+220*y11+200*y12+90*y21+120*y22+90*y41+90*y42+90*y31+50*y32+80*y51+40*y52;n2=120*y11*t11+80*y12*t12+100*y21*t21+120*y22*t22+100*y31*t31+90*y32*t32+100*y41*t41+100*y42*t42+130*y51*t51+90*y52*t52;c=y11+y12+y21+y22+y31+y32+y41+y42+y51+y52;t11+t12+t21+t22+t31+t32+t41+t42+t51+t52=10;t113;t123;t213;t223;t313;t323;t413;t423;t513;t52=level(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i); ););for(link:bin(x);for(cities(i)|i#gt#1: level(i)=1+(n-2)*x(i,1););End模型三源程序：max=(c+n3)/n;n=n1+n2;n1=L1+L2+L3+L4+L5+220*x11+200*x12+90*x21+120*x22+90*x41+90*x42+90*x31+50*x32+80*x51+40*x52;n2=1