下载文档原格式
数学建模最佳旅游路线地选择模型引言：旅游是人们休闲娱乐、增长见闻的重要方式之一。
然而，选择旅游目的地时常常会面临如何评估不同地点之间的优劣以及如何确定最佳的旅游路线的问题。
为了解决这一难题，我们可以借助数学建模的方法，通过建立旅游路线地选择模型，帮助人们在众多选项中找到最佳的旅游路线。
一、问题描述：我们面临的问题是，在给定的旅游目的地中选择最佳的旅游路线。
假设旅游目的地共有n个，分别用D1、D2、…、Dn表示。
我们需要确定从起始地（称为S）到达终点地（称为E）的最佳路线。
二、模型建立：在建立模型之前，我们需要确定几个关键因素：1.每个旅游目的地之间的距离：我们可以通过地理或交通工具的信息来获取旅游目的地之间的距离。
2.每个旅游目的地的景点质量：我们可以通过用户评价、专家评分等手段来评估每个旅游目的地的景点质量。
3.旅游者的偏好：不同的旅游者对景点的偏好可能存在差异，例如有的人喜欢自然景观，有的人偏好历史文化。
我们可以通过问卷调查等方式了解旅游者的偏好。
基于以上因素，我们可以建立如下的旅游路线地选择模型：1.建立旅游目的地之间的距离矩阵：假设共有n个旅游目的地，则可以建立一个n×n的距离矩阵D，其中D(i,j)表示第i个旅游目的地到第j个旅游目的地的距离。
2.建立旅游目的地的景点质量评分向量：假设共有n个旅游目的地，则可以建立一个n维向量Q，其中Q(i)表示第i个旅游目的地的景点质量评分。
3.建立旅游者的偏好向量：假设共有m个旅游者，则可以建立一个m维向量P，其中P(i)表示第i个旅游者的偏好。
4.确定最佳路线：通过综合考虑旅游目的地之间的距离、景点质量和旅游者的偏好，可以使用数学模型（如线性规划、多目标规划等）来确定最佳路线。
具体的模型则需要根据实际情况进行调整和选择。
三、模型求解：根据建立的数学模型，我们可以通过求解最佳路线问题来得到旅游的最佳路线。
具体的求解方法可以有多种：1.基于算法的求解：可以利用优化算法（如遗传算法、模拟退火算法等）来求解最佳路线问题。
2012高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。
如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 12 所属学校（请填写完整的全名）：鲁东大学参赛队员 (打印并签名) ：1. 张亭2. 任雪雪3. 卜范花指导教师或指导教师组负责人 (打印并签名)：日期： 2010 年 8 月 2 日赛区评阅编号（由赛区组委会评阅前进行编号）：2010高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：最佳旅游路线的选择模型摘要：本文研究的是最佳旅游路线的选择问题，此问题属于旅行商问题，我们建立了路径最短，花费最少，省钱、省时、方便三个模型。
根据周先生的不同需求，我们用改良圈算法和多目标规划解决了该问题，之后我们结合实际情况对三个模型进行科学地误差分析，并分析了该算法的复杂性。
针对问题一，题目中给出了100个城市的经纬度，要求我们为周先生设计一条最短的旅行路线，即从驻地出发，经过每个城市恰好一次，再回到驻点。
由此可知，此问题属于旅行商问题。
首先，我们按附件所给各城市的顺序编号1,2,,100，以两城市间的直线距离代替实际距离。
然后，我们运用改良圈算法求解旅行商问题，以任意两点之间的最短距离矩阵为权重，利用1100100(,)w i j ⨯邻接矩阵构造无向图1UG ，据题意不知周先生的起始地点，因此利用Matlab 软件重复进行100次改良圈算法即以每一个城市为出发点，从100个Hamilton 圈得到了最优圈1circle ，即最短的旅行路线。
最佳云南旅游路线设计摘要本文主要研究最佳旅游路线的设计问题。
在满足相关约束条件的情况下,花最少的钱游览尽可能多的景点是我们追求的目标。
基于对此的研究,建立数学模型,设计出最佳的旅游路线。
第一问给定时间约束，要求为设计合适的旅游路线。
我们建立了一个最优规划模型,在给定游览景点个数的情况下以人均总费用最小为目标。
再引入0—1变量表示是否游览某个景点,从而推出交通费用和景点花费的函数表达式，给出相应的约束条件,使用lingo编程对模型求解.推荐方案：第二问放松时间约束，要求游客们游遍所有的景点,该问题也就成了典型的货郎担(TSP）问题。
同样使用第一问的模型，改变时间约束，使用lingo编程得到最佳旅游路线为:本文思路清晰,模型恰当，结果合理.由于附件所给数据的繁杂，给数据的整理带来了很多麻烦，故我们利用Excel排序，SPSS预测，这样给处理数据带来了不少的方便.本文成功地对0—1变量进行了使用和约束，简化了模型建立难度，并且可方便地利用数学软件进行求解。
此外，本文建立的模型具有很强普适性,便于推广。
关键词：最佳路线TCP问题景点个数最小费用一问题重述云南是我国的旅游大省，拥有丰富的旅游资源,吸引了大批的省外游客，旅游业正在成为云南的支柱产业。
随着越来越多的人选择到云南旅游，旅行社也推出了各种不同类型的旅行路线，使得公众的面临多条线路的选择问题。
假设某一个从没有到过云南的人准备在假期带家人到云南旅游，预计从昆明出发,并最终返回昆明。
请你们为他设计一条在云南旅游的最佳路线初步设想有如下线路可供选择：一号线：昆明-玉溪-思茅二号线：昆明—大理-丽江三号线:昆明—大理-香格里拉四号线：昆明-玉溪—西双版纳五号线：昆明-玉溪—思茅—西双版纳-大理-丽江-香格里拉每条线路中的景点可以全部参观，也可以参观其中之一。
结合上述要求,请你回答下列问题:一、请你们为游客设计合适的旅游路线，假设使游客在10天时间内花最少的钱尽可能的游更多的地方。
数学建模论文-旅游线路的优化设计一、问题重述随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。
江苏徐州有一位旅游爱好者打算在今年的五月一日早上8点之后出发，到全国一些著名景点旅游，由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。
他预最后回到徐州。
选了十个省市旅游景点，如附表1(见附录I)所示。
假设(A)城际交通出行可以乘火车(含高铁)、长途汽车或飞机(不允许包车或包机)，并且车票或机票可预订到。
(B)市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。
(C)旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。
晚上20:00至次日早晨7:00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。
吃饭等其它费用60元/天。
(D)假设景点的开放时间为8:00至18:00。
问题:根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，信息。
在景点的停留时间等(1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用,请建立相关数学模型并设计旅游行程表。
(2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间,请建立相关数学模型并设计旅游行程表。
(3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。
(4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。
(5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。
二、问题假设1、忽略乘坐出租车时经过收费路段所交的费用;2、在每个城市中停留时，难免会遇到等车、堵车等延时情况，在此问题中我们不做考虑;3、所有旅馆都未客满，并且忽略从旅馆到火车站或景点的时间;4、列车车次和飞机航班没有晚点等情况发生;5、列车和飞机的票足够，没有买不到票的情况发生;6、景点的开放，列车和航班的运营不受天气的影响;7、绘图时，经线和纬线近似平行分布;8、将城市和路径的关系转化为图论问题;9、在时间的认识上，我们把当天的8点至次日的8点作为一天。
数学建模最佳旅游路线的选择模型优选资料在当今社会，旅游已经成为人们生活中不可或缺的一部分。
无论是为了放松身心、领略不同的风土人情，还是为了增长见识、丰富人生阅历，人们都热衷于踏上旅程。
然而，如何在众多的旅游景点中选择出一条最佳的旅游路线，成为了许多旅行者面临的难题。
这时候，数学建模就能够发挥出其强大的作用，为我们提供科学合理的决策依据。
数学建模是一种通过数学语言和方法来描述和解决实际问题的手段。
在旅游路线选择的问题上，数学建模可以帮助我们综合考虑各种因素，如景点的吸引力、交通便利性、旅行时间和费用等，从而找到最优的解决方案。
接下来，我们将介绍几种常见的用于选择最佳旅游路线的数学建模方法。
一、图论模型图论是数学的一个重要分支，它可以很好地应用于旅游路线的规划。
我们可以将旅游景点看作图中的节点，景点之间的道路看作图中的边，边的权重可以表示距离、时间或费用等。
通过图论中的算法，如最短路径算法（Dijkstra 算法、FloydWarshall 算法等），我们可以找到从起点到终点的最短路径，或者在一定限制条件下（如时间或费用预算）的最优路径。
例如，如果我们想要在有限的时间内游览尽可能多的景点，就可以使用最短时间路径算法来规划路线。
假设我们有 5 个景点 A、B、C、D、E，它们之间的距离和所需时间如下表所示：｜起点｜终点｜距离（km）｜时间（h）｜｜：：｜：：｜：：｜：：｜｜ A ｜ B ｜ 50 ｜ 1 ｜｜ A ｜ C ｜ 80 ｜ 15 ｜｜ A ｜ D ｜ 120 ｜ 2 ｜｜ A ｜ E ｜ 100 ｜ 15 ｜｜ B ｜ C ｜ 60 ｜ 1 ｜｜ B ｜ D ｜ 90 ｜ 15 ｜｜ B ｜ E ｜ 70 ｜ 1 ｜｜ C ｜ D ｜ 70 ｜ 1 ｜｜ C ｜ E ｜ 50 ｜ 05 ｜｜ D ｜ E ｜ 80 ｜ 1 ｜如果我们的时间限制为 5 小时，从景点 A 出发，那么通过 Dijkstra 算法可以计算出最优的游览路线为 A B E C D，总时间为 45 小时。
运用数学模型优化旅游线路设计数学模型可以被运用来优化旅游线路的设计。
通常情况下，旅游线路的设计需要综合考虑多个因素，如景点的距离、游客的时间限制、预算以及个人的旅游偏好等。
通过建立一个数学模型，我们可以将这些因素结合在一起，并通过优化算法找到最佳的旅游线路。
我们需要定义一个数学模型来表示旅游线路的设计问题。
假设有n个景点，我们可以使用一个n×n的矩阵来表示每个景点之间的距离。
我们还可以定义一个n维向量来表示每个景点的游玩时间，并设定一个总的游玩时间限制。
我们还可以考虑每个景点的门票价格，并设置一个总的预算限制。
接下来，我们需要定义一个目标函数来衡量旅游线路的优劣。
这个目标函数可以是景点之间的距离总和，因为我们通常希望将旅游时间最小化。
如果我们希望在预算和时间限制下尽可能多地游玩景点，我们可以考虑将目标函数定义为游玩的景点数量。
然后，我们可以使用优化算法来找到使目标函数最小化（或最大化）的旅游线路。
一种常用的优化算法是遗传算法，它模拟了进化过程中的遗传变异和选择。
使用遗传算法，我们可以生成一个初始的旅游线路，然后通过交叉和变异操作来生成新的旅游线路，最终选择最优的旅游线路。
在进行优化算法之前，我们还可以考虑引入一些约束条件。
我们可能希望在每个景点停留的时间不能超过一定的上限，或者我们可能希望将一些特定的景点包含在旅游线路中。
我们可以使用计算机编程语言来实现这个数学模型，并通过输入适当的数据来运行优化算法。
在算法运行完之后，我们可以得到一个最佳的旅游线路，并将其输出为可视化的地图或详细的行程计划。
运用数学模型优化旅游线路设计旅游线路设计是一项复杂的任务，需要考虑众多因素，如旅游景点的位置、时间、距离等。
而数学模型可以帮助我们优化旅游线路的设计，使得旅游线路更加合理、高效。
我们可以运用图论模型来解决旅游线路中的路径选择问题。
图论是研究顶点和边之间关系的数学分支，可以通过建立图模型来描述旅游景点之间的距离、连通关系等。
在图模型中，每个旅游景点可以表示为一个顶点，而两个旅游景点之间的距离则可以表示为边的权重。
通过使用最短路径算法，比如Dijkstra算法或Floyd-Warshall算法，我们可以找到从一个旅游景点到另一个旅游景点的最短路径，从而确定游览的顺序和路径。
我们可以运用约束优化模型来考虑旅游线路中的时间限制和资源分配问题。
约束优化模型可以将旅游线路设计问题转化为一个数学优化问题，通过设定目标函数和约束条件来找到最优解。
我们可以将每个旅游景点的吸引力、游览时间和交通成本等视为目标函数的参数，然后通过设置约束条件来限制旅游线路的总时间、总费用等。
通过求解这个优化问题，我们可以得到一个最优的旅游线路设计方案。
我们还可以运用网络流模型来解决旅游线路中的资源分配问题。
网络流模型是一种用于描述资源流动和分配的数学模型，可以帮助我们合理分配旅游资源，如交通工具、食宿设施等。
通过建立一个网络图模型，将旅游景点和资源之间的关系转化为节点和边，我们可以使用最大流算法来确定每个旅游景点所需的资源量，从而实现资源的均衡和合理分配。
运用数学模型可以帮助我们优化旅游线路的设计。
通过运用图论模型解决路径选择问题、约束优化模型解决时间限制和资源分配问题，以及网络流模型解决资源分配问题，我们可以得到一个更加合理、高效的旅游线路设计方案。
这些数学模型的运用，不仅可以提高旅游线路的满意度和效益，还可以为旅游行业的发展提供科学依据。
旅游路线设计数学建模旅游是人们生活中重要的一部分，而旅游路线的规划和设计是旅游行业中非常重要的一环。
随着人们旅游需求的增加和旅游信息的丰富，如何设计一条满足旅游者需求的旅游路线，成为了一个亟待解决的问题。
数学建模作为一种解决实际问题的有效工具，也可以用来设计旅游路线。
旅游路线的设计需要考虑旅游者的需求和旅游资源的分布。
我们可以将旅游路线设计成一条带权有向图，点表示旅游景点，边表示旅游路线，边权表示旅游路线的长短或者旅游者对该路线的评价。
而在旅游路线的设计中，我们需要考虑一些问题，如何选择出旅游者最感兴趣的景点，如何安排旅游者的行程，以及如何保证旅游者的安全等。
我们可以将旅游者的需求和景点的特点用数学模型进行表达。
在旅游路线的设计中，我们可以采用TOPSIS多属性决策模型，将旅游者的需求和景点的特点用多个属性进行描述，然后通过计算每个景点的TOPSIS得分，选出得分最高的景点进行旅游路线的规划。
同时，在计算景点的TOPSIS得分时，我们还需要考虑不同属性之间的权重，以更好地反映旅游者的需求。
除此之外，我们还可以采用遗传算法来设计旅游路线。
遗传算法是一种模拟自然选择和遗传机制的优化算法，通过模拟自然进化的过程，从原始的旅游路线中产生出更优秀的旅游路线。
在遗传算法中，我们需要设计适应度函数，将旅游者的需求和景点的特点转化为适应度值，然后通过选择、交叉、变异等操作，产生出更优秀的旅游路线。
我们还可以采用蚁群算法来设计旅游路线。
蚁群算法是一种模拟蚂蚁觅食行为的优化算法，通过模拟蚂蚁在搜索食物时留下信息素的行为，从而产生出更优秀的旅游路线。
在蚁群算法中，我们需要设计信息素更新规则、信息素挥发规则和路径选择规则，从而产生出更优秀的旅游路线。
旅游路线设计数学建模是一个复杂而有趣的问题，需要考虑旅游者的需求、旅游资源的分布以及数学建模方法的选择等问题。
未来随着旅游行业的发展和旅游者需求的变化，旅游路线设计数学建模也将不断发展和完善。
景区路线规划摘要本文主要研究最短旅游路线的设计问题。
在满足题目中的条件下，找到最佳的路径且用最短的距离是我们追求的目标。
毕竟，能否设计出合理且令人满意的旅游路径，对景区的经济效益和长远发展有着密切的关系。
对此本文用数学联系实际，建立数学模型，设计出相对科学的景区旅游景点路线，来解决此类问题。
对于问题一，从题目中我们了解到我们要设计出6种只含4个景点的最短路径，且至少包括两个特色景点，而旅游内容相近的同类景点如1，6和9,10又不能同时出现。
根据这些条件，我们运用floyd算法的原理，通过matlab编程，建立带权邻接矩阵，再用插入顶点的方法构造出距离矩阵，同时也能求出插入点矩阵，最终得到初步符合条件的旅游套餐。
再经过用Excel软件对得出的数据进行分类，整理，排序，最终得出符合题意的6种旅游套餐。
同时，在我们对景点的组合中可以发现，有多种景点组合都存在游览顺序不同而导致的行程不同的现象。
对这种游览顺序不同，但游览的景点是相同的情况，我们视其为同一种旅游套餐。
对于问题二，题目要求我们设计出6种不同旅游套餐，并在在景区特色景点的客流容纳人数是其他景点的两倍的情况下计算出各种套餐的人数比例，使得景点的客流量基本均衡，且总行程尽可能短。
对此我们0-1变量的思想表示是否游览某个景点，从而推出总行程尽可能短的约束条件，再用Lingo编程对模型进行求解，得出初步可能的旅游套餐。
然后再引入方差的思想，方差是描述数据离散程度的量，方差越小各景点的客流量越均衡。
所以，我们接下来可以利用 6 个旅游套餐中所有景点的客流量的方差来刻画景点客流量的均衡程度，要使方差尽量小，首先6个套餐应覆盖尽量多的景点，再由每种套餐的比例来约束方差，使得方差尽量小。
由此，我们可以建立关于游客量的方程和关于方差的函数。
然后再对之前得出的旅游套餐使用综合评判的方法，并经过灵敏度的分析，得出符合要求的6种旅游套餐。
关键词 floyd算法 Exce软件 matlab软件 0-1变量 Lingo软件一、问题重述图1某景区有10个景点，各景点的交通示意图如图1。
校园最佳游览路线问题的数学模型分析廖川荣(南昌大学数学系, 江西南昌330031)[摘要] 将某高校的校园示意图转化为赋权连通图,求得该连通图的邻接矩阵,利用Floyd算法及图论软件包构造一个最短路径矩阵,得到一个赋权完全图,将求校园最佳游览路线问题归结为图论中的最佳推销员回路问题,建立混合整数线性规划模型,并利用优化软件求得最优解.从而解决了校园开放日游览计划中提出的关于校园最佳游览路线和校园游览车最优配置问题.[关键词] 赋权完全图；最佳游览路线；最优配置.[中图分类号] O157.6 [文献标识码] A [文章编号] 911361 引言现在国内许多高校每年都会定期举办校园开放日,开放日旨在全面展示该校的办学特色及优美的校园环境,反映大学生丰富多彩的校园生活.通过举办开放日,为考生填报高考志愿提供全面真实和具体的信息,让考生和家长了解学校的历史和现状,熟悉招生政策,在大学和考生之间建立一个友好顺畅的交流沟通平台.某高校开放日,将会有许多考生及家长要求参观该校的新校园,以下为校园简化示意图:(其中v i为参观者需参观的主楼、景点和场地,连线为两参观点间道路,连线上数字为两参观点间距离，单位:公里)图1:校园简化示意图说明:V1医学院教学大楼, V2本科生公寓A区, V3学生食堂A, V4国际学术交流中心, V5白求恩广场, V6医学实验大楼, V7青年教师宿舍区, V8研究生院, V9运动场A, V10正门, V11工程实验楼, V12天健园, V13研究生公寓区, V14基础实验大楼, V15本科生公寓B区, V16办公楼, V17中心广场, V18图书馆, V19计算机实验中心, V20保安楼, V21理科生命大楼, V22材料楼, V23环境楼, V24正气广场, V25人文楼, V26信工楼, V27法学楼, V28机电楼与建工楼, V29综合教学楼, V30学生食堂B, V31外经楼, V32学工楼, V33艺术楼, V34商业街, V35校医院, V36本科生公寓C区, V37学生食堂C, V38体育馆, V39体育场, V40游泳馆, V41运动场B.校方拟在本校高年级学生中招募一批临时导游,负责接待并陪同考生及家长乘坐校园游览车（限载 50人,时速20公里/小时）参观游览新校园,路线是从新校园正大门出发,最后返回到出发地.为了向所有参观者展示该校的风貌和亮点,同时满足参观者了解校园的不同要求,校方要求应聘者提供一份详细的校园游览计划,计划中应包括以下内容:1）根据考生的理、文、工、医四种报考专业为参观者选择下车参观的主楼、景点和场地.2）根据校园简化示意图及问题1确定的下车参观的主楼、景点和场地,建立数学模型,按报考专业分别设计4条不同的最佳游览路线,使每条游览路线的总路程最短.3）假设有3000本省考生及1000外省考生想在开放日这天参观游览该校的新校园；且根据历年统计，开放日上午参观人数约为全天参观人数的60%.问该校开放日至少要预备多少辆校园游览车? 2 模型假设1) 不同报考专业的参观者总是更有兴趣参观与本专业有关的主楼、景点或场地,导游通过指示牌来引导报考不同专业的考生及家长乘坐不同路线的游览车.2) 道路通畅,游览车只在选定参观点仃车,每个参观点只参观一次.3) 对相同性质的楼群只参观一栋有代表性的主楼.4) 不考虑天气等环境因素的影响.5) 校园游览车限载50人,时速20公里/小时.6) 参观者参观选定的主楼、景点与场地的时间均为5分钟.7) 在开放日这天有3000本省考生及1000外省考生想参观游览该校的新校园.8) 不考虑参观者上下车时间.9) 开放日工作时间为上午8:00-12:00, 下午1:00-17:00.10) 根据历年统计, 校园开放日上午参观人数约为全天参观人数的60%.11）将各主楼、景点或场地看作平面上的质点,不考虑自身形状的大小,均称之为图论中的结点。
3 符号说明v i : 参观者需参观的主楼、景点和场地. ()1,2,,41i =(),i j d v v ：两参观点v i 与v j 之间的路程.(),1,2,,41i j =(),min ,i j i j d d v v =: 两参观点v i 与v j 之间的最短路程.(),1,2,,41i j = D k ：第k 条游览路线的最短路径矩阵(Floyd 矩阵).,()k k k i j nn D d ⨯=，其中n k 表示第k 条游览路径中的参观点数. (n 1 =15, n 2 =17, n 3 =19, n 4 =12) x (v i , v j ): 代表游览路径中两参观点间的特征变量. 当v i 与v j 为最佳游览路线上两个相邻的需下车参观的景点时x (v i , v j )=1, 反之, x (v i , v j )=0. (i, j=1,2, (41)P i : 参观者乘游览车游览第i 条路线的概率. (i =1,2,3,4)R i : 第i 条游览路线上参观游览的人数. (i =1,2,3,4)S i : 第i 条游览路线起点发车速率. (i =1,2,3,4)T i : 游览车在第i 条路线行驶一圈所需时间. (i =1,2,3,4)N i : 第i 条游览路线需要预备的最低校园游览车数. (i =1,2,3,4)N : 校方需要预备的最低校园游览车数. (N = N 1 + N 2 + N 3 + N 4 )M : 在开放日这天想参观游览该校新校园的本省及外省考生的总人数.(M =4000)4 模型建立与求解4.1 选择参观者下车参观的主楼、景点和场地校园开放日活动是社会各界认识了解高校的一个重要窗口,是加强学校与社会联系的一个重要途径,是提升高校社会影响力,发挥高校在科学技术领域中引领作用的重要措施,高校应在开放日向参观者充分展现该校的风貌和亮点.如:基础教学设施,医疗卫生设施,体育运动设施,亮点建筑和人文景观,同时还应考虑到参观者了解校园的不同要求.为此,根据考生的理、文、工、医四种报考专业为参观者选择下列需下车参观的主楼、景点和场地.1) 理科路线参观点: v 10正门, v 16办公楼, v 17中心广场, v 18图书馆, v 14基础实验大楼, v 19计算机实验中心, v 21理科生命大楼, v 30学生食堂B, v 29综合教学楼, v 32学工楼, v 34商业街, v 36本科生公寓C 区, v 35校医院, v 41运动场B, v 24正气广场. (n 1=15)2） 文科路线参观点: v 10正门, v 16办公楼, v 17中心广场, v 18图书馆, v 19计算机实验中心, v 25人文楼, v 27法学楼, v 31外经楼, v 29综合教学楼, v 30学生食堂B, v 32学工楼, v 34商业街, v 33艺术楼, v 35校医院, v 36本科生公寓C 区, v 41运动场B, v 24正气广场. (n 2 =17)3） 工科路线参观点: v 10正门, v 16办公楼, v 17中心广场, v 18图书馆, v 11工程实验楼, v 14基础实验大楼, v 19计算机实验中心, v 22材料楼, v 23环境楼, v 26信工楼, v 28机电楼与建工楼, v 30学生食堂B, v 29综合教学楼, v 32学工楼, v 34商业街, v 35校医院, v 36本科生公寓C 区, v 41运动场B, v 24正气广场. (n 3=19)4） 医科路线参观点: v 10正门, v 16办公楼, v 17中心广场, v 18图书馆, v 6医学实验大楼, v 5白求恩广场, v 9运动场A, v 3学生食堂A, v 2本科生公寓A 区, v 1医学院教学大楼, v 4国际学术交流中心, v 24正气广场. (n 4=12)4.2 设计4条不同的最佳游览路线1）最短路径矩阵将校园示意图转化为赋权连通图G(V , E):()()(),,,,i j i j i j v v E v v d v v ω∀∈=.求得该连通图的邻接矩阵,并利用Floyd 算法及图论软件包构造一个最短路径矩阵(Floyd 矩阵),得到一个赋权完全图()'',G V E ,［1］其中E′中每条边的权等于结点v i 与v j 在图G(V , E)中的最短路径的权:()()()'',,,,min ,i j i j i j i j v v E v v d d v v ω∀∈==.根据问题1确定的理、文、工、医4个报考专业,分别得到4个赋权完全子图的最短路径矩阵。
例如医科路线的Floyd 矩阵为:4,1212()i j D d ⨯==[0.00 0.40 0.65 0.90 0.80 0.60 1.35 1.25 1.00 0.60 0.40 0.900.40 0.00 0.25 0.50 1.20 1.00 1.75 1.65 1.40 1.00 0.80 0.500.65 0.25 0.00 0.25 1.40 1.25 1.60 1.85 1.60 1.25 1.05 0.750.90 0.50 0.25 0.00 1.15 1.35 1.35 1.60 1.35 1.50 1.30 1.000.80 1.20 1.40 1.15 0.00 0.20 0.55 0.45 0.20 0.40 0.40 1.700.60 1.00 1.25 1.35 0.20 0.00 0.75 0.65 0.40 0.20 0.20 1.501.35 1.75 1.60 1.35 0.55 0.75 0.00 0.30 0.60 0.95 0.952.251.25 1.65 1.85 1.60 0.45 0.65 0.30 0.00 0.30 0.70 0.852.151.00 1.40 1.60 1.35 0.20 0.40 0.60 0.30 0.00 0.40 0.60 1.900.60 1.00 1.25 1.50 0.40 0.20 0.95 0.70 0.40 0.00 0.20 1.500.40 0.80 1.05 1.30 0.40 0.20 0.95 0.85 0.60 0.20 0.00 1.300.90 0.50 0.75 1.00 1.70 1.50 2.25 2.15 1.90 1.50 1.30 0.00];2）最佳游览路线求解求考生理、文、工、医四种报考专业的最佳游览路线问题可归结为图论中的最佳推销员回路问题,［2］即在4个赋权完全子图中分别求一个近似最优的Hamilton 圈,［3］该最优H 圈问题可用以下两种方法求解：方法一：二边逐次修正法.［4］（1）输入图()'',G V E 的一个初始圈;（2）用对角线完全算法产生一个初始H 圈;（3）随机搜索出G′中若干个H 圈,例如2000个;（4）对第1、2、3步所得的每个H 圈,用二边逐次修正法进行优化,得到近似最佳H 圈;（5）在第4步求出的所有H 圈中,找出权最小的一个,此即要找的最佳H 圈的近似解.方法二：混合整数线性规划模型.［5］,111min .1,1,2,....1,1,2,....1,20,1,1,2,.....02,3,....n ij ij i j n ij i n ij j i j ij ij i Z d x st x j n x i n u u nx n i j n x i j n u i n ===⎧=⎪⎪⎪==⎪⎪⎪⎨==⎪⎪-+≤-≤≠≤⎪⎪==⎪⎪≥=⎩∑∑∑说明: 约束条件()()..111,1,2,....,1,1,2,.....n ni j i j i j x j n x i n ======∑∑只是该线性规划模型中的两个必要约束条件,而约束条件1,(2)i j ij u u nx n i j n -+≤-≤≠≤是为避免产生子巡回而附加的充分约束条件,其中()2,3,i u i n =可看作n-1个额外的变量.可以证明:任何含子巡回的路线都不满足该约束条件,全部巡回路线都满足该约束条件. 求解结果如下(不加括号为下车参观点）：（1）理科最佳游览路线: v 10→(v 16)→v 24→(v 31)→v 29→v 35→(v 36)→v 41→v 36→v 34→v 32→v 30→(v 28)→(v 26) →(v 22)→v 21→(v 19)→v 14→v 19→v 18→v 17→v 16→v 10, 共有n 1=15个下车参观点;最短游览路程：5.900000（公里）.（2）文科最佳游览路线: v 10→v 16→v 24→v 25→v 27→v 29→v 31→v 33→(v 39)→v 35→(v 36)→v 41→v 36→v 34→ v 32→v 30→(v 28)→(v 26)→(v 22)→(v 21)→v 19→v 18→v 17→(v 16)→v 10，共有n 2=17个下车参观点；最短游览路程：6.300000（公里）.（3）工科最佳游览路线: v 10→(v 16)→v 24→(v 31)→v 29→v 35→(v 36)→v 41→v 36→v 34→v 32→v 30→v 28→v 26→ v 22→v 23→(v 22)→(v 21)→(v 19)→v 14→v 11→(v 14)→v 19→v 18→v 17→v 16→v 10, 共有n 3=19个下车参观点；最短游览路程：6.800000（公里）.（4）医科最佳游览路线: v 10→v 4→v 1→v 5→v 6→v 2→v 3→(v 7)→v 9→(v 8)→(v 11)→(v 14)→(v 19)→v 18→v 17 →v 16→v 24→(v 16)→v 10, 共有n 4 =12个下车参观点；最短游览路程：5.050000（公里）.3) 计算校方开放日需要预备的最低校园游览车数由问题假设,开放日将有3000本省考生及1000外省考生及其家长参观游览该校的新校园,参观者总数为M=4000;开放时间为上午8:00-12:00下午13:00-17:00.参观者按问题2确定的4条最佳游览路线分别参观游览新校园。
