最佳旅游线路-数学建模[]

来源：小侦探旅游网

最佳旅游路线设计

摘要

本文主要研究最佳旅游路线的设计问题。在满足相关约束条件的情况下，花最少的钱游览尽可能多的景点是我们追求的目标。基于对此的研究，建立数学模型，设计出最佳的旅游路线。

第一问给定时间约束，要求为主办方设计合适的旅游路线。我们建立了一个最优规划模型，在给定游览景点个数的情况下以人均总费用最小为目标。再引入0—1变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求解。推荐方案：成都→都江堰→青城山→丹巴→乐山→成都，人均费用为949元（此处不考虑旅游人数对游览费用的影响）。

第二问放松时间约束，要求代表们游遍所有的景点，该问题也就成了典型的货郎担（TSP）问题。同样使用第一问的模型，改变时间约束，使用lingo编程得到最佳旅游路线为：成都→乐山→峨眉→海螺沟→康定→丹巴→四姑娘山→青城山→都江堰→九寨沟→黄龙→成都，人均费用为3243元。

第三问要求在第一问的基础上充分考虑代表们的旅游意向，建立模型求解。通过对附件一数据的观察，我们使用综合评判的方法，巧妙地将代表们的意愿转化为对相应旅游景点的权重，再对第一问的模型稍加修改，编程求出对应不同景点数的最佳路线。推荐路线：成都→乐山→都江堰→青城山→丹巴→成都，人均费用为927元。

对于第四问，由于参观景点的人数越多每人承担的费用越少，因此我们要考虑的是尽量使得两组代表在共同旅游的时间内在相同的景点游览。正是基于此，我们建立模型求解。推荐路线：第一组：成都→乐山→丹巴→都江堰→青城山→成都第二组：成都→都江堰→青城山→峨眉→乐山→成都，两组在都江堰会合并且共同游览了都江堰和青城山，人均费用为971元。

第五问中，首先我们修改了不合理数据，并用SPSS软件对缺省数据进行了时间序列预测。其次我们合理定义了阴雨天气带来的损失，以人均总花费最小和阴雨天气带来的损失最小为目标，建立加权双目标规划模型。推荐路线：成都→康定→青城山→都江堰→乐山→成都，相应人均消费987元，阴雨天气带来的损失为1.6。

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

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

1 问题重述

今年暑假，西南交通大学数学系要召开“××学术会议”，届时来自国内外的许多著名学者都会相聚成都。在会议结束后，主办方希望能安排这些远道而来的贵宾参观四川省境内的著名自然和人文景观，初步设想有如下线路可供选择：

一号线：成都→九寨沟、黄龙；二号线：成都→乐山、峨嵋；三号线：成都→四姑娘山、丹巴；四号线：成都→都江堰、青城山；五号线：成都→海螺沟、康定；

每条线路中的景点可以全部参观，也可以参观其中之一。不仅如此，一起参观景点的人数越多，每人承担的费用也会越小。

结合上述要求，请你回答下列问题：

一、请你们为主办方设计合适的旅游路线，使会议代表在会议结束后的10天时间内花最少的钱游尽可能多的地方。

二、如果有一些会议代表的时间非常充裕（比如一个月），他们打算将上述旅游景点全部参观完毕后才离开四川，请你们为他们设计合适的旅游路线，使在四川境内的交通费用尽量地节省。

三、主办方在会议开始前对所有参会的100位代表旅游意向进行了调查，调查数据见附件1所示。充分考虑这些代表的意愿，请你们为主办方设计代表们合适的旅游路线，使他们在会议结束后的10天时间内花最少的钱游尽可能多的地方。

四、由于会议安排原因，附件1中的后50位代表要拖后四天时间才能去旅游观光（每人旅游总时间保持不变）。请在问题三基础上考虑时间滞后因素，为主办方设计合适的旅游路线，使代表们在10天的时间里花最少的钱游尽可能多的地方。

五、在旅游过程中最担心出现阴雨天气，这种气候环境是最不适合旅游的。因此，在出发前，主办方询问了四川省气象局这五条旅游线路降雨的概率，具体数据见附件2。请在问题三的基础上增加气候因素，为主办方设计合适的旅游路线，使代表们在10天的时间里花最少的钱游尽可能多的地方，同时因阴雨天气而带来的旅游不便损失降为最低。

2 问题分析

2.1问题背景的理解：

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

问题一要求我们为主办方设计合适的旅游路线，使会议代表在会议结束后的10天时间内花最少的钱游尽可能多的地方。在这里我们的做法是在满足相应的约束条件下，先确定游览的景点数，然后计算出在这种情况下的最小花费。这样最终会得出几种最佳方案，而组织方可以根据自己的实际情况进行选择。

问题二实质上是在问题一的基础上改变了时间约束，即代表们要游览所有的

景点，我们完全可以使用与问题一同样的方法进行求解。 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——每个会议代表的旅游总花费；

ti——每个会议代表在第i个景点的逗留时间； ci——每个会议代表在i个景点的总消费； tij——从第i个景点到第j个景点路途中所需时间；

cij——从第i个景点到第j个景点所需的交通费用；

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

其他0

5 模型建立及求解

5.1 问题一：

5.1.1 目标函数的确立：经过对题目分析，我们可以知道本题所要实现的目标是，使会议代表在10天时间内花最少的钱游览尽可能多的地方。显然，花费最少和游览的景点尽量多是该问题的两个目标。因此，我们的做法是在满足相应的约束条件下，先确定游览的景点数，然后计算出在这种情况下的最小花费。这样最终会得出几种旅游路线，而组织方可以根据自己的实际情况进行选择。

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

m——每个代表的旅游总花费；

m1——每个代表的交通总费用；

m2——每个代表的旅游景点的花费；从而得到目标函数： Min m＝m1＋m2 （1）交通总花费

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

m1rijcij

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

因为ci表示会议代表们在i个景点的总消费，rij也可以表示出代表们是

否到达过第i个和第j个景点，而整个旅游路线又是一个环形，因此

rcc实际上将代表们在所到景点的花费计算了两遍，从而我们

ijiji1j11111可得旅游景点的花费为：

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

2i1j1从而我们可以得到目标函数为：

Min m＝m1＋m2

11111 ＝rijcij+rijcicj

2i1j1i1j111115.1.2 约束条件：

①时间约束

由题目可知，代表们在川的旅游时间应该不多于10天(120小时)，而

这些时间包括在路途中的时间和在旅游景点逗留的时间。因为tij表示从第i个景点到第j个景点路途中所需时间，所以路途中所需总时间为

ri1j11111ijtij；ti表示会议代表们在第i个景点的逗留时间，故代表们在旅游

11111景点的总逗留时间为rijtitj。因此，总的时间约束为：

2i1j111111rijtij+rijtitj120 2i1j1i1j11111 ②旅游景点数约束

根据假设，整个旅游路线是环形，即最终代表们要回到成都，因此

ri1j11111ij即表示代表们旅游的景点数，这里我们假定要旅游的景点数为n（n=2，3，……，11）。因此旅游景点数约束为：

ri1j11111ijn （n=2，3，……，11）

③0——1变量约束

我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束：

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

ij 当i1时，因为成都是出发点，所以rij1；

i1j1时，因为代表们最终要回到成都，所以rij1。

j1 综合以上可知，

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

ri1ij1 rij1

j1 同样，当i，j2时，根据题意不可能出现rijrji1，即不可能出

现游客在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。因此我们可得约束：

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

5.1.3模型建立：

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

Min m＝m1＋m2

11111 ＝rijcij+rijcicj

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

约束条件：

11111rijtij+rijtitj120 2i1j1i1j11111ri1j11111ijn （n=2，3，……，11）

rii1ijrjij1 （i，j=1，2，……，11）

rij1 rij1

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

5.1.4 模型求解与结果分析：在这里我们引入以下符号：

dij——第i个景点和第j个景点之间的路程；

v——代表们所乘坐的旅游大巴的平均时速，v=50km/h； m——代表们所乘坐的旅游大巴的平均费用，h=0.3元/h；

