2007高教社杯全国大学生数学建模竞赛.DOC

1、12007 高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从 A/B/C/D 中选择一项填写）： B 我们的参赛报名号为（如

2、果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 西南交通大学 参赛队员 (打印并签名) ：1. 张书瑞 2. 裴星星 3. 黄如君 指导教师或指导教师组负责人 (打印并签名)： 徐跃良 日期： 2007 年 09 月 24 日赛区评阅编号（由赛区组委会评阅前进行编号）：22007 高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：3乘公交 看奥运摘要为建立公交线路选择问题的自主查询计算机系统，从实际情况出发

3、考虑，本文建立了满足查询者的各种不同需求的线路选择模型与算法。并给出一些结果。问题一为仅考虑公汽线路的情况下给出任意两公汽站点之间线路选择问题的一般数学模型与算法。本文从费用、时间及换乘次数出发，先单独再综合的对三个因素进行了详细讨论。在建模中我们将费用和时间视为有向图边的邻接矩阵权，使原题巧妙的转化为了图论的最短路问题，建立了一个线性规划模型，采用 Dijkstra 算法对模型进行求解。对于多目标，我们采用将目标转化为约束条件和将目标无量纲化后进行线性加权相结合的办法进行计算，得出最优线路，如 S3359S1828 的线路有：1、S3395（L324）S1746（L027）S1784（L16

4、7）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） 。并对最优线路给出了详细的评价。问题二，同时考虑地铁和公汽的线路选择问题，我们从时间和费用两方面进行讨论。建模中，我们保留第一问的建模思想，同时考虑了地铁的情况，建立了 01 规划模型。对此模型，我们采用 Floyd 最短路径算法和 Dijkstra 算法再结合仿真算法用 C 语言编程求解。并得到最优线路，如 S

5、3359S1828 的线路：S3359-L015（上行）-S1327-L296（环行）-S0992-L475（上行）-S1828，时间：72 分钟，费用:元。问题三，在知道所有站点之间的步行时间的情况下的公交线路选择问题，我们从费用最少、总时间最少和步行时间最少进行讨论。在建模中，我们巧妙的把步行看作一种特殊的不花费用的交通方式，并结合图论知识建立了 3 个目标的多目标 0-1 规划模型。最后，我们还给出了求解此模型的思想和算法。在问题一中，构造了有向赋权图，巧妙地将原问题转化为图论的最短路问题是本文的亮点。在问题三中，将步行看作一种特殊的不花费用的交通方式，大大减轻了我们建模难度。另外，本文

6、还采用了多个图论算法，简化了模型求解难度。最后，我们还对本文提出了推广和改进的方案。关键词：0-1 规划 Dijkstra 算法 Floyd 算法 仿真算法 多目标规划 有向赋权图4一、问题提出我国人民翘首企盼的第 29 届奥运会明年 8 月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达 800 条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核

