最佳旅游路线设计第三组11. 问题描述今年暑假，西南交通大学数学系要召开“学术议”，届时来自国内外的许多著名学者都会相聚成都。在会议结束后，主办方希望能安排这些远道而来的贵宾参观四川省境内的著名自然和人文景观，初步设想有如下线路可供选择：一号线：成都九寨沟、黄龙；二号线：成都乐山、峨嵋；三号线：成都四姑娘山、丹巴；四号线：成都都江堰、青城山；五号线：成都海螺沟、康定；每条线路中的景点可以全部参观，也可以参观其中之一。不仅如此，一起参观景点的人数越多，每人承担的费用也会越小。2结合上述要求，请你回答下列问题：一、请你们为主办方设计合适的旅游路线，使会议代表在会议结束后的10天时间内花最少的钱游尽可能多的地方。二、如果有一些会议代表的时间非常充裕（比如一个月），他们打算将上述旅游景点全部参观完毕后才离开四川，请你们为他们设计合适的旅游路线，使在四川境内的交通费用尽量地节省。三、主办方在会议开始前对所有参会的100位代表旅游意向进行了调查，调查数据见附件1所示。充分考虑这些代表的意愿，请你们为主办方设计代表们合适的旅游路线，使他们在会议结束后的10天时间内花最少的钱游尽可能多的地方。32. 问题分析2.1问题背景的理解：根据对题目的理解我们可以知道，旅游的总费用包括交通费用和在景点游览时的费用，而在确定了要游览的景点的个数后，所以我们的目标就是在满足所有约束条件的情况下，求出成本的最小值。2.2问题一和问题二的分析：问题一要求我们为主办方设计合适的旅游路线，使会议代表在会议结束后的10天时间内花最少的钱游尽可能多的地方。在这里我们的做法是在满足相应的约束条件下，先确定游览的景点数，然后计算出在这种情况下的最小花费。这样最终会得出几种最佳方案，而组织方可以根据自己的实际情况进行选择。问题二实质上是在问题一的基础上改变了时间约束，即代表们要游览所有的景点，我们完全可以使用与问题一同样的方法进行求解。2.3问题三的分析：问题三要求我们在问题一的基础上充分考虑代表们对各个景点的意愿来设计最佳旅游路线，而代表们的意愿由附件1给出。对于意愿，我们的做法是将其转化为相应的权重，然后乘以相应的旅游景点的花费，再利用问题一的模型得出几种最佳方案供主办方选择。43.模型假设1.所给的5条路线每条路线中的景点可以全部参观，也可以参观其一；2.参观景点的人数越多，每人承担的费用越少；3.数学系使用旅游大巴安排代表们往返于各个旅游景点，其交通费用、在景点的花费、在景点的逗留时间参照当地客运公司及旅行社的数据；4.代表们所乘坐的旅游大巴平均时速为50km/h，平均费用为0.3元/km；5.一个景点直接到达另外一个景点是指，途中经过的其他景点只是一个转站地，而并不进行游览；6.在限定的时间内，代表们最终要返回成都，并且假设成都是代表们肯定要去的一个旅游景点；7.假设参观景点的人数每增加一人，每个代表在景点的费用就减少原价的1；8.代表们在途中和游览景点的时间为12小时，而另外12小时为休息、用餐及其他琐事时间。54. 符号说明 , 第 个或者第 个景点， =1,2,11; 分别表示成都、九寨沟、黄龙、乐山、峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺沟、康定； 每个会议代表的旅游总花费； 每个会议代表在第 个景点的逗留时间； 每个会议代表在第 个景点的总消费； 从第 个景点到第 个景点路途中所需时间； 从第 个景点到第 个景点所需的交通费用； 6 5. 模型建立5.1 问题一： 目标函数的确立： 经过对题目分析，我们可以知道本题所要实现的目标是，使会议代表在10天时间内花最少的钱游览尽可能多的地方。显然，花费最少和游览的景点尽量多是该问题的两个目标。因此，我们的做法是在满足相应的约束条件下，先确定游览的景点数，然后计算出在这种情况下的最小花费。这样最终会得出几种旅游路线，而组织方可以根据自己的实际情况进行选择。 游览的总费用由2部分组成，分别为交通总费用和在旅游景点的花费。我们定义： 每个代表的旅游总花费； 每个代表的交通总费用； 每个代表的旅游景点的花费；从而得到目标函数： Min 7（1）交通总花费因为 表示从第 个景点到第 个景点所需的交通费用，而 是判断代表们是否从第 个景点直接到第 个景点的01变量，因此我们可以很容易的得到交通总费用为：8（2）旅游景点的花费 因为 表示会议代表们在 个景点的总消费， 也可以表示出代表们是否到达过第 个和第 个景点，而整个旅游路线又是一个环形， 因此 实际上将代表们在所到景点的花费计算了两遍，从而我们可得旅游景点的花费为：9目标函数如下：Min 10时间约束由题目可知，代表们在川的旅游时间应该不多于10天(120小时)，而这些时间包括在路途中的时间和在旅游景点逗留的时间。因为 表示从第 个景点到第 个景点路途中所需时间，所以路途中所需总时间 表示会议代表们在第 个景点的逗留时间，故代表们在旅游景点的总逗留时间为 因此，总的时间约束为：11旅游景点数约束根据假设，整个旅游路线是环形，即最终代表们要回到成都，因此 即表示代表们旅游的景点数，这里我们假定要旅游的景点数为 （n =2，3，11）。因此旅游景点数约束为：1201变量约束我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束： （i，j =1，2，11）当 时，因为成都是出发点，所以 ； 时，因为代表们最终要回到成都，所以 13约束条件如下：14 模型的求解与结果分析：15从而根据模型，使用Lingo编程，得出结果如下表：（其中数字（其中数字1-11分别表示成都、九寨沟、黄龙、乐山、分别表示成都、九寨沟、黄龙、乐山、峨嵋、四姑娘山、丹巴、峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺沟、康定都江堰、青城山、海螺沟、康定）16对于上述结果，我们的推荐为：路线一：成都乐山都江堰青城山成都 旅游景点数：4 人均费用：623元；路线二：成都都江堰青城山丹巴乐山成都 旅游景点数：5 人均费用：949元；路线三：成都乐山康定丹巴青城山都江堰成都 旅游景点数：6 人均费用：1207元。17创新 一min max18约束条件19创新 二转化单目标法线性加权和法：按照m个目标 的重要程度，分别乘以一组权系数，然后相加作为目标函数。20约束条件215.2 问题二此问与第一问大同小异，不同的是代表们要完成所有景点的旅游，而目标函数是求最少的交通费。由第一问结论可知，交通费用为： 22模型建立：综上所述，我们可以得到总的模型为：约束条件：23模型求解与结果分析：根据模型，使用Lingo编程，得出结果为：245.3 问题三此问在第一问的基础上增加了代表们意愿这一条件，通过对附件一的观察，我们发现代表们的意愿分为“去”、“不去”和“无所谓”三种。怎样将这些文字转换到公式中来表达代表们的意愿就成为了解决该问的关键。在这里我们采用加权重的方式，将代表们的意愿理解为对该线路上两个景点的权重，又因为我们最终的目标是使旅游的费用最少，因此越热门的景点相应的权重也应该越低（这是因为权重越低，其与该景点的费用相乘后也越低，从而增加了对该景点游览的可能性）。25代表们意愿26数据处理将所有的“去”替换为0，所有的“不去”替换为1，所有的“无所谓”替换为0.5，从而得到一个100X5的矩阵 我们定义： 第 个旅游景点的权重。由假设可知成都是代表们肯定要游览的一个景点，因此 。27对其他权重进行标准化处理可得：28模型建立综上所述，我们可以得到总的模型为：约束条件：29模型求解与结果分析：（其中数字（其中数字111分别表示成都、九寨沟、黄龙、乐山、峨嵋、四姑娘山、丹巴、分别表示成都、九寨沟、黄龙、乐山、峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺沟、康定）都江堰、青城山、海螺沟、康定）30对于上述结果，我们的推荐为路线一：成都青城山都江堰乐山成都 旅游景点数：4 人均费用：573元；路线二：成都乐山都江堰青城山丹巴成都 旅游景点数：5 人均费用：927元；路线三：成都乐山都江堰青城山丹巴康定成都旅游景点数：6 人均费用：1160元。31谢谢 谢！谢！32