通过上网查询资料，我们可以得到dij的具体值，根据公式tij=dij/v可得到相应的tij，同样根据公式cij=dij×m可以得到相应的cij（i，j=1，2，……，11）。（dij、tij和cij的具体数值见附录）

同样，通过对四川的一些旅行社进行咨询，我们得出会议代表们在第i个景点的最佳逗留时间和他们在第i个景点总消费：

t10 t11 24 17 (单位：小时) c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 120 423 300 135 378 390 175 90 148 303 241 (单位：元) 从而根据模型，使用Lingo编程，得出结果如下表：旅游景点数n 2 3 4 每人总花费m250 406 623 （单位：元）路线 1→8→1 1→9→8→1 1→4→8→9→1 旅游景点数n 5 6 每人总花费m 949 1207 （单位：元）路线 1→8→9→7→4→1 1→4→11→7→9→8→1

t1 7 t2 24 t3 18 t4 12 t5 36 t6 30 t7 12 t8 9 t9 15 旅游景点数n 7 每人总花费m1534 （单位：元）路线 1→4→10→11→7→9→8→1 （其中数字1—11分别表示成都、九寨沟、黄龙、乐山、峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺沟、康定）

对于上述结果，我们的推荐为：

路线一：成都→乐山→都江堰→青城山→成都

旅游景点数：4 人均费用：623元；

路线二：成都→都江堰→青城山→丹巴→乐山→成都

旅游景点数：5 人均费用：949元；

路线三：成都→乐山→康定→丹巴→青城山→都江堰→成都

旅游景点数：6 人均费用：1207元。

5.2 问题二

5.2.1 目标函数的确立：

此问与第一问大同小异，不同的是代表们要完成所有景点的旅游，而目标函数是求最少的交通费。由第一问结论可知，交通费用为：m1rijcij

i1j11111因此，该问题的目标函数为：

Min m1rijcij

i1j111115.2.2 约束条件： ①时间约束

该问与上一问相比，放宽了对时间的要求，不妨可以假定限制的时间为一个月（360个小时），同上一问可得：

11111rijtij+rijtitj360 2i1j1i1j11111②旅游景点数约束

由题目要求可知，因为代表们时间充裕，因此他们打算游览完全部11个景点。由第一问知道rij表示代表们游览的景点总数，因此该约束为：

i1j1111111

ri1j111ij11 (i，j=1，2，……，11)

③0——1变量约束

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

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

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

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

5.2.3模型建立：

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

Min m1rijcij

i1j11111

约束条件：

11111rijtij+rijtitj360 2i1j1i1j11111ri1j11111ij11 （i，j=1，2，……，11）

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

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

5.2.4 模型求解与结果分析：

根据模型，使用Lingo编程，得出结果为：旅游景点数n 11 每人总花费m 3243 （单位：元）成都→乐山→峨眉→海螺沟→康定→丹巴→四姑路线娘山→青城山→都江堰→九寨沟→黄龙→成都

5.3 问题三

5.3.1目标函数的确立 5.3.1.1问题的再次分析

此问在第一问的基础上增加了代表们意愿这一条件，通过对附件一的观察，我们发现代表们的意愿分为“去”、“不去”和“无所谓”三种。怎样将这些文字转换到公式中来表达代表们的意愿就成为了解决该问的关键。在这里我们采用加权重的方式，将代表们的意愿理解为对该线路上两个景点的权重，又因为我们最终的目标是使旅游的费用最少，因此越热门的景点相应的权重也应该越低（这是因为权重越低，其与该景点的费用相乘后也越低，从而增加了对该景点游览的可能性）。

5.3.1.2数据处理

将所有的“去”替换为0，所有的“不去”替换为1，所有的“无所谓”替换为0.5，从而得到一个1005的矩阵Aks1005（见附录）。我们定义：

i——第i个旅游景点的权重。

由假设可知成都是代表们肯定要游览的一个景点，因此10。对其他权重进行标准化处理可得：

23Ak1s1100k11005k11005A100k1=0.185 45ksAk1s1100k11005k11005A100k2=0.217

ks67Ak3Ak1s1=0.196 89Ak4=0.206

ksksAk1s11011Ak1s1k11005A100k10.196

ks5.3.1.3确定目标函数

本文我们的做法同样是在满足相应的约束条件下，先确定游览的景点数，然后计算出在这种情况下的最小花费。这样最终会得出几种最佳方案，而组织方可以根据自己的实际情况进行选择。

游览的总费用由2部分组成，分别为交通总费用和在旅游景点的花费。又根据假设，参观景点的人数每增加一人，在景点的总费用就减少原价的1‰，由于共有100名代表，这就相当于每人在旅游景点的花费打了“九折”，因此得目标函数为：

11111Min m=100irijcij+ 90irijcicj

2i1j1i1j11111而所得结果所对应的每个代表的总花费为：

1901111rijcicj m=rijcij+ 2100i1j1i1j111115.3.2 约束条件

①时间约束

由题目可知，代表们在川的旅游时间应该不多于10天(120小时)，而

这些时间包括在路途中的时间和在旅游景点逗留的时间。因为tij表示从第i个景点到第j个景点路途中所需时间，所以路途中所需总时间为

ri1j11111ijtij；ti表示会议代表们在第i个景点的逗留时间，故代表们在旅游

11111景点的总逗留时间为rijtitj。因此，总的时间约束为：

2i1j111111rijtij+rijtitj120 2i1j1i1j11111 ②旅游景点数约束

根据假设，整个旅游路线是环形，即最终代表们要回到成都，因此

ri1j11111ij即表示代表们旅游的景点数，这里我们假定要旅游的景点数为n（n=2，3，……，11）。因此旅游景点数约束为：

ri1j11111ijn （n=2，3，……，11）

③0——1变量约束

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

当i1时，因为成都是出发点，所以rij1；

i1 当j1时，因为代表们最终要回到成都，所以rij1。

j1 综合以上可知，

rii1ijrjij1 （i，j=1，2，……，11）

rij1 rij1

j1 同样，当i，j2时，根据题意不可能出现rijrji1，即不可能出

现游客在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。因此我们可得约束：

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

5.3.3模型建立：

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

11111Min m=100irijcij+ 90irijcicj

2i1j1i1j11111约束条件：

11111rijtij+rijtitj120 2i1j1i1j11111ri1j11111ijn （n=2，3，……11）

rii1ijrjij1 （i，j=1，2，……，11）

r

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

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

5.3.4 模型求解与结果分析：旅游景点数n 2 3 4 每人总花费c 229 370 573 （单位：元）路线 1→8→1 1→8→9→1 1→9→8→4→1 旅游景点数n 5 6 每人总花费c 927 1160 （单位：元）路线 1→4→8→9→7→1 1→4→8→9→7→11→1

旅游景点数n 7 每人总花费c 1412 （单位：元）路线 1→8→9→7→11→10→4→1 （其中数字1—11分别表示成都、九寨沟、黄龙、乐山、峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺沟、康定）对于上述结果，我们的推荐为：

路线一：成都→青城山→都江堰→乐山→成都

旅游景点数：4 人均费用：573元；

路线二：成都→乐山→都江堰→青城山→丹巴→成都

旅游景点数：5 人均费用：927元；

路线三：成都→乐山→都江堰→青城山→丹巴→康定→成都

旅游景点数：6 人均费用：1160元。

第四问： 5.4.1

5.4.1.1问题的再次分析：

该问中，由于会议安排原因，前50名（第一组）代表先行出发旅游，而后50名代表（第二组）则拖后4天。由假设可知，参观景点的人数越多，每人承担的费用越少，因此为了达到费用最少的目标，我们应该尽量安排两组代表在同时旅游的6天内在同样的景点旅游。

5.4.1.2数据的处理

类似上一问，我们定义：

i'——第i个旅游景点对于第一组代表的权重；

i''——第i个旅游景点对于第二组代表的权重。

运用与第一问同样的方法，我们可以得到：

