数学建模(走遍全国)

1、2010年中国矿业大学徐海学院暑期数学建模集训承 诺 书我们仔细阅读了中国矿业大学徐海学院暑期数学建模集训的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从a/b/c中选择一项填写）： a 我们的参赛号为

2、： 201001 参赛队员 (打印并签名) ：1. 王奎 2. 仇文阳 3. 刘新云 指导教师或指导教师组负责人 (打印并签名)： 教练组 日期： 2010 年 8 月24 日评阅编号（由组委会评阅前进行编号）：2010年中国矿业大学徐海学院暑期数学建模集训编 号 专 用 页评阅编号（由组委会评阅前进行编号）：评阅记录（可供评阅时使用）：评阅人评分备注统一编号：评阅编号：a题：旅行方案张先生喜爱旅游，梦想游遍中国。今年他计划利用假期，从南京出发到全国所有的省份的省会城市、四个直辖市、两个特别行政区旅游。请你为他按下面要求制定旅行方案：1、根据地理位置设计行程，做到最短路线；2、张先生想7月1日

3、出发，采取航空或铁路出行，每到一个城市游玩3天，若通过互联网订票，请为他设计最经济的订票方案；3、综合考虑时间短、经济、方便等因素，设定评价准则，调整你的方案。走遍全中国摘要要从34个城市中制定最短的旅游路线，本文主要采动态规划方法求解，当然空间复杂性及时间复杂性都十分庞大。因此，为解决问题（1），本文采用分区域旅游，然后依次进行动态规划。这样就可以很好的解决了旅游城市数量大的缺点此方法节约计算资源，具有良好的可扩展性和实用性，给问题（2）和问题（3）奠定很好的基础。随着问题（1）的解决，问题（2）和问题（3）都是在问题一得出的路线最优解的前提下，设计省钱、省时又方便的互联网订票方案。本文将这

4、个问题归结为多属性决策的问题。用层次分析法求解。（一）信息的获取：我们将中国交通网上把具体的时刻表、价位表、打折等相关的信息进行整理（见下文）。周先生的满意度本文主要通过对大部分人的满意度调查表的结果进行分析。（二）排序和择优：本文从不同的方面考虑各个属性的权值和所占的空间。得出的部分结果为：南京上海 杭州台北福州南昌长沙武汉广州香港澳门海口南宁贵阳昆明重庆成都拉萨乌鲁木齐西宁兰州银川呼和浩特北京哈尔滨长春沈阳天津济南石家庄太原西安郑州合肥南京总距离：15917km经济支出：20040元 最优时间：102天关键词：动态分析 层次分析 经纬度、最短路线、订票方案、graph软件、满意度、mayt

5、lab程序、 综合评价一、问题重述与分析1.1 问题重述张先生喜爱旅游，梦想游遍中国。今年他计划利用假期，从南京出发到全国所有的省份的省会城市、四个直辖市、两个特别行政区旅游。请你为他按下面要求制定旅行方案：1、根据地理位置设计行程，做到最短路线；2、张先生想7月1日出发，采取航空或铁路出行，每到一个城市游玩3天，若通过互联网订票，请为他设计最经济的订票方案；3、综合考虑时间短、经济、方便等因素，设定评价准则，调整你的方案。1.2 问题分析随着人们生活水平的不断提高，旅游已经成为人们忠爱的休闲方式之一。在制定旅游计划的同时需要考虑很多方面的问题，比如：旅游路线的选择、交通工具的选择、旅途用时、

6、经济花销等等。为了在完成旅游计划的基础上实现省时、方便、经济的目标，需要制定一个最优的旅游方案。本文给出张先生的旅游计划既游遍中国的省会城市、直辖市、香港、澳门以及台北，要求达到旅途最短、经济、省时又方便的目的，为了实现这一目标，需要制定一个最优的旅游方案。首先要实现旅途最短，本问题属于多点的距离最短的问题，很显然，如果利用传统的动态规划解法在n为34的情况下，解法的空间复杂性及时间复杂性都十分庞大，不利于旅行方案的确定，因此，我们采用区域化的动态规划解法。将全国各个地方先进行区域划分，每一个区域进行动态分析。最后在通过各个区域的动态分析。最终达到游遍全国各个省会距离最短的目的。问题（2）和问

