数学建模求最短路径.doc

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：0.21M 资料格式：doc 举报版权申诉

b2cf6616-343e-4d99-bbc3-fb0756742fc5.doc.pdf-第1页.png

第1页 / 共18页

b2cf6616-343e-4d99-bbc3-fb0756742fc5.doc.pdf-第2页.png

第2页 / 共18页

b2cf6616-343e-4d99-bbc3-fb0756742fc5.doc.pdf-第3页.png

第3页 / 共18页

b2cf6616-343e-4d99-bbc3-fb0756742fc5.doc.pdf-第4页.png

第4页 / 共18页

b2cf6616-343e-4d99-bbc3-fb0756742fc5.doc.pdf-第5页.png

第5页 / 共18页

b2cf6616-343e-4d99-bbc3-fb0756742fc5.doc.pdf-第6页.png

第6页 / 共18页

b2cf6616-343e-4d99-bbc3-fb0756742fc5.doc.pdf-第7页.png

第7页 / 共18页

b2cf6616-343e-4d99-bbc3-fb0756742fc5.doc.pdf-第8页.png

第8页 / 共18页

文本预览

2011 年第八届苏北数学建模联赛承诺书我们仔细阅读了第八届苏北数学建模联赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们的参赛报名号为：参赛组别（研究生或本科或专科）：本科参赛队员 (签名) ：队员 1：队员 2：队员 3：获奖证书邮寄地址：

2011 年第八届苏北数学建模联赛编号专用页参赛队伍的参赛号码：（请各个参赛队提前填写好）：竞赛统一编号（由竞赛组委会送至评委团前编号）：竞赛评阅编号（由竞赛评委团评阅前进行编号）：

2011 年第八届苏北数学建模联赛题目基于 Hamilton 回路算法的最优旅游路线设计问题摘要本文围绕五一黄金周的旅游问题进行了定量评估，对无时限的旅游费用问题、无费用限制的旅游时间问题、有费用限制的旅游质量问题、有时限的旅游质量问题、既有时限又有费用限制的旅游质量问题分别建立了数学模型并设计了旅游行程表，对求解结果进行了分析。问题一放开了对时间的限制，要求设计一条用尽可能少的费用游览十个景点的旅游线路。首先，我们对预选的旅游景点之间消耗的费用和时间进行了分析。由于约束条件只要求费用最低，因此我们从火车和长途汽车班次中选取费用最低的并记录下来建立了最优通行费表。第二步，根据 Hamilton 回路算法的有关方法，以费用为参考量，我们建立了一个适用于本问题最优规划模型。第三步，用 C 语言编写模型的指令，运行后得到最优旅游路线：；第四步，综合考虑安排，建立行程表；计算可得最少的总旅行费用为 3101 元。问题二在不限制费用的条件下，要求用最短的时间游览完十个景点。其原理与问题一非常相似，故可用问题一的数学模型及方法，改用景点之间消耗的时间作为参考量，最终得到行程表且知最优旅游路线：；最短的旅行总时间T  8 天 22 小时 23 分。问题三要求我们在只有 2000 元旅游费用的条件下游览尽可能多的城市。因此我们引入 0—1 变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件。这样寻找不同景点数时的最优旅游路线，并计算其总费用。则最优旅游路线的总花费为 1795 元，游览了 7 个景点，是不超过 2000 元的最大值，据此构建行程表。问题四中我们要在 5 天的时间内游览最多的景点并回到徐州。其实质是把问题三中的费用约束条件变成了时间约束，故在此我们依然可用问题三中的模型进行求解，得到最多可游览 6 个景点，耗时 4 天 13 小时（106 小时），据此建立行程表。问题五可看做是问题三、四的合并，其中费用和时间都是约束条件。因此我们综合问题三、四中的算法，运用问题三中的模型对其进行全面分析，得到最多可游览 6 个景点，并建立行程表。关键词：Hamilton 回路算法 C 语言最优旅游路线 0—1 模型 1.问题重述随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上 8 点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如表 1 所示。表 1. 预选的十个省市旅游景点省市景点名称在景点的最短停留时间

