交通路口红绿灯__数学建模
交通路口红绿灯__数学建模
交通路口红绿灯交通路口红绿灯
十字路口绿灯亮30秒，最多可以通过多少辆汽车, 十字路口绿灯亮30秒，最多可以通过多少辆汽车, 一问题重述一问题重述
因为十字路口的交通现象较复杂，通过路口的车辆的多少依赖于路面上汽车的型号，数量和它们的行驶速度和方向以及同时穿过路口的非机动车辆的行人的状态等因素有关，因此，我们在求解“十字路口绿灯亮30秒，最多可以通过多少辆汽车”时应综合考虑各方面因素二模型假设二模型假设
(1)十字路的车辆穿行秩序良好不会发生阻塞;
(2)所有车辆都是直行穿过路口，不拐弯行驶，并且仅考虑马路一侧的车辆。
(3)所有车辆长度相同，并且都是从静止状态开始匀加速启动; (4)红灯下等侍的每辆相邻车之间的距离相等;
(5)前一辆车启动后同后一辆车启动的延迟时间相等。另外在红灯下等侍的车队足够长，以至排在队尾的司机看见绿灯又转为红灯时仍不能通过路口。
参数，变量: 车长L，车距D，加速度a，启动延迟T，在时刻 t 第 n 辆车的位置 S(t) n
用数轴表示车辆行驶道路,数轴的正向为汽车行驶方向, 数轴原点为红绿灯的位置。于是, 当S(30)>0时, 表明在第30秒第n辆车已通n
过红绿灯，否则，结论相反。
三模型建立三模型建立
1.停车位模型: S(0)=–(n-1)(L+D) n
2. 启动时间模型: t =(n-1)T n
23. 行驶模型: S(t)=S(0)+1/2 a (t-t) , t>t nnnn
参数估计 L=5m，D=2m，T=1s，a=2m/s
四模型求解四模型求解
2解: S(30)=-7(n-1)+(30-(n-1))>0 得 n,19 且 t=18<30=t 成n19立。
答案: 最多19辆车通过路口. 改进:考虑到城市车辆的限速，在匀加速运动启动后，达到最高限速后，停止加速, 按最高限速运动穿过路口。
最高限速:校园内v*=15公里/小时=4米/秒，长安街上v*=40公里/小时=11米/秒，环城路上 v*=60公里/小时=17米/秒
* *取最高限速 v*=11m/s，达到最高限速时间t=v/a+t=5.5+n-1 nn 限速行驶模型:
2**** S(t)=S(0)+1/2 a(t–t)+v(t-t), t>t nnn n nn
2*=S(0)+1/2 a (t-t) , t>t>t nnnn
= S(0) t>t nn
2*解:S(30)=-7(n-1)+(5.5)+11(30-5.5-(n-1))>0 得 n,17 且 tn17
=5.5+16=21.5<30=t 成立。
结论: 该路口最多通过17辆汽车.
五模型的检验与应用五模型的检验与应用
1. 调查一个路口有关红绿灯的数据验证模型是否正确。
0 1. 调查的位置，走向，车道数，时间。
调查数据(至少三次): 绿灯时间，通过的车数。分析数据不同的原因。
0 2. 分析模型的假设与实际是否一致;模型的参数与实际是否一致。
0 3. 分析模型的计算结果与观测结果是否一致,为什么,不一致时，如何修改模型。
2. 分析绿灯亮后，汽车开始以最高限速穿过路口的时间。
3. 给出穿过路口汽车的数量n随时间t变化的数学模型。
数学建模论文十字路口绿灯
江西师范高等专科学校 论文题目：十字路口绿灯亮30秒，最多可以通过多少辆汽车？ 组长：肖根金学号：9015300135 班级：15数教1班 组员：叶强学号：9015300143 班级：15数教1班 组员：谭伟学号：9015300132 班级：15数教1班 2017年4月15日
目录 一、问题重述 (3) 1.1问题背景 (3) 1.2问题简述 (4) 二、模型假设 (4) 3.1 停车位模型 (5) 3.2 启动时间模型 (5) 3.3 行驶模型 (5) 三、模型建立 (5) 四、模型求解 (5) 五、模型的检验与应用 (6) 5.1调查一个路口有关红绿灯的数据验证模型是否正确 5.2分析绿灯亮后，汽车开始以最高限速穿过路口的时间 5.3给出穿过路口汽车的数量n随时间t变化的数学模型 六、模型的评价 (6) 6.1 模型的优点 (6) 6.2 模型的缺点 (7) 参考文献
一、问题重述 1.1问题背景 随着经济和社会快速发展,我国城市道路建设增多,出行车辆增加,城市交通进入了快速发展阶段,城市交通的几个问题,即交通阻塞、交通事故、公共交通问题城市，道路交通问题日益突出.,为城市交通建设和路网规划提供方案和依据,达到优化城市道路交通状况的目的.因此我们针对于交通问题事故，将“十字路口绿灯亮30秒问题”单独列出以建模的形式来进行合理的规划，让十字路口的交通，更安全。在每年的节假时间里，有很多的人喜欢去旅游，交通的拥挤阻塞已经是很大问题，好多事故的发生。这是我们不愿意见到的事实。“十字路口绿灯亮30时间”对于现在的这个新时代的我们来说，城市的汽车车水马龙，它的合理设计是十分重要的。在交通管理中，绿灯的作用是为了维持交通秩序。在十字路口行驶的车辆中，主要因素是机动车辆，驶近交叉路口的驾驶员，在看到绿色信号后要通过路口。利用数学模型解决绿灯在十字路口亮30秒的问题，可以减少交通事故的发生，也相对合理的运用社会科学知识解决实际问题。某一天一个式子路口的绿灯灯亮30秒，那么能通过几辆汽车呢？ 1.2问题简述 因为十字路口的交通现象较复杂，通过路口的车辆的多少依赖于路面上汽车的型号，数量和它们的行驶速度和方向以及同时穿过路口的非机动车辆的行人的状态等因素有关，因此，我们在求解“十字路
数学建模实验报告第十一章最短路问答
实验名称：第十一章最短路问题 一、实验内容与要求 掌握Dijkstra算法和Floyd算法，并运用这两种算法求一些最短路径的问题。 二、实验软件 MATLAB7.0 三、实验内容 1、在一个城市交通系统中取出一段如图所示，其入口为顶点v1，出口为顶点v8，每条弧段旁的数字表示通过该路段所需时间，每次转弯需要附加时间为3，求v1到v8的最短时间路径。 V1 1 V2 3 V3 1 V5 6 V6 V4 2 V7 4 V8
程序： function y=bijiaodaxiao(f1,f2,f3,f4) v12=1;v23=3;v24=2;v35=1;v47=2;v57=2;v56=6;v68=3;v78=4; turn=3; f1=v12+v23+v35+v56+turn+v68; f2=v12+v23+v35+turn+v57+turn+v78; f3=v12+turn+v24+turn+v47+v78; f4=v12+turn+v24+v47+turn+v57+turn+v56+turn+v68; min=f1; if f2 f4 实验结果： v1到v8的最短时间路径为15，路径为1-2-4-7-8. 2、求如图所示中每一结点到其他结点的最短路。V110 V3V59 V6 floy.m中的程序： function[D,R]=floyd(a) n=size(a,1); D=a for i=1:n for j=1:n R(i,j)=j; end end R for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j) 建模实习作业题 之红绿灯闪烁模型班级：计算1502 交通管理中非数字灯闪烁时间模型 摘要 本文在了解过车辆通过红绿灯所遇见的情况，以及对车型的分析下，重点通过常微分方程建立起时间，刹车距离，以及刹车制动因素相关的数学模型。 在问题中对红绿灯灯应闪烁时间做出等价转换，闪烁的意图是让车辆在黄灯前停在停止线前，对于影响车辆刹车距离的因素主要由车辆制动力控制，闪烁时间应为驾驶员观察到信号变换反应的时间与驾驶员制动使车辆停在停车线所需时间之和。在法定通过红绿灯的速度下对大型车辆进行讨论，因为小型车辆制动距离明显小于大型载货汽车。 对于模型的评价，本文采用与实际生活中数据以及对车辆理论数据进行对比，以此检验模型建立的合理性及正确性。 最后，本文分析了现有模型的缺陷，并提出进一步改进方法，使之与贴合生活方面进一步。 【关键词】微分方程；刹车制动力；制动因素 目录 一、问题重 述………………………………………………………………………………… …4 二、基本假 设………………………………………………………………………………… …4 三、符号说 明………………………………………………………………………………… …4 四、模型建立、分析与求 解 (5) 五、模型评价与改 进 (6) 六、参考文 献 (7) 一、问题重述 从2013年元月一日，国家开始实行新的交通法规。在十字路口的交通管理中，最大而且最有争议的改变是闯黄灯。在以前的交规中，亮红灯之前要亮一段时间黄灯，这是为了让那些行驶在十字路口或距十字路口太近以致无法停下来的车辆通过路口.现在规定闯黄灯也是违规行为，为了不违反交通法规，对有时间数字的交通灯，司机根据时间数字可以提前对自己的行动作出决策，但还有很多交通灯是非数字的，这就不可避免的对司机的判断造成障碍，为此，非数字的交通灯在变灯前加入了闪烁，以提醒司机。为了让司机在十字路口有足够的时间决定过不过马路，请你考察实际生活中的道路，给出最佳的闪烁时间。 二、基本假设 1.假设刹车途中，刹车制动力恒定 2.行驶过程中没有意外事故 基于最短路问题的研究及应用 ： Fanmeng 学号： 指导老师： 摘要 最短路问题是图论中的一大问题，对最短路的研究在数学建模和实际生活中具有很重要的实际意义，介绍最短路问题的定义及这类问题的解决办法Dijkstra算法，并且能够在水渠修建实例运用到此数学建模的方法，为我们解决这类图论问题提供了基本思路与方法。 关键字数学建模最短路问题 Dijkstra算法水渠修建。 目录 第一章．研究背景 (1) 第二章．理论基础 (2) 2.1 定义 (2) 2.2 单源最短路问题Dijkstra求解: (2) 2.2.1 局限性 (2) 2.2.2 Dijkstra算法求解步骤 (2) 2.2.3 时间复杂度 (2) 2.3 简单样例 (3) 第三章．应用实例 (4) 3.1 题目描述 (4) 3.2 问题分析 (4) 3.3符号说明 (5) 3.4 模型假设 (5) 3.5模型建立与求解 (5) 3.5.1模型选用 (5) 3.5.2模型应用及求解 (5) 3.6模型评价 (5) 第四章. 参考文献 (6) 第五章．附录 (7) 第一章．研究背景 在现实生活中中，我们经常会遇到图类问题，图是一种有顶点和边组成，顶点代表对象，在示意图中我们经常使用点或者原来表示，边表示的是两个对象之间的连接关系，在示意图中，我们使用连接两点G点直接按的下端来表示。顶点的集合是V，边的集合是E的图记为G[V,E] ,连接两点u和v的边用e(u,v)表示[1]。最短问题是图论中的基础问题，也是解决图类问题的有效办法之一，在数学建模中会经常遇到，通常会把一个实际问题抽象成一个图，然后来进行求的接任意两点之间的最短距离。因此掌握最短路问题具有很重要的意义。 十字路口红绿灯的合理设置 陈金康 检索词：红绿灯设置、红绿灯周期 一、问题的提出 作为城市交通的指挥棒，红绿灯对交通的影响起着决定性作用。如果红绿灯的设置不合理，不仅会影响到交通秩序；还有可能会影响到行人和自行车的安全。 目前杭城还有很多路口的红绿灯设置存在一些不合理的因素，我们以古墩路一个路口(界于天目山路和文苑路之间)的红绿灯设置为例，该路口是刚开通的，交管部门对路况和车流量的研究还不是很成熟，因此红绿灯的设置存在一些问题。该路口的车流量相对比较小，有几个方向的车流量特别小，但绿灯时间设置太长，经常出现路口空荡荡但是车辆必须长时间等待的情况；同时在这样的路口，右转红灯显得有些多余。另外，该路口不同时段的红绿灯设置没有什么区别，显然这是非常不合理的。 下面我们就针对该路口来研究一下红绿灯设置的合理方案。我们主要研究两个方面：红绿灯周期的设置以及一个周期内各个方面开绿灯的时间。 二、模型的建立 1、红绿灯周期 从《道路交通自动控制》中，我们可以找到有关红绿信号灯的最佳周期公式： s q L C ∑ -+= 15 其中 : C 为周期时间。 相位：同时启动和终止的若干股车流叫做一个相位。 L 为一个周期内的总损失时间。每一相位的损失时间I=启动延迟时间-结束滞后时间；而整个周期的总损失时间为各个相位总损失时间的和加上各个绿灯间隔时间R 。（通俗地讲，启动延迟时间即司机看到绿灯到车子启动的反应时间，结束滞后时间即绿灯关闭到最后一辆车通过的时间。） 即R I L +∑= q 为相应相位的车流量 s 为相应相位的饱和车流量。（当车辆以大致稳定的流率通过路口时，该流率即该相位的饱和车流量。） 2、南北方向和东西方向开绿灯时间的分配 不妨忽略黄灯，将交通信号灯转换的一个周期取作单位时间，又设两个方向的车流量是稳定和均匀的，不考虑转弯的情形。 交通路口红绿灯 十字路口绿灯亮30秒，最多可以通过多少辆汽车？一问题重述 因为十字路口的交通现象较复杂，通过路口的车辆的多少依赖于路面上汽车的型号，数量和它们的行驶速度和方向以及同时穿过路口的非机动车辆的行人的状态等因素有关，因此，我们在求解“十字路口绿灯亮30秒，最多可以通过多少辆汽车”时应综合考虑各方面因素二模型假设 (1)十字路的车辆穿行秩序良好不会发生阻塞； (2)所有车辆都是直行穿过路口，不拐弯行驶，并且仅考虑马路一侧的车辆。 (3)所有车辆长度相同，并且都是从静止状态开始匀加速启动； (4)红灯下等侍的每辆相邻车之间的距离相等； (5)前一辆车启动后同后一辆车启动的延迟时间相等。 另外在红灯下等侍的车队足够长，以至排在队尾的司机看见绿灯又转为红灯时仍不能通过路口。 参数，变量：车长L，车距D，加速度a，启动延迟T，在时刻 t 第n 辆车的位置 S n（t） 用数轴表示车辆行驶道路,数轴的正向为汽车行驶方向, 数轴原点为红绿灯的位置。于是, 当S n(30)>0时, 表明在第30秒第n辆车已通过红绿灯，否则，结论相反。 三模型建立 1.停车位模型： S n（0）=–(n-1)(L+D) 2. 启动时间模型: t n =(n-1)T 3. 行驶模型: S n(t)=S n(0)+1/2 a (t-t n) 2, t>t n 参数估计 L=5m，D=2m，T=1s，a=2m/s 四模型求解 解: S n(30)=-7(n-1)+(30-(n-1))2>0 得 n≤19 且 t19=18<30=t 成立。 答案: 最多19辆车通过路口. 改进：考虑到城市车辆的限速，在匀加速运动启动后，达到最高限速后，停止加速, 按最高限速运动穿过路口。 最高限速：校园内v*=15公里/小时=4米/秒，长安街上v*=40公里/小时=11米/秒，环城路上 v*=60公里/小时=17米/秒 取最高限速 v*=11m/s，达到最高限速时间t n*=v* /a+t n =5.5+n-1 限速行驶模型: S n(t)=S n(0)+1/2 a(t n *–t n )2+v*(t-t n*), t>t n* =S n(0)+1/2 a (t-t n) 2, t n*>t>t n = S n(0) t n>t 解：S n(30)=-7(n-1)+(5.5)2+11(30-5.5-(n-1))>0 得 n≤17 且 t17 * =5.5+16=21.5<30=t 成立。 结论: 该路口最多通过17辆汽车. 摘要 近年来随着机动车辆的迅猛增长，城市道路的交通压力日渐增大，各大城市对旧城改造及城市道路建设的投入也不断扩大，交通拥挤问题却仍旧日益严重。因此，科学全面地分析和评价城市的绩效，进而找到适合我国的城市交通规划模式，已成为我国城市交通迫切需要解决的课题。 本文通过大量查阅城市交通绩效评价指标，结合目前我国交通发展现状，以兰州为例，首先建立了绩效评价指标的层次结构模型，确定了目标层，准则层（一级指标），子准则层（二级指标）。 其次，建立评价集V=(优，良，中，差)。对于目标层下每个一级评价指标下相对于第m 个评价等级的隶属程度由专家的百分数u 评判给出，即U ＝[0,100]应用模糊统计建立它们的隶属函数A(u)， B(u)， C(u) ，D(u)，最后得出目标层的评价矩阵Ri ，（i=1,2,3,4,5）。利用A,B 两城相互比较法，根据实际数据建立二级指标对于相应一级指标的模糊判断矩阵P i （i=1,2,3,4,5） 然后，我们经过N 次试验调查，明确了各层元素相对于上层指标的重要性排序，构造模糊判断矩阵P ，利用公式 1 ,ij ij n kj k u u u ==∑ 1 ,n i ij j w u ==∑ 1 ,i i n j j w w w ==∑ []R W R W R W R W R W W R W O 5544332211,,,,==计算出权重值，经过一致性检验公式RI CI CR = 检验后，均有0.1CR <，由此得出各层次的权向量()12,,T n W W W W =K 。然后后， 给出建立绩效评价模型（其中O 是评价结果向量），应用模糊数学中最大隶属度原则，对被评价城市交通的绩效进行分级评价。 接着，为了优化兰州安宁区道路交通，我们建立了评价城市交通的指标体系，继而构造模糊判断矩阵P ，计算出相应的权重值。我们挑选了道路因素进行优化，以主干道利用率约束、红绿灯效率约束、公交站点数目约束、非负约束为约束条件建立了安宁区道路交通优化方案的权系数模型，最后利用实际测算数据给出最终优化模型，提出合理化的优化建议，希望能为更好的建设兰州交通体系作出贡献。 关键词：城市交通 层次分析 模糊综合评判 绩效评价 隶属度 运输问题 摘要 本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd算法、Kruskal算法，以及整数规划的方法建立相关问题的模型，通过matlab，lingo编程求解出最终结果。 关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进行分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进行编程求解，运行得到结果：2-3-8-9-10总路程为85公里。 关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线： 1-5-7-6-3-4-8-9-10-2；然后利用问题一的Floyd算法编程，能求得从客户2到客户1（提货点）的最短路线是：2-1，路程为50公里。即最短路线为：1-5-7-6-3-4-8-9-10-2-1。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进行编程求解，求解出的回路与Kruskal算法求出的回路一致。 关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进行优化。得到优化结果为：第一辆车：1-5-2-3-4-8-9-1，第二辆车：1-7-6-9-10-1，总路程为280公里。 关于问题四，在问题一的基础上我们首先用Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。根据matlab运行结果分析得出4条最优路线分别为：1-5-2，1-4-3-8，1-7-6，1-9-10。最短总路线为245公里，最小总费用为645。 关键词： Floyd算法 Kruskal算法整数规划旅行商问题 一、问题重述 某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）用下面矩阵中的(,) i j(,1,,10) i j=位置上的数表示（其中∞表示两个客户之间无直接的路线到达）。 1、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送 货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。 2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满10个 客户所需要的全部货物，请问货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？对所设计的算法进行分析。 3、现因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。每辆小 数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MA TLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的 基于最短路问题的研究及应用令狐采学 姓名：Fanmeng 学号： 指导老师： 摘要 最短路问题是图论中的一大问题，对最短路的研究在数学建模和实际生活中具有很重要的实际意义，介绍最短路问题的定义及这类问题的解决办法Dijkstra算法，并且能够在水渠修建实例运用到此数学建模的方法，为我们解决这类图论问题提供了基本思路与方法。 关键字数学建模最短路问题Dijkstra算法水渠修建。 目录 第一章．研究背景1 第二章．理论基础2 2.1 定义2 2.2 单源最短路问题Dijkstra求解:2 2.2.1 局限性2 2.2.2 Dijkstra算法求解步骤2 2.2.3 时间复杂度2 2.3 简单样例3 第三章．应用实例4 3.1 题目描述4 3.2 问题分析4 3.3符号说明4 3.4 模型假设5 3.5模型建立与求解5 3.5.1模型选用5 3.5.2模型应用及求解5 3.6模型评价5 第四章. 参考文献5 第五章．附录6 第一章．研究背景 在现实生活中中，我们经常会遇到图类问题，图是一种有顶点和边组成，顶点代表对象，在示意图中我们经常使用点或者原来表示，边表示的是两个对象之间的连接关系，在示意图中，我们使用连接两点G点直接按的下端来表示。顶点的集合是V，边的集合是E的图记为G[V,E] ,连接两点u和v的边用e(u,v)表示[1]。最短问题是图论中的基础问题，也是解决图类问题的有效办法之一，在数学建模中会经常遇到，通常会把一个实际问题抽象成一个图，然后来进行求的接任意两点之间的最短距离。因此掌握最短路问题具有很重要的意义。 第二章．理论基础 2.1 定义 最短路问题（short-path problem ）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点，（通常是源节点和目标节点）之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管道铺设，线路安装，厂区布局和设备更新等实际问题[2]。 2.2 单源最短路问题Dijkstra 求解: 2.2.1局限性 Dijkstra 算法不能够处理带有负边的图，即图中任意两点之间的权值必须非负。 2.2.2Dijkstra 算法求解步骤 (1).先给图中的点进行编号，确定起点的编号。 (2).得到图的构成，写出写出图的矩阵 0000(,)(,) (,) (,) n n n n u u u u G u u u u = (3).根据要求求出发点S 到终点E 的最短距离，那么需要从当前没被访问过的结点集合 unvist={u | u {1,2,3...}}n ∈中找到一个距离已经标记的点的集合中vist={u | u {1,2,3...}}n ∈的最短距离，得到这个顶点； (4).利用这个顶点来松弛其它和它相连的顶点距离S 的值 (5).重复步骤(2)和(3)，直到再也没有点可以用来松弛其它点，这样我们就得到了由起点S 到其它任意点的最短距离。 2.2.3时间复杂度 时间复杂度达到 2 ()O N 运筹学模型（一） 本章重点： 线性规划基础模型、目标规划模型、运输模型及其应用、图论模型、最小树问题、最短路问题 复习要求： 1.进一步理解基本建模过程，掌握类比法、图示法以及问题分析、合理假设的内涵. 2.进一步理解数学模型的作用与特点. 本章复习重点是线性规划基础模型、运输问题模型和目标规划模型.具体说来，要求大家会建立简单的线性规划模型，把实际问题转化为线性规划模型的方法要掌握，当然比较简单.运输问题模型主要要求善于将非线性规划模型转化为运输规化模型，这种转化后求解相当简单.你至少把一个很实际的问题转化为用表格形式写出的模型，至于求解是另外一回事，一般不要求.目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型.另外，关于图论模型的问题涉及到最短路问题，具体说来用双标号法来求解一个最短路模型.这之前恐怕要善于将一个实际问题转化为图论模型.还有一个最小数的问题，该如何把一个网络中的最小数找到.另外在个别场合可能会涉及一笔划问题. 1.营养配餐问题的数学模型 或更简洁地表为 其中的常数C j 表示第j 种食品的市场价格，a ij 表示第j 种食品含第i 种营养的数量，b i 表示人或动物对第i 种营养的最低需求量. 2.合理配料问题的数学模型 有m 种资源B 1，B 2，…，B m ，可用于生产n 种代号为A 1，A 2，…，A n 的产品.单位产品A j 需用资源B i 的数量为a ij ，获利为C j 单位，第i 种资源可供给总量为b i 个单位.问如何安排生产，使总利润达到最大？ 设生产第j 种产品x j 个单位（j =1，2，…，n ），则有 或更简单地写为 3.运输问题模型 运输问题也是一种线性规划问题，只是决策变量设置为双下标变量.假如问题具有m 个产地和n 个销地，第i 个产地用A i 表示，其产量为a i （i =1，2，…，m ），第j 个销地用B j 表示，其销量为b j （j =1，2，…，n ），从A i 运往B j 的运价为c ij ， 而 ∑∑===m i n j j i b a 11表示产销平衡.那么产销平衡运输问题的一般模型可以写成为 4.目标规划模型 某工厂生产代号为Ⅰ、Ⅱ的两种产品，这两种产品都要经甲、乙两个车间加工，并经检验与销售两部门处理.已知甲、乙两车间每月可用生产工时分别为120小时和150小时，每小时费用分别为80元和20元，其它数据如下表 表4-1 问题分析与模型假设 经与工厂总经理交谈，确定下列几条： 190 实验十 交通管理问题 【实验目的】 1．了解微分方程的一些基本概念。 2．初步掌握微分方程模型建立、求解的基本方法和步骤。 3．学习掌握用MA TLAB 软件中相关命令求解常微分方程的解析解。 【实验内容】 在城市道路的十字路口，都会设置红绿交通灯。为了让那些正行驶在交叉路口或离交叉路口太近而又无法停下的车辆通过路口，红绿灯转换中间还要亮起一段时间的黄灯。对于一名驶近交叉路口的驾驶员来说，万万不可处于这样进退两难的境地：要安全停车但又离路口太近；要想在红灯亮之前通过路口又觉得距离太远。那么，黄灯应亮多长时间才最为合理呢？ 已知城市道路法定速度为0v ，交叉路口的宽度为I ，典型的车身长度统一定为L ，一般情况下驾驶员的反应时间为T ，地面的磨擦系数为μ。（假设I ＝9m ，L ＝4.5m ，μ＝0.2，T ＝1s ） 【实验准备】 微分方程是研究函数变化过程中规律的有力工具，在科技、工程、经济管理、人口、交通、生态、环境等各个领域有着广泛的应用。如在研究牛顿力学、热量在介质中的传播、抛体运动、化学中液体浓度变化、人口增长预测、种群变化、交通流量控制等等过程中，作为研究对象的函数，常常要和函数自身的导数一起，用一个符合其内在规律的方程，即微分方程来加以描述。 1．微分方程的基本概念 未知的函数以及它的某些阶的导数连同自变量都由一已知方程联系在一起的方程称为微分方程。如果未知函数是一元函数，称为常微分方程。如果未知函数是多个变量的函数，称为偏微分方程。联系一些未知函数的多个微分方程称为微分方程组。微分方程中出现的未知函数的导数的最高阶数称为微分方程的阶。若方程中未知函数及其各阶导数都是一次的，称为线性常微分方程，一般表示为 )(n y ＋)1(1)(-n y t a ＋…＋'1)(y t a n -＋y t a n )(＝)(t b （1） 若（1）式中系数)(t a i （i ＝1，2，…，n ）均与t 无关，称之为常系数（或定常、自治、时不变）的。 建立微分方程模型要根据研究的问题作具体的分析。一般有以下三种方法： 根据规律建模：在数学、力学、物理、化学等学科中已有许多经过实践检验的规律和定律，如牛顿运动定律、基尔霍夫电流及电压定律、物质的放射性规律、曲线的切线的性质等，这些都涉及某些函数的变化率。我们可以根据相应的规律，列出常微分方程。 微元法建模：利用微积分的分析法建立常微分方程模型，实际上是寻求一些微元之间的关系式，在建立这些关系式时也要用到已知的规律或定理。与第一种方法不同之处在于这里不是直接对未知函数及其导数应用规律和定理来求关系式，而是对某些微元来应用规律。 模拟近似法建模：在社会科学、生物学、医学、经济学等学科的实践中，常常要用模拟近似法来建立微分方程模型。这是因为，上述学科中的一些现象的规律性我们还不是很清楚， 评分栏 1、设计"绿色波浪"红绿灯 摘要： 本文主要研究交通问题中的“绿色波浪”线控模型，把主干道相邻交通交通信号联 动起来，通过对其距离和信号周期的分析，给出“时间-距离”图，利用图解法对简单系 统优化求解；提出对复杂系统的数值计算法，用精确的数值进一步研究红绿灯控制问题， 并实地考察从哈尔滨秋林公司到太平桥各路口的实际情况，采集了数据，用此法给出了对 此路段的“绿色波浪”红绿灯的设计方案。从而政府可以逐渐改变道路的结构和尽可能多 地设置“绿色波浪”道路，大大节约整个行车组的汽油消耗，改善环境。 一、问题重述 随着全球温室效应的加剧和石油资源的逐渐减少,很多国家都将节能减排 提到了政府工作的重要议事日程之中。城市拥堵的交通是造成汽油消耗和大量 尾气排放的重要元凶，而汽车在反复刹车减速和提速的过程中不但耗油量是正 常行驶的数倍以至十多倍,所排放的有害气体也是成倍增加。哈尔滨秋林公司 到太平桥路线，该路段长约4公里，但是地处繁华地带，红绿灯密集，一路上 有大约10多处红绿灯，行车缓慢经常拥堵，行车时间长达20分钟。需要依照“绿色波浪”想法设计一套红绿灯系统。在保证安全的前提下尽可能实现顺畅 通行，并在最后向司机写一份推广文，介绍想法做法，和司机应该如何顺利实 现“绿色波浪”。 二、问题的分析与假设 1、假设从秋林公司到太平桥这一段，马路的宽度相等、各向车道数相等。 2、假设此路段上车总量大于与其他交叉的其他路口的车流量。 3、从各个路口进入此路段的车流量等于注入此路口的车流量。即各个路 口对此路段的车流量没有影响，此路段与它们相交叉时自身的车流量不会改变。 4、假设此路段从西到东的车流量相等，而且两个方向汽车的平均速度相等。 5、信号灯只有红灯、绿灯两种，不考虑黄灯。 6、各个路口的信号周期（红灯+绿灯时间）相等。 7、不考虑转盘等设施，认为在这些路口仍然使用红绿灯。 三、模型的建立与求解 在提出模型之前，现进行符号说明和参数解释。 浅谈最短路的数学模型解问题 在生产与科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个互相联系的阶段，在它的每一个阶段都需要做出决策，从而使整个过程达到最好的活动效果。因此，各个阶段的决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线。这种把一个问题可看作一个前后关联且具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题，而最短路问题是这类问题中的比较典型的一种。 现在我们一起来探讨这类问题的特点和解决方法。 问题1（最小价格的管道铺设方案） 如下图 用点表示城市，现有共7个城市。点与点之间的连线表示城市间有道路相连。连线旁的数字表示道路的长度。现计划从城市A到城市D铺设一条天然气管道，请设计出最小价格管道铺设方案。 首选我们要明确以下2点： （1）管道长短与成本价格之间有什么关系？显然，管道越短，成本越低。 （2）你能在众多管道路线中找到一条最短的管道路线吗？答案是肯定的。这是一般人都有的最直接最原始的思路。 我们在这里就是要寻找一个比较简便的方法。 本题的实质就是求从城市A到城市D的一条最短路。 1、建立数学模型： Min{d（xk，xk+1）+f（xk+1）}的含义是： 前一个阶段距离加上后一状态变量到终点的最短距离，然后在这些距离和中取最小者，即为所求的最短距离。 其中xk+1=u（xk），即从状态xk出发，采取决策uk到达下一状态xk+1； Sk表示从状态xk 出发的所有可能选取的决策的集合； 而f4（x4）=0称为边界条件，因为状态x4=D已经是终点； 红绿灯的时间设置问题 令狐文艳 摘要 随着经济发展,人口和交通工具的增多,世界各国都面临着交通问题,如何科学地进行交通管理为人们所关注.现考察十字路口的交通管理办法.目前,各国对交叉路口实施交通管理的方法主要有两种,其中红绿灯管理是常见的一种方法. 假设平均流量已知，我们要通过建立数学模型，设定适当的红灯和绿灯时间，在道路保持通畅的基础上，使在一个红绿灯周期内所有车辆在路口停滞的时间之和最短（一辆车在路口的滞留时间通常包括两部分，一部分是每辆车遇红灯后的停车等待时间，另一部分是停车后从启动到正常车速的时间）在本次论文研究中，我们就此问题介绍如何运用Matlab 软件进建立数学建模对实际问题进行最优化处理。 关键词：红绿灯管理Matlab软件最优化处理 The timing of the traffic problem summary Along with the economic development, population and transport increases, the world are facing traffic problems, and how to scientifically, traffic management concern for people. Now examine intersection traffic management solution. Currently, countries in the intersection of traffic management method to basically have two kinds, including traffic management is a common method. The average flow hypothesis, we should known by establishing mathematics model, setting appropriate red and green time, on the basis of keeping unobstructed road, make in a traffic light cycle all vehicles at intersections stagnation total time shortest (a car in the intersection of retention time usually includes two parts, one is each car event of a red light after parking waiting time, another part is after parking from start-up to normal speed in this paper the time) study, we introduce how to use this software Matlab into establishing mathematical modeling of actual problem optimal processing. Keywords: traffic management software Matlab optimum processing 目录 一、问题的提出 作为城市交通的指挥棒，红绿灯对交通的影响起着决定性作用。如果红绿灯的设置不合理，不仅会影响到交通秩序；还有可能会影响到行人和自行车的安全。目前杭城还有很多路口的红绿灯设置存在一些不合理的因素，我们以古墩路一个路口(界于天目山路和文苑路之间)的红绿灯设置为例，该路口是刚开通的，交管部门对路况和车流量的研究还不是很成熟，因此红绿灯的设置存在一些问题。该路口的车流量相对比较小，有 问题重述： 现准备在7 个居民点v 1, v 2, … , v7中设置一银行.问设在哪个点, 最合理？要建2个银行呢？ 解：先作出距离矩阵,如下: D （0）=???????????? ??????????????0 1.5 ∞ ∞ ∞ ∞ ∞ v7 1.5 0 4 ∞ ∞ 2.5 ∞ v6∞ 4 0 3 2 18 ∞ v5∞ ∞ 3 0 6 ∞ ∞ v4∞ ∞ 2 6 0 2 ∞ v3∞ 2.5 18 ∞ 2 0 3 v2∞ ∞ ∞ ∞ ∞ 3 0 v1 v7 v6 v5 v4 v3 v2v1 然后对k=1,2,3…,n 依次利用算法原理中第n 步递归公式，由已知的D n-1各元素确定D n 的各元素值。插入v 1后D （1）的个元素和相应的最短路径因为对成性，D （1）的第一行元素和第一列元素与D (0)相同，D （1）的主对角线上的元素均为0，所以只需要计算其余15个元素的值： D 23(1)=min{d 23(0),d 21(0)+d 13(0)}=min{2,3+∞}=2 D 24(1)=min{d 24(0),d 21(0)+d 14(0)}=min{∞,3+∞}=3 D 25(1)=min{d 25(0),d 21(0)+d 15(0)}=min{18,3+∞ }=3 D 26(1)=min{d 26(0),d 21(0)+d 16(0)}=min{2.5,3+∞}=2.5 D 27(1)=min{d 27(0),d 21(0)+d 17(0)}=min{∞,3+∞}=3 D 34(1)=min{d 34(0),d 31(0)+d 14(0)}=min{6,∞+∞}=6 D 35(1)=min{d 35(0),d 31(0)+d 15(0)}=min{2,∞+∞}=2 D 36(1)=min{d 36(0),d 31(0)+d 16(0)}=min{∞,∞+∞}=∞ D 37(1)=min{d 37(0),d 31(0)+d 17(0)}=min{∞,∞+∞}=∞ D 45(1)=min{d 45(0),d 41(0)+d 15(0)}=min{3,∞+∞}=3 D 46(1)=min{d 46(0),d 41(0)+d 16(0)}=min{∞,∞+∞}=∞ D 47(1)=min{d 47(0),d 41(0)+d 17(0)}=min{∞,∞+∞}=∞ D 56(1)=min{d 56(0),d 51(0)+d 16(0)}=min{4,∞+∞}=4 D 57(1)=min{d 57(0),d 51(0)+d 17(0)}=min{∞,∞+∞}=∞ D 67(1)=min{d 67(0),d 61(0)+d 17(0)}=min{1.5,∞+∞}=1.5 由此可知 D （1）=?? ? ? ??? ?? ? ? ???????????∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞0 1.5 3 1.5 0 4 2.5 4 0 3 2 3 3 0 6 3 2 6 0 2 3 2.5 3 3 2 0 3 3 0,依次插入中间点v 2,v 3,v 4,v 5,v 6,v 7 可得不断更新的距离矩阵为： 题 目：最短路问题 摘要： 1 引言： 图论是应用数学的一个分支，它的概念和结果来源都非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的格尼斯堡七桥问题，以及在民间广泛流传的一些游戏的难题，如迷宫问题，博弈问题等。这些古老的难题，吸引了很多学者的注意。 1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出很大的作用。在实践中，图论已成为解决自然科学，工程技术，社会科学，军事等领域中许多问题的有力工具之一。 最短路问题是图论理论中的经典问题，寻找最短路径就是在指定网络中两节点间找一条距离最小的路。 （1） 基 本 概 念： 定义１ 在无向图G=(V,E,ψ)中： （1）顶点与边相互交错且i i i v v e 1)(-=ψ (i=1,2,…k)的有限非空序列 )(12110k k k v e v e v e v w -= 称为一条从0v 到k v 的通路，记为k v v W 0 （２）边不重复但顶点可重复的通路称为道路，记为k v v T 0 （３）边与顶点均不重复的通路称为路径，记为k v v P 0 A=4 3 21 432105375083802720v v v v v v v v ??????? ? ?∞∞ 定义２ （１）任意两点均有路径的图称为连通图． （２）起点与终点重合的路径称为圈． （３）连通而无圈的图称为树． 定义３ （１）设P(u,v)是赋权图G 中从u 到v 的路径， 则称∑∈= ) ()()(P E e e w P w 为路径P 的权． (2) 在赋权图G 中，从顶点u 到顶点v 的具有最小权的路 ),(*v u P ，称为u 到v 的最短路． 1.实验的目的和要求 了解最短路的算法及应用，会用Matlab 软件求最短路。 2.实验内容和原理 内容:最短路求法,求下图从顶点1u 到其余顶点的最短路。 交通红绿灯管制研究 交通红绿灯管制研究 摘要 交通流模型和红绿灯交通流模型,是城市交通管理的科学依据,是科学设置城市交通管理中红绿灯转换周期的根据.本文通过对交通高峰时期的车流进行模拟，利用粒子群算法，研究如何调整交通灯来分配交通资源，从而尽可能的缓解交通压力。 1.十字路口交通简介 红绿灯有着一套自 己的调度算法，它把车辆 离开的路口当做出口，把 要去往的路口当做入口， 它就是要实现在同一时 间入口的放行量最大化， 也就是尽量保证疏导去 同一个路口的车辆。根据 现代城市的规划方法，十字路口是十分常见的，而设置在十字路口的红绿灯运行起来就更加复杂了。十字路口交通情况如上图所示。其中R表示车辆右拐 L：表示车辆左拐 S:表示车辆直行 P:表示人行数字1、2、3、4表示路口1、2、3、4。 上图中，常规交通灯的 绿灯亮状态（通行）顺 序如左图所示。其中， “1-2”表示1P和2P可以通过路口2通行；“2-3”表示2P和3P可以通过路口3通行；“3-4”表示3P和4P可以通过路口4通行；“4-1”表示4P和1P可以通过路口1通行。2.问题分析与模型的建立 2.1问题的简化与分析 A.在对实际的十字路口交通状况进行了分析之后，我们认为可以对十字路口 进行如下的简化： 首先，车流量的堆积同路口的行人没有实质的联系，在此我们先舍去了行人的影响，即图1-2中的“1-2P, 2-3P, 3-4P, 4-1P”即可舍去。 对大部分的十字路口而言，右转车辆一般直接放行，在这样的简化条件下，我们放弃考虑1R,2R,3R,4R的右转车流量而直接考虑路口的直行和左转车辆。 此外对于大多数的道路而言，在路口处都分为，左、直、右三道行驶，因此，在我们的模型中，将把左、直、右三个方向上的车流视为独立的事件，即这些车辆在十字路口处并不构成互相的干扰而独立行驶。 最后考虑到相对于整个红绿灯的交通周期，黄灯的时间较短且对整个交通的影响较小，因此我们在考虑问题时也忽略黄灯带来的影响。 B.对于交通拥堵的原因，我们进行了如下的分析： 交通的堵塞可以归结为3个原因，一个是由于激增的车流量超出的道路的承载力，从而导致堵车等现象，另一个则是因为道路行驶资源分布不均导致部分地区出现拥挤而部分地区没有的情况，最后则是由于道路维修、车祸等意外情况导致的道路拥挤。 最后一种情况非常容易理解，假设三车道的道路最大承载车流量为3A，那个在出现车祸等情况以后，占用的一个车道，则在事故地截面的承载力下降到2A，若道路上的车流量处于2A-3A之间，则在发生事故以后必将产生道路的阻塞。但是对于红绿灯，我们默认其变化与周期是固定的，因此突发情况不再这个课题的讨论围之。 第一种情况的影响因素只有道路的承载力和激增的车流量本身。即对于承载数学建模,红绿灯闪烁模型
数学建模模最短路
数学建模 红绿灯问题
交通路口红绿灯__数学建模
数学建模--交通问题
数学建模运输问题
数学建模中常见的十大模型
数学建模模最短路
数学建模运筹学模型一
数学建模——交通管理问题
数学建模 绿色波浪红绿灯
浅谈最短路的数学模型解问题
红绿灯的时间设置问题之令狐文艳创作
最短路径问题数学模型
最短路数学建模
道路交通红绿灯管制研究Scilab数学建模计算与分析报告