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

《2007高教社杯全国大学生数学建模竞赛B题评阅要点.doc》由会员分享，可在线阅读，更多相关《2007高教社杯全国大学生数学建模竞赛B题评阅要点.doc（3页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2007高教社杯全国大学生数学建模竞赛B题评阅要点说明本要点仅供参考，各赛区评阅组应根据对题目的理解及学生的解答，自主地进行评阅。命题思路 本题根据公交线路查询系统研制的实际需求简化改编而成。问题容易理解，相关参考文献也较多，但涉及到公汽与地铁线路的联系，以及换乘时间等细节的处理，加上需要处理的数据量较大，问题并不十分简单。这是一个多目标优化问题，换乘次数最少、费用最省、时间最短显然是乘客在选择乘车线路时最关心的几个目标，从该问题的实际背景来看，采取加权合成将问题转化为单目标优化问题的解题思路不太合适。比较适当的方法是对每个目标寻求最佳线路，然后让乘客按照自己的需求进行选择。本题1、2问要求在

2、不知道站点地理信息的条件下给出解决线路选择问题的模型与算法，并就题目给定的数据计算得到线路选择结果，此二问主要考核建模及编程能力。第3问加上了步行因素，建模难度更大一些。问题1 不考虑地铁线路时的公交线路选择可能主要有以下几种解法。1、 图论模型，这可能是最常使用的方法，首先要考虑如何根据不同目标建立有向赋权图（如利用不同的矩阵表示），然后再求给定点对之间的最小换乘次数或最短路。求两点间最短路有Dijkstra算法与Floyd算法等，但并不能将这两种算法直接套用于本问题，还需要处理好换乘和换乘时间问题，阅卷时需要重点关注。2、 规划模型，包括0-1规划方法与动态规划方法等。3、数据库模型，利用

3、数据库技术直接对线路及站点数据进行搜索。注（1）本问的关键点是换乘时间的处理及最短时间线路的选择。（2）若算法运算时间比较长，可事先计算出所有最佳线路，将结果存入数据库备查。因此算法的运算时间问题不是本题的考察重点。（3） 对于原始数据中出现的一些异常数据，同学可根据自己的理解作出假设和处理。如：l 对于个别线路相邻站点名相同，可以采取去掉其中1个点或不作处理等方式，一般不会影响实例计算中线路选择的结果。l 对于L406未标明是环行线的问题，无论学生是否将其当作环线处理，一般不会影响到实例的计算结果。l 对于L290标明是环线，但首尾站点分别为1477与1479的问题，可将所有线路中1477与

4、1479统一为1477后计算。同学也可以按照各自认为合理的方式处理，包括不当作环线，实例计算用到的是该线路中部的几个站点，一般不会影响实例计算结果。问题2 考虑地铁线路时的公交线路选择本问可以有多种处理方法，关键是看合理性与可操作性。换乘时间的处理较第一问要复杂，需重点关注。问题3 已知站点间步行时间条件下的公交线路选择 这是比较一般的线路选择问题，更接近实际。由于增加了步行因素，每个站点的可换乘方案大大增加了，于是用图论方法处理的难度也会有很大增加。最常用的目标有：换车次数最少，乘车的总站数最少，步行的总时间最少，总车费最少等等，应该针对不同的情况分别写出模型。实例结果注（1）本计算结果由命

5、题人提供，并不一定完全准确（如最优可能仅为次优），仅供参考。此外，由于假设的不同（如对换乘时间的处理不同），结果也可能会有差异。（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*3 / 3