7、题（3）都是模型的优化问题。我们主要是考虑了时间短、经济、方便、舒适等各个方面的因素等。本文将其归结为多重属性的决策问题。二、 模型的基本假设和符号说明2.1 模型假设1. 假设在旅途中旅游车的准时出发到达,且不考虑突发事件干扰车子的行程;2. 在旅游的过程中,当天旅游目的地附近都有宾馆,且第一天的目的地就是第二天的出发点；3. 在每个城市的吃饭、购物、在城市中观光景点等所需的费用费用视为相同；4. 假设周先生自带充足食物，并不考虑住宿问题；在旅行过程中只考虑购票的经济花费，不考虑其他的消费5. 票价不考虑除打折以外的其他优惠；6. 旅游的这段时间内不会有价格变化;7. 假设经纬线是均匀的；8

8、. 假设球面的地图可以看成平面；9. 假设问题（3）中，参考的调查数据都是真实可靠地；10. 假设周先生直接可以订购到台北的机票。2.2符号说明南京合肥郑州西安太原石家庄济南天津沈阳长春哈尔滨北京呼和浩特银川兰州西宁乌鲁木齐拉萨成都重庆昆明贵阳南宁海口澳门香港广州武汉长沙南昌福州台北杭州上海三、 模型的建立及求解3.1 问题（1）模型的建立及求解3.1.1 模型的建立定义（1）表示由到的最短距离 （2）表示由到的最短距离下面用动态规划的方法计算。最短线路问题的特性：如果最短线路在第k站通过点，则这一线路在由出发到达终点的那一部分线路，对于从点到达终点所有可能选择的不同线路来说，必定也是距离最短

9、的。（反正法）。最短线路问题的这一特性启示我们，从最后一段开始，用从后向前逐步递推的方法，求出各点到的最短线路，最后求得从到的最短线路。地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。图一k=6时：设表示由到的最短距离；表示由到的最短距离取min（，）k=5时（1）从出发，有两种选择，到或，设表示由到的最短距离。表示到的距离，表示从到或的选择，则 = =，最短线路是-（2）从出发也有两种选择，即到或。，的定义与（1）类似，则=最短路线是-（3）从出发，同样有 = ，最短线路是-k=4时：分别以,为出发点计算得，最短线路是-，最短线路是-，最短线路是- k=3时：

10、分别以，为出发点计算得，最短线路是-，最短线路是-，最短线路是- ,最短线路是-k=2时分别以，为出发点计算得，最短线路是-，最短路线是-k=1时出发点只有，计算得，最短路线是-图二现在，我们想从城市到达城市。怎样走才能使得路径最短，最短路径的长度是多少？ 如上图所示，从城市a出发，按照与城市a的路径长度划分阶段。阶段0包含的出发城市有阶段1所含的城市有阶段2包含的出发城市有阶段3包含的出发城市有阶段4包含城市这种划分可以明确每个城市的次序，因为阶段的划分具有如下性质阶段i的取值只与阶段i+1有关，阶段i+1的取值只对阶段i的取值产生影响：每个阶段的顺序是确定的，不可以调换任两个阶段的顺序；我

11、们从阶段4的城市出发，按照阶段的顺序倒推至阶段0的城市。定义（1）表示由到的最短距离 （2）表示由到的最短距离分别以,为出发点计算得，最短线路是-，最短线路是-，最短线路是- 分别以，为出发点计算得，最短线路是-，最短线路是-，最短线路是- ,最短线路是-k=2时分别以，为出发点计算得，最短线路是-，最短路线是-k=1时出发点只有，计算得，最短路线是-3.1.2 模型的求解地区名称经度纬度北京e11628n3954上海e12129n3114天津e11711n3909重庆e10632n2932哈尔滨e12641n4545长春e12519n4352沈阳e12324n4150呼和浩特e11148n4

