最佳旅游线路-数学建模

1最佳旅游路线设计摘要本文主要研究最佳旅游路线的设计问题。在满足相关约束条件的情况下，花最少的钱游览尽可能多的景点是我们追求的目标。基于对此的研究，建立数学模型，设计出最佳的旅游路线。第一问给定时间约束，要求为主办方设计合适的旅游路线。我们建立了一个最优规划模型，在给定游览景点个数的情况下以人均总费用最小为目标。再引入0—1变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求解。推荐方案：成都→都江堰→青城山→丹巴→乐山→成都，人均费用为949元（此处不考虑旅游人数对游览费用的影响）。第二问放松时间约束，要求代表们游遍所有的景点，该问题也就成了典型的货郎担（TSP）问题。同样使用第一问的模型，改变时间约束，使用lingo编程得到最佳旅游路线为：成都→乐山→峨眉→海螺沟→康定→丹巴→四姑娘山→青城山→都江堰→九寨沟→黄龙→成都，人均费用为3243元。第三问要求在第一问的基础上充分考虑代表们的旅游意向，建立模型求解。通过对附件一数据的观察，我们使用综合评判的方法，巧妙地将代表们的意愿转化为对相应旅游景点的权重，再对第一问的模型稍加修改，编程求出对应不同景点数的最佳路线。推荐路线：成都→乐山→都江堰→青城山→丹巴→成都，人均费用为927元。对于第四问，由于参观景点的人数越多每人承担的费用越少，因此我们要考虑的是尽量使得两组代表在共同旅游的时间内在相同的景点游览。正是基于此，我们建立模型求解。推荐路线：第一组：成都→乐山→丹巴→都江堰→青城山→成都第二组：成都→都江堰→青城山→峨眉→乐山→成都，两组在都江堰会合并且共同游览了都江堰和青城山，人均费用为971元。第五问中，首先我们修改了不合理数据，并用SPSS软件对缺省数据进行了时间序列预测。其次我们合理定义了阴雨天气带来的损失，以人均总花费最小和阴雨天气带来的损失最小为目标，建立加权双目标规划模型。推荐路线：成都→康定→青城山→都江堰→乐山→成都，相应人均消费987元，阴雨天气带来的损失为1.6。本文思路清晰，模型恰当，结果合理.由于附件所给数据的繁杂，给数据的整理带来了很多麻烦，故我们利用Excel排序，SPSS预测，这样给处理数据带来了不少的方便。本文成功地对0—1变量进行了使用和约束，简化了模型建立难度，并且可方便地利用数学软件进行求解。此外，本文建立的模型具有很强普适性，便于推广。关键词：最佳路线TCP问题综合评判景点个数最小费用21问题重述今年暑假，西南交通大学数学系要召开“××学术会议”，届时来自国内外的许多著名学者都会相聚成都。在会议结束后，主办方希望能安排这些远道而来的贵宾参观四川省境内的著名自然和人文景观，初步设想有如下线路可供选择：一号线：成都→九寨沟、黄龙；二号线：成都→乐山、峨嵋；三号线：成都→四姑娘山、丹巴；四号线：成都→都江堰、青城山；五号线：成都→海螺沟、康定；每条线路中的景点可以全部参观，也可以参观其中之一。不仅如此，一起参观景点的人数越多，每人承担的费用也会越小。结合上述要求，请你回答下列问题：一、请你们为主办方设计合适的旅游路线，使会议代表在会议结束后的10天时间内花最少的钱游尽可能多的地方。二、如果有一些会议代表的时间非常充裕（比如一个月），他们打算将上述旅游景点全部参观完毕后才离开四川，请你们为他们设计合适的旅游路线，使在四川境内的交通费用尽量地节省。三、主办方在会议开始前对所有参会的100位代表旅游意向进行了调查，调查数据见附件1所示。充分考虑这些代表的意愿，请你们为主办方设计代表们合适的旅游路线，使他们在会议结束后的10天时间内花最少的钱游尽可能多的地方。四、由于会议安排原因，附件1中的后50位代表要拖后四天时间才能去旅游观光（每人旅游总时间保持不变）。请在问题三基础上考虑时间滞后因素，为主办方设计合适的旅游路线，使代表们在10天的时间里花最少的钱游尽可能多的地方。五、在旅游过程中最担心出现阴雨天气，这种气候环境是最不适合旅游的。因此，在出发前，主办方询问了四川省气象局这五条旅游线路降雨的概率，具体数据见附件2。请在问题三的基础上增加气候因素，为主办方设计合适的旅游路线，使代表们在10天的时间里花最少的钱游尽可能多的地方，同时因阴雨天气而带来的旅游不便损失降为最低。2问题分析2.1问题背景的理解：根据对题目的理解我们可以知道，旅游的总费用包括交通费用和在景点游览时的费用，而在确定了要游览的景点的个数后，所以我们的目标就是在满足所有约束条件的情况下，求出成本的最小值。2.2问题一和问题二的分析：问题一要求我们为主办方设计合适的旅游路线，使会议代表在会议结束后的10天时间内花最少的钱游尽可能多的地方。在这里我们的做法是在满足相应的约束条件下，先确定游览的景点数，然后计算出在这种情况下的最小花费。这样最终会得出几种最佳方案，而组织方可以根据自己的实际情况进行选择。问题二实质上是在问题一的基础上改变了时间约束，即代表们要游览所有的3景点，我们完全可以使用与问题一同样的方法进行求解。2.3问题三的分析：问题三要求我们在问题一的基础上充分考虑代表们对各个景点的意愿来设计最佳旅游路线，而代表们的意愿由附件1给出。对于意愿，我们的做法是将其转化为相应的权重，然后乘以相应的旅游景点的花费，再利用问题一的模型得出几种最佳方案供主办方选择。2.4问题四和问题五的分析：问题四将100名代表平均分成了两组，而第二组则晚了四天出发。由于题目中告诉我们参观景点的人数越多，每人承担的费用越少，因此我们应该考虑使两组同时在外旅游是尽量在同一景点游览，来减少旅游总费用。基于此思想建立模型求解即可。问题五在问题三的基础上考虑了天气的因素，因为阴雨会给代表们带来一定的损失，因此该问又增加了一个使损失最小的目标。我们在定义这个损失后，对总费用和损失两个目标分别加权，以最小为目标求出相应的方案即可。3模型假设1.所给的5条路线每条路线中的景点可以全部参观，也可以参观其一；2.参观景点的人数越多，每人承担的费用越少；3.数学系使用旅游大巴安排代表们往返于各个旅游景点，其交通费用、在景点的花费、在景点的逗留时间参照当地客运公司及旅行社的数据；4.代表们所乘坐的旅游大巴平均时速为50km/h，平均费用为0.3元/km；5.一个景点直接到达另外一个景点是指，途中经过的其他景点只是一个转站地，而并不进行游览；6.在限定的时间内，代表们最终要返回成都，并且假设成都是代表们肯定要去的一个旅游景点；7.假设参观景点的人数每增加一人，每个代表在景点的费用就减少原价的1‰；8.代表们在途中和游览景点的时间为12小时，而另外12小时为休息、用餐及其他琐事时间。4符号说明i,j——第i个或者第j个景点，i，j=1，2，……，11；分别表示成都、九寨沟、黄龙、乐山、峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺沟、康定；c——每个会议代表的旅游总花费；it——每个会议代表在第i个景点的逗留时间；ic——每个会议代表在i个景点的总消费；ijt——从第i个景点到第j个景点路途中所需时间；4ijc——从第i个景点到第j个景点所需的交通费用；01ijr其他个景点个景点到达第代表们直接从第ji5模型建立及求解5.1问题一：5.1.1目标函数的确立：经过对题目分析，我们可以知道本题所要实现的目标是，使会议代表在10天时间内花最少的钱游览尽可能多的地方。显然，花费最少和游览的景点尽量多是该问题的两个目标。因此，我们的做法是在满足相应的约束条件下，先确定游览的景点数，然后计算出在这种情况下的最小花费。这样最终会得出几种旅游路线，而组织方可以根据自己的实际情况进行选择。游览的总费用由2部分组成，分别为交通总费用和在旅游景点的花费。我们定义：m——每个代表的旅游总花费；1m——每个代表的交通总费用；2m——每个代表的旅游景点的花费；从而得到目标函数：Minm＝1m＋2m（1）交通总花费因为ijc表示从第i个景点到第j个景点所需的交通费用，而ijr是判断代表们是否从第i个景点直接到第j个景点的0—1变量，因此我们可以很容易的得到交通总费用为：1111111ijijijcrm（2）旅游景点的花费因为ic表示会议代表们在i个景点的总消费，ijr也可以表示出代表们是否到达过第i个和第j个景点，而整个旅游路线又是一个环形，因此111111ijjiijccr实际上将代表们在所到景点的花费计算了两遍，从而我们可得旅游景点的花费为：111111221ijjiijccrm5从而我们可以得到目标函数为：Minm＝1m＋2m＝111111ijijijcr+11111121ijjiijccr5.1.2约束条件：①时间约束由题目可知，代表们在川的旅游时间应该不多于10天(120小时)，而这些时间包括在路途中的时间和在旅游景点逗留的时间。因为ijt表示从第i个景点到第j个景点路途中所需时间，所以路途中所需总时间为111111ijijijtr；it表示会议代表们在第i个景点的逗留时间，故代表们在旅游景点的总逗留时间为11111121ijjiijttr。因此，总的时间约束为：111111ijijijtr+11111121ijjiijttr120②旅游景点数约束根据假设，整个旅游路线是环形，即最终代表们要回到成都，因此111111ijijr即表示代表们旅游的景点数，这里我们假定要旅游的景点数为n（n=2，3，……，11）。因此旅游景点数约束为：111111ijijnr（n=2，3，……，11）③0——1变量约束我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束：iijr1jijr（i，j=1，2，……，11）当1i时，因为成都是出发点，所以11iijr；1j时，因为代表们最终要回到成都，所以11jijr。综合以上可知，iijr1jijr（i，j=1，2，……，11）611iijr11jijr同样，当i，2j时，根据题意不可能出现1jiijrr，即不可能出现游客在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。因此我们可得约束：0jiijrr（i，j=2，3，……，11）5.1.3模型建立：综上所述，我们可以得到总的模型为：Minm＝1m＋2m＝111111ijijijcr+11111121ijjiijccr约束条件：111111ijijijtr+11111121ijjiijttr120111111ijijnr（n=2，3，……，11）iijr1jijr（i，j=1，2，……，11）11iijr11jijr0jiijrr（i，j=2，3，……，11）5.1.4模型求解与结果分析：在这里我们引入以下符号：ijd——第i个景点和第j个景点之间的路程；v——代表们所乘坐的旅游大巴的平均时速，v=50km/h；m——代表们所乘坐的旅游大巴的平均费用，h=0.3元/h；通过上网查询资料，我们可以得到ijd的具体值，根据公式ijt=ijd/v可得到相应的ijt，同样根据公式ijc=ijd×m可以得到相应的ijc（i，j=1，2，……，11）。（ijd、ijt和ijc的具体数值见附录）同样，通过对四川的一些旅行社进行咨询，我们得出会议代表们在第i个景点的最佳逗留时间和他们在第i个景点总消费：7t1t2t3t4t5t6t7t8t9t10t1172418123630129152417(单位：小时)c1c2c3c4c5c6c7c8c9c10c1112042330013537839017590148303241(单位：元)从而根据模型，使用Lingo编程，得出结果如下表：旅游景点数n