数学建模竞赛获奖作品

承 诺 书

我们仔细阅读了新余学院大学生数学建模竞赛的竞赛规则。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B中选择一项填写）： B

我们的参赛报名号为（如果设置报名号的话）： 24

参赛队员 (打印并签名) ：1. 刘水根 2. 游凯 3. 王娟

日期： 2011 年 05 月 15 日

评阅编号：

精选文库

新余学院第二届数学建模竞赛

评阅专用页

假设的合理性 10分 算法的正确性 20分 语言文字表述创新性 清晰、流10分 畅 20分 论文的整体美观度 10分 论文的完整性 10分 评阅编号 阅卷人 （签名） 摘要 20分 总分 总平均分 组长签名： 年 月 日

--

2

精选文库

最佳旅游路线设计

摘要

本文主要研究最佳旅游路线的设计问题。在满足相关约束条件的条件下，实现小张的旅游愿望。基于对此的研究，建立数学模型，设计出最佳的旅游路线和途径。

第一问没有时间的约束，要求设计合适的旅游路线。该问题是典型的货郎担（TSP）问题。我们建立了一个最优规划模型，在将八个旅游景点全部游完的前提下花最少的钱为目的。从而推出交通费用、住宿餐饮费用和景点花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求解。推荐方案：新余→福建武夷山→温州梅雨潭→河南嵩山少林寺→四川九寨沟→云南丽江古城→贵州黄果树→广西桂林大漓江→宜春明月山→新余。预计总费用为约2658.5元人名币。

第二问放松费用的约束，要求游完所有景点。同样使用第一问的模型，改变时间约束，使用lingo编程得到最佳旅游路线为：新余→宜春明月山→福建武夷山→浙江温州梅雨潭→河南嵩山少林寺→四川九寨沟→云南丽江古城→贵州黄果树→新余。

第三问在一、二问的基础上，增加了时间和费用的先限制，要求设计合适的旅游线路，使在约束条件下，所游景点最多。再引入0—1变量表示是否游览某个景点，从而推出交通费用、住宿餐饮费用和景点花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求解。推荐方案：

1. 新余→宜春明月山→福建武夷山→温州梅雨潭→河南嵩山少林寺→新余 2. 新余→宜春明月山→桂林大漓江→贵州黄果树→云南丽江古城→新余

本文思路清晰，模型恰当，结果合理.由于附件所给数据的繁杂，给数据的整理带来了很多麻烦，故我们利用Excel排序，word编辑，这样给处理数据带来了不少的方便。本文成功地对0—1变量进行了使用和约束，简化了模型建立难度，并且可方便地利用数学软件进行求解。此外，本文建立的模型具有很强普适性，便于推广。

关键词：最佳路线 TCP问题 综合评判 景点个数 最小费用

--

3

精选文库

1 问题重述

随着人们生活水平的不断提高，假期旅行已受到越来越多人的青睐。假设小张也是一位旅游爱好者，想通过今年暑假到全国的一些著名景点旅游，具体旅游时间从7月3日上午八点开始，从新余出发，最后回到新余。考虑到跟团旅行受到的各种限制，他打算作为一名背包客出行，并列选了全国八个旅游景点作为游玩对象，具体的旅游景点名称、门票价格及最短逗留时间如下表： 省市 景点名称 门票价格 在景点最短逗留时间 广西 江西 云南 贵州 福建 河南 四川 浙江 桂林大漓江 宜春明月山 丽江古城 黄果山 武夷山 嵩山少林寺 九寨沟 温州梅雨潭 220 100 100 180 120 100 220 120 4小时 4小时 3小时 3小时 6小时 4小时 5小时 3小时 假设已知条件还有： 1、两城市之间来往可乘火车（动车或高铁）、长途汽车或飞机（不允许包车

或包机）；

2、市内交通可乘坐公交车、地铁或出租车；

3、旅游的门票价格以上标价格为准，不存在学生票半价，其他旅游费用包

