超速行驶问题.doc

超速行驶问题————————————————————————————————作者:————————————————————————————————日期: 超速行驶问题摘要本文主要研究的是探讨驱车从始发地至目的地的最短时间路径问题和最少花费问题,以及在超速情况下的最短时间和最少花费问题。首先,从整个题目的两个问题入手,发现两个问题都是优化问题,具有一定的联系。然后针对第一问,本文建立了0-1规划的优化模型,根据模型的约束条件及矩阵的含义进行编程,找出所有可能出现的路径,每种路径对应两个0-1矩阵,分别表示横向路线和纵向路线,再将两个矩阵分别点乘横向路线与纵向路线所表示的时间矩阵,,并找出时间最短的路线为:然后,对于花费最少问题,本文建立了在每段公路上费用与速度的关系式,根据求极小值,找出每段公路花费最少时的速度,从而可计算每段公路的花费最少的金额,再根据时间最短路线的算法,给每段公路赋值(最少花费),,其中一条花费最少的路线为:最后,考虑到罚款问题,本文建立了汽车超速百分比分别与被探测可能性和罚款金额的线性关系式,以及每段公路超速罚款金额的期望值与超速百分比的线性关系式,并假设在整个路线中的速度保持不变,即可计算得出每段公路在最小速度的条件下的花费(包括罚款),再利用问题一的0-,找出该路线为:在所得结果的基础上,我们再次进行模型的修改与优化,并能将此题的解法应用于车辆监控导航系统中。关键词:0-1规划最优化线性关系极小值概率期望一、问题重述你驱车从A城赶往B城。A城和B城间的道路如下图所示,A在左下角,B在右上角,横向纵向各有10条公路,任意两个相邻的十字路口距离为100公里,所以A城到B城相距1800公里。任意相邻的十字路口间的一段公路(以下简称路段)都有限速,标注在图上,单位为公里每小时。标注为130的路段是高速路段,每段收费3元。 整个旅途上的费用有如下两类。第一类与花费时间相关,如住店和饮食,由公式c1=5t;给出,t单位为小时。第二类是汽车的油费,每百公里油量(升)由公式c2=av+b;给出,其中a=,b=,v的单位为公里/每小时。。请建立数学模型,解决以下问题:,那么时间最短的路线和花费最少的路线分别是哪一条?,交警放置了一些固定雷达在某些路段上,如图上红色的路段。另外,他们放置了20个移动雷达。这些雷达等概率地出现在各个路段,你可能在一个路段同时发现多个雷达,也可能在装有固定雷达的路段发现移动雷达。每个雷达都监控了自身所在的整个路段。如果你超速10%,则你有70%的可能被雷达探测到,且会被罚款100元;如果你超速50%,你有90%的可能被雷达探测到,且会被罚款200元。假设T是遵守所有限速规定所花的最少时间,,那么包括罚款在内最少花费多少?路线又是哪一条?二、问题分析本题是一个对选择路线的优化问题,需要对每段路线的最短时间及最少费用的最佳速度进行分析,并找出它们的联系。对于问题一,若要找出时间最短的路线,必须知道车在每段公路不超速的前提下的最少时间,将每段公路行驶的最短时间作为此公路的权值,并且必须限定车的行驶方向为向右或向上,因此车最少需经过18条公路,在此基础上,我们建立0-1规划模型,建立以路线的最少时间为目标函数,以汽车行驶方向和经过的公路总数建立约束条件,然后设计可行程序,寻找时间最短路线,并依据目标函数计算出最短时间。对于第一问中的花费最少的路径,我们只需计算在每条公路上的最少花费,而花费与时间和油量相关,而时间和油量都与速度相关,因此我们只需建立一个以速度为自变量和以花费为因变量的函数关系式,利用求极小值的方法求出每段路上最少花费对应的速度,再计算出每段路对应的最少花费,然后转化为求时间最短路线的问题,将每段公路行驶的最少花费作为此公路的权值,从而可以寻找出花费最少的路线,并计算出最少的费用。对于问题二,分析题目可知汽车超速的百分比分别与汽车被雷达探测到的可能性和超速罚款金额线性相关,因此我们可建立超速百分比分别与被探测可能性和罚款金额的线性关系式,由每段路汽车超速被探测到的可能性(考虑是否固定雷达)和罚款金额可知在这段路罚款金额的期望值,从而建立每段公路超速罚款金额的期望值与超速百分比的线性关系式。由于有急事从A城到B城,我们假设在这途中的速度保持不变,则由时间的限定,我们可得到可行速度的一个下限,根据这个速度我们可分别计算出限速50、90、11、130千米每时的公路上的所有费用(包括住店、饮食、油费、收费及罚款),接着利用问题一的0