1'=0 2'3'0.2 4'5'0.212 6'7'0.188 8'9'0.212 10'11'0.188 1''=0 2''3''0.169 4''5''0.221 8''9''0.201 10''11''0.204 6''7''0.205 5.4.1.3目标函数的确立：

此问中，我们引入以下符号：

m——旅游总花费；

m1——第一组每个代表的交通总费用； m1——第二组每个代表的交通总费用； m2——第一组每个代表的旅游景点的花费；

''''m2——第二组每个代表的旅游景点的花费。

''（上述四个量是假设两个组分别旅游的费用）

m3——两个组同时在一景点旅游比分别旅游节约的费用。

由以上的假设和符号，我们可以很容易的得到总的目标函数为：

Min m=m1+m1+m2+m2－m3 而所得结果所对应的每个代表的总花费为：

1901111rijcicj m=rijcij+ 2100i1j1i1j11111''''''定义：

i个景点到达第j个景点1第一组直接从第' rij

其他0

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

0其他''

从而可以推得：

m150irijcij

'''i1j1111111m150irijcij

''''''i1j111 又因为假设参观景点的人数每增加一人，每个代表在景点的费用就减少原价的1‰，因此可得：

11111''m2=500.95irijcicj

2i1j1'11111''''m2=500.95irijcicj

2i1j1''（2）节约的费用定义：

1i0两组代表同时在第i个景点旅游

其他因为两组分别旅行时按照原价的95﹪收费，而两组同时在同一景点旅游时按照原价的90﹪收费，因此后者比前者便宜了定价的5﹪，因此：

11111m31000.05ijiicijjcj

2j1i15.4.2 约束条件 ①时间约束

由题目可知，代表们在川的旅游时间应该不多于10天（120小时），而

这些时间包括在路途中的时间和在旅游景点逗留的时间。因为tij表示从第i个景点到第j个景点路途中所需时间，所以两组代表们在路途中所需总时间分别为rijtij和rijtij；ti表示会议代表们在第i个景点的逗留

'''i1j1i1j11111111111111'时间，故两组代表们在旅游景点的总逗留时间分别为rijtitj2i1j111111''和rijtitj。因此，总的时间约束为： 2i1j111111'rijtij+rijtitj120 2i1j1i1j1'111111111''rijtij+rijtitj120 2i1j1i1j1''1111

②旅游景点数约束

根据假设，整个旅游路线是环形，即最终代表们要回到成都，因此

ri1j11111ij即表示代表们旅游的景点数，这里我们假定两组代表要旅游的景点

数均为n（n=2，3，……，11）。因此旅游景点数约束为：

r=r'iji1j1i1j111111111''ijn

③0——1变量约束

ri'ij''rjj'ij''1

1 （i，j=2，……，11）

'''riijrij当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，……，11）

''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，……，11）

''''''

5.4.3模型建立：

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

Min m=m1+m1+m2+m2－m3 其中：

m150irijcij

'''i1j1111111''''''m150irijcij

''''''i1j111111''m2=500.95irijcicj

