2007高教社杯全国大学生数学建模竞赛B题评阅要点.docx

2007高教社杯全国高校生数学建模竞赛B题评阅要点说明本要点仅供参考，各赛区评阅组应依据对题目的理解及学生的解答，自主地进展评阅。命题思路  本题依据公交线路查询系统研制的实际需求简化改编而成。问题简洁理解，相关参考文献也较多，但涉及到公汽与地铁线路的联络，以及换乘时间等细微环节的处理，加上须要处理的数据量较大，问题并不非常简洁。这是一个多目的优化问题，换乘次数最少、费用最省、时间最短明显是乘客在选择乘车线路时最关切的几个目的，从该问题的实际背景来看，实行加权合成将问题转化为单目的优化问题的解题思路不太适宜。比拟适当的方法是对每个目的寻求最佳线路，然后让乘客依据自己的需求进展选择。本题1、2问要求在不知道站点地理信息的条件下给出解决线路选择问题的模型与算法，并就题目给定的数据计算得到线路选择结果，此二问主要考核建模及编程实力。第3问加上了步行因素，建模难度更大一些。 问题1  不考虑地铁线路时的公交线路选择可能主要有以下几种解法。1、 图论模型，这可能是最常运用的方法，首先要考虑如何依据不同目的建立有向赋权图（如利用不同的矩阵表示），然后再求给定点对之间的最小换乘次数或最短路。求两点间最短路有Dijkstra算法与Floyd算法等，但并不能将这两种算法干脆套用于本问题，还须要处理好换乘和换乘时间问题，阅卷时须要重点关注。2、 规划模型，包括0-1规划方法与动态规划方法等。3、数据库模型，利用数据库技术干脆对线路及站点数据进展搜寻。 注（1）本问的关键点是换乘时间的处理及最短时间线路的选择。（2）若算法运算时间比拟长，可事先计算出全部最佳线路，将结果存入数据库备查。因此算法的运算时间问题不是本题的考察重点。（3） 对于原始数据中出现的一些异样数据，同学可依据自己的理解作出假设和处理。如：l        对于个别线路相邻站点名一样，可以实行去掉其中1个点或不作处理等方式，一般不会影响实例计算中线路选择的结果。l        对于L406未标明是环行线的问题，无论学生是否将其当作环线处理，一般不会影响到实例的计算结果。l        对于L290标明是环线，但首尾站点分别为1477与1479的问题，可将全部线路中1477与1479统一为1477后计算。同学也可以依据各自认为合理的方式处理，包括不当作环线，实例计算用到的是该线路中部的几个站点，一般不会影响实例计算结果。 问题2  考虑地铁线路时的公交线路选择本问可以有多种处理方法，关键是看合理性与可操作性。换乘时间的处理较第一问要困难，需重点关注。 问题3  已知站点间步行时间条件下的公交线路选择    这是比拟一般的线路选择问题，更接近实际。由于增加了步行因素，每个站点的可换乘方案大大增加了，于是用图论方法处理的难度也会有很大增加。最常用的目的有：换车次数最少，乘车的总站数最少，步行的总时间最少，总车费最少等等，应当针对不同的状况分别写出模型。 实例结果注（1）本计算结果由命题人供应，并不肯定完全精确（如最优可能仅为次优），仅供参考。此外，由于假设的不同（如对换乘时间的处理不同），结果也可能会有差异。（2）下表中每行第1目的为最优结果（带 * 号者），其余两个目的在第1目的最优条件下为最优或次优结果。（表中“时间”包括起始站点处的3分钟等车时间。） 仅考虑公汽同时考虑公汽与地铁点对第1目的换乘次数时间（分）费用（元）换乘次数时间（分）费用（元）S3359S1828换乘次数1*10431*1043时间267*3267*3费用2673*2673*S1557S0481换乘次数2*10932*1093时间3102*43102*4费用21093*21093*S0971S0485换乘次数1*13131*1313时间2106*34105.5*7费用21063*21063*S0008S0073换乘次数1*8621*862时间462*5356.5*5费用1862*1862*S0148S0485换乘次数2*10932*10932*90.55时间3105*4389.5*6费用21093*21093*S0087S3676换乘次数1*6820*303时间249*3030*3费用1682*1682*