7、心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下 6 对起始站终到站之间的最佳路线（要有清晰的评价说明） 。(1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。二、模型假设1、假设

8、题目所提供参数均真实可信。2、忽略堵车等其他意外情况对题目计算的影响。3、假设公汽和地铁容量、数量足够，即忽略由于满载造成乘客不得上车的影响。4、不计乘客上、下车时间及公交启动、加速、滑行制动时间（因为题中给的是平均时间） 。5、假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费） 。三、符号说明与概念引入1、概念引入（1）直达若 能直接坐一趟车到达 点则称 直达，否则不直达（注：此i j,ij处 与 直达不相同） 。,ij,i（2）站点编号为了方便论文的叙述，我们对公汽站点和地铁站点进行重新编号。S0001-站点 1S0002-站点 2S3957-站点 3957D1-站

9、点 3958D2-站点 39595D39-站点 3996（3）线路编号为了方便论文的叙述和计算的方便，我们对公汽线路和地铁线路进行重新编号。L001-线路 1L002 上行-线路 2L002 下行-线路 3L520 上行-线路 928L520 下行-线路 929T1-线路 930T2-线路 9312、符号说明-表示是否通过站点 直达站点 线路（01 变量）ijxij-表示从站点 直达站点 的费用（若不能直达，则记 无穷大）ijw ijw-表示从站点 直达站点 的时间（若不能直达，则记 无穷大）ijtij ijt-表示从站点 直达站点 所选乘的线路（若不能直达，则记 为 0）ijy ijy-表示

10、起始站1r-表示终到站2四、问题分析4.1 问题背景的理解题目要求给出任意两公汽站点之间的最佳线路，最佳线路是一个模糊概念，在此我们根据乘客的实际情况出发，对乘坐时间、费用和换乘次数进行讨论。显然，由于不同乘客的要求不同，不可能直接找到一条令所有人都满意的线路，对此我们根据不同乘客的需求，求出不同的参考乘车线路。我们的目标就是根据题目所给统计资料，把乘车线路问题抽象成一个明确完整的数学模型，并求解，根据我们的解，为不同需求的乘客提供乘车线路，以使乘客乘车利益最大化。64.2 问题一的分析问题一要求仅考虑公汽线路，给出任意两公汽站点之间的线路选择。我们通过对乘客线路选择心理的调查讨论，发现影响选

11、择的因素共有三个：时间、费用和换乘次数。为了方便我们对三个因素的全面讨论，我们首先分别对各个因素建模进行细致的讨论，然后再对三个因素建立三目标的优化模型进行讨论。在建模过程中，我们以 3957 个公汽站点为顶点，分别用 和 为边 到 赋权ijwijtj值，构成了 3957 个顶点的有向赋权图，也就将题目转化成了一个图论问题 1。我们要找到最佳乘车线路，即是找到顶点 到顶点 的最短路径。1r24.3 问题二的分析此题加入了对地铁线路的讨论，使的乘坐工具的选择更加多样化和更加接近实际。对于此问我们以 3996 个站点为顶点，分别用 和 为边 到 赋权值，ijwijtj构成了 3996 个顶点的有向

12、赋权图，也就将题目转化成了一个图论问题。我们要找到最佳乘车线路，即是找到顶点 到顶点 的最短路径。此题相对第一问难1r2点主要在于多了公汽转地铁、地铁转公汽和地铁转地铁。4.4 问题三的分析对于问题三，引入了步行方式，对于步行的解决我们采用将步行看作一种新的乘坐工具，不过此乘坐工具费用为 0。然后我们从费用、总时间和步行时间这三个因素对线路选择进行了详细讨论。五、模型建立及求解5.1 问题一1、模型建立模型 1.1（只考虑乘车费用最少的情况）7我们在此以 3957 个公汽站点为顶点，以 为边 到 的权，构成了 3957ijwj个顶点的有向赋权图。我们要找到最佳乘车线路，即是找到顶点 到顶点 的

13、1r2最短路径（即乘车费用最小的路径） 。显然，从站点 直达站点 可能会有多条线路选择，但必有一条为费用最少ij的，记此条线路为 ，其费用为 ，时间为 ；若不能直达，则记 为 0，ijyijwijt ijy和 为无穷大。ijwijt设决策变量为 ，当 =1，说明边 位于顶点 到顶点 的路上；否则ijxij (,)ij1r2为 0。ijx所以，可以用数学表达式表示出，乘车费用为：39571ijijixw由于从费用考虑，即要满足费用最小，所以目标函数为：Min 39571ijijixw又因为要满足从顶点 到达顶点 ，所以由图论一笔画问题 2可知，顶点r2r的出度减去其入度等于 1，顶点 的出度减去

14、入度等于，其余顶点均满足1r入度等于出度。所以，约束条件如下：s.t. 139573957211,()0,ijjirxi等 于 其 他 ）为变量ij综上，可以建立模型如下：Min 39571ijijixws.t. 139573957211,()0,ijjiri等 于 其 他 ）为变量ijx模型 1.2（只考虑乘车时间最短的情况）8同理，我们记站点 直达站点 时间最短的那条线路为 ，其费用为 ，ij ijyijw时间为 ；若不能直达，记 为 0， 和 为无穷大。ijt ijyijwijt我们在此以 3957 个公汽站点为顶点，以 为边 到 的权，构成了 3957 个ijj顶点的有向赋权图，我们就

15、是要找到时间最少的乘车线路。设决策变量为 ，当 =1，说明边 位于顶点 到顶点 的路上；否则ijxij (,)ij1r2为 0。ijx所以，可以用数学表达式表示出，乘车时间为：39571ijixt显然， 表示的是总的乘车趟数，所以换车次数为39571ijix39571()iji换车时间为： ，总时间为：39571()iji3957395711()ij iji ixxt由于从乘车时间考虑，即要满足时间最小，所以目标函数为：Min 3957395711()ij iji ixxt又因为要满足从顶点 到达顶点 ，所以由图论一笔画问题可知，顶点 的r2r 1r出度减去其入度等于 1，顶点 的出度减去入度

16、等于，其余顶点均满足入度等于出度。所以，约束条件如下：s.t. 139573957211,()0,ijjirxi等 于 其 他 ）为变量ij综上，可以建立模型如下：Min 3957395711()ij iji ixxts.t. 39573957211,()0,ijjiri等 于 其 他 ）9为变量ijx模型 1.3（只考虑换乘次数优先的情况下）设决策变量为 ，当 =1，说明边 位于顶点 到顶点 的路上；否则ijxij (,)ij1r2为 0。ijx容易求得乘车趟数为： ，所以换乘次数为39571ijix39571ijix由目标换乘次数最小，目标函数为：Min 39571ijix同理可以写出约束

17、，综上，建立出模型如下：Min 39571ijixs.t. 139573957211,()0,ijjiri等 于 其 他 ）为变量ijx模型 1.4（同时考虑时间、费用及换乘次数的影响）我们从费用与时间两方面考虑，记站点 直达站点 的最佳线路为 ，并记ijijy此时的费用为 ，时间为 ；若不能直达，记 为 0， 和 为无穷大。ijwijt ijyijwijt我们在此以 3957 个公汽站点为顶点，以 为边 到 的权，构成了 3957 个ijt顶点的有向赋权图。我们要找到最佳乘车线路，即是找到顶点 到顶点 的最1r2短路径（即乘车时间最小的路径） 。我们在此以 3957 个公汽站点为顶点，以 为

18、边 到 的权，构成了 3957ijwj个顶点的有向赋权图。我们要找到最佳乘车线路，即是找到顶点 到顶点 的1r2最短路径（即乘车费用最小的路径） 。显然对于以上两个有向图，具有相同的顶点，但边的赋权不同。数学表达式表示出，换乘次数为： ；总时间为：39571ijix10；乘车费用为：3957395711()ij iji ixxt39571ijijixw所以，目标函数如下：换乘次数最少Min 39571ijix总时间最少Min 3957395711()ij iji ixxt总费用最少Min 39571ijijixw另一方面，由图论知识，可以写出约束条件如下：s.t. 139573957211,()0,ijjirxi等 于 其 他 ）为变量ij综上，可以建立出模型如下：Min 39571ijixMin 3957395711()ij iji ixtMin 39571ijijixws.t. 139573957211,()0,ijjiri等 于 其 他 ）为变量ijx2、模型求解模型 1.1 的求解：对于这个单目标规划，由于数据量巨大，现成软件的常规办法不能完成求解。在此，我们采用 Dijkstra 算法 3通过 VC 编程进行求解。算法步骤如下：STEP1： 对于数据进行简单的预处理，将上行和下行的线路当作两种不同