括交通费、住宿费、餐饮费等。又假如小张为晚上20：00至次日7：00之间在某地逗留时间超过6小时，则必须住宿，住宿费用不超过180元/天，餐饮费用为60元/天，出租车费用外算； 4、各景点的开放时间为08：00-19：00.

请根据以上已知条件，针对如下几种情况，结合实际问题，为小张设计详细的旅游行程表，入住宾馆的时间、地点、及宾馆名称，景点的停留时间等信息。

1、如果时间不限，将所有八个旅游景点全部游完，至少需要多少时间，请建立相应的数学模型并设计旅游行程表；

2、如果旅游费用不限，将所有八个景点全部游玩，至少需要多少时间，请建立相应的数学模型并设计旅游行程表；

3、如果游客只有四天时间，1500元旅游费用，想尽可能多的旅游景点，请建立相应的数学模型并设计旅行行程表。

2 问题分析

2.1问题背景的理解：

--

4

精选文库

根据对题目的理解我们可以知道，旅游的总费用包括交通费用、住宿餐饮费用和在景点游览时的费用，而在确定了要游览的景点的个数后，所以我们的目标就是在满足所有约束条件的情况下，求出成本的最小值。 2.2问题一、问题二和问三的分析。

问题一要求我们为小张设计合适的旅游路线，使小张在时间充裕的条件下花最少的钱将所有景点游完。在这里我们的做法是在满足相应的约束条件下，计算出在这种情况下的最小花费。

问题二实质上是在问题一的基础上改变了约束条件，使得没有费用的限制下花最少的时间去将所有的景点游完。我们完全可以使用与问题一同样的方法进行求解。

问题三要求我们在问题一的基础上充分考虑小张的实际情况来设计最佳旅游路线，在这里我们的做法是在满足相应的约束条件下，先确定游览的景点数，然后计算出在这种情况下的最小花费。

3模型假设

1、所给前两条线路中的景点必须全部参观，最后一条线路中的景点可以去不参观，也可以参观其一；

2、不考虑旅游天气对游览费用的影响； 3、一个景点直接到达另外一个景点是指，途中经过的其他景点只是一个转站地，而并不进行游览；

4、在限定的时间内，代表们最终要返回成都，并且假设成都是代表们肯定要去的一个旅游景点；

5、使用旅游大巴安排代表们往返于各个旅游景点，其交通费用参照当地客运公司的数据；在景点的花费、在景点的逗留时间参照题目中的附表中的数据； 6、小张乘坐的旅游大巴平均时速为50km/h，平均费用为0.3元/km；

4 符号说明

i,j——第i个或者第j个景点， i，j=1，2，……，8；

分别表示桂林大漓江、明月山、丽江古城、黄果山、武夷山、嵩山少林寺、九寨沟、温州梅雨潭；

c——小张的旅游总花费；

ti——小张在第i个景点的逗留时间； ci——小张在第i个景点的总消费；

tij——从第i个景点到第j个景点路途中所需时间； cij——从第i个景点到第j个景点所需的交通费用；

-- 5

精选文库

n—— 表示小张在旅途中的住宿总费用（具体见附表）。

i个景点到达第j个景点1代表直接从第 rij

其他05 模型建立及求解

5.1 问题一：

5.1.1 目标函数的确立：

经过对题目分析，我们可以知道本题所要实现的目标是，使小张在时间充裕的条件下花最少的钱游览全部的旅游景点。显然，花费最少是该问题的一个目标。因此，我们的做法是在满足相应的约束条件下，确定游览的8景点数，然后计算出在这种情况下的最小花费。这样最终会得出几种旅游路线，而小张可以根据自己的实际情况选择。

游览的总费用由3部分组成，分别为交通总费用、住宿餐饮费用和在旅游景点的花费。我们定义：

m——小张的旅游总花费；

m1——小张的交通总费用；

m2——小张的旅游景点的花费；

m3——小张的餐饮总费用。

从而得到目标函数： Min m＝m1＋m2+m3 （1）交通总花费

因为cij表示从第i个景点到第j个景点所需的交通费用，而rij是判断代表们是否从第i个景点直接到第j个景点的0—1变量，因此我们可以很容易的得到交通总费用为：

m1rijcij