12、049石家庄e11428n3802太原e11234n3752济南e117n3638郑州e11342n3448西安e10854n3416兰州e10349n3603银川e1061n3820西宁e10145n3638乌鲁木齐e 8736n4348合肥e11718n3151南京e11850n3202杭州e12009n3014长沙e113n2811南昌e11552n2841武汉e11421n3037成都e10405n3039贵阳e10642n2635福州e11918n2605广州e11315n2308海口e11020n2002南宁e10820n2248昆明e10241n25拉萨e 9110n2940香港

13、e11410n2218澳门e11330n2212台北e12131n2503表一 （1-1）实际距离km（实际距离） （1-2）经过计算的部分距离城市南京上海杭州合肥拉萨乌鲁木齐纬度118.81121.47120.16117.2391.1187.62经度32.0631.2430.2831.8229.6643.83距离南京上海杭州合肥拉萨乌鲁木齐南京0267.79235.95151.462650.333008.07上海267.790164.51406.992906.583266.77杭州235.95164.510327.452791.623228.1合肥151.46406.99327.450250

14、1.962901.82拉萨2650.332906.582791.622501.9601605.68乌鲁木齐3008.073266.773228.12901.821605.680将数据代入模型最短距离为15917km不难得到如图所示的利用excel，建立适当坐标系生成折线图，如图所示 图33.2 问题（2）与（3）模型的建立及求解3.2.1 模型的建立在模型（1）的基础上，本文主要通过层次分析法对第二个问题进行建模分析。目标层就是选择怎么样的交通方式方案层是有什么样交通方式准则层就是价格、时间、距离、方式。下面就问题（2）进行讨论。选择方式方式价格距离时间存在的交通方式图四设某层有n个因素，要比

15、较它们对上一层某一准则（或目标）的影响程度，确定在该层中相对于某一准则所占的比重。（即把n个因素对上层某一目标的影响程度排序）用表示第个因素相对于第个因素的比较结果，则a则称为成对比较矩阵：交通方式的选择价格p（x）0.4时间t(x)0.3距离l(x)0.2方式m (x)0.1交通情况t or f 表二3.2.2 模型的求解1、对最优解路径的求解（对问题（1）的改进）（1）对于每个决策因素的重要性程度周游先生赋以下值：（3）假设周游先生对于不同里程区间的三种交通方式的满意度赋以下值：963893769（4）假设周游先生对于不同出发时间区间的满意度赋以下值：1234567823567973第二问

16、的路线：南京上海杭州台北福州南昌长沙武汉广州香港澳门海口南宁贵阳昆明重庆成都拉萨西宁兰州乌鲁木齐兰州银川呼和浩特北京哈尔滨长春沈阳天津济南石家庄太原西安郑州合肥南京全程共34段路程，除去5段乘坐飞机的还剩29段。而在这29段中有很多两城市之间的距离很短根本用不上坐飞机。（8）利用matlab计算每段旅途的每个车次或航班的满意度，再取其中满意度最高的车次或航班作为最佳互联网订票标准，以此类推，得出全国路线的最佳订票方案。车次 始发站 车辆类型 发时 到时 历时 硬卧中t224/t221拉萨空调特快13:1020:3931:29:00486/502/519t24/t21拉萨空调特快13:1020:

17、3931:29:00486/502/519k542/k543重庆北空调快速7:5516:2232:27:00437/452/467k452/k453成都空调快速8:5318:5434:01:00437/452/467k594/k595杭州空调快速12:2918:3630:07:00437/452/467k1208/k1205上海快速1:4014:2336:43:00269/279/289t52/t53上海空调特快14:1516:0125:46:00437/452/4671354/1351连云港东空调普快4:3217:0036:28:00407/422/4371085济南普快2:439:1030

18、:27:00249/259/2691043西安普快23:397:0031:21:00249/259/269t192/t193汉口空调特快8:1610:2326:07:00437/452/467t197郑州空调特快5:217:2526:04:00437/452/4671045商丘普快6:0313:5231:49:00249/259/269t69北京西空调特快8:4110:4226:01:00437/452/467其中出发时间与到达时间按转换，其中为计算采用格式，为24小时制时间。在matlab命令窗口输入运行程序得到最佳车次或航班，按此类推，得到整个路线的车次或航班。结果如下表（详细参考请见附录

