全国大学生数学建模一等奖获奖论文要点.doc

2007 高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。我们知道,抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料(包括网上查到的资料) ,必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。如有违反竞赛规则的行为,我们将受到严肃处理。我们参赛选择的题号是(从 A/B/C/D 中选择一项填写):B 我们的电子文件名: B0302 所属学校(请填写完整的全名):广西师范学院参赛队员(打印并签名): (打印并签名):韦程东日期:2007 年9月24日赛区评阅编号(由赛区组委会评阅前进行编号): 2007 高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号(由赛区组委会评阅前进行编号): 赛区评阅记录(可供赛区评阅时使用): 评阅人评分备注全国统一编号(由赛区组委会送交全国前编号): 全国评阅编号(由全国组委会评阅前进行编号): 乘公交,看奥运摘要我们基于最小换乘次数算法,设计了公交查询系统,能够分别从时间和花费出发考虑,选择最优路径,以满足查询者的各种不同需求。问题一:采用最小换乘次数算法,求出任意两站的最小换乘次数,在次数一定的情况下,分别选取花费最少和时间最少作为优化目标,建立两种模型:最少时间模型: ????????? 31 315 )))1(((3),( min i ii iiiixqxnxBAf ; 最少花费模型: ))1((),( min ''' 31 iiiyxxBAg????;利用两种模型求出 6组数局的最佳路线如下(两种模型求出的最优结果是一样的); 起始站→终点站乘车路线时间费用 S3359 → S1828 L436 下行( S1784 )→ L167 下行 101 3 S1557 → S0481 L084 下行( S1919 )→ L189 下行( S3186 ) → L460 下行……(有 2条最优路线) 106 3 S0485 → S0971 L013 下行( S0992 )→ L417 下行 128 3 S0008 → S0073 L159 下行( S0491 )→ L058 下行……(有 5条最优路线) 832 S0148 → S0485 L308 上行( S0036 )→ L156 上行( S3351 ) → L417 下行 101 3 S0087 → S3676 L454 上行( S3496 )→ L209 下行 652 问题二:把两条地铁的任意站点的附近公交站点以相同的序号表示,因此将地铁的线路转化成公交的问题,改进问题一中的模型求出此问题的最少时间模型????????????))) 5 )))1(((3((),( min 31 31 31ii ii iiiiixqxnxyBAf????????????)4 ))) )1((( )(1(( 31 31 ' 31ii ii ii iiixqxnxy??? 31 i)z1(7 i iy +?? 31 iz6 i iy 得到 6组数据的最优路线如下: 起始站→终点站乘车路线所需费用 S3359 → S1828 L436 下行( S1784 )→ L167 下行 101 分3元 S1557 → S0481 L363 下行( S1919 )→ L189 下行( S3186 ) → L460 下行……(有两条) 106 分3元 S0485 → S0971 L013 下行( S0992 )→ L417 下行 128 分 3元 S0008 → S0073 L159 下行( S0491 )→ L058 下行……(有 5条) 83分 2元 S0148 → S0485 L308 上行( S0036 )→ L156 上行( S3351 ) → L417 下行 101 分 3元 S0087 → S3676 T2 ( D27 → D36 )33分3元问题三:考虑到会存在紧邻站点与终点站的直达线路,所以我们对问题一的最小换乘算法进行了改进。关键词:最小换乘次数, 算法,紧邻点,数据库,路线集 1 问题重述第 29 届奥运会明年 8 月将在北京举行,届时有大量观众到现场观看奥运比赛,其中大部分人将会乘坐公共交通工具(简称公交,包括公汽、地铁等)出行。这些年来,城市的公交系统有了很大发展,北京市的公交线路已达 800 条以上, 使得公众的出行更加通畅、便利,但同时也面临多条线路的选择问题。针对市场需求,某公司准备研制开发一个解决公交线路选择问题的自主