i1j188（2）旅游景点的花费

因为ci小张在i个景点的总消费，rij也可以表示出小张是否到达过第i个和第j个景点，而整个旅游路线又是一个环形，因此rijcicj实

i1j188际上将小张在所到景点的花费计算了两遍，从而我们可得旅游景点的花费为：

188m2rijcicj

2i1j1-- 6

精选文库

（3）餐饮费用

根据题目意思餐饮费用为60元/天，所以餐饮总费用60我们可以的到小张的餐饮总费用为

(ti1i188itij)24，

m3=60(ti1i188itij)24

（4）住宿费用

由下表可知住宿总费用为n=223元人民币

从而 旅馆名字 住宿费 成都广胜旅社 九寨沟雅来旅社 贵阳永逢旅社 柳州云来旅社 桂林平顺旅社 我们可以得到目标函数为：

Min m＝m1＋m2+m3+n

入住时间 40 50 45 39 49 21:10 20:15 2:00 2:30 1:30 =

8ri1j188ijcij+

188rijcicj2i1j1+60



(ti1i18itij)24+n

5.1.2 约束条件：

①旅游景点约束

根据旅游线路使环形，即最终小张要回到新余因此i1i1小张旅游的景点数。因此旅游景点数约束为：

j8j8rij8即表示

ri1i188ij8

-- 7

精选文库

②时间条件

由题目可知，小张如果在20：00至次日7：00之间在某地逗留小时则

必住宿，为了节省开资，某地逗留时间t要小于6小时。 ③0——1变量约束

根据假设，整个旅游路线是环形，即最终代表们要回到新余，因此我们可以把整个路线看做一个Hamilton圈，这样该问题就归结为货郎担（TSP）问题，当然前提是我们已经知道了要旅游所有的景点。因此，对于Hamilton圈中的每个点来说，只允许有一条边进入，同样，也只允许有一条边出去。用公式表示即为：

riij1 rij1 （i，j=1，2，……，11）

j同样，当i，j2时，根据题意不可能出现rijrji1，即不可能出 现游客在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。因此我们可得约束：

rijrji0 （i，j=2，3，……，11）

5.1.3模型建立：

综上所述，我们可以得到总的模型为：

Min m＝m1＋m2+m3+n

=

ri1j188ijcij8+

188rijcicj2i1j1+

60

(ti1i18itij)24+n

约束条件：

ri1j188ijn （n=8）

riij1 rij1

jrijrji0

t6

--

8

精选文库

5.1.4 模型求解与结果分析： 各景点逗留时间（小时） t1 t2 t3 t4 t5 t6 t7 t8 4 4 3 各景点价格（元） c1 3 c4 6 c5 4 c6 5 c7 3 c7 c2 c3 220 100 100 180 120 100 220 120 行程表 起点乘车类起始时到达时景点停终点站 车次 票价 站 型 间 间 留时间 新余 武夷山 火车 K1681/k1684 0:29 7:07 6小时 63 武夷上饶 火车 2002 18:14 20:35 、 18 山 上饶 温州 火车 2208/2205 23:01 6:55 3小时 57 温州 合肥 火车 K8492/K8493 22:00 10:59 、 126 合肥 郑州 火车 2192/2193 23:45 8:01 、 41 郑州 登封 汽车 、 11:32 11:50 4小时 18 登封 郑州 汽车 、 17:30 17:48 、 18 郑州 成都 火车 K290/K291 21:39 19:56 、 170 成都 九寨沟 汽车 、 7:20 12:20 5小时 63 九寨成都 汽车 、 8:00 15:00 、 65 沟 成都 广通 火车 K145 15:40 7:46 、 125 广通 丽江东 火车 K9610/K9611 12:42 17:56 3小时 67 丽江昆明 火车 K9612/K9609 21:30 6:03 、 88 东 昆明 安顺 火车 K110 6:35 15:52 3小时 79 安顺 贵阳 火车 K156 1:21 1:42 、 16 贵阳 柳州 火车 K850/K851 17:05 1:40 、 35 柳州 桂林 火车 2514 22:40 0:54 4小时 14 桂林 宜春 火车 1558 0:43 12:39 4小时 81 宜春 新余 火车 1236 18:43 19:24 、 4.5 从而根据模型，使用Lingo编程，得出结果如下表：