19、-最佳订票方案）：路线哈尔滨长春：长春沈阳：沈阳天津：天津北京：北京呼和浩特：呼和浩特太原车次或航班d26d22d178t5681/t5684jd52898l9946/hu9946满意度（h）8.57588.39397.12128.54557.57586.7576路线太原石家庄：石家庄济南：济南郑州：郑州西安：西安银川：银川兰州：车次或航班d166或d167mu5154或mu5529d157g2007hu7848mu2301或mu5154满意度（h）8.57584.06066.48487.51528.45456.5455路线兰州西宁：西宁乌鲁木齐：乌鲁木齐拉萨：拉萨昆明：昆明成都：成都重庆：车

20、次或航班t213cz3629hu7893或ca4420mu58383u8819或mu5849d5110或d5112满意度（h）8.36366.66676.66675.78797.09098.0909路线重庆贵阳：贵阳南宁：南宁海口：海口广州：广州澳门：澳门香港：车次或航班mu2603hu7520gs7520或hu7520zh9612大巴轮船满意度（h）7.36367.90917.93947.63647.6977.5455路线香港台北：台北福州:福州南昌：南昌长沙：长沙武汉：武汉合肥：车次或航班ci914ka481或ka662cz8150或3u8960t146或t147d150d5477或d30

21、51或d3054满意度（h）6.63645.45457.84857.57587.15158.0909路线合肥南京：南京杭州：杭州上海：上海哈尔滨： 车次或航班d5481或d5484d5589d56769c8869满意度（h）8.33337.39398.63646.9394注：其中广州到澳门与澳门到香港因在网上无法进行动车、特快卧铺、航班的订票，所以本文分别用大巴与轮船作为交通工具，计算满意度时均采用的标准。由附录-最佳订票方案中数据计算得：总行程时间，因为每个城市停留3天（出去哈尔滨）总的停留天数为，完成旅游计划总用时，即5月1日从哈尔滨出发，环游中国后8月11日返回哈尔滨；购票总价；总行程；

22、平均满意度。如果对以上结果又不满意之处，可通过调整因素重要性程度与满意度来重新决定订票方案。最佳订票方案：经过模型（2）的计算和查询火车和飞机航班线路和票价，得到最佳的订票方案（起点南京）为：路径车次或航班出发时间到达时间旅途用时（min)里程(km)票价（元）满意度哈尔滨长春：d2615:3817:24106246918.5758长春沈阳：d2215:1817:331353001118.3939沈阳天津：d17813:1417:442706893517.1212天津北京：t5681/t568413:5615:1882127978.5455北京呼和浩特：jd528918:4519:456041

23、6.063627.5758呼和浩特太原：8l994620:1521:1055336.724046.7576hu994620:1521:1055336.724306.7576太原石家庄：d166/d16717:1918:3374225848.5758石家庄济南：mu5154/mu55297:5518:45650270.4813214.0606济南郑州：d15718:2023:303106682486.4848郑州西安：g200715:0017:261465053907.5152西安银川：hu784816:4517:5065525.172138.4545银川兰州：mu2301/mu515413:3

24、518:20285351.45306.5455兰州西宁：t21317:4420:03139216508.3636西宁乌鲁木齐：cz362916:1518:351401437.117436.6667乌鲁木齐拉萨：hu7893/ca44208:5016:404701602.5720556.6667拉萨昆明：mu583811:2515:002151264.3417935.7879昆明成都：3u881916:3017:4070638.177107.0909mu584916:2517:3570638.177187.0909成都重庆：d511013:2415:251213151178.0909d51121

25、6:5618:551193151178.0909重庆贵阳：mu260318:3019:3060334.624407.3636贵阳南宁：hu752016:1017:0555448.953787.9091南宁海口：gs752017:5518:4045374.292847.9394hu752017:5518:4045374.293017.9394海口广州：zh961216:4017:4060459.945007.6364广州澳门：大巴10:0012:00120110.92807.697澳门香港：轮船9:0011:0012061.77607.5455香港台北：ci91415:3517:15100817

