数学建模论文最佳旅游路线设计院系:信息科学与技术学院2保证书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则，我们完全明白在竞赛开始后不能以任何方式与队外的任何人讨论有关竞赛试题的求解内容，抄袭别人的成果也是违反竞赛规则的，如被发现将会受到严肃处置。我们也知道如果引用别人的成果或其他公开的资料（包括网上查到的资料）必须按照规定的参考文献的表述方式在正文和参考文献中明确列出。为了确保竞赛的公正、公平性，我们保证严格遵守竞赛规则。参赛院系：信息科学与技术学院 参赛队员： 2008 年 6 月 28 日3最佳旅游路线设计摘 要为了提出合适的旅游线路，从实际情况出发考虑，本文建立了合适的线路选择模型，并给出了一些结果。问题一为既考虑旅游消费，又考虑旅游的景点数的旅游线路选择问题。本文对去各景点间的路费、景点门票、在景点内每天的平均消费加以考虑，建立了 规划模型。对于多目标模型，我们采用适当的拟合将多目标转化为单目01标。并使用 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 算法0141 问题重述随着生活水平的提高，旅游逐渐成为最热门的户外活动之一。在旅游的过程中，我们不仅可以感受大自然的美，而且可以领略不同地方的文化气息，乡土风情。在这里考虑到旅游者的以下需求：1.旅游的费用尽可能最省；2.观赏的旅游景点尽可能多；3.旅游者对旅游路线的满意度尽可能高。设计合适的旅游线路方案来满足旅游者的各种需求，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足旅游者的各种不同需求。在这里只针对将要来参加西南交通大学数学系召开的“学术会议”的来自国内外的许多著名学者，为其设计合适的旅游路线。需要解决如下问题：1.根据提供的五条线路，要求设计出合适的旅游路线，使得会议代表能在10 天内花最少的钱，游最多的地方。2.上面考虑的是只有十天时间的情况，当代表时间非常充裕（比如一个月）时，可以游完所有的景点才离开，设计合适的旅游路线，使在四川境内的交通费用尽量地节省。3.根据主办方对代表的游意调查，充分考虑这些代表的意愿，为设计代表们合适的旅游路线，使他们在会议结束后的 10 天时间内花最少的钱游尽可能多的地方。2 条件假设1假设查阅的数据基本符合事实。2假设各景点间的路费及各景点的门票长期基本保持不变。3假设在问题一中不考虑每一条路线的最优，而是考虑整个旅游过程的最优问题。4假设代表在某景点旅游的最长时间不超过 3 天 。3 符号说明模型一中：第 条线路中第 个景点（ 变量）ijyij01第 条路线第 个景点的门票（单位：元）ijp在第 条路线第 个景点平均每天的基本消费（单位：元）ijaij第 条路线的平均路费（单位：元）il10 天中旅游的景点总数c10 天中的总消费（单位：元）n在第 条线路第 个景点观赏的总时间（单位：天）ijtij模型二中：5路线决策变量（ 变量）ijx01 景点到 景点间的路费（单位：元）ijmj总路费（单位：元）L模型三中：去第 条线路的满意度isi去第 条线路的满意度上限0ir去第 条线路的满意度下限1ii整个旅游过程中的满意度之和k4 问题分析题目背景：随着我国经济实力的提高，人们的生活水平也不断的提高。旅游也随之成为很热门的户外活动。旅游不仅可以释放心情，也可以感受到大自然的美，不同的风土人情，不同的人文气息。所以越来越多的人把旅游作为一种享受。在旅游的时候，人们往往会想，怎样才能花最少的钱游最多的地方，怎样的旅游路线才能够使自己最满意。这样就要求我们建立适当的数学模型来解决这些问题。首先我们知道本问题属于旅游线路的优化问题。为了建立模型，首先应该将各景点线路转化为纯数学形式的点线的集合，进行图论方面的分析。1.本问题要解决两方面的问题：在 10 天的旅游时间内，满足（1）旅游的费用尽可能少；（2）观赏的旅游景点尽可能多。根据这些需求，可以从以下两种方案入手：（1）建立多目标优化模型，考虑分层序列法，以旅游费用尽可能少为第一目标，观赏的景点尽可能多作为第二目标。在第一目标求得的可行解集里搜索满足第二目标的路线，将该路线作为最合适的旅游路线。（2）同样建立多目标规划模型，通过适当的拟合或线性加权，把多目标转化为单目标。在这里还把各景点的门票和每天的平均消费考虑进去，以增加模型的实用性。分析上面的两种方案可知，方案一求出来的旅游线路不一定是最佳线路，因为当在满足旅游费用尽可能少时，得到的线路不一定就满足第二个条件，即观赏的景点尽可能多。所以方案一存在一定的问题，我们选择方案二，用通过适当的拟合把多目标转化为一个单目标求解模型。下面给出各条线路的平均路费，各景点的门票，以及各景点平均每天的基本消费：6线路一 线路二 线路三 线路四 线路五 线路价格（元）项目九寨沟黄龙 乐山 峨眉 四姑娘山丹巴 都江堰青城山海螺沟康定平均路费 108 35 105 20 100门票 220 200 90 120 90 50 90 90 90 40每天平均消费 120 80 100 120 100 90 100 100 130 90表二各条线路平均路费、各景点的门票、各景点平均每天的基本消费（单位：元）2在代表的时间比较充裕的条件下，可以把所有的景区参观完，要求建立合适的模型，使得交通费用尽量最省。这时代表就是从成都出发，逐一到达各个景点（不能重复到达） ，观赏完所有景点之后返回成都。根据上面分析可知，该问题属于旅行商问题（Traveling Salesman Problem, TSP） 。为了建立模型，首先应该将各景点转化为纯数学形式的点线的集合，进行图论方面的分析。下面给出旅行商问题的定义：旅行商问题: 一位销售商从N个城市中的某一城市出发, 不重复地走完其余N-1个城市并回到原出发点, 在所有可能路径中求出路径长度最短的一条.用数学语言描述TSP，即给定一组N 个城市和它们两两之间的直达距离, 寻找一条闭合的旅程, 使得每个城市刚好经过一次且总的旅行距离最短。用图语言来描述TSP: 给出一个图G=(V, E) , 每边eE 上有非负权值w(e), 寻找G 的Hamilton 圈C, 使得C的总权 ()eEcWw最小。TSP 问题是一个典型的组合优化问题, 其可能的搜索路径随着城市数目N 的增加呈指数增长, 属于NP完全问题。了解了以上知识后，我们更加确定了该问题就是旅行商问题。只是在实际的处理中，我们把两景点的路费作为赋权值w(e),在一定程度上，各景点间的距离与这两点间的单程路费是成正比的，所以把两景点的路费作为权值w(e)是可行的。下表给出的是任意两景点间的单程车费。路费 地名地名成都 九寨 黄龙 乐山 峨眉山四姑娘山丹巴 都江堰青城山海螺沟康定成都 0 108 100 42 35 105 110 12 20 100 90九寨 108 0 15 200 130 100 120 100 100 220 200黄龙 100 15 0 180 190 90 110 90 90 210 190乐山 42 200 180 0 20 150 170 60 60 100 120峨眉山 35 130 190 20 0 150 180 80 88 50 70四姑娘山 105 100 90 150 150 0 60 30 38 150 120丹巴 110 120 110 170 180 60 0 90 98 130 80都江堰 12 100 90 60 88 30 90 0 8 160 140青城山 20 100 90 60 80 38 98 8 0 170 150海螺沟 110 220 210 100 50 150 130 160 170 0 30康定 90 200 190 120 70 120 80 140 150 30 07表二 各景点间的单程路费（单位：元）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.2=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=120*x11*t11+80*x12*t12+100*x21*t21+120*x22*t22+100*x31*t31+ 70*x32*t32+100*x41*t41+110*x42*t42+130*x51*t51+90*x52*t52;c=x11+x12+x21+x22+x31+x32+x41+x42+x51+x52;n3=z1*s1+(1-z1)*(1-s1)+z2*s2+(1-z2)*(1-s2)+z3*s3+(1-z3)*(1-s3)+