5.2 问题二

5.2.1 目标函数的确立：

此问与第一问大同小异，不同的是小张要花最少的时间游完全部的景点，而目标函数是求最少的时间。由第一问结论可知，总时间为：t(tijti)

i1j188-- 9

精选文库

因此，该问题的目标函数为：

Min t(titij)

i1j188

5.2.2 模型建立：

综上所述，我们可以得到的模型为

Min t(titij)

i1j1885.2.3 模型求解与结果分析：

根据模型，使用Lingo编程，得出结果：

行程表 起点站 新余 宜春 武夷山 温州 郑州 登封 郑州 九寨沟 丽江 贵阳 安顺 贵阳 桂林

--

10

终点站 宜春 武夷山 温州 郑州 登封 郑州 九寨沟 丽江 贵阳 安顺 贵阳 桂林 新余 乘车类型 火车 火车 飞机 飞机 客车 客车 飞机 飞机 飞机 火车 火车 飞机 火车 车次 D205/D208 K1681/K1684 MF8088 CZ3680 \\ \\ 3U8858\\3U8608 MU5852 MU5960 T8881/T8884 K9370 CZ3667/CZ3951 K960 起始时间 9:10 23:44 16:45 12:25 14:30 20:10 21:35 14:35 23:30 8:30 15:08 16:45 14:05 景点到达停留时间 时间 4小9:36 时 6小7:07 时 3小17:25 时 14:10 / 4小15:35 时 21:15 / 5小7:40 时 3小21:25 时 8:10 / 3小9:06 时 16:28 / 4小23:10 时 2:42 / 精选文库

住宿表及住宿费用 入住宾馆时间 23:55 0:00 价钱 13束河古镇龙泉行政村文明而社 丽江九域乡村束河客栈 6 13市中心-漓江风景区 贵客 0773 酒店 3 地点 名称

5.3 问题三

5.3.1目标函数的确立

此问在第一问的基础上改变约束条件，使小张的t旅游时间限定在4天内，旅游的总费用限定在1500元，我们的做法同样是在满足相应的约束条件下，计算出在一定条件下最多游览的景点个数，得出几种方案，在根据实际情况选出最佳方案，这样最终会得出几种最佳方案，而组织方可以根据自己的实际情况进行选择得出最后方案 。①时间约束

游览的总时间由2部分组成，分别为在景点的逗留时间和第i个景点到第j个景点路途中所需时间

从而我们可以得到函数为

11111t=rijtij+rijtitj

2i1j1i1j11111

②费用约束

游览的总费用由3部分组成，分别为交通总费用，住宿餐饮总费用和在旅游景点的花费。

从而我们可以得到函数为

m＝m1＋m2+m3+n

=

8ri1j188ijcij+

188rijcicj2i1j1+60

(ti1i18itij)24+n

--

11

精选文库

③0——1变量约束

我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。

对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束方程为：

rij'irij1

'jri''ijrj''ij1 （i，j=2，……，8）