江苏山东北京山西河南安徽湖北陕西江西浙江常州市恐龙园青岛市崂山八达岭长城祁县乔家大院洛阳市龙门石窟黄山市黄山武汉市黄鹤楼西安市秦始皇兵马俑九江市庐山舟山市普陀山 4 小时 6 小时 3 小时 3 小时 3 小时 7 小时 2 小时 2 小时 7 小时 6 小时假设： (A) 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。 (B) 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。 (C) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上 20：00 至次日早晨 7：00 之间，如果在某地停留超过 6 小时，必须住宿，住宿费用不超过 200 元/天。吃饭等其它费用 60 元/天。 (D) 假设景点的开放时间为 8:00 至 18:00。问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。 (1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。 (2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。 (3) 如果这位游客准备 2000 元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 (4) 如果这位游客只有 5 天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 (5) 如果这位游客只有 5 天的时间和 2000 元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 2.1 模型的假设 2.模型的假设与符号说明

五一黄金周正值旅游旺季，各地旅游景点吸引了大批游客前往观光。考虑到该游客的旅游路线跨越区域较大，交通情况尚存在一些不确定因素。为了研究方便，我们给出以下假设：（1）城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到；（2）市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车；（3）旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)，晚上 20：00 至次日早晨 7：00 之间，如果在某地停留超过 6 小时，必须住宿，住宿费用不超过 200 元/天。吃饭等其它费用 60 元/天；（4）假设景点的开放时间为 8:00 至 18:00；（5）假设火车、汽车和飞机均正点到达，行程中无事故、无阻碍；（6）假设由火车换乘汽车或者汽车换乘火车的时间很短，忽略不计；（7）假设旅游过程中天气条件良好，不影响行程；（8）由于考虑到在城市内有时需坐公交（大巴）有时需坐出租车，经过近似计算，取每个城市内交通费用为 10 元。 2.2 模型的符号说明（1）i,j 表示第 i 个城市（景点）或第 j 个城市（景点），i，j=0,1,2·······10；（2） Z 表示计划行程中的总费用；（3）W 表示各城市（景点）之间的交通费用的总和， ijW 表示各城市（景点）之间的交通费用；（4） A 表示在景点所在城市的总花费，其中包括 iM 表示第 i 个城市（景点）内的交通费用， iS 表示第 i 个城市（景点）内的食宿费用， iG 表示第 i 个城市的景点门票费用， iA 表示第 i 个城市（景点）内的总费用，故（5） it 表示在第 i 个城市（景点）的逗留时间， ijt 表示从第 i 个景点到第 j 个景点路途中所需时间，T 表示本次旅游的总时间； GSMA ；   i  i i i ijr  （6）  1 0 游客直接从第 i 个到第 j 个景点其他 3.1 问题背景的分析 3.问题的分析根据对题目的理解我们知道，旅游时的总费用包括交通费用、住宿费用和在景点旅游时的费用，在研究确定旅游路线和选用的交通工具后，我们的目标就是在所有的约束条件情况下，求出所求目标的最优解。 3.2 对问题一和问题二的分析问题一要求我们在不限定时间的情况下，游览完十个景点，并设计出花费最少的旅游路线，故要尽量选择便宜的交通工具。这里我们的做法是以任意两景点间的交通费用为权值，构建一个完备图；然后利用 Hamilton 回路算法[1]计算出近似最佳旅游路线，进而得出最佳方案。

问题二实质上是在问题一的基础上改变了约束条件，在不限资金的条件下尽快结束十个景点的旅程。故可用与问题一类似的方法，且应尽量乘坐飞机以减少时间。 3.3 对问题三和问题四的分析经过分析，我们可以知道这两个问题所要实现的目标是，使游客在规定的时间内和规定的花费内游览尽可能多的地方。游览的总费用由两部分组成，分别为交通总费用和在旅游景点的花费。对于问题三，花费在 2000 元以内且游览的景点尽量多是该问题的目标。因此，我们的做法是在满足相应的约束条件下，先确定游览的景点数，然后利用 Hamilton 回路算法和 0--1 模型[2]计算出在这种情况下的最小花费，这样最终会得出几种旅游路线。问题四中，花费在 2000 元以内的条件改为限定时间为最多 5 天，故可使用与问题三类似的方法求得最优解。 3.4 对于问题五的分析问题五是对问题三和问题四进一步综合，要求我们用 5 天的时间和 2000 元的旅游费用游览尽可能多的景点。故可采用与问题三、四类似的方法，进行综合性的求解。 4.模型的准备先给 11 个旅游城市分别进行编号，徐州、常州、青岛、北京、祁县、洛阳、黄山、武汉、西安、九江、舟山分别编为、、、、、、、、、、，则这 11 个城市和其交通线路构成了一个网络图。这些城市可看作该网络图的节点，这些节点由相应的交通线路相连，节点之间的边就是交通线路。 4.2 0——1 模型 4.2.1 目标函数的确立：游览的总费用由 2 部分组成，分别为交通总费用和在旅游景点的花费。我们已经定义： Z ——旅游总花费； W ——交通总费用； A ——旅游景点的花费；从而得到目标函数：交通总花费 AWZ Min   因为 ijW 表示第 i 个景点到第 j 个景点所需的交通费用，而 ijr 是判断游客们是否从第 i 个景点直接到第 j 个景点的 0——1 变量，因此我们可以很容易的得到交通总费用为： W  旅游景点的花费 10 10  0i  0j  ij Wr ij 

因为 iA 表示游客在 i 个景点的总消费， ijr 也可以表示出是否到达过第 i 个和第 j 个景点，而整个旅游路线又是一个环形，因此到景点的花费计算了两遍，从而我们可以得到旅游景点的花费为： 0i  0j  10 10  r ij  （ AA  i ） j 实际上将所 1A  2 从而我们可以得到目标函数为：  Min 10 10  0i  0j  r ij  （ AA  i ） j AWZ  10    10 0i  0j  1Wr   2 ij ij 10 10  0i  0j  r ij  （ AA  i ） j 4.2.2 约束条件: ①时间约束旅游时间应该不超过 5 天，而这些时间包括在路途中的时间和在旅游景点逗留的时间。因为 ijt 表示从第 i 个景点到第 j 个景点路途中所需时间，所以路途中所需 10 10  0i  0j  r ij  t ij 的总时间为 10 1 2  10  0i  0j  r ij  （ t i 时间为； it 表示在第 i 个景点的逗留时间，故在旅游景点的总逗留 t  ） j 。因此，总的时间约束为： 10 10 10 10  0i  0j  r ij  t ij 1 2  0i  0j  r ij  （ t i  t  ） j 120 ②旅游景点数约束根据假设，整个旅游路线是环形，即最终要回到徐州，因此即表示旅游的景点数，这里我们假定要旅游的景点数为 n（n=1，2，3，……，10）。因此旅游景点数约束为： 0i  0j  10 10  ijr 10 10  0i  0j  r ij  n （ 3,2,1n   ， 10 ） ③0——1 变量约束[3] 我们可以吧所有的景点连成一个圈，而把妹一个景点看做圈上一个点。对于每个景点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且有一条边进入就要有一条边出去。因此可得约束： 1   r ij r ij  i j ，，，（ 2,10j   i 10, ）

当 i=1 时，因为徐州是出发点，所以  ij 1 r  0j  。综上所述，我们可以得到总的模型为： ij 1 r   0i  ；j=1 时，因为最终要回到徐州，所以 Min  AWZ  10    10 0i  0j  1Wr   2 ij ij 10 10  0i  0j  r ij  （ AA  i ） j r ij  （ t i  t  ） j 120  t ij 1 2 （ 10 10  0j 0i   2,1n  n r ij 10 10 1i  r ij r ij 0j  10 0i  10 约束条件：         1j     r   ij j   1 r  ij   1 r  ij  0j  r r    ij ij 0   0i  i  ），， 10  1 ，（ i 1,0j   ），， 10 ，（ i 10,2,1j   ），各大景点门票信息[4] 常州市恐龙园青岛市崂山八达岭长城祁县乔家大院景点洛阳龙门石窟黄山市黄山武汉市黄鹤楼西安市秦始皇兵马俑九江市庐山舟山市普陀山门票 160 元 65 元 45 元 40 元 120 元 230 元 80 元 90 元 180 元 200 元 5.模型的建立与求解 5.1 建立无时限的旅游费用 Hamilton 回路模型根据问题一中的约束条件，由于要求在没有时间限制的条件下旅行，因此为了保证游完十个景点所花费用最少，我们选择了耗资最少的方式旅行：首先在选择交通工具时飞机的费用明显过高，予以排除，从现有火车和汽车方案中选择便宜的进行计算；其次，在景点所在城市尽量减少住宿费和餐饮费。根据此思路，搜集资料得出任意两景点之间的最优通行费用表（见下表），以表内费用值作为 Hamilton 回路图中各边的权值。最少旅费（元）徐州常州青岛北京祁县洛阳黄山武汉西安九江舟山（宁波）停留时间最优通行费用表[5]

分享到：

赞收藏

资料库

数学建模求最短路径.doc

相关推荐

课程资源

热门标签

最新资料