2i1j1'1111111''''m2=500.95irijcicj 2i1j1''11111m31000.05ijiicijjcj 2j1i1 约束条件：

11111'rijtij+rijtitj120 2i1j1i1j1'111111111''rijtij+rijtitj120 2i1j1i1j1''1111rij=rijn （n=2，3，……，11）

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

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

i1''j1rij1 rij1

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

''''''

5.4.4 模型求解与结果分析：

使用lingo编程，得到最佳结果：旅游景点数n 5 每人总花费c 971 （单位：元）第一组：成都→乐山→丹巴→都江堰→青城山→成都路线第二组：成都→都江堰→青城山→峨眉→乐山→成都即第一组先行出发，在游览了乐山和丹巴后前往都江堰，与第二组代表会合，两组代表共同游览了都江堰和青城山，之后第一组返回成都，而第一组则前往峨眉和乐山游览。

问题五：

在问题三的基础上我们引入以下符号：

l——阴雨天气带来的旅游损失；

c(n)min——代表们旅游n个景点需要的最小的花费； c(n)max——代表们旅游n个景点需要的最大的花费；

l(n)min——代表们旅游n个景点阴雨天气所带大的最小损失； l(n)max——代表们旅游n个景点阴雨天气所带大的最大损失。

5.5.1目标函数的确立 5.5.1.1问题的再次分析

本问在问题三的基础上考虑了天气的因素，相应的也就增加了一个目标即：使因阴雨天气而带来的旅游损失降到最低。对于旅游损失，我们定义为代表们在景点逗留时所对应的阴雨天气概率的总和。

5.5.1.2数据处理

（1）对附件二数据的处理

Ⅰ.对于附件中超过100％的数据我们修定其为100％；

Ⅱ.对于附件中缺失的数据，我们使用SPSS软件进行时间序列预测如下：对于丹巴的降水概率，最优拟合曲线为二次曲线，拟合结果为：丹巴

第七天降雨的概率为10.33898﹪，我们取10﹪.

拟合曲线图如下：

VAR0000130.00ObservedQuadratic25.0020.0015.0010.005.000.000246810Sequence 对于康定的降水概率，最优拟合曲线为三次曲线，拟合结果为：康定第九天降水的概率为63.39119﹪，我们取63﹪.

拟合曲线图如下：

VAR0000180.00ObservedCubic70.0060.0050.0040.0030.0020.0010.000246810Sequence 综上我们得到最终的矩阵：P。 is115（见附录）

（2）数据的归一化处理（原因）

通过观察数据，我们发现旅游总花费和阴雨天气带来的旅游损失的数值差距较大，在利用二者综合确立目标时，为了避免其的影响，采用数据常用处理方法——极差变化法，将数据做归一化处理。即： Ccc(n)minll(n)min ； L

c(n)maxc(n)minl(n)maxl(n)min

（3）确定目标函数

对于该问，沿用上几问的思想，我们的做法是在满足相应的约束条件下，先确定游览的景点数，然后分别表示出相应的旅游总费用和阴雨天气带来的旅游损失，归一化处理后加权求最小值。这样最终会得出几种最佳方案，而组织方可以根据自己的实际情况进行选择。由此得到最终的目标函数：

Min Q1C2L

12为权重且121) (其中C,L如上所述，

Ⅰ.对于C:

11111由第三问可知：c＝100irijcij+ 100irijcicj，

2i1j1i1j11111而相应的c(n)min与c(n)max也可以根据前几问的模型计算出（具体值见附录表格），因此我们用可以已知的结果来表达C。

Ⅱ.对于L：

在L的表达式中，关键是表示出l，表示出l后l(n)min和l(n)max可以根据相应的

模型通过编程很容易的计算出来。因为l表示阴雨天气带来的旅游损失，而我

们定义该损失为代表们在景点逗留时所对应的阴雨天气概率的总和。这里我们设：

Pis——第i个景点在第s天阴雨的概率；（s=1，2，……10） Ti——代表们到达第i个景点的时间；

V——代表们游览的景点的集合，如V={1，8，5，7}表示代表们游览了第1、

8、5、7个景点。

因此代表们会从第Ti天到第Titi天都留在第i个景点（表示取整）。综上，l的可以表示为TItiiVsTIPis，这样我们也就可以表达出L。

5.5.2约束条件 ①时间约束

由题目可知，代表们在川的旅游时间应该不多于10天，而这些时间包

括在路途中的时间和在旅游景点逗留的时间。因为tij表示从第i个景点到第j个景点路途中所需时间，所以路途中所需总时间为rijtij；ti表示会

i1j11111议代表们在第i个景点的逗留时间，故代表们在旅游景点的总逗留时间为

11111rijtitj。因此，总的时间约束为： 2i1j111111rijtij+rijtitj120 2i1j1i1j11111 ②旅游景点数约束

根据假设，整个旅游路线是环形，即最终代表们要回到成都，因此

ri1j11111ij即表示代表们旅游的景点数，这里我们假定要旅游的景点数为n（n=2，3，……，11）。因此旅游景点数约束为：

ri1j11111ijn （n=2，3，……，11）

③0——1变量约束

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

ij 当i1时，因为成都是出发点，所以rij1；

i1 当j1时，因为代表们最终要回到成都，所以rij1。

j1 综合以上可知，

rii1ijrjij1 （i，j=1，2，……，11）

rij1 rij1

j1 同样，当i，j2时，根据题意不可能出现rijrji1，即不可能出

现游客在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。因此我们可得约束：

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

④对Ti的约束

因为Ti表示代表们到达第i个景点的时间，因此Ti应该等于到达第

i1个景点的时间与第i1个景点到第i个景点途中时间的和。从而可得： Ti=Ti1ti1,i （i=2，3，……，11）

5.5.3模型建立：

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

Min Q1C2L

约束条件：

11111rijtij+rijtitj120 2i1j1i1j11111ri1j1iji1111ijk

rrjij1 （i，j=1，2，……，11）

rijrji0 （i，j2）

Ti=Ti1ti1,i （i=2，3，……，11）

5.5.4模型求解与结果分析：

由于结果数据庞大，我们在这里只列出n5的情形。

当10.6,20.4时当10.4,20.6时人均总费用C 损失（单位：元） 965 1.7 路线：1→11→7→4→8→1 人均总费用C 损失（单位：元） 1028 1.6 路线：1→7→9→8→4→1 当10.7,20.3时当10.3,20.7时人均总费用C 损失（单位：元） 946 1.8 路线：1→10→11→7→4→1 人均总费用C 损失（单位：元） 1206 0.9 路线：1→11→9→8→4→1 当10.5,20.5时

人均总费用C 损失（单位：元） 987 1.6 路线：1→11→9→8→4→1 （其中数字1—11分别表示成都、九寨沟、黄龙、乐山、峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺沟、康定）

由以上结果，我们推荐路线为：成都→康定→青城山→都江堰→乐山→成都，相应人均消费987元，阴雨天气带来的损失为1.6。

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

6.1．模型的评价

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

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

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

1.实际情况中，两景点之间可能还有出公路外其他交通方式，如航班、铁路，

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

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

7 参考文献

[1]姜启源谢金星叶俊，《数学模型（第三版）》，北京：高等教育出版社，2003。 [2]谢金星薛毅，《优化建模与LINDO/LINGO软件》，北京：清华大学出版社，2005。 [3]周仁郁，《SPSS13.0统计软件》，成都，西南交通大学出版社，2005。 [4]李庆扬王能超易大义，《数值分析》，北京：清华大学出版社施普林格出版社，2001。

8 附录

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

附录2为相关程序及运行结果

附录1：

网上查询到的一些数据及相应的计算出的数据：

tij1111= 8.54 0 4.74

1.22

2.82 11.52 3.44 12.14 5.08 10.9 8.4 13.1 1.32 8.84 1.54 8.98 6.14 14.84 6.6 15.54 0 8.54 4.74 1.22 0 11.22

11.82 9.38 11.58 7.66 2.82 11.52 11.22 0 0.88

7.78 8.08 4.02 3.44 12.14 11.82 0.88 0 8.42 8.24 4.66 5.08 10.9 9.38 7.78 8.42 0 2.18 4.24 8.4 13.1 11.58 8.08 8.24 2.18 0 6.08 1.32 8.84 7.66 4.02 4.66 4.24 6.08 0 1.54 8.98 7.46 4.24 4.88

4.04 6.22 0.3 6.14 14.84 13.44 5.84 6 5.98 3.86 6.28 6.6

15.54 13.9

6.3

6.46

6.74

2.86

6.74

cij1111= 0 128 71 42 52 76 126 20 128 0 18 173 182 164 197 133 71 18 0 168 177 141 174 115 42 173 168 0 13 117 121 60 52 182 177 13 0 126 124 70 76 164 141 117 126 0 33 64 126 197 174 121 124 33 0 91 20 133 115 60 70 64 91 0 23 135 112 64 73 61 93 5 92 223 202 88 90 90 58 94 99

233

209

101

43 101 Pis115=

0.15 0.1 0.3 0.8 0.7 0.5 0.6 1 0.8 0.8 0.5 0.5 0.4 0.5 0.5 1 0.9 1 0.3 0 0.2 0.1 0 0.1 0.5 0.5 0.7 0.3 0.3 0.4 0.4 0.6 0.3 0.3 0.2 0.6 0.6 0.6 0.5 0.8 0.3 0.1 0.3 0.2 0.2 0.1 0 0.1 0.1 0.4 0.3 0.3 0.2 0.4 0.9 0.9 0.5 0.3 0.3 0.4 0.3 0.8 1 0.2 0.6 0.6 0.4 0.1 0 0.8 0.1

0.1

0.3

0.5

0.6

0.8

7.46 13.44 4.24 5.84

4.88 6 4.04 5.98 6.22 3.86 0.3 6.28 0 6.08

6.08 0 6.54

2.08

23 92 135 223 112 202 64 88 73 90 61 90 93 58 5 94 0 91 91 0 98 31 0.3 0.1 0.6 0.3 0 0.4 0.3 0.1 0.4 0.6 0.1 0.1 0.2 0.2 0.9 0.8 0.9 0.9 0.7 0.6 0.7

0.63

13.9 6.3 6.46 6.74 2.86 6.74 6.54 2.08 0

99 233 209 95 97 101 43 101 98 31 0

0 0.2 0.4 0.1 0.6 1 0.3 0.8 0.9 0.4 0.4

附录2：程序及运行结果（由于数据庞大，只选择了部分数据）第一问：

（程序） sets:

jingdian/1..11/:c,t,l;

!其中：1,2,...,11分别代表成都、九寨沟、黄龙、乐山、峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺沟、康定；c，t分别表示旅行团在各景点的吃住消费和逗留时间；w表示各景点选择性权重；l是为了控制不出现两个以上环形回路而设的一个变量; links(jingdian,jingdian):r,cc,tt;

!其中：r为0-1变量（0表示两景点不相连，1表示两景点相通）；cc为两景点之间的交通费用；tt为两景点之间的交通时间; endsets data:

t=7 24 18 12 36 30 12 9 15 24 17;

c=120 423 300 135 378 390 175 90 148 303 241;

tt=0 8.54 4.74 2.82 3.44 5.08 8.4 1.32 1.54 6.14 6.6 8.54 0 1.22 11.52 12.14 10.9 13.1 8.84 8.98 14.84 15.54

4.74 1.22 0 11.22 11.82 9.38 11.58 7.66 7.46 13.44 13.9

2.82 11.52 11.22 0 0.88 7.78 8.08 4.02 4.24 5.84 6.3 3.44 12.14 11.82 0.88 0 8.42 8.24 4.66 4.88 6 6.46 5.08 10.9 9.38 7.78 8.42 0 2.18 4.24 4.04 5.98 6.74

cc=0 128.1 71.1 42.3 51.6 76.2 126 19.8 23.1 92.1 99 128.1 0 18.3 172.8 182.1 163.5 196.5 132.6 134.7 222.6 233.1

71.1 18.3 0 168.3 177.3 140.7 173.7 114.9 111.9 201.6 208.5

42.3 172.8 168.3 0 13.2 116.7 121.2 60.3 63.6 87.6 94.5

51.6 182.1 177.3 13.2 0 126.3 123.6 69.9 73.2 90 96.9 76.2 163.5 140.7 116.7 126.3 0 32.7 63.6 60.6 89.7 101.1

126 196.5 173.7 121.2 123.6 32.7 0 91.2 93.3 57.9 42.9 19.8 132.6 114.9 60.3 69.9 63.6 91.2 0 4.5 94.2 101.1 23.1 134.7 111.9 63.6 73.2 60.6 93.3 4.5 0 91.2 98.1

92.1 222.6 201.6 87.6 90 89.7 57.9 94.2 91.2 0 31.2 99 233.1 208.5 94.5 96.9 101.1 42.9 101.1 98.1 31.2 0; !其中：主对角线为零,表示各景点到自身的交通时间为零; n=?;

!其中：n表示计划游玩的景点数目; enddata

min=@sum(jingdian(j):@sum(jingdian(i):r(i,j)*(cc(i,j)+0.5*(c(i)+c(j))))); !目标函数：表示计划游玩的景点数目为n时的最小费用; @for(jingdian(i):r(i,i)=0);

!约束条件：表示各景点到自身没有路线相连的约束条件;

@for(jingdian(i)|i#ge#2:@for(jingdian(j)|j#ge#2:r(i,j)+r(j,i)<1));

!约束条件：表示除起点（成都）外，若旅行团从景点i到景点j去游玩（即r(i,j)=1），则不会再从景点j到景点i去游玩（即r(j,i)=0），也就是说除起点外每个景点只游玩一次; a=@sum(jingdian(j):@sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j))))); @sum(jingdian(j):@sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j)))))<120; !约束条件:表示总的旅行时间（交通时间和景点逗留时间）不超过给定时间10天120小时; @for(jingdian(i):@sum(jingdian(j):r(i,j))=@sum(jingdian(j):r(j,i))); @for(jingdian(i)|i#eq#1:@sum(jingdian(j):r(i,j))=1); @for(jingdian(i)|i#ne#1:@sum(jingdian(j):r(i,j))<1);

!这三个约束条件：表示起点（成都）有且仅有一条路线出去和一条路线进来，其它景点要么有且仅有一条路线出去和一条路线进来，要么既没有路线出去也没有路线进来; @for(links:@bin(r));

!约束条件:表示0-1变量约束;

@sum(jingdian(j):@sum(jingdian(i):r(i,j)))=n; !约束条件:表示旅游景点的数目为n的约束;

@for(jingdian(i):@for(jingdian(j)|j#gt#1#and#j#ne#i:l(j)>=l(i)+r(i,j)-(n-2)*(1-r(i,j))+(n-3)*r(j,i)));

@for(jingdian(i)|i#gt#1:l(i)1+(n-2)*r(i,1));

!这两个约束条件：为了控制不出现两个以上环形回路，保证有且仅有一条环形路线；结果：（以n=5为例）

由于数据庞大，只剪切出重要的部分如下：

Global optimal solution found at iteration: 2042 Objective value: 949.1000

Variable Value Reduced Cost

N 5.000000 0.000000

R( 1, 4) 1.000000 169.8000

R( 4, 7) 1.000000 276.2000 R( 7, 9) 1.000000 254.8000 R( 8, 1) 1.000000 124.8000 R( 9, 8) 1.000000 123.5000 第二问： sets:

jingdian/1..11/:c,t,l;

!其中：r为0-1变量（0表示两景点不相连，1表示两景点相通）；cc为两景点之间的交通费用；tt为两景点之间的交通时间; endsets data:

t=7 24 18 12 36 30 12 9 15 24 17;

c=120 423 300 135 378 390 175 90 148 303 241;

tt=0 8.54 4.74 2.82 3.44 5.08 8.4 1.32 1.54 6.14 6.6 8.54 0 1.22 11.52 12.14 10.9 13.1 8.84 8.98 14.84 15.54

4.74 1.22 0 11.22 11.82 9.38 11.58 7.66 7.46 13.44 13.9

2.82 11.52 11.22 0 0.88 7.78 8.08 4.02 4.24 5.84 6.3 3.44 12.14 11.82 0.88 0 8.42 8.24 4.66 4.88 6 6.46 5.08 10.9 9.38 7.78 8.42 0 2.18 4.24 4.04 5.98 6.74

8.4 13.1 11.58 8.08 8.24 2.18 0 6.08 6.22 3.86 2.86 1.32 8.84 7.66 4.02 4.66 4.24 6.08 0 0.3 6.28 6.74 1.54 8.98 7.46 4.24 4.88 4.04 6.22 0.3 0 6.08 6.54 6.14 14.84 13.44 5.84 6 5.98 3.86 6.28 6.08 0 2.08 6.6 15.54 13.9 6.3 6.46 6.74 2.86 6.74 6.54 2.08 0; !其中：主对角线为零,表示各景点到自身交通费用为零; cc=0 128 71 42 52 77 126 20 23 92 99 128 0 18 173 182 164 197 133 135 223 233 71 18 0 168 177 141 174 115 112 202 209 42 173 168 0 13 117 121 60. 64 88 95 52 182 177 13 0 126 124 70 73 90 97

76 164 141 117 126 0 33 64 61 90 101 126 197 174 121 124 33 0 91 93 58 43 20 133 115 60 70 64 91 0 5 94 101 23 135 112 64 73 61 93 5 0 91 98 92 223 202 88 90 90 58 94 91 0 31 99 233 209 95 97 101 43 101 98 31 0;

!其中：主对角线为零,表示各景点到自身的交通时间为零; enddata

min=@sum(jingdian(j):@sum(jingdian(i):r(i,j)*(cc(i,j)+0.5*(c(i)+c(j))))); !目标函数：表示计划游玩的景点数目为n时的最小费用; @for(jingdian(i):r(i,i)=0);

!约束条件：表示各景点到自身没有路线相连的约束条件;

@for(jingdian(i)|i#ge#2:@for(jingdian(j)|j#ge#2:r(i,j)+r(j,i)<1));

!约束条件：表示除起点（成都）外，若旅行团从景点i到景点j去游玩（即r(i,j)=1），

则不会再从景点j到景点i去游玩（即r(j,i)=0），也就是说除起点外每个景点只游玩一次; a=@sum(jingdian(j):@sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j))))); @sum(jingdian(j):@sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j)))))<360; !约束条件:表示总的旅行时间（交通时间和景点逗留时间）不超过给定时间30天360小时; @for(jingdian(i):@sum(jingdian(j):r(i,j))=@sum(jingdian(j):r(j,i))); @for(jingdian(i)|i#eq#1:@sum(jingdian(j):r(i,j))=1); @for(jingdian(i)|i#ne#1:@sum(jingdian(j):r(i,j))<1);

!约束条件:表示0-1变量约束;

@sum(jingdian(j):@sum(jingdian(i):r(i,j)))=11; !约束条件:表示旅游景点的数目为n的约束;

@for(jingdian(i):@for(jingdian(j)|j#gt#1#and#j#ne#i:l(j)>=l(i)+r(i,j)-(n-2)*(1-r(i,j))+(n-3)*r(j,i)));

@for(jingdian(i)|i#gt#1:l(i)1+(n-2)*r(i,1));

!这两个约束条件：为了控制不出现两个以上环形回路，保证有且仅有一条环形路线；第二问结果（以n=5为例）：

Local optimal solution found at iteration: 390 Objective value: 3243.000

Variable Value Reduced Cost R( 1, 4) 1.000000 0.000000 R( 2, 3) 1.000000 0.000000 R( 3, 1) 1.000000 0.000000 R( 4, 5) 1.000000 0.000000 R( 5, 10) 1.000000 0.000000 R( 6, 9) 1.000000 0.000000 R( 7, 6) 1.000000 0.000000 R( 8, 2) 1.000000 0.000000 R( 9, 8) 1.000000 0.000000 R( 10, 11) 1.000000 0.000000 R( 11, 7) 1.000000 0.000000 第三问： data:

t=7 24 18 12 36 30 12 9 15 24 17;!其中:t(1)=0,表示在成都的逗留时间为0，因为相对旅行团而言，由于成都既是起点又是终点，并未在成都游玩;

c=120 423 300 135 378 390 175 90 148 303 241;!其中：c(1)=0，表示在成都的吃住费用算做，理由同上;

w= 0 0.185 0.185 0.217 0.217 0.196 0.196 0.206 0.206 0.196 0.196; tt=0

8.54

4.74

2.82

3.44

5.08 13.1

8.4 1.32 8.84

1.54 6.14 6.6

14.84 15.54 13.44 13.9

8.54 0 1.22

11.52 12.14 10.9

8.98 7.46

4.74 1.22 0 11.22 11.82 9.38 11.58 7.66

2.82 11.52 11.22 0 0.88 3.44

12.14 11.82 0.88

7.78

11.58 8.08

7.66 7.46

5.08 10.9 9.38 8.4 13.1 1.32 1.54 6.14

8.84 8.98

7.78 8.08 4.02 4.24 6.08 6.22 6.74

4.24 4.04 6.22

5.84 5.98 3.86

6.3 6.74 2.86 6.74 6.54 0;

0 8.42

2.18

8.24 4.66 4.88 6 6.46

8.42 8.24

0 2.18

4.24 4.04 2.86

0 6.08

4.02 4.24

4.66 4.88 6.74

0 0.3 6.28 0.3 0 6.08

6.08 6.54

2.08

14.84 13.44 5.84

6.3 6.46

6 5.98 3.86 6.28 0 2.08

6.6 15.54 13.9

!其中：主对角线为零,表示各景点到自身交通费用为零; cc=0 128 71 42 52 77 126 20 23 92 99 128 0 18 173

182 164

197 133 135 223 233

71 18 0 168 177 141 174 115 112 202 209 42 173 168 0 13 117 121 60. 64 88 95 52 182 177 13 0 126 124 70 73 90 97 76 164 141 126 197

117 126 0 33 64 61 90 101 174 121 124 33 0 91 93 58 43

20 133 115 60 70 64 91 0 5 94 101 23 135 112 64 73 61 93 5 0 91 98 92 223 202 88 90 90 58 94 91 0 31 99 233 209 95 97 101 43 101 98 31 0; !其中：主对角线为零,表示各景点到自身的交通时间为零; n=?;!其中：n表示计划游玩的景点数目; enddata

min=@sum(jingdian(j):@sum(jingdian(i):100*w(j)*r(i,j)*(cc(i,j)+0.5*90*(c(i)+c(j)))));!目标函数：表示计划游玩的景点数目为n时的

最小费用;

b=@sum(jingdian(j):@sum(jingdian(i):r(i,j)*(cc(i,j)+0.45*(c(i)+c(j)))));

@for(jingdian(i):r(i,i)=0);!约束条件：表示各景点到自身没有路线相连的约束条件; @for(jingdian(i)|i#ge#2:@for(jingdian(j)|j#ge#2:r(i,j)+r(j,i)<1));!约束条件：表示除起点（成都）外，若旅行团从景点i到景点j去游玩（即r(i,j)=1），则不会再从景点j到景点i去游玩（即r(j,i)=0），也就是说除起点外每个景点只游玩一次;

@sum(jingdian(j):@sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j)))))<120;!约束条件:表示总的旅行时间（交通时间和景点逗留时间）

不超过给定时间10天;

@for(jingdian(i):@sum(jingdian(j):r(i,j))=@sum(jingdian(j):r(j,i))); @for(jingdian(i)|i#eq#1:@sum(jingdian(j):r(i,j))=1);

@for(jingdian(i)|i#ne#1:@sum(jingdian(j):r(i,j))<1);!这三个约束条件：表示起点（成都）有且仅有一条路线出去和一条路线进来，其它景点要么有且仅有一条路线出去和一条路线进来，要么既没有路线出去也没有路线进来; @for(links:@bin(r));!约束条件:表示0-1变量约束;

@sum(jingdian(j):@sum(jingdian(i):r(i,j)))=n;!约束条件:表示旅游景点的数目为n的约束;

@for(jingdian(i):@for(jingdian(j)|j#gt#1#and#j#ne#i:l(j)>=l(i)+r(i,j)

-(n-2)*(1-r(i,j))+(n-3)*r(j,i)));

@for(jingdian(i)|i#gt#1:l(i)1+(n-2)*r(i,1));!这两个约束条件：为了控制不出现两个以上环形回路，保证有且仅有一条环形路线；第三问结果：（以n=5为例）

Global optimal solution found at iteration: 620 Objective value: 137.0414

Variable Value Reduced Cost N 5.000000 0.000000 B 927.2000 0.000000 R( 1, 4) 1.000000 34.01475 R( 4, 8) 1.000000 33.21750 R( 7, 1) 1.000000 0.000000 R( 8, 9) 1.000000 23.09260 R( 9, 7) 1.000000 46.71660 第四问程序： sets:

jingdian/1..11/:c,rrv,t,w,w2,l,l2,v,v2,b,b2,y,tv,tv2,sv;!其中：

1,2,...,11分别代表成都、九寨沟、黄龙、乐山、峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺、沟康定；c，t分别表示旅行团在各景点的吃住消费和逗留时间；w表示各景点选择性权重；l是为了控制不出现两个以上环形回路而设的一个变量; gailv/1..10/;

links(jingdian,jingdian):r,r2,cc,tt,ssv,rrr,u1,u2,u3,u4,u5,u6,u7,u8,u9,u10,u11;!其中：r为0-1变量（0表示两景点不相连，1表示两景点相通）；cc为两景点之间的交通费用；tt为两景点之间的交通时间; links2(jingdian,gailv):pp,pv;

links1(jingdian,jingdian,jingdian):x,x2,bb,bb2,ppv; endsets data:

t=7 24 18 12 36 30 12 9 15 24 17;!其中:t(1)=0,表示在成都的逗留时间为0，因为相对旅行团而言，由于成都既是起点又是终点，并未在成都游玩;

c=120 423 300 135 378 390 175 90 148 303 241;!其中：c(1)=0，表示在成都的吃住费用算做，理由同上;

w=0 1 1 1.058 1.058 0.942 0.942 1.058 1.058 0.942 0.942; w2=0 0.843 0.843 1.104 1.104 1.024 1.024 1.004 1.004 1.024 1.024; cc=0

128 71

42 52 77 126 20 23 92 99 182 164

197 133 135 223 233

128 0 18 173

71 18 0 168 177 141 174 115 112 202 209 42 173 168 0 13 117 121 60. 64 88 95 52 182 177 13 0 126 124 70 73 90 97 76 164 141 126 197

117 126 0 33 64 61 90 101 174 121 124 33 0 91 93 58 43

20 133 115 60 70 64 91 0 5 94 101 23 135 112 64 73 61 93 5 0 91 98 92 223 202 88 90 90 58 94 91 0 31

99 233 209 95 97 101 43 101 98 31 0;!其中：主对角线为零,表示各景点到自身交通费用为零;

tt=0 8.54 4.74 8.54 0 1.22

2.82

3.44

5.08

8.4 1.32

8.84 4.02 4.24 6.08 6.22 6.74

1.54 8.98 7.46 4.24 4.04 6.22

6.14

6.6

11.52 12.14 10.9

7.78

13.1 8.08

14.84 15.54 13.44 13.9 5.84 5.98 3.86

6.3 6.74 2.86 6.74 6.54 0;!其6 6.46

4.74 1.22 0 11.22 11.82 9.38 2.82 11.52 11.22 0 0.88 3.44

12.14 11.82 0.88

7.78

11.58 8.08

7.66 7.46

5.08 10.9 9.38 8.4 13.1 1.32 1.54 6.14

8.84 8.98

11.58 7.66

8.24

0 8.42

2.18

4.66 4.88

8.42 8.24

0 2.18

4.24 4.04 2.86

0 6.08

4.02 4.24

4.66 4.88 6.74

0 0.3 6.28 0.3 0 6.08

6.08 6.54

2.08

14.84 13.44 5.84

6.3 6.46

6 5.98 3.86 6.28 0 2.08

6.6 15.54 13.9

中：主对角线为零,表示各景点到自身的交通时间为零;

z=0.95; n2=6;

n=6;!其中：n表示计划游玩的景点数目; enddata

min=@sum(jingdian(j):@sum(jingdian(i):w(j)*r(i,j)*(cc(i,j)+0.95*c(j)*(1-rrv(j)*(1-z)))))+@sum(jingdian(j):@sum(jingdian(i):w2(j)*r2(i,j)*(cc(i,j)+0.95*c(j)*(1-rrv(j)*(1-z)))));!目标函数：表示计划游玩的景点数目为n时的最小费用；w(j)为各景点权重的倒数或1-该权重所得;

feiyong=@sum(jingdian(j):@sum(jingdian(i):r(i,j)*(cc(i,j)+0.95*c(j)*(1-rrv(j)*(1-z)))));

feiyong2=@sum(jingdian(j):@sum(jingdian(i):r2(i,j)*(cc(i,j)+0.95*c(j)*(1-rrv(j)*(1-z)))));

@sum(jingdian(j):@sum(jingdian(i):w(j)*r(i,j)*(cc(i,j)+0.95*c(j)*(1-rrv(j)*(1-z)))))+@sum(jingdian(j):@sum(jingdian(i):w2(j)*r2(i,j)*(cc(i,j)+0.95*c(j)*(1-rrv(j)*(1-z)))))>1493;

@for(jingdian(i):r(i,i)=0);!约束条件：表示各景点到自身没有路线相连的约束条件; @for(jingdian(i):r2(i,i)=0);

@for(jingdian(i)|i#ge#2:@for(jingdian(j)|j#ge#2:r(i,j)+r(j,i)<1));!约束条件：表示除起点（成都）外，若旅行团从景点i到景点j去游玩（即r(i,j)=1），则不会再从景点j到景点i去游玩（即r(j,i)=0），也就是说除起点外每个景点只游玩一次;

@for(jingdian(i)|i#ge#2:@for(jingdian(j)|j#ge#2:r2(i,j)+r2(j,i)<1)); @sum(jingdian(j):@sum(jingdian(i):r(i,j)*(tt(i,j)+t(j))))<120;!约束条件:表示总的旅行时间（交通时间和景点逗留时间）不超过给定时间10天;

@sum(jingdian(j):@sum(jingdian(i):r2(i,j)*(tt(i,j)+t(j))))<120; @for(jingdian(i):@sum(jingdian(j):r(i,j))=@sum(jingdian(j):r(j,i))); @for(jingdian(i):@sum(jingdian(j):r2(i,j))=@sum(jingdian(j):r2(j,i)));

@for(jingdian(i)|i#eq#1:@sum(jingdian(j):r(i,j))=1); @for(jingdian(i)|i#eq#1:@sum(jingdian(j):r2(i,j))=1);

@for(jingdian(i)|i#ne#1:@sum(jingdian(j):r(i,j))<1);!这三个约束条件：表示

起点（成都）有且仅有一条路线出去和一条路线进来，其它景点要么有且仅有一条路线出去和一条路线进来，要么既没有路线出去也没有路线进来;

@for(jingdian(i)|i#ne#1:@sum(jingdian(j):r2(i,j))<1); @for(links:@bin(r));!约束条件:表示0-1变量约束; @for(links:@bin(r2)); @for(jingdian:@bin(rrv)); @for(links:@bin(rrr));

@sum(jingdian(j):@sum(jingdian(i):r(i,j)))=n; @sum(jingdian(j):@sum(jingdian(i):r2(i,j)))=n2; !@sum(jingdian(j):@sum(jingdian(i):r(i,j)))>n-0.5; !@sum(jingdian(j):@sum(jingdian(i):r(i,j)))!@sum(jingdian(j):@sum(jingdian(i):r2(i,j)))!@sum(jingdian(j):@sum(jingdian(i):r2(i,j)))>n2-0.5;

@for(jingdian(i):@for(jingdian(j)|j#gt#1#and#j#ne#i:l(j)>=l(i)+r(i,j)-(n-2)*(1-r(i,j))+(n-3)*r(j,i)));

@for(jingdian(i):@for(jingdian(j)|j#gt#1#and#j#ne#i:l2(j)>=l2(i)+r2(i,j)-(n2-2)*(1-r2(i,j))+(n2-3)*r2(j,i)));

@for(jingdian(i)|i#gt#1:l(i)1+(n-2)*r(i,1));!这两个约束条件：为了控制不出现两个以上环形回路，保证有且仅有一条环形路线;

@for(jingdian(i)|i#gt#1:l2(i)1+(n2-2)*r2(i,1));

@for(jingdian(i)|1#eq#i:v(i)=1;b(i)=0);

!@for(jingdian(k)|1#lt#k#and#k#le#n:@for(jingdian(i):@for(jingdian(j):x(k,i,j)=@if(r(i,j)#eq#1#and#v(k-1)#eq#i,j,0)));!v(k)=@sum(jingdian(j):@sum(jingdian(i):x(k,i,j))));

@for(jingdian(k)|1#lt#k#and#k#le#n:@for(jingdian(i):@for(jingdian(j):x(k,i,j)=@if(0.5#le#r(i,j)#and#r(i,j)#le#1.5#and#(i-0.5)#le#v(k-1)#and#v(k-1)#le#(i+0.5),j,0)));v(k)=@sum(jingdian(j):@sum(jingdian(i):x(k,i,j))));

@for(jingdian(i)|1#eq#i:v2(i)=1;b2(i)=0);

!@for(jingdian(k)|1#lt#k#and#k#le#n2:@for(jingdian(i):@for(jingdian(j):x2(k,i,j)=@if(r(i,j)#eq#1#and#v2(k-1)#eq#i,j,0)));!v2(k)=@sum(jingdian(j):@sum(jingdian(i):x2(k,i,j))));

@for(jingdian(k)|1#lt#k#and#k#le#n2:@for(jingdian(i):@for(jingdian(j):x2(k,i,j)=@if(0.5#le#r2(i,j)#and#r2(i,j)#le#1.5#and#(i-0.5)#le#v2(k-1)#and#v2(k-1)#le#(i+0.5),j,0)));v2(k)=@sum(jingdian(j):@sum(jingdian(i):x2(k,i,j))));

@for(jingdian(i)|2#le#i#and#i#le#(n):@for(jingdian(k):@for(jingdian(j):bb(k,i,j)=@if(v(i)#eq#j#and#v(i-1)#eq#k,t(k)+tt(k,j),0)));b(i)=@sum(jingdian(j):@sum(jingdian(k):bb(k,i,j))));

@for(jingdian(k)|k#le#n:tv(k)=@sum(jingdian(i)|i#le#(k):b(i))/12); @for(jingdian(i)|2#le#i#and#i#le#(n2):@for(jingdian(k):@for(jingdian(j):bb2(k,i,j)=@if(v2(i)#eq#j#and#v2(i-1)#eq#k,t(k)+tt(k,j),0)));b2(i)

=@sum(jingdian(j):@sum(jingdian(k):bb2(k,i,j))));

@for(jingdian(k)|k#ne#1#and#k#le#n2:tv2(k)=@sum(jingdian(i)|i#le#(k):b2(i))/12+4);

@for(jingdian(k)|k#eq#1#or#k#gt#n2:tv2(k)=0);

@for(jingdian(k)|k#le#n2:@for(jingdian(j)|j#le#n:rrr(j,k)=@if(v(j)#eq#v2(k)#and#(tv2(k)-tv(j))#lt#1#and#(tv(j)-tv2(k))#lt#1,1,0))); @for(links(j,k)|(j#gt#n#and#k#le#n2)#or#(j#le#n#and#k#gt#n)#or#(j#gt#n#and#k#gt#n):rrr(j,k)=0);

@for(jingdian(j)|j#ge#2#and#j#le#n2:rrv(j)=@sum(jingdian(k):rrr(j,k)));

@for(jingdian(k)|k#eq#1#or#k#gt#n2:rrv(k)=0); End

第四问结果（以n=5为例）：

Local optimal solution found at iteration: 5831 Objective value: 1617.405

Variable Value Reduced Cost Z 0.9500000 0.000000 N2 5.000000 0.000000 N 5.000000 0.000000 FEIYONG 960.6000 0.000000 FEIYONG2 980.4500 0.000000 V( 1) 1.000000 0.000000 V( 2) 0.000000 0.000000 V( 3) 0.000000 0.000000 V( 4) 0.000000 0.000000 V( 5) 0.000000 0.000000 V( 6) 0.000000 0.000000 V( 7) 0.000000 0.000000 V( 8) 0.000000 0.000000 V( 9) 0.000000 0.000000 V( 10) 0.000000 0.000000 V( 11) 0.000000 0.000000 V2( 1) 1.000000 0.000000 V2( 2) 0.000000 0.000000 V2( 3) 0.000000 0.000000 V2( 4) 0.000000 0.000000 V2( 5) 0.000000 0.000000 V2( 6) 0.000000 0.000000 V2( 7) 0.000000 0.000000 V2( 8) 0.000000 0.000000 V2( 9) 0.000000 0.000000 V2( 10) 0.000000 0.000000 V2( 11) 0.000000 0.000000

第五问程序：（以n=5为例） sets:

jingdian/1..11/:c,t,w,l,v,b,y,tv;!其中：1,2,...,11分别代表成都、九寨沟、黄龙、乐山、峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺、沟康定；c，t分别表示旅行团在各景点的吃住消费和逗留时间；w表示各景点选择性权重；l是为了控制不出现两个以上环形回路而设的一个变量; gailv/1..10/;

links(jingdian,jingdian):r,cc,tt;!其中：r为0-1变量（0表示两景点不相连，1表示两景点相通）；cc为两景点之间的交通费用；tt为两景点之间的交通时间; links2(jingdian,gailv):pp,pv;

links1(jingdian,jingdian,jingdian):x,bb,ppv; endsets data:

t=7 24 18 12 36 30 12 9 15 24 17;!其中:t(1)=0,表示在成都的逗留时间为0，因为相对旅行团而言，由于成都既是起点又是终点，并未在成都游玩;

c=120 423 300 135 378 390 175 90 148 303 241;!其中：c(1)=0，表示在成都的吃住费用算做，理由同上;

w= 0 0.185 0.185 0.217 0.217 0.196 0.196 0.206 0.206 0.196 0.196; tt=0 8.54 4.74 8.54 0 1.22

2.82

3.44

5.08

8.4 1.32

8.84 4.02 4.24 6.08 6.22 6.74

1.54 8.98 7.46 4.24 4.04 6.22

6.14

6.6

11.52 12.14 10.9

7.78

13.1 8.08

14.84 15.54 13.44 13.9 5.84 5.98 3.86

6.3 6.74 2.86 6.74 6.54 0; 6 6.46

4.74 1.22 0 11.22 11.82 9.38 2.82 11.52 11.22 0 0.88 3.44

12.14 11.82 0.88

7.78

11.58 8.08

7.66 7.46

5.08 10.9 9.38 8.4 13.1 1.32 1.54 6.14

8.84 8.98

11.58 7.66

8.24

0 8.42

2.18

4.66 4.88

8.42 8.24

0 2.18

4.24 4.04 2.86

0 6.08

4.02 4.24

4.66 4.88 6.74

0 0.3 6.28 0.3 0 6.08

6.08 6.54

2.08

14.84 13.44 5.84

6.3 6.46

6 5.98 3.86 6.28 0 2.08

6.6 15.54 13.9

!其中：主对角线为零,表示各景点到自身交通费用为零;

cc=0 128 71 42 52 77 126 20 23 92 99 128 0 18 173

182 164

197 133 135 223 233

71 18 0 168 177 141 174 115 112 202 209 42 173 168 0 13 117 121 60. 64 88 95 52 182 177 13 0 126 124 70 73 90 97 76 164 141 126 197

117 126 0 33 64 61 90 101 174 121 124 33 0 91 93 58 43

20 133 115 60 70 64 91 0 5 94 101 23 135 112 64 73 61 93 5 0 91 98 92 223 202 88 90 90 58 94 91 0 31 99 233 209 95 97 101 43 101 98 31 0; !其中：主对角线为零,表示各景点到自身的交通时间为零; n=5;!其中：n表示计划游玩的景点数目; pp=0.15 0.1 0.3 0.8 0.7 0.5 0.6 0.3 0.1 0

1 0.8 0.8 0.5 0.5 0.4 0.5 0.6 0.3 0.2 0.5 1 0.9 1 0.3 0 0.2 0 0.4 0.4 0.1 0 0.1 0.5 0.5 0.7 0.3 0.3 0.1 0.1 0.3 0.4 0.4 0.6 0.3 0.3 0.2 0.4 0.6 0.6 0.6 0.6 0.6 0.5 0.8 0.3 0.1 0.1 0.1 1 0.3 0.2 0.2 0.1 0 0.1 0.1 0.2 0.2 0.3 0.4 0.3 0.3 0.2 0.4 0.9 0.9 0.9 0.8 0.8 0.5 0.3 0.3 0.4 0.3 0.8 1 0.9 0.9 0.9 0.2 0.6 0.6 0.4 0.1 0 0.8 0.7 0.6 0.4 0.1 0.1 0.3 0.3 0.5 0.6 0.8 0.7 0.63 enddata

min=0*(p-0.9)/3.3+0.9*(quan- 137)/173;!目标函数：表示计划游玩的景点数目为n时的最小费用;

quan=@sum(jingdian(j):@sum(jingdian(i):w(j)*r(i,j)*(cc(i,j)+0.45*(c(i)+c(j)))));

q=@sum(jingdian(j):@sum(jingdian(i):r(i,j)*(cc(i,j)+0.45*(c(i)+c(j)))));

@sum(jingdian(j):@sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j)))))<120;!约束条件:表示总的旅行时间（交通时间和景点逗留时间）不超过给定时间10天;

@for(jingdian(i):@sum(jingdian(j):r(i,j))=@sum(jingdian(j):r(j,i))); @for(jingdian(i)|i#eq#1:@sum(jingdian(j):r(i,j))=1);

@sum(jingdian(j):@sum(jingdian(i):r(i,j)))=n;!约束条件:表示旅游景点的数目为n的约束;

@for(jingdian(i):@for(jingdian(j)|j#gt#1#and#j#ne#i:l(j)>=l(i)+r(i,j)-(n-2)*(1-r(i,j))+(n-3)*r(j,i)));

@for(jingdian(i)|i#gt#1:l(i)1+(n-2)*r(i,1));!这两个约束条件：为了控制不出现两个以上环形回路，保证有且仅有一条环形路线; @for(jingdian(i)|1#eq#i:v(i)=1;b(i)=0);

@for(jingdian(i)|2#le#i#and#i#le#(n):@for(jingdian(k):@for(jingdian(j):bb(k,i,j)=@if(v(i)#eq#j#and#v(i-1)#eq#k,t(k)+tt(k,j),0))));

0.4;

@for(jingdian(i)|2#le#i#and#i#le#(n):b(i)=@sum(jingdian(j):@sum(jingdian(k):bb(k,i,j))));

@for(jingdian(k)|k#le#n:tv(k)=@sum(jingdian(i)|1#le#i#and#i#le#(k):b(i)/12));

!@for(jingdian(j)|j#le#n:@for(jingdian(i):ssv(i,j)=@if(v(j)#eq#i,t(i),0)));

!@for(jingdian(j)|j#le#n:sv(j)=@sum(jingdian(i):ssv(i,j)));

@for(jingdian(j)|2#le#j#and#j#le#n:@for(gailv(k):@for(jingdian(i):ppv(i,j,k)=@if(v(j)#eq#i#and#(tv(j))#le#k#and#k#le#(tv(j)+t(i)/12),pp(i,k),0))));

@for(links2(j,k)|2#le#j#and#j#le#n:pv(j,k)=@sum(jingdian(i):ppv(i,j,k)));

@for(links2(j,k)|j#lt#2#or#j#gt#n:pv(j,k)=0); p=@sum(links2(j,k):pv(j,k)); end

第五问结果：

Variable Value Reduced Cost

N 5.000000 0.000000 P 1.600000 0.000000 QUAN 157.8990 0.000000 Q 927.2000 0.000000 V( 1) 1.000000 0.000000 V( 2) 7.000000 0.000000 V( 3) 9.000000 0.000000 V( 4) 8.000000 0.000000 V( 5) 4.000000 0.000000 V( 6) 0.000000 0.000000 V( 7) 0.000000 0.000000 V( 8) 0.000000 0.000000 V( 9) 0.000000 0.000000 V( 10) 0.000000 0.000000 V( 11) 0.000000 0.000000

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文