26、.728606.6364台北福州:ka481/ka66214:5019:00250248.840905.4545福州南昌：cz815018:3019:4070443.021607.84853u896013:0014:1070443.022367.8485南昌长沙：t146/t14713:2018:172974191187.5758长沙武汉：d1507:2610:351893621357.1515武汉合肥：d54777:588:5658156808.0909d3051/d305412:20130909合肥南京：d5481/d548414:1715:26691561148

27、.3333南京杭州：d558912:2716:412545041877.3939杭州上海：d567615:5517:2792173648.6364上海哈尔滨：9c886916:4519:301651326.266206.9394四、模型的误差分析1、本模型利用动态规划计算最短路径时是依据的两两城市之间的最短距离，而实际上两城市之间的行车里程并不是两两城市之间的直接距离。2、实际里程或航程并不是球面直接距离，因此模型（1）得出的总路径长度与模型（2）的出的结果有一定差距。 3、本模型在选取车次时判断标准为人为主观因素，在具有了普遍性的同时也具有了随机性，为减少随机性，可通过多次打分，得出较多个结

28、果，再从中选取最优解。4、在旅途中会遇到很多客观的不定因素，比如天气问题等，会使正常计划受到一定的影响。五、 模型复杂性分析1、模型的复杂性：（1）运用动态分析法解决游遍全国的省会城市、直辖市、香港、澳门、台北这一问题还是比较困难的，数据量很大。本文主要是将数据量降低，将全国各地省会进行区域性划分。然后再运用动态分析解决了模型（1）。模型（1）来计算完成旅游计划的最短行程，相对于传统的动态规划解法，达到了省时、简便的效果，大大降低了计算的复杂性。（2）如何方便的订票，本文充分考虑了地域这个问题。比如说不能坐火车到台湾。并且好多地方时不能直接通火车的。或者时间的问题考虑直接用飞机相对的也是比较舒

29、适的。在模型（1）的基础上，适当的调整。给出了模型（2）、（3）的求解；综合考虑了出行方式，出发时间，到达时间，旅行用时，旅行路程，票价等的重要性给出比较主观的结论（3）建立的模型能与实际紧密联系，结合实际情况对所提出的问题进行求解，使模型更贴近实际，达到了运用数学知识解决实际问题的目的。六、 模型可行性与推广本案例建立的模型解决了旅游出行优化问题，采用了动态分析的方法解决了最短路径问题，运用决策分析方法解决了旅行费用优化问题。因此，本模型还可以运用于很多领域类似的关于路径优化以及经济优化的问题，如:输油管道的铺设问题、邮递员送信问题、交通运输问题、快递的投送等。参考文献1彭红军 张伟 中国矿

30、业大学徐海学院 层次分析法讲义 2 彭红军 张伟中国矿业大学徐海学院 动态分析讲义3 吴文虎 王建德，青少年国际和全国信息学（计算机）奥林匹克竞赛指导组合数学的算法与程序设计，清华大学出版社，1997年版4 薛定宇等. 高等运用数学的matlab求解. 北京：清华大学出版社. 2008.105 王莉，李文权，公共交通系统，东南大学学报，第34卷第2期：第265页，2004年3月。6张兴永 朱开永 数学建模入门 煤炭工业出版社2008.10附录最佳订票方案：路径车次或航班出发时间到达时间旅途用时（min)里程(km)票价（元）满意度哈尔滨长春：d2615:3817:24106246918.575

31、8长春沈阳：d2215:1817:331353001118.3939沈阳天津：d17813:1417:442706893517.1212天津北京：t5681/t568413:5615:1882127978.5455北京呼和浩特：jd528918:4519:4560416.063627.5758呼和浩特太原：8l994620:1521:1055336.724046.7576hu994620:1521:1055336.724306.7576太原石家庄：d166/d16717:1918:3374225848.5758石家庄济南：mu5154/mu55297:5518:45650270.4813214.0606济南郑州：d15718:2023:303106682486.4848郑州西安：g200715:0017:261465053907.5152西安银川：hu784816:4517:5065525.172