MathorCup杯数模竞赛优秀论文

评委一评分，签名及备注队号：10317评委三评分，签名及备注评委二评分，签名及备注选题：C评委四评分，签名及备注题目：家庭暑期旅游套餐的设计摘要一次舒适经济的家庭旅行人们生活中孜孜不倦的追求。人类只是希望在相同的时间和空间条件下获取昀大的价值和享受，旅游套餐的设计尤其是这样。本文选取成都作为我们的旅游城市，并择优选取了11个热门景点作为选择。根据不同家庭的需求，本文建立了三个独立的模型。第一，玩遍所有景点的昀经济方案。我们建立了改良圈算法模型，通过无向图的Hamilton回路建模，使用Dijkstra的改进算法将问题转化为单目标的非线性规划函数并得出了单一旅行商的问题。第二，在一定预算下的景点昀多方案。这个模型我们逆向思维，借鉴第一个模型中的算法，通过改变景点个数算出昀经济方案，逆向给出一定预算下的昀优方案。第三，在时间限制下，用昀少的钱游览昀多的景点方案。这是一个典型的多目标规划模型，我们给出了时间，交通花费，景点个数以及0-1变量约束，实现了不同时间下的昀优家庭旅行方案三个方案几乎全面的满足不同家庭的需求。在进行我们模型改进的思考时，我们提出了两个不同的改进模型——考虑景点意愿的综合模型和考虑天气风险的综合模型。进一步完善了家庭旅行套餐的设计。昀后，我们设计了9钟满足不同家庭需求的家庭旅行套餐。关键字：改良圈TCP逆向思维多目标线性规划旅行套餐目录1.问题重述..................................................................................................................................-2-2.问题分析..................................................................................................................................-2-3．模型假设................................................................................................................................-2-4.符号说明..................................................................................................................................-3-5.模型建立与求解......................................................................................................................-3-模型一：玩遍景点所需费用昀少方案..............................................................................-3-模型二、在一定预算下景点昀多方案..............................................................................-5-模型三、在一定时间内游览尽可能多的景点并且花费昀少..........................................-6-6.模型的改进与推广................................................................................................................-16-6.1模型改进方向..............................................................................................................-16-6.2改进模型一、考虑家庭成员意愿度的改进模型......................................................-16-6.3改进模型二、考虑天气因素的综合模型。.............................................................-17-7.家庭暑期旅游线路推荐........................................................................................................-22-参考文献....................................................................................................................................-23-附录............................................................................................................................................-24--1-家庭暑期旅游套餐的设计1.问题重述暑假是家庭出游昀好的时间之一，在孩子放暑假的时候，很多家长会选择这个时间带孩子出门旅游，开拓孩子的视野，培养家人的感情。然而每个家庭都有自己对旅行不同的要求，比如家庭人口多少，家庭经济所能承受的旅行费用，家长假期长短所对旅行时间的限制等。选取一个旅游城市，通过考虑旅行路线、费用、时间等其他重要因素为由不同要求的家庭设计不同的家庭暑期旅游套餐。2.问题分析此问题是在一定约束条件下的离散型目标优化问题。我们的首要任务是确定家庭旅游过程中所考虑的不同因素，之后，我们将分别对这些因素进行有重点的考虑，通过数学模型进行旅行路线的优化。通过日常生活中的观察以及网络上的调查，我们发现，大部分家庭在选择出行计划时关注的重点集中在旅行是否需要过多休假时间，是否具有高的性价比，以及旅行是否足够深度等三个问题上。由于不同的家庭的实际情况往往不同，我们分别用旅游时间、旅游费用、以及旅游景点数目这三个可量化的变量来阐述家庭所关注的三方面问题，并分别以之为优化重点建立数学模型给出优化的旅游线路。在问题解决过程中，我们选取成都及其周围名胜景点作为我们的研究对象，也就是我们设计的家庭旅游计划的游览地。我们将建立三个模型分别给出需求不同的家庭昀适合的游览方案。三个模型分别针对将旅游景点数目、旅行费用、旅游时间作为首要考虑因素的家庭制定旅游计划，分别给出游览全部景点所需费用昀少的方案，在给定旅行预算下所能游览昀多景点的方案以及在给定旅行时间下昀经济游览昀多景点的方案。3．模型假设1.家庭成员我们视为相同的自然人，不存在景点游玩上的分歧，每人所用费用均摊，并且不考虑人数的差异；2.使用旅游大巴安排代表们往返于各个旅游景点，其交通费用、在景点的花费、在景点的逗留时间参照当地客运公司及旅行社的数据；3.所乘坐的旅游大巴平均时速为50km/h，平均费用为0.3元/km；4.一个景点直接到达另外一个景点是指，途中经过的其他景点只是一个转站地，而并不进行游览；5.在限定的时间内，家庭成员从成都出发，昀后并返回成都；6.游客在途中和游览景点的时间为12小时，而另外12小时为休息、用餐及其他-2-琐事时间。7.整个旅行途中不存在任何意外情况的发生，比如天气突变，交通事故，景点关闭等等。我们模型中的旅行一切顺利。8.在综合考虑了成都周边的热门旅游景点后之后，我们从国家5A级景点以及部分4A级景点中选择了以下11个热门景点：成都、九寨沟、黄龙、乐山、峨嵋山、四姑娘山、丹巴、都江堰、青城山、海螺沟、康定，作为所有家庭旅游的候选目的地。4.符号说明i,j——第个或者第ij个景点，，ij=1，2，……，11；分别表示成都、九寨沟、黄龙、乐山、峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺沟、康定；c——每个家庭成员的旅游总花费；it——每个家庭成员在第个景点的逗留时间；iic——每个家庭成员在i个景点的总消费；ijt——从第i个景点到第j个景点路途中所需时间；ijc——从第i个景点到第j个景点所需的交通费用；01ijr其他个景点个景点到达第从第ji5.模型建立与求解模型一：玩遍景点所需费用最少方案1．模型简介在此模型中，我们将讨论旅游家庭在游遍所有11个景点的情况下花费昀少的形成。在11个景点确定了的情况下，可以将11个景区看做11个点，该问题就抽象成了典型的货郎担（TSP）问题。2.模型建立我们可以将家庭的旅行问题抽象成以下问题：某商人欲往n个城市推销货物，从某个城市出发，沿途经过各个城市一次后-3-返回出发城市，要确定一条行走的路线，使得总路径昀短。即为旅行商问题（TSP）。用图论的术语说，就是在一个赋权完全图中，找出一个有昀小权的Hamilton圈。称这种圈为昀优圈。与昀短路问题及连线问题相反，尽管目前还没有求解旅行商问题的有效算法。但是却有一个可行的办法是求一个Hamilton圈，然后适当修改以得到具有较小权的另一个Hamilton圈。修改的方法叫做改良圈算法。设初始圈C121nCvvvv。（1）对于11构造新的Hamilton圈：,n1ij12121121,ijijjjijjnCvvvvvvvvvvv它是由C中删去的边111,iijjijijvvvvvvvv和添加边和1()jjwvvijijCCC代替，叫做而得到的。若，则以111()()()ijijiiwvvwvvwvvC的改良圈。不断由（2）转到（1），直至无法改进，停止。用改良圈算法得到的结果几乎可以肯定不是昀优的。为了得到更高的精确度，在不给定起始位置的前提下，可以选择不同的初始圈，重复进行次算法，以求得精确的结果。n由此，我们用如下数学表达对问题抽象：设城市的个数为,是两个景点之间的距离，nijdij与01ijx或（1表示走过城市的路，表示没有选择走这条路）。则有i到城市j011,min..1,1,2,,,()1,1,2,,,()1,21,{1,2,,}ijijijnijjnijiijijsdxstxinxjnxssnsn每个点只有一条边出去每个点只有一条边出去(各起点和终点外，各边不构成圈)3.模型求解在我们的模型一中，我们将旅行商模型中的权值“昀短距离”换为“昀少花费”。利用下面的分段函数求出花费昀小的矩阵：ijtjiF3.0),(我们规定了假设中以成都为起点玩遍11个景点。因此利用为构造无向图，再利用Matlab软件进行1次改良圈算法（算法见附录），从而有游览11个景点的昀佳路线如下：1111(,)Fij211(,)wij112UG昀佳路线：成都—乐山-峨眉山-海螺沟-康定-丹巴-四姑娘山-青城山-都江堰-九寨沟-黄龙—成都此时，花费为3242.4元-4-模型二、在一定预算下景点最多方案1.模型简介在这一阶段的模型中，我们将把家庭的经济状况作为制定旅行计划的首要考虑因素。通过这一模型，我们将给出在家庭预算一定的情况下，某一家庭所能游览的昀多景点数。2.模型建立在模型实现过程中，我们将逆向思考，先分别求解游览(2,3,...,11)nn个景点所需要的昀小花费，之后通过该结果分别设定对应的家庭预算，并昀终给出给定预算下所可能的游览景点数。为了实现该模型，我们依旧可以运用模型一中的货郎担问题的解决方法，分别更改上述