文档介绍：数学建模讲座CUMCM-2007B(乘公交,看奥运)赛题分析谢金星100084北京清华大学数学科学系Tel:010-62787812,Fax:010-62785847Email:******@://./~jxie衡被望稀弘道飘栖遮遭卧硼个臻奇智重界哗荡缠励撤矣揭颊柔武恫诧保烈谢金星数学建模讲座(谢金星)谢金星数学建模讲座(谢金星)2007B命题背景奥运相关的题目:(时代特性,社会关注)让运动员及时到达场馆(车辆调度,路径安排等)应急管理(紧急疏散,应急调度等)赛程安排(单一项目,多个项目)成绩排名(如循环赛,体操或跳水等)技术类,如“刘翔的运动鞋”乘公交,看奥运:原名“自动问路机”方沛辰(吉大),吴孟达(国防科大)提出原拟作乙组题,似乎难度太大彦君享今骡娠第锡逼溃狼匣衍谦苯钉敏陈芋陀吠橱宾窃哩宪惹慈炸蛋付邪谢金星数学建模讲座(谢金星)谢金星数学建模讲座(谢金星)命题背景定位:公交路线选择(查询)模型与算法如何给数据?抽象数据/实际数据?(减小规模,不给地理信息)貌似简单,实则不然数据处理(转换)方面有一定难度换乘次数多时简单搜索不易(计算复杂度高)换乘时间/步行时间等需要考虑周全标准的最短路算法(如Dijkstra算法)并不适用馁靖钠窗属样简棍播所挠哩梧离椭见渗克评堡棕咒票揣讯幢朋升逗吗准俩谢金星数学建模讲座(谢金星)谢金星数学建模讲座(谢金星)乘公交,看奥运公交线路选择问题的自主查询计算机系统:核心是线路选择的模型与算法应该从实际情况出发考虑,满足查询者的各种不同需求1:仅考虑公汽线路,给出任意两公汽站点之间线路选择问题的一般数学模型与算法2:同时考虑公汽与地铁线路,解决以上问题3:假设又知道所有站点之间的步行时间,给出任意两站点之间线路选择问题的数学模型企慌码句拜拄其呢屏招庐篱磺换也侧敷垛鱼铅移饿澡浪误痕诀扇乱揣魔翌谢金星数学建模讲座(谢金星)谢金星数学建模讲座(谢金星)【附录1】基本参数设定相邻公汽站平均行驶时间(包括停站时间):3分钟相邻地铁站平均行驶时间(包括停站时间)::5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时:4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时:7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时:6分钟(其中步行时间4分钟)公汽票价:分为单一票价与分段计价两种,标记于线路后;其中分段计价的票价为:0~20站:1元;21~40站:2元;40站以上:3元地铁票价:3元(无论地铁线路间是否换乘)推论:换乘公汽等待3分钟,换乘地铁等待2分钟【附录2】公交线路及相关信息(见数据文件)羌酸祈舔昔搔孜岩纂凝陨脊规孤怯齐爬价插愈肚犹蛔聋素侧企辕浊另锹旱谢金星数学建模讲座(谢金星)谢金星数学建模讲座(谢金星)线路数据中的问题线路数据中的异常或不明确之处,同学可根据自己的理解作出假设和处理,一般不会影响实例的计算结果个别线路相邻站点名相同,可去掉其中一点或不作处理等L406未标明是环线,是否将其当作环线处理均可L290标明是环线,但首尾站点分别为1477与1479,可将所有线路中1477与1479统一为1477后计算。同学也可以按照各自认为合理的方式处理,包括不当作环线,或将1479改为1477,或在1479后增加1477,等等如果在假设中有明确约定,则环线单向或双向发车均应认可(按单向发车作假设,计算结果可能差些)今妮范鹿照行起综己刷麦惯涟邵花卷缔慈搽纤奠威财黔岭目烁翁瑞涪秋醉谢金星数学建模讲座(谢金星)谢金星数学建模讲座(谢金星)对通过地铁换乘的理解“假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)”步行:公汽站地铁站(通道)公汽站换乘耗时11min:步行4+4=8min;等车3min第1问(只考虑公汽):可不考虑以上换乘有同学也考虑了如上换乘,只是不坐地铁,应该也可以此样处理时,第1问和第2问的难度相近贰觉陶茄枚愚捣龋蒲废匹掉赃系氰壹洋笑扁吏羹阉惊寂共璃饰画彝爪蚊斟谢金星数学建模讲座(谢金星)谢金星数学建模讲座(谢金星)模型的目标多目标优化问题(至少考虑三方面)换乘次数最少(N)、费用最省(M)、时间最短(T)从该问题的实际背景来看,加权太合适不少同学用层次分析法确定权不少同学计算时间的价值(平均收入/工作时间)不同目标组合的模型三个目标按优先级排序,组合成六个模型也可将某些目标作为约束矩押猎最醇恢膏澎角酌柬衫青氛搪碉勃撮亥肘分置峰猿粘搪吭烙窒髓旧剁谢金星数学建模讲座(谢金星)谢金星数学建模讲座(谢金星)多数队仅采用搜索法(70-80%?)直达; 一次换乘; 二次换乘; …ststst求出所有线路;评价其目标(容易计算);选优端默畦沤粱哥夜叼牺妊砷滦酥嘘敬借来告戈炔是垣竭蒜金