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

2007高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：西南交通大学参赛队员(打印并签名)：1.张书瑞2.裴星星3.黄如君指导教师或指导教师组负责人(打印并签名)：徐跃良日期：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分钟，费用:４元。问题三，在知道所有站点之间的步行时间的情况下的公交线路选择问题，我们从费用最少、总时间最少和步行时间最少进行讨论。在建模中，我们巧妙的把步行看作一种特殊的不花费用的交通方式，并结合图论知识建立了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、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。二、模型假设1、假设题目所提供参数均真实可信。2、忽略堵车等其他意外情况对题目计算的影响。3、假设公汽和地铁容量、数量足够，即忽略由于满载造成乘客不得上车的影响。4、不计乘客上、下车时间及公交启动、加速、滑行制动时间（因为题中给的是平均时间）。5、假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费）。三、符号说明与概念引入1、概念引入（1）直达——若i能直接坐一趟车到达j点则称,ij直达，否则不直达（注：此处,ij与,ji直达不相同）。（2）站点编号——为了方便论文的叙述，我们对公汽站点和地铁站点进行重新编号。S0001------站点1S0002------站点2…………S3957------站点3957D1------站点3958D2------站点3959…………D39------站点3996（3）线路编号——为了方便论文的叙述和计算的方便，我们对公汽线路和地铁线路进行重新编号。L001------线路1L002上行------线路2L002下行------线路3…………L520上行------线路928L520下行------线路929T1------线路930T2------线路9312、符号说明ijx------表示是否通过站点i直达站点j线路（0—1变量）ijw------表示从站点i直达站点j的费用（若不能直达，则记ijw无穷大）ijt------表示从站点i直达站点j的时间（若不能直达，则记ijt无穷大）ijy------表示从站点i直达站点j所选乘的线路（若不能直达，则记ijy为0）1r------表示起始站2r------表示终到站四、问题分析4.1问题背景的理解题目要求给出任意两公汽站点之间的最佳线路，最佳线路是一个模糊概念，在此我们根据乘客的实际情况出发，对乘坐时间、费用和换乘次数进行讨论。显然，由于不同乘客的要求不同，不可能直接找到一条令所有人都满意的线路，对此我们根据不同乘客的需求，求出不同的参考乘车线路。我们的目标就是根据题目所给统计资料，把乘车线路问题抽象成一个明确完整的数学模型，并求解，根据我们的解，为不同需求的乘客提供乘车线路，以使乘客乘车利益最大化。4.2问题一的分析问题一要求仅考虑公汽线路，给出任意两公汽站点之间的线路选择。我们通过对乘客线路选择心理的调查讨论，发现影响选择的因素共有三个：时间、费用和换乘次数。为了方便我们对三个因素的全面讨论，我们首先分别对各个因素建模进行细致的讨论，然后再对三个因素建立三目标的优化模型进行讨论。在建模过程中，我们以3957个公汽站点为顶点，分别用ijw和ijt为边i到j赋权值，构成了3957个顶点的有向赋权图，也就将题目转化成了一个图论问题[1]。我们要找到最佳乘车线路，即是找到顶点1r到顶点2r的最短路径。4.3问题二的分析此题加入了对地铁线路的讨论，使的乘坐工具的选择更加多样化和更加接近实际。对于此问我们以3996个站点为顶点，分别用ijw和ijt为边i到j赋权值，构成了3996个顶点的有向赋权图，也就将题目转化成了一个图论问题。我们要找到最佳乘车线路，即是找到顶点1r到顶点2r的最短路径。此题相对第一问难点主要在于多了公汽转地铁、地铁转公汽和地铁转地铁。4.4问题三的分析对于问题三，引入了步行方式，对于步行的解决我们采用将步行看作一种新的乘坐工具，不过此乘坐工具费用为0。然后我们从费用、总时间和步行时间这三个因素对线路选择进行了详细讨论。五、模型建立及求解5.1问题一1、模型建立模型1.1（只考虑乘车费用最少的情况）我们在此以3957个公汽站点为顶点，以ijw为边i到j的权，构成了3957个顶点的有向赋权图。我们要找到最佳乘车线路，即是找到顶点1r到顶点2r的最短路径（即乘车费用最小的路径）。显然，从站点i直达站点j可能会有多条线路选择，但必有一条为费用最少的，记此条线路为ijy，其费用为ijw，时间为ijt；若不能直达，则记ijy为0，ijw和ijt为无穷大。设决策变量为ijx，当ijx=1，说明边(,)ij位于顶点1r到顶点2r的路上；否则ijx为0。所以，可以用数学表达式表示出，乘车费用为：3957395711ijijijxw由于从费用考虑，即要满足费用最小，所以目标函数为：Min3957395711ijijijxw又因为要满足从顶点1r到达顶点2r，所以由图论一笔画问题[2]可知，顶点1r的出度减去其入度等于1，顶点2r的出度减去入度等于－１，其余顶点均满足入度等于出度。所以，约束条件如下：s.t.1395739572111,()1,()0,(ijjijjirxxiri等于其他）ijx为０—１变量综上，可以建立模型如下：Min3957395711ijijijxws.t.1395739572111,()1,()0,(ijjijjirxxiri等于其他）ijx为０—１变量模型1.2（只考虑乘车时间最短的情况）同理，我们记站点i直达站点j时间最短的那条线路为ijy，其费用为ijw，时间为ijt；若不能直达，记ijy为0，ijw和ijt为无穷大。我们在此以3957个公汽站点为顶点，以ijt为边i到j的权，构成了3957个顶点的有向赋权图，我们就是要找到时间最少的乘车线路。设决策变量为ijx，当ijx=1，说明边(,)ij位于顶点1r到顶点2r的路上；否则ijx为0。所以，可以用数学表达式表示出，乘车时间为：3957395711ijijijxt显然，3957395711ijijx表示的是总的乘车趟数，所以换车次数为3957395711(1)ijijx换车时间为：3957395711(1)5ijijx，总时间为：39573957395739571111(1)5ijijijijijxxt由于从乘车时间考虑，即要满足时间最小，所以目标函数为：Min39573957395739571111(1)5ijijijijijxxt又因为要满足从顶点1r到达顶点2r，所以由图论一笔画问题可知，顶点1r的出度减去其入度等于1，顶点2r的出度减去入度等于－１，其余顶点均满足入度等于出度。所以，约束条件如下：s.t.1395739572111,()1,()0,(ijjijjirxxiri等于其他）ijx为０—１变量综上，可以建立模型如下：Min39573957395739571111(1)5ijijijijijxxts.t.1395739572111,()1,()0,(ijjijjirxxiri等于其他）ijx为０—１变量模型1.3（只考虑换乘次数优先的情况下）设决策变量为ijx，当ijx=1，说明边(,)ij位于顶点1r到顶点2r的路上；否则ijx为0。容易求得乘车趟数为：3957395711ijijx，所以换乘次数为39573957111ijijx由目标换乘次数最小，目标函数为：Mi