数学建模--伦敦奥运会公交网络系统设置问题论文.doc

呼伦贝尔学院Hulunbeier University数学建模竞赛论文论文题目:伦敦奥运会公交网络系统设置问题 姓名1： 苑伟 学号：2011121138 专业：计算机科学与技术姓名2： 刘海平 学号：2011121116 专业：计算机科学与技术姓名3： 冯曦 学号：2011121102专业：计算机科学与技术2012 年 5月 2日2012年呼伦贝尔学院数学建模竞赛承 诺 书我们仔细阅读了呼伦贝尔学院数学建模的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B中选择一项填写）： A 所属学院（请填写完整的全名）：计算机科学与技术学院 参赛队员 (打印并签名) ：1. 苑伟 2. 刘海平 3. 冯曦 日期： 年 月 日2012年呼伦贝尔学院数学建模竞赛编 号 专 用 页评阅编号（由组委会评阅前进行编号）：赛区初评记录（可供评阅时使用）：评阅人总评分评分备注复评结果：伦敦奥运会公交网络系统设置问题摘要：繁忙的伦敦公共交通如今已接近饱和，奥运会时乘客流量激增，容量不够的问题就摆在面前。为了使奥运会能够顺利的进行，提前将交通问题解决好是尤为重要的。本论文将伦敦奥运会的公交网络数学化进行细致分析，以为了更好的将伦敦奥运会公交交通网络设计和维护做出初步计划。 本文中我们主要选取了伦敦公交交通网络的各个路段的最大运力来分析现在的伦敦公交交通网络的实际最大承受力，忽略了时间对交通的影响，即忽略人流高峰期和低迷期在此段时间的出现，全部运算均使用平均值。其他忽略条件会在模型假设中详细提出。 此次建模我们主要用到了运筹学中的图与网络模型相关的知识使问题变得简单，此次运算中，我们运用最大流的标号运算的方法来列出公交线路的种种可能，并运用了标号算法来估计了各个线路运送的人数，以确定本公交交通网络的最大运力。运用了lingo软件对本次数学建模的第一问进行了模型运算，充分利用了运筹学方面的知识解决和完善本次建模。对于本次建模的第二问，对于本次建模的第二问，使用线性规划的方法来确定使用有限的资金来建立一个可以最大的增加公交网运力的方法，通过lingo运行结果分析，得到答案。最后，考虑了各种人流量的影响问题与公交网络运力的关系，建立更符合实际的层次分析模型，是模型的求解更加精确。 关键词：图与网络模型、最大流的标号算法、线性规划、LINGO（一） 问题的重述：繁忙的伦敦公共交通如今已接近饱和，奥运会时乘客流量激增，容量不够的问题就摆在面前。根据已有数据，运用数学建模的方法 ，对伦敦奥运会参赛运动员的生活区、购物区及七个比赛主场馆的公交网络系统（分布如下图，连线为公交线路，每条连线上所标的数字为该线路的最大运力为千人/小时，其中S为生活区，G为购物区，、为七个比赛主场馆。）进行分析，解决其中从生活区S，到购物区G单位时间内最大人流量是多少？并画出人流分布图。以及用有限的资金去改造公交网络中的某一段线路，使总公交网络最大运力得到有效地提高。（二） 模型的假设：1. 假设奥运会期间观看比赛全部流入的观众等于全部流出的观众。2. 假定全部流入一个比赛场所的观众等于全部流出这个比赛场所的观众，忽略观看比赛未知部分的具体观众人数，试建立数学模型。3. 假定人与人之间是相互独立的，互不影响。4. 假定每一个观众选定公交路段是随机的且概率相同。5. 假设观众只从S区到G区，无其他地区的游客和观众介入到本公交交通网络中。6. 假设公交车不只是一辆。7. 假定改造每段道路的费用相同。（三） 问题的分析：对于奥运会的进行，做好观众的人流量控制以及疏散显得尤为重要，于奥运会人流量问题，我们打算就以下几方面进行分析：1进行问题分析以及资料查询，将于本问题有关的次要因素在问题假设过程中设为定值或可忽略因素。2运用运筹学中的图与网络模型以及线性规划方面的知识进行对本问题的进一步分析。3网上搜集相关和相类似的问题进行学习以及应用。4利用数学软件进行结果运算与验证，使建模结果更接近实际情况5为了方便说明我们用人流量来表示公交车的运力千人/每小时（四） 符号的设定：符号名称符号意义生活区（发点）购物区（收点）比赛主场馆（VS发点与VG收点间的中间点）两主场馆之间道路的实际人流量（可行流）俩个相邻的主场馆该公交交通网络（有向网络图）两主场馆间最大人流量（容量函数）其中某一段公交路线（弧的集合）到购物区G单位时间内最大人流量（净流出量）从生活区S到购物区G的某一条公交路的最大人流量改造某一段公交路线后增加的人流量（五） 模型建立与求解1.模型分析该模型中我们先不考虑不同时间对人流量的影响情况，只考虑单位时间内人流量不变。由于人流量是通过各个路段人流量的限定而决定的，所以用某些路段的人流量限定为研究对象比较方便，下面提到的人流量均仅指其中的各个路段人流量。即先预设各个路段的人流量，然后根据预设列出方程式，即可计算出各个路段的人流量，并画出人流分布图，同时可算出从生活区S到购物区G单位时间内最大人流量是多少。我们算出最人大流以及对道路的分析，人们的心理因素走最短的路或是走最繁华的街道，在许多实际问题中，人流量及关键道路很重要。可知改造关键道路等价于某段路最大人流量得到提高时，某路段实际人流量得到提高，最后最大的运力提高。最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点，解决这个问题的方法较之线性规划的一般方法要方便、直观得多。2.模型的建立设fij表示两主场馆之间道路的实际人流量（弧上的流量），则根据题意（如图），建立如下数学模型为：V5V1VGV6V4V2VS 5 7 3 4 5 7V7V3S 5 3 3 7 G6 5 4 5 6 4 a.用 表示各路段实际人流量, 由实际问题可知模型构成网络，通过上述数学模型，以及最大流问题的数学描述，可知最大人流问题就是在容量网络中，求一个实际人流量f=，使其流量V(f)达到最大: maxZ=V(f) 满足式中v(f)为该公交道路的实际人流量，即发点S的净输入该公交网络的人流量，或收点G的净输出该公交网络的人流量。对于该公交网络的人流量，实际人流量总是存在的。b.可知最小费用流问题可以用如下的线性规划建立数学模型：我们不考虑每条路的不同费用，使其为常量，由上述模型可得当（某段路最大人流量）得到提高时（某路实际人流量）得到提高，这时从生活区S到购物区G单位时间内最大人流量得到最大的提高。3 模型的求解 a.通过以上分析以及模型的建立再结合网络图我们采用了最大流的一种算法标号（Ford Fulkerson算法）使问题更容易解决。（1）改进公交交通网络上某一公交路段的最大人流量（弧的容量）网络图上表示 对每条公交路段弧（，fij）的最大人流量（容量）用一对数(,0)标在弧上，靠近点，0靠近点 ，表示从到容许通过的最大人流量(容量)为 ，而从到容许通过的最大人流量(容量)为0，这样可以省去弧的方向了。 V1 5 0 V5 0 0 4 0 7 7 3 0 5 0VS 5 0 V2 3 0 V4 3 0 V6 7 0 VG 6 0 0 0 0 0 5 4 5 6 V3 4 0 V7（2）求最大人流第一次迭代:A找出一条从生活区S到购物区G最少路段的路程（从发点到收点包含弧数最少的路）VSV3V7VG在这条路上的每一条路段顺流方向的人流量都大于0，表示还没有求得最大人流量。B找出这条路上各条路段的最小的顺流的人流量，通过这条路增加公交网络的人流量。 Pf =4C在这条路上，减少每一条路段的顺流人流量Pf ，同时增加这些路段的逆流人流量Pf如下图： V1 5 0 V5 0 0 4 0 7 7 3 0 5 0VS 5 0 V2 3 0 V4 3 0 V6 7 0 VG4 2 0 0 0 4 4 5 4 5 2 V3 0 4 V7第二次迭代:A 找出一条从生活区S到购物区G最少路段的路程（从发点到收点包含弧数最少的路）在这条路上的每一条路段顺流方向的人流量都大于0VSV1V5VGB 找出这条路上各条路段的最小的顺流的人流量，通过这条路增加公交网络的人流量。 Pf =5C 在这条路上，减少每一条路段的顺流人流量Pf ，同时增加这些路段的逆流人流量Pf如下图： V1 0 5 V5 5 0 4 0 2 2 3 0 5 5VS 5 0 V2 3 0 V4 3 0 V6 7 0 VG9 2 0 0 0 4 4 5 4 5 2 V3 0 4 V7第三次迭代:A 找出一条从生活区S到购物区G最少路段的路程（从发点到收点包含弧数最少的路）在这条路上的每一条路段顺流方向的人流量都大于0 VSV2V4V6VGB 找出这条路上各条路段的最小的顺流的人流量，通过这条路增加公交网络的人流量。 Pf =3C 在这条路上，减少每一条路段的顺流人流量Pf ，同时增加这些路段的逆流人流量Pf如下图： V1 0 5 V5 5 0 4 0 2 2 3 0 5 5VS 2 3 V2 0 3 V4 0 3 V6 4 3 VG12 2 0 0 0 4 4 5 4 5 2 V3 0 4 V7 第四次迭代:A 找出一条从生活区S到购物区G最少路段的路程（从发点到收点包含弧数最少的路）在这条路上的每一条路段顺流方向的人流量都大于0 VSV3V4V5VGB找出这条路上各条路段的最小的顺流的人流量，通过这条路增加公交网络的人流量。 Pf =2C在这条路上，减少每一条路段的顺流人流量Pf ，同时增加这些路段的逆流人流量Pf如下图： V1 0 5 V5 5 0 4 2 0 2 3 0 3 7VS 2 3 V2 0 3 V4 0 3 V6 4 3 VG14 0 2 0 0 4 6 3 4 5 2 V3 0 4 V7通过四次迭代后已经找不到从生活区S，到购物区G一条路上的每一条顺流容量都大于0。运算停止。最大人流量为14，因此可知从生活区S，到购物区G单位时间内最大人流量是14000人/小时 画出类似人流分布图如下：第一种： 5千人 5千人 2千人 7千人 S 3千人 3千人 3千人 3千人 G 2千人 6千人 4千人 4千人 第二种： 5千人 6千人 1千人 2千人 7千人 S 3千人 3千人 3千人 3千人 G4千人 5千人 4千人 第三种： 5千人 7千人 2千人 2千人 7千人 S 3千人 3千人 3千人 3千人 G 4千人 4千人 4千人 第四种： 5千人 5千人 2千人 2千人 7千人 2千人 S 5千人 3千人 3千人 3千人 G 4千人 4千人 4千人 第五种： 5千人 5千人 1千人 2千人 7千人 1千人 S 4千人 3千人 3千人 3千人 G 1千人 5千人 4千人 4千人 第六种： 5千人 6千人 2千人 2千人 7千人 1千人 S 4千人 3千人 3千人 3千人 G 4千人 4千人 4千人 b.为了进一步解决下一个问题同时验证上一步我们所得到的结果的真确性，我们使用上述建立的线性规划模型最大流的数学规划表达式，编写如下LINGO 程序：得到运行结果如下：Global optimal solution found. Objective value: 14.00000 Total solver iterations: 9 （其他数据见附录表） 通过完整运行结果数据分析以及我们要解决的用有限的资金去改造公交网络中的某一段线路，使总公交网络最大运力得到有效地提高的具体要求，与上述b.中数学模型结合，提炼出如下关键数据：Objective value: 14.00000 Total solver iterations: 9 F( 3, 7) 4.000000 -1.000000F( 4, 6) 3.000000 -1.000000F( 5, G) 7.000000 -1.000000由上可知需要改造的几个主场馆间的路段有： 改造 中的某一路段使其的最大人流量（ ）得到提高，当提高时数据返回上述b.中的数学模型可得最大人流量可达16；提高时数据返回上述b.中的数学模型可得最大人流量可达18；提高时数据返回上述b.中的数学模型可得最大人流量可达17.由上述最大人流量的计算及人流量分布图可以看出，如果把路段的公交路线方向改变就可以提高整个公交网络的最大运力可达18千人/小时。因此可以看出如果关键时刻可以改变反向以解决一些问题，在此我们不涉及该公交线路改变如下是通过上述计算得到的 路段最大人流量增加对整公交网络最大人流量的提高图通过上述分析如果有一笔追加资金可用于改造公交网络中的某一段线路，我们认为应将这笔资金投向如图线路的改造，才提高整个公交网络的最大运力（六）模型检验及误差分析 通过上述线性规划以及编写LINGO程序所得到的数据的验证，我们可以得到改造 中的某一路段可以使最大人流量得到提高，使该公交线路的最大运力得到最大的发挥，如果要追加一笔资金用于改造公交网络中的某一段线路，经计算可得应该将这笔资金投向于线路的改造，这样才能提高整个公交网络的最大运力，使整个公交网络得到最大的发挥，为伦敦奥运会的成功的召开及参赛运动员提供方便。 由于实际中人流量受到时间，在建模中受知识量的限制，问题考虑不全面等因素的影响产生一定的误差，如果把改造路线的运费及人流高峰低峰时期考虑到就可以减小误差，是问题更接近实际。（七）模型的评价优点： 对此模型的建立我们采用先假设后分析的传统方法，在此之后我们对符号进行设定便于对方程进行求解，对最大流的求解过程中我们采用标号算法使模型变得更简单，将其分为第一迭代、第二迭代、第三迭代、第四迭代，通过这四种迭代求解出从生活区S到购物区G的单位时间内的最大人流量，画出人流分布图便于接下来的分析与判断，编写LINGO程序对所得的数据进行一个系统的验证，使通过建立数学模型所计算出的最大人流量更加的精确。缺点：在进行模型分析时并没有很全面很细致，对模型的假设也太过简单考虑的问题不够全面，在使用LINGO编写程序所得的数据量太大，对进行结果分析增加了困难(八)参考文献1 韩伯棠 管理运筹学（第3版） 高等教育出版社 2010年2 陈戈止 管理运筹学西南财经大学出版社 2006年3 谢金星，薛毅 优化建模LINDO/LINGO软件 2005年4 卢开澄 线性规划 清华大学出版社 2009年5 朱道元 数学建模案例精选 科学出版社 2003年附录最大人流量计算数据结果Variable Value Reduced Cost N 9.000000 0.000000 FLOW 14.00000 0.000000 V( S, S) 0.000000 0.000000 V( S, 1) 7.000000 0.000000 V( S, 2) 5.000000 0.000000 V( S, 3) 6.000000 0.000000 V( S, 4) 0.000000 0.000000 V( S, 5) 0.000000 0.000000 V( S, 6) 0.000000 0.000000 V( S, 7) 0.000000 0.000000 V( S, G) 0.000000 0.000000 V( 1, S) 0.000000 0.000000 V( 1, 1) 0.000000 0.000000 V( 1, 2) 0.000000 0.000000 V( 1, 3) 0.000000 0.000000 V( 1, 4) 4.000000 0.000000 V( 1, 5) 5.000000 0.000000 V( 1, 6) 0.000000 0.000000 V( 1, 7) 0.000000 0.000000 V( 1, G) 0.000000 0.000000 V( 2, S) 0.000000 0.000000 V( 2, 1) 3.000000 0.000000 V( 2, 2) 0.000000 0.000000 V( 2, 3) 0.000000 0.000000 V( 2, 4) 3.000000 0.000000 V( 2, 5) 0.000000 0.000000 V( 2, 6) 0.000000 0.000000 V( 2, 7) 0.000000 0.000000 V( 2, G) 0.000000 0.000000 V( 3, S) 0.000000 0.000000 V( 3, 1) 0.000000 0.000000 V( 3, 2) 0.000000 0.000000 V( 3, 3) 0.000000 0.000000 V( 3, 4) 5.000000 0.000000 V( 3, 5) 0.000000 0.000000 V( 3, 6) 0.000000 0.000000 V( 3, 7) 4.000000 0.000000 V( 3, G) 0.000000 0.000000 V( 4, S) 0.000000 0.000000 V( 4, 1) 0.000000 0.000000 V( 4, 2) 0.000000 0.000000 V( 4, 3) 0.000000 0.000000 V( 4, 4) 0.000000 0.000000 V( 4, 5) 5.000000 0.000000 V( 4, 6) 3.000000 0.000000 V( 4, 7) 0.000000 0.000000 V( 4, G) 0.000000 0.000000 V( 5, S) 0.000000 0.000000 V( 5, 1) 0.000000 0.000000 V( 5, 2) 0.000000 0.000000 V( 5, 3) 0.000000 0.000000 V( 5, 4) 0.000000 0.000000 V( 5, 5) 0.000000 0.000000 V( 5, 6) 0.000000 0.000000 V( 5, 7) 0.000000 0.000000 V( 5, G) 7.000000 0.000000 V( 6, S) 0.000000 0.000000 V( 6, 1) 0.000000 0.000000 V( 6, 2) 0.000000 0.000000 V( 6, 3) 0.000000 0.000000 V( 6, 4) 0.000000 0.000000 V( 6, 5) 0.000000 0.000000 V( 6, 6) 0.000000 0.000000 V( 6, 7) 0.000000 0.000000 V( 6, G) 7.000000 0.000000 V( 7, S) 0.000000 0.000000 V( 7, 1) 0.000000 0.000000 V( 7, 2) 0.000000 0.000000 V( 7, 3) 0.000000 0.000000 V( 7, 4) 4.000000 0.000000 V( 7, 5) 0.000000 0.000000 V( 7, 6) 5.000000 0.000000 V( 7, 7) 0.000000 0.000000 V( 7, G) 6.000000 0.000000 V( G, S) 0.000000 0.000000 V( G, 1) 0.000000 0.000000 V( G, 2) 0.000000 0.000000 V( G, 3) 0.000000 0.000000 V( G, 4) 0.000000 0.000000 V( G, 5) 0.000000 0.000000 V( G, 6) 0.000000 0.000000 V( G, 7) 0.000000 0.000000 V( G, G) 0.000000 0.000000 F( S, S) 0.000000 -1.000000 F( S, 1) 3.000000 0.000000 F( S, 2) 5.000000 0.000000 F( S, 3) 6.000000 0.000000 F( S, 4) 0.000