文档介绍：,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。我们知道,抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。如有违反竞赛规则的行为,我们将受到严肃处理。我们参赛选择的题号是(从A/B/C/D中选择一项填写):B 我们的参赛报名号为(如果赛区设置报名号的话):所属学校(请填写完整的全名):西南交通大学参赛队员(打印并签名): (打印并签名):徐跃良日期:2007年09月24日赛区评阅编号(由赛区组委会评阅前进行编号):2007高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号(由赛区组委会评阅前进行编号):赛区评阅记录(可供赛区评阅时使用):评阅人评分备注全国统一编号(由赛区组委会送交全国前编号):全国评阅编号(由全国组委会评阅前进行编号):乘公交看奥运摘要为建立公交线路选择问题的自主查询计算机系统,从实际情况出发考虑,本文建立了满足查询者的各种不同需求的线路选择模型与算法。并给出一些结果。问题一为仅考虑公汽线路的情况下给出任意两公汽站点之间线路选择问题的一般数学模型与算法。本文从费用、时间及换乘次数出发,先单独再综合的对三个因素进行了详细讨论。在建模中我们将费用和时间视为有向图边的邻接矩阵权,使原题巧妙的转化为了图论的最短路问题,建立了一个线性规划模型,采用Dijkstra算法对模型进行求解。对于多目标,我们采用将目标转化为约束条件和将目标无量纲化后进行线性加权相结合的办法进行计算,得出最优线路,如S3359→S1828的线路有:1、S3395(L324)S1746(L027)S1784(L167)S1828(时间73,费用3,换乘2);2、S3359(L436)S1784(L167)S1828(时间101,费用3,换乘1);3、S3359(L015)S1327(L296)S992(L475)S1671(L041)S1828(时间72,费用4,换乘3)。并对最优线路给出了详细的评价。问题二,同时考虑地铁和公汽的线路选择问题,我们从时间和费用两方面进行讨论。建模中,我们保留第一问的建模思想,同时考虑了地铁的情况,建立了0—1规划模型。对此模型,我们采用Floyd最短路径算法和Dijkstra算法再结合仿真算法用C语言编程求解。并得到最优线路,如S3359→S1828的线路:S3359---〉L015(上行)---〉S1327---〉L296(环行)---〉S0992---〉L475(上行)---〉S1828,时间:72分钟,费用:4元。问题三,在知道所有站点之间的步行时间的情况下的公交线路选择问题,我们从费用最少、总时间最少和步行时间最少进行讨论。在建模中,我们巧妙的把步行看作一种特殊的不花费用的交通方式,并结合图论知识建立了3个目标的多目标0-1规划模型。最后,我们还给出了求解此模型的思想和算法。在问题一中,构造了有向赋权图,巧妙地将原问题转化为图论的最短路问题是本文的亮点。在问题三中,将步行看作一种特殊的不花费用的交通方式,大大减轻了我们建模难度。另外,本文还采用了多个图论算法,简化了模型求解难度。最后,我们还对本文提出了推广和改进的方案。关键词:0-1规划Dijkstra算法Floyd算法仿真算法多目标规划有向赋权图一、问题提出我国人民翘首企盼的第29届奥运会明年8月将在北京举行,届时有大量观众到现场观看奥运比赛,其中大部分人将会乘坐公共交通工具(简称公交,包括公汽、地铁等)出行。这些年来,城市的公交系统有了很大发展,北京市的公交线路已达800条以上,使得公众的出行更加通畅、便利,但同时也面临多条线路的选择问题。针对市场需求,某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统,其核心是线路选择的模型与算法,应该从实际情况出发考虑,满足查询者的各种不同需求。请你们解决如下问题:1、仅考虑公汽线路,给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据,利用你们的模型与算法,求出以下6对起始站→终到站之间的最佳路线(要有清晰的评价说明)。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路,解决以上问题。3、假设又知道所有站点之