《超速行驶问题》由会员分享，可在线阅读，更多相关《超速行驶问题（11页珍藏版）》请在金锄头文库上搜索。
1、超速行驶问题摘要 本文主要研究的是探讨驱车从始发地至目的地的最短时间路径问题和最少花费问题，以及在超速情况下的最短时间和最少花费问题。首先，从整个题目的两个问题入手，发现两个问题都是优化问题，具有一定的联系。然后针对第一问，本文建立了0-1规划的优化模型，根据模型的约束条件及矩阵的含义进行编程，找出所有可能出现的路径，每种路径对应两个0-1矩阵，分别表示横向路线和纵向路线，再将两个矩阵分别点乘横向路线与纵向路线所表示的时间矩阵，从而由目标函数利用计算机得出最优解17.78小时，并找出时间最短的路线为：然后，对于花费最少问题，本文建立了在每段公路上费用与速度的关系式，根据求极小值，找出每段公路花
2、费最少时的速度，从而可计算每段公路的花费最少的金额，再根据时间最短路线的算法，给每段公路赋值（最少花费），可得最优解为274.64元，其中一条花费最少的路线为：最后，考虑到罚款问题，本文建立了汽车超速百分比分别与被探测可能性和罚款金额的线性关系式，以及每段公路超速罚款金额的期望值与超速百分比的线性关系式，并假设在整个路线中的速度保持不变，即可计算得出每段公路在最小速度的条件下的花费（包括罚款），再利用问题一的0-1规划模型算出汽车在0.8T时间内到达B城最少的花费为524.99元，找出该路线为： 在所得结果的基础上，我们再次进行模型的修改与优化，并能将此题的解法应用于车辆监控导航系统中。关键词
3、：0-1规划 最优化 线性关系 极小值 概率 期望 一、问题重述你驱车从A城赶往B城。A城和B城间的道路如下图所示， A在左下角，B在右上角，横向纵向各有10条公路，任意两个相邻的十字路口距离为100公里，所以A城到B城相距1800公里。任意相邻的十字路口间的一段公路(以下简称路段)都有限速，标注在图上，单位为公里每小时。标注为130的路段是高速路段，每段收费3元。整个旅途上的费用有如下两类。第一类与花费时间相关，如住店和饮食，由公式c1=5t;给出，t单位为小时。第二类是汽车的油费，每百公里油量(升)由公式c2=av+b;给出，其中a=0.0625，b=1.875,v的单位为公里/每小时。汽
4、油价格为每升1.3元。请建立数学模型，解决以下问题：1. 若你遵守所有的限速规定，那么时间最短的路线和花费最少的路线分别是哪一条？2.为了防止超速行驶，交警放置了一些固定雷达在某些路段上，如图上红色的路段。另外，他们放置了20个移动雷达。这些雷达等概率地出现在各个路段，你可能在一个路段同时发现多个雷达，也可能在装有固定雷达的路段发现移动雷达。每个雷达都监控了自身所在的整个路段。如果你超速10%，则你有70%的可能被雷达探测到，且会被罚款100元；如果你超速50%，你有90%的可能被雷达探测到，且会被罚款200元。假设T是遵守所有限速规定所花的最少时间，但你有急事想在0.8T时间内赶往B城，那么
5、包括罚款在内最少花费多少？路线又是哪一条？二、问题分析 本题是一个对选择路线的优化问题，需要对每段路线的最短时间及最少费用的最佳速度进行分析，并找出它们的联系。 对于问题一，若要找出时间最短的路线，必须知道车在每段公路不超速的前提下的最少时间，将每段公路行驶的最短时间作为此公路的权值，并且必须限定车的行驶方向为向右或向上，因此车最少需经过18条公路，在此基础上，我们建立0-1规划模型，建立以路线的最少时间为目标函数，以汽车行驶方向和经过的公路总数建立约束条件，然后设计可行程序，寻找时间最短路线，并依据目标函数计算出最短时间。对于第一问中的花费最少的路径，我们只需计算在每条公路上的最少花费，而花
6、费与时间和油量相关，而时间和油量都与速度相关，因此我们只需建立一个以速度为自变量和以花费为因变量的函数关系式，利用求极小值的方法求出每段路上最少花费对应的速度，再计算出每段路对应的最少花费，然后转化为求时间最短路线的问题，将每段公路行驶的最少花费作为此公路的权值，从而可以寻找出花费最少的路线，并计算出最少的费用。 对于问题二，分析题目可知汽车超速的百分比分别与汽车被雷达探测到的可能性和超速罚款金额线性相关，因此我们可建立超速百分比分别与被探测可能性和罚款金额的线性关系式，由每段路汽车超速被探测到的可能性（考虑是否固定雷达）和罚款金额可知在这段路罚款金额的期望值，从而建立每段公路超速罚款金额的期
7、望值与超速百分比的线性关系式。由于有急事从A城到B城，我们假设在这途中的速度保持不变，则由时间的限定，我们可得到可行速度的一个下限，根据这个速度我们可分别计算出限速50、90、11、130千米每时的公路上的所有费用（包括住店、饮食、油费、收费及罚款），接着利用问题一的0-1规划模型算出汽车在0.8T时间内到达B城最少的花费，并找出该路线。 三、模型假设1、车在每个十字路口只能选择往上或往右行驶。 2、因为有急事，减速与加速的转换过于麻烦，所以我从A城到B城的途中的速度不发生改变。四、符号说明 每条路段相交的点形成的矩阵每条路段相交的点B横向路段形成的矩阵每段横向路的坐标C纵向路段形成的矩阵每段
8、纵向路的坐标W每个横向路段在限速范围内所用最少时间形成的矩阵每个横向路段在限速范围内所用最少时间V每个纵向路段在限速范围内所用最少时间形成的矩阵每个纵向路段在限速范围内所用最少时间X矩阵B点乘矩阵W矩阵B与矩阵W对应的元素相乘Y矩阵C点乘矩阵V矩阵C与矩阵V对应的元素相乘Z所选从A到B总路段的时间点乘在限速的范围内，每段路花费最少时的速度在限速的范围内，每段路花费最少时的金额在限速的范围内，每个横向路段所用最少花费在限速的范围内，每个纵向路段所用最少花费矩阵B点乘矩阵所选横向路段所用最少费用矩阵C点乘矩阵所选纵向路段所用最少费用所选路段总共的费用包括罚款在内的每段路所花费的费用P被测到的概率Q
9、被罚款的金额每段路是否有雷达的概率包括罚款在内，所选路段所用总共的金额M在不变的速度下，每个横向路段包括罚款金额在内的所用费用N在不变的速度下，每个横向路段包括罚款金额在内的所用费用超速的百分比 五、模型建立及求解5.1时间最短路线及花费最少路线5.1.1时间最短路线求时间最短路线，需知每段公路的最短时间，然后将每种可能的路线的每段公路附上该公路相应的最少时间，最后求和取最小值。由题目所给图，设点A为点，点B为点，即可把每个路口用点表示出来如下：定义= ， 每段公路行驶的最短时间 i,j=0、19， v表示每段公路的限速以路段的最少时间和建立目标函数如下：从而可得约束条件 st由约束条件利用计
10、算机设计可行程序并得出可行路线（见附表1）将横向路段选取与否用0-1矩阵表示为 将纵向路段选取与否用0-1矩阵表示为 横向每个路段最少时间表示的矩阵为 W=纵向每个路段最少时间表示的矩阵为 V=从而横向与纵向所有选取路段的花费分别为 ， 即 ， 由计算机计(见附件4)算可得最优路线为（见附件1）最短时间为17.78小时。5.1.2花费最少的路线花费最少的路线实质上是在上一问中矩阵W与V的改变，由每段公路的最少时间改变为每段公路的最少花费，而我们的花费与汽车行驶的速度有关，因此我们将每一段花费最少时速度利用求极值算出，并计算出每段路最少的花费。由公式得： 令 , 则能得到极小值点v=78.45
11、即求的花费最少时的速度为v=78.45（其中a=0.0625,b=1.875, 的取值在自身公路限速的范围之内，如50、90、110、130以内）例若该段路限速 最少花费以下为不同限速路段花费最少的速度与最少花费金额的图表：每段路的最少花费Z花费最少时的速度5078.4578.4578.45该短路最少的花费16.515.184515.184518.1845图5-1则建立花费最少的目标函数为则依据上述模型将W，V矩阵按上诉表格进行替换为： 由计算机改变相应的矩阵（见附件5），运算可得最少花费的路线共有3312条，其中一条的路线为（见附件2），最少花费的金额为274.64元，所选择的路线不止一条,
12、共有3312条路线。5.2由题意知图中红色线段必有雷达还有20个移动雷达，由图知共有180条路，则该段路有雷达的概率为：由题中得：如果超速10%，则有70%的可能被雷达探测到，且会被罚款100元；如果超速50%，有90%的可能被雷达探测到，且会被罚款200元。可以得到超速的百分比与被雷达测到的概率成一个线性关系即： 可以得到超速的百分比与被罚款的金额成一个线性关系即： 则若超速被罚款的期望为： 假设该车在每一段路上行驶的速度是不变的即因为在0.8T时间内赶往B城，由第一题已知既要满足即若要以不变的速度从A到B则至少要行驶的速度为126.55公里每小时要使罚款最少，则速度取最小值即可，设该段路超
13、速的百分比为当速度为时，每段路的包括罚款的花费为：当速度为，各个路包括罚款在内的，为：见下表 路段限速50路段红色的限速50路段限速90路段红色的限速90路段限速110路段限速130路段超速百分比1.5311.5310.40610.40610.15050该段路的花费71.9939664.615833.4023167.255325.746419.6707图5-2则横向每段路的花费矩阵为：纵向每段路的花费矩阵为：由模型一得该题的目标函数为： 在进行问题一的模型的程序(见附件6)得出包括罚款花费最少为524.99，所选路径为：（见附件3）综上所得，本题时间最短路线、花费最少路线及包括罚款的话费最少路
14、线如下图：图5-3七、模型检验 我们将模型所得的路线，找出路线所得的每段公路并求出在此公路上的时间再求和，所得结果与计算机所得结果完全吻合，说明我们的计算非常的准确。但在问题二中，若我们在每段公路选取不同的速度，在时间的限制条件下，计算每段公路所用花费，再求和，发现所得结果小于我们所得的最优路线的花费总额，由此说明，给整个路线赋予固定的速度，所算的结果并不是最优，在此基础上，我们对模型进行修改，如在问题二中，计算得出的是速度不变的情况下，包括罚款在内的花费最少的路线，由上题知，在限速50公里每小时的红色路段，花费为664.6158元，所以可以在程序的数组中将664.6158改成无穷大，编程验证结果。另外可以将限速50公里每小时的红色路段和限速90公里每小时的红色路段的花费改成无穷大，得出最短路线。 八、模型评价模型优点：1、模型原理简单明了，求解过程直观、简洁，且容易理
