数学模型典型例题+乘公交,看奥运.docVIP

乘公交，看奥运 摘要 公交在奥运会期间将会扮演一个举足轻重的角色，本文就“乘公交，看奥运”如何选择线路的问题建立了数学模型，我们从实际情况出发对不同条件下最优公交路线选择进行分析判断。 在问题一中，我们利用最优化原理，建立出一个动态规划模型，并运用数据结构的思想给出了基于广度优先的公交换乘有哪些信誉好的足球投注网站算法；然后，在模型和算法的基础上，利用C++语言进行编程，实现了系统查询功能；最后，根据模型和算法，运用C++程序，得出问题中给出的6对起始站至终到站之间的最佳路线（见正文），例如S3359S1828的乘车路线如下： 从L436下行线上的S3359站点上车，到S1784站点下车，然后转乘L167下行线到S1828站点下车。 总花费：3元 用时：101分钟 在处理问题二时，我们在问题一的基础上，进一步建立了MC-最优问题模型，并运用MC-最优问题的Kruskal算法，分析得出在同时考虑公汽和地铁线路时的最优路线。我们发现，在求得的最优路径中，“S0008→S0073、S0971→S0485、S3359→S1828”的最优路径与问题一相比并非最优，因此，这三对路径的最优路径与问题一相同（结果见正文）；对于路径S0087→S3676，问题二中可乘地铁直达（即D27-D36），花费为3元，用时25分钟；而在问题一中乘坐公汽时，花费2元，但用时65分钟。根据实际情况权衡这两个结果，应选择乘地铁，路径为：D27-D36。（另外两对路线结果见正文） 对于问题三的处理，我们则通过建立公交网络初始时间矩阵，列出任意两点之间线路所花费时间的方程，根据交通路线规则选择合适的时间方程并求出在考虑步行的情况下任意两站点之间的线路选择。 本文的特点是在建立模型和算法的基础上，利用C++语言进行编程，使其具备系统查询功能，克服了人工查询数据的繁杂过程，使得到的结果更为准确，同时，此程序可以进行推广使用，为解决日常生活中最优路径的选择问题提供了方法，给人们的出行带来方便。 关键词：动态规划 MC-最优问题模型 线路选择 最优线路 数据结构 1．问题的提出 第29届奥运会将于明年8月在北京举行，届时将有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统发展很快，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，研制开发一个解决公交线路选择问题的自主查询计算机系统已经迫在眉睫。 在设计这样一个系统时，应该从实际情况出发，满足查询者的各种不同需求，其核心是线路选择的模型与算法。 解决的问题是： 1．仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 2．同时考虑公汽与地铁线路，解决以上问题。 3．假设又知道所有站点之间的步行时间，请给出任意两站点之间线路选择问题的数学模型。 2．模型的假设和符号说明 2.1模型的假设 (1)假设模型的优先策略不受其他因素的影响，仅从绝大部分人的思维出发，以有无直达车或换车最少的路线及花钱最少的路线考虑。（换乘次数最少优先策略） (2)设定换乘次数的上界N，然后可在不大于N次换乘的某次循环中找到可行路径 (3)假设给出了各站点的坐标 2.2符号说明 公交站点个数； 任意一个公交站点； 任意一个公交站点； 任意两个公交站点之间的距离； 任意两个公交站点的终点； 效益； 站点集； 到的实际距离； 边权； 任意两站点形成的线段； 无向网络图的所有生成树之集； 边权之和； 车线条数； 车线的车辆全线行驶时间； 线路的全线长度； 到的步行距离； 平均步行速度； 在允许换乘改变站点时设定的最大步行距离； 3．问题的分析 根据人们的出行习惯，人们在选择公交线路时考虑的因素很多，如乘车是否最方便（换乘次数最少，行走距离最短），乘车费用是否便宜，乘车时间是否最少等。因为乘客的目的是在最短时间内以最小代价到达目的地。由于多数城市已采用无人售票及单一票制，所以转乘次数最少则代价也最小。 (1)在选择从站到站的行车线路时，首先会先看经过站的车是否有直接到站的，如果有，马上会选择直达车，如果存在不止一条的直达线路，再考虑距离、时间、