'''当i1时，因为新余是出发点，所以rij1并且rij1；

i1i1' 当j1时，因为代表们最终要回到新余，所以rij1并且rij1。

''j1j1 综合以上可知，

rii'ij''rjj'ij''1

rij'i1rij1 （i，j=2，……，8）

''i1''rij1 rij1 rj1'ij1 rij1

j1同样，当i，j2时，根据题意不可能出现rijrji1和rijrji1，即不可能出现游客在两地见往返旅游，因为这样显然不满足游览景点尽量多的原则。因此我们可得约束：

''''''rijrji0

rijrji0 （i，j=2，3，……，8） 5.3.2模型建立：

综上所述，我们可以得到总的模型为

约束条件

--

12

''''''精选文库

11111 rijtij+rijtitj96

2i1j1i1j11111

188rijcij+rijcicj+602i1j1i1j188(ti1i188itij)24+n1500

rij'irij1

'jrij''irj''ij1 （i，j=2，……，8）

5.2.3 模型求解与结果分析：

根据模型，使用Lingo编程，得出结果：

行程一 乘车类起点站 终点站 车次 型 新余 宜春 火车 D205/D208 宜春 武夷山 火车 K1681/K1684 武夷山 温州 火车 2002 温州 合肥 火车 K8492/K8493 合肥 郑州 火车 2192/2193 郑州 新余 火车 1437 行程二 乘车类起点站 终点站 车次 型 新余 宜春 火车 D205/D208 宜春 桂林 火车 K1681/K1684 桂林 贵州 火车 K1588 贵州 安顺 火车 K8492 安顺 丽江 火车 K2175/K2156 丽江 新余 火车 K1437 起始时到达时间 间 9:10 9:36 23:44 7:07 18:14 20:35 22:00 10:59 23:45 8:01 7:20 12:20 景点停票价 留时间 4小时 4.5 6小时 63 3小时 18 、 126 4小时 41 100 起始时到达时间 间 9:10 9:36 22:00 7:07 15:14 20:35 22:00 10:59 23:45 8:01 15:30 4:20 景点停留时间 4小时 6小时 、 3小时 3小时 票价 4.5 63 18 126 41 160

6 模型的评价、改进及推广

--

13

精选文库

6.1．模型的评价

1.本文思路清晰，模型恰当，得出的方案合理；

2.本文成功的使用了0—1变量，使模型的建立和编程得以顺利进行； 3.在解决实际问题中采用了合理简便算法，简化了模型的求解难度；

4.问题中由于数据庞大，对程序的要求很高，尽管经过了检验，但结果依然比较粗糙，有待进行进一步的改进。 6.2．模型的改进与推广：

1.实际情况中，在景点之间游玩可能还会受天气，交通堵塞和意外等因素影

响，增加这些考虑后，结果会更加合理。

2.因数据资料搜集的不完整，准确性也有待商榷，而且没有对最终方案进行更为细致的讨论研究，这些方面有待改进。

7 参考文献

[1]谢金星 薛毅，《优化建模与LINDO/LINGO软件》，北京：清华大学出版社，2005。

[2]寿纪麟，数学建模 - 方法与范例，西安交通大学出版社，1993 [3]叶其孝主编，大学生数学建模竞赛辅导教材（三），湖南教育出版社，1998

[4]白其峥等，数学建模案例分析，海洋出版社，

[5] 朱道元，数学建模精品案例，东南大学出版社，1999

--

14

精选文库

8 附录

附录清单 1为搜集的一些数据

2为相关程序及运行结果

网上查询到的一些数据及相应的计算出的数据： 起点终点乘车类起始时到达时景点停留车次 站 站 型 间 间 时间 新余 宜春 火车 D205/D208 9:10 9:36 4小时 宜春 桂林 火车 K1681/K1684 22:00 7:07 6小时 桂林 贵州 火车 K1588 15:14 20:35 、 贵州 安顺 火车 K8492 22:00 10:59 、 安顺 丽江 火车 K2175/K2156 23:45 8:01 、 丽江 新余 火车 K1437 15:30 4:20 九寨成都 汽车 、 8:00 15:00 、 沟 成都 广通 火车 广通 丽江东 昆明 安顺 贵阳 柳州 丽江东 火车 K145 K9610/K9611 K9612/K9609 K110 K156 K850/K851 2514 1558 1236 15:40 12:42 21:30 6:35 1:21 17:05 22:40 0:43 18:43 7:46 、 17:56 3小时 6:03 、 15:52 1:42 1:40 0:54 3小时 、 、 4小时 票价 4.5 63 18 126 41 160 门票 100 180 120 100 住宿费 餐饮费用 18 220 170 120 63 35 40 昆明 火车 安顺 贵阳 柳州 桂林 火车 火车 火车 火车 65 125 67 88 79 49 50 45 桂林 宜春 火车 宜春 新余 火车 12:39 4小时 19:24 、 63 4.5 14 81 4.5 1171 840 150 20-- 15