超速行车问题的数学模型解决方案

《超速行车问题的数学模型解决方案》由会员分享，可在线阅读，更多相关《超速行车问题的数学模型解决方案（27页珍藏版）》请在装配图网上搜索。

1、数学建模论文所在学校： 河北科技大学 所在学院： 理学院 参赛年级： 11级 参赛学生： 杜玫、马涛、周楠楠 2013年5月31日超速行车问题的数学模型解决方案【摘要】本文要解决的问题是在行车问题中通过对时间和费用的权衡，从而选择出所需的行车路线的方案问题。实际生活中，为了缩短时间和减少费用开支必然会面对路线选择的问题。因此如何快速、高效地从众多可行路线中选出符合题目要求的最优路线成为了解决此问题的关键。鉴于本题路线选择的多样性和路线分布的整齐度，本文中采用了常规的Dijkstra算法。其基本思想是从起点A出发，在每个十字路口选择所要走的路线时根据所给的要求，进行最优选择，从而搜寻出满足要求的

2、最优路线，然后对可行解进行进一步处理，得到明确的路线。针对问题一的两个小问，本文采用了同一算法，只是变换了算法中对应的模型。在第一问中（只考虑速度，即最快达到B），本文将在每个单位路段上以其所给的最高限速行驶时所需要的时间作为每个路段的权值，并选择时间最短作为此问的目标优化模型，并通过VC+编程得到了A与B两点间的一条最优号路线。在第二问中（只考虑费用，即花费最少到达B），本文将在每个单位路段上以其所给的最高限速行驶时所需要的花费作为每个路段的权值，并选择花费最少作为此问的目标优化模型，仍按第一问的算法思路进行VC+编程得到了A与B两点间的最优号路线。针对问题二，根据本题需要同时考虑费用和时间

3、，在本文中根据问题一的第一小问已得出的所需时间最短时选择的号路线，所以问题二只需考虑在此路线选择18个路段可行的超速方案，使在0.8T内可以用最少的花费由A到B，本文中分别将题中的四种限速在不超速（超速0%）以及两种超速（超速10%，超速50%）情况下的花费分别算出，即每个路段上有三种花费情况，将其花费作为对应的路线选择的权值，并选择最少的总花费作为此问的目标优化模型，同样通过VC+编程得到了A与B两点间的最优的超速选择。本文的主要特点在于，所用算法的效率十分显著。在对题目中的数据做简单预处理后便可以进行编程，实现路线的选择，另外，本文所建立的模型简单、所用算法比较清晰。关键字：最短路径 Di

4、jkstra算法 权值的选择1、 问题的重述从A城到B城，路段如下图所示， A在左下角，B在右上角，横向纵向各有10条公路，任意两个相邻的十字路口距离为100公里，所以A城到B城相距1800公里。任意相邻的路段都有限速，如图，单位为km/h。标注为130的路段是高速路段，每段收费3元。整个旅途上的费用有如下两类。第一类与花费时间相关，如住店和饮食，由公式给出，单位为小时。第二类是汽车的油费，每百公里油量(升)由公式给出，其中，的单位为公里/每小时。汽油价格为每升7元。需要解决的问题：1. 遵守所有的限速规定，求时间最短的路线和花费最少的路线分别是哪一条？2.为了防止超速行驶，交警放置了一些固定

5、雷达在某些路段上，如图上红色的路段。另外，他们放置了20个移动雷达。这些雷达等概率地出现在各个路段，你可能在一个路段同时发现多个雷达，也可能在装有固定雷达的路段发现移动雷达。每个雷达都监控了自身所在的整个路段。如果你超速，则你有的可能被雷达探测到，且会被罚款100元；如果你超速，你有的可能被雷达探测到，且会被罚款200元。假设是遵守所有限速规定所花的最少时间，但你有急事想在时间内赶往B城，那么包括罚款在内最少花费多少？路线又是哪一条？2、 问题分析（1） 模型假设1、 当行车到十字路口时，路线选择只能为图的上方或右方；2、 移动雷达出现在每个路段的概率相同，且当多个移动雷达同时出现同一路段时，

6、被罚款的概率不叠加；3、 在安装固定雷达路段，若超速，则必被罚款；4、 超速行车时只考虑超速10%与50%的情况，且无论被移动或固定雷达发现，超速10%罚款100元，超速50%罚款200元；5、 当遵守限速规则的时候，在每个路段上行驶的速度恰都按照所给的限速行驶。（2） 建立模型及求解最短路径问题是网络理论中应用最广泛的问题之一，通过对上题的分析，本文中采用Dijkstra算法12对题中路线分步进行点对点编程录入，然后输出最短路径的结果。1、问题一第一小问，建立模型及求解（用Dijkstra算法12求时间最短路线）本问以时间最短作为最优路线的模型，首先为了方便计算与程序录入，运用下式运算将题的

7、每个路段对应的限速转化为以此速度行驶对应的时间：设t1、t2、t3、t4分别对因为在某路段上分别以行驶所耗的时间，为行驶所用时间的总和，n1、n2、n3、n4分别为通过限速为v1、v2、v3、v4的路段的个数。列式计算，如下式子：目标函数 通过Dijkstra算法12编程取 则可算得 计算得出 根据选择路线，则可得符合题意的号路线为如下图中粗实线所示： BA2、 问题一第二小问，建立模型及求解（用Dijkstra算法12求解花费最少路线）本问以费用最少作为最优路线的模型，在最高限速分别为的公路上遵守所有限速规则且花费最少的时候，所对应的行驶速度仍为（单位：），即，且在本题中已知单位路段花费共有

8、四种情况，为，且计算式为：下面以为例，并计算数据，如下：同理可得 本题中以每个路段对应的最高限速经过该路段所对应的时间分别为（单位：小时），相对应的走过每种不同限速路段的个数为个，设从A到B的总花费为元， 目标函数为 同样通过Dijkstra算法12编程取 则可算得将已知数据代入目标函数解得花费最少的路线总花费为根据的值选择路线，则可得符合题意的号路线为如下图中粗实线所示： BA3、 问题二建立模型及求解，在已知号路线上求花费最少的超速方案分析题后得知，本问需要同时考虑费用和时间，当以第一问所求出的用时最少的路线为基础时，就不用再次考虑时间最短的问题了，故在此选择号路线，所以在此只需考虑号路线

9、上计算18个路段如何分配超速，如何选择超速百分比，使时间可以提高到原来所用时间的80%。且本题建立在下图的路线基础上： BA为了方便数据在算法中的录入，在此我们将题中的四种限速在不超速（超速0%）以及两种超速（超速10%，超速50%）情况下每个路段上的花费、时间分别算出。根据公式如下：超速0%的：超速10%的：超速50%的：以上公式计算将高速路段除外，因为高速路段每段收费3元，所以我们在用上式算出高速路段后再加3元即可，如下：超速0%的：超速10%的：超速50%的：代入数据，计算后将数据做成表格，如下表：速度 项目 50km/h 90km/h超速0%超速10%超速50%超速0%超速10%超速5

10、0%花费符号w1w2w3w4w5w6元4554.0872.6058.0669.2995.89时间符号t1t2t3t4t5t6小时21.821.331.111.010.74 速度 项目 110km/h 130km/h超速0%超速10%超速50%超速0%超速10%超速50%花费符号w7w8w9w10w11w12元65.8077.99108.3476.8589.98124时间符号t7t8t9t10t11t12小时0.910.830.610.770.700.51为了方便计算与录入程序，我们设为此问中花费对应的个数，由题可知在经过的18个路段中，通过限速50km/h的有1段，90km/h的有3段,110

11、km/h的有12段，130km/h的有2段，则可知满足以下限制条件：在此文中设用的总花费为，总时间为，且总时间需要小于等于0.8,所以有以下条件： 目标函数为同样通过Dijkstra算法12编程取 则可算得 即得知超速路段情况如下：速度 项目 1段限速为50km/h 3段限速为90km/h超速0%超速10%超速50%超速0%超速10%超速50%路段个数 001段1段02段 速度 项目 12段限速为110km/h 2段限速为130km/h超速0%超速10%超速50%超速0%超速10%超速50%路段个数07段5段02段0此时验证时间，可得，所以结果满足走法的要求。将上述数据代入此问的目标函数可得3

12、、 模型的算法描述针对问题一的模型，我们采用了Dijkstra算法，将题中图的每个十字路口编号,如下图：我们采用Dijkstra算法，用带权的邻接矩阵edges来表示带权有向图，edgesij表示弧上的权值。那么从a1出发，到图上其余各顶点ai可能达到最短路线，然后搜索出最优路线。针对问题二，我们解题是按照下图中的路线去思考的，如下图： 这一问的思考中，我们将每个路段的花费作为其权值，并且分析题得知，每个路段的走法有三种选择（即从一个路口到下一个路口有三种速度可以选择），速度可以为不超速，超速10%，超速50%，对应的花费也不同，我们在此选择三种速度分别对应的花费为每种选择的权值。即可知从1到

13、2有3种走法，从2到4也有3种走法，从4到7也有3种走法，则从1到4就有种走法，从1到7有种走法，往后依次根据此思想去走。在此我们将Dijkstra算法中部分路线的检索原理（此处仅列出从1到7的路线分析）如下图： 四、模型的优缺点及改进（一）模型的评价1、模型优点本文的模型简单，其算法直观，容易编程实现。本文模型比较注重数据的处理，大大提高了查询效率。本文模型结合有效的算法，使其完全可以满足题目的要求。2、模型缺点在建模与编程过程中，使用的数据在前期计算处理中已经进行了相应的近似，因而得出的结果可能与现实情况有一定的差距。由于数据量大，在算法编程后，录入时也比较繁琐。5、 参考文献1秦锋，数据

14、结构（C语言版），合肥，中国科学技术大学出版社，第194页，20102胡运权，运筹学教程（第三版），北京，清华大学出版社，第250页，2008六、附录（一）问题一程序代码1、时间最短路线#include stdio.h#include iostream.h#include fstream.h/输入输出流#include stdlib.h#define mvnum 1000/最大定点数#define maxint 999999typedef char vertextype;typedef int adjmatrix;struct mgraph vertextype vexsmvnum;/顶点数组

15、，假定为 char型 adjmatrix arcsmvnummvnum;/临街矩阵，假定为int型;double dmvnummvnum,pmvnummvnum;/void createmgraph(mgraph *G)/采用邻接矩阵表示法构造无向图Gint i,j,k,w;ifstream graphlist(map.txt,ios:in);/定义一个流对象，并且和文件关联for(i=1;ivexsi=(char)i;for(i=1;i=100;i+)for(j=1;jarcsij=maxint;/初始化邻接矩阵for(k=1;ki;graphlistj;graphlistw; G-arcs

16、ij=w;G-arcsji=G-arcsij;/构造无向网/cout图的存储结构建立完毕！endl;graphlist.close();/关闭文件/void floyd(mgraph *G)int i,j,k;for(i=1;i=100;i+)/设置路径长度D和路径初值for(j=1;jarcsij!=maxint) pij=j;elsepij=0;dij=G-arcsij;for(k=1;k=100;k+)for(i=1;i=100;i+)for(j=1;j=100;j+)if (dik+dkjdij) dij=dik+dkj;pij=pik;/void main() mgraph *G;i

17、nt v,w,k;int xz=1;G=(mgraph *)malloc(sizeof(mgraph);cout欢迎进入公路交通网查询系统.endl;createmgraph(G);while(xz!=0) cout*求城市之间最短路径*endl; cout=endl; cout请选择：1 查询 0 结束endl; cout=xz; coutendl; if(xz) floyd(G); cout城市名称及编号如下endl; cout 1 2 3 4 5 endl; cout 6 7 8 9 10 endl; cout 11 12 13 14 15 endl; cout 16 17 18 19

18、20 endl; cout 21 22 23 24 25 endl; cout 26 27 28 29 30 endl; cout 31 32 33 34 35 endl; cout 36 37 38 39 40 endl; cout 41 42 43 44 45 endl; cout 46 47 48 49 50 endl; cout 51 52 53 54 55 endl; cout 56 57 58 59 60endl; cout 61 62 63 64 65endl; cout 66 67 68 69 70 endl; cout 71 72 73 74 75 endl; cout 76

19、 77 78 79 80endl; cout 81 82 83 84 85endl; cout 86 87 88 89 90endl; cout 91 92 93 94 95 endl; cout 96 97 98 99 100endl; cout请输入源点和终点: vw; k=pvw;/k为起点i的后继顶点 if(k=0) cout无路径！endl; else cout所求最短路径为：endl; coutv; while(k!=w) coutk; k=pkw; coutw; cout路径长度为：dvw公里endl; coutendl; else cout谢谢使用，祝您旅途愉快！endl; 2

20、、 花费最少路线#include stdio.h#include iostream.h#include fstream.h/输入输出流#include stdlib.h#define mvnum 1000/最大定点数#define maxint 9999999typedef char vertextype;typedef int adjmatrix;struct mgraph vertextype vexsmvnum;/顶点数组，假定为 char型 adjmatrix arcsmvnummvnum;/临街矩阵，假定为int型;double dmvnummvnum,pmvnummvnum;/vo

21、id createmgraph(mgraph *G)/采用邻接矩阵表示法构造无向图Gint i,j,k,w;ifstream graphlist(map.txt,ios:in);/定义一个流对象，并且和文件关联for(i=1;ivexsi=(char)i;for(i=1;i=100;i+)for(j=1;jarcsij=maxint;/初始化邻接矩阵for(k=1;ki;graphlistj;graphlistw; G-arcsij=w;G-arcsji=G-arcsij;/构造无向网/cout图的存储结构建立完毕！endl;graphlist.close();/关闭文件/void floyd

22、(mgraph *G)int i,j,k;for(i=1;i=100;i+)/设置路径长度D和路径初值for(j=1;jarcsij!=maxint) pij=j;elsepij=0;dij=G-arcsij;for(k=1;k=100;k+)for(i=1;i=100;i+)for(j=1;j=100;j+)if (dik+dkjdij) dij=dik+dkj;pij=pik;/void main() mgraph *G;int v,w,k;int xz=1;G=(mgraph *)malloc(sizeof(mgraph);cout欢迎进入铁路交通网查询系统.endl;createmgr

23、aph(G);while(xz!=0) cout*求城市之间花费最少*endl; cout=endl; cout请选择：1 查询 0 结束endl; cout=xz; coutendl; if(xz) floyd(G); cout城市名称及编号如下endl; cout 1 2 3 4 5 endl; cout 6 7 8 9 10 endl; cout 11 12 13 14 15 endl; cout 16 17 18 19 20 endl; cout 21 22 23 24 25 endl; cout 26 27 28 29 30 endl; cout 31 32 33 34 35 end

24、l; cout 36 37 38 39 40 endl; cout 41 42 43 44 45 endl; cout 46 47 48 49 50 endl; cout 51 52 53 54 55 endl; cout 56 57 58 59 60endl; cout 61 62 63 64 65endl; cout 66 67 68 69 70 endl; cout 71 72 73 74 75 endl; cout 76 77 78 79 80endl; cout 81 82 83 84 85endl; cout 86 87 88 89 90endl; cout 91 92 93 94

25、 95 endl; cout 96 97 98 99 100endl; cout请输入源点和终点: vw; k=pvw;/k为起点i的后继顶点 if(k=0) cout无路径！endl; else cout所求花费最少为：endl; coutv; while(k!=w) coutk; k=pkw; coutw; cout权重：dvw权。endl; coutendl; else cout谢谢使用，祝您旅途愉快！endl; （二）问题二程序代码#includevoid main()int n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,n12,n13,n14,n15,n16,

26、n17,n18,i=0,j;double t18,w18,T=0,W=0,Wmin=100000;for(n1=0;n13;n1+)if(n1=0)w1=65.80;t1=0.91;else if(n1=1)w1=140.19;t1=0.83;elsew1=268.34;t1=0.61;for(n2=0;n23;n2+) if(n2=0) w2=65.80; t2=0.91; else if(n2=1) w2=140.19; t2=0.83; else w2=268.34; t2=0.61; for(n3=0;n33;n3+) if(n3=0) w3=65.80; t3=0.91; else

27、if(n3=1) w3=140.19; t3=0.83; else w3=268.34; t3=0.61;for(n4=0;n43;n4+) if(n4=0) w4=65.80; t4=0.91; else if(n4=1) w4=140.19; t4=0.83; else w4=268.34; t4=0.61; i+;for(n18=0;n183;n18+) if(n18=0) w0=65.80; t0=0.91; else if(n18=1) w0=140.19; t0=0.83; else w0=268.34; t0=0.61; i+;for(n5=0;n53;n5+) if(n5=0)

28、 w5=65.80; t5=0.91; else if(n5=1) w5=140.19; t5=0.83; else w5=268.34; t5=0.61;for(n6=0;n63;n6+) if(n6=0) w6=65.80; t6=0.91; else if(n6=1) w6=140.19; t6=0.83; else w6=268.34; t6=0.61; for(n7=0;n73;n7+) if(n7=0) w7=65.80; t7=0.91; else if(n7=1) w7=140.19; t7=0.83; else w7=268.34; t7=0.61; i+;for(n8=0;

29、n83;n8+) if(n8=0) w8=65.80;t8=0.91; else if(n8=1) w8=140.19;t8=0.83; else w8=268.34;t8=0.61;for(n9=0;n93;n9+) if(n9=0) w9=65.80; t9=0.91; else if(n9=1) w9=140.19; t9=0.83; else w9=268.34; t9=0.61;for(n10=0;n103;n10+) if(n10=0) w10=65.80; t10=0.91; else if(n10=1) w10=140.19; t10=0.83; else w10=268.34

30、; t10=0.61;for(n11=0;n113;n11+) if(n11=0) w11=65.80; t11=0.91; else if(n11=1) w11=140.19; t11=0.83; else w11=268.34; t11=0.61;for(n12=0;n123;n12+) if(n12=0) w12=73.85;t12=0.77; else if(n12=1) w12=149.18; t12=0.70; else w12=281.00; t12=0.51; for(n13=0;n133;n13+) if(n13=0) w13=73.85; t13=0.77; else if

31、(n13=1) w13=149.18; t13=0.70; else w13=281.00; t13=0.51; for(n14=0;n143;n14+) if(n14=0) w14=58.06; t14=1.11; else if(n14=1)w14=131.49; t14=1.01; else w14=255.89; t14=0.74; for(n15=0;n153;n15+) if(n15=0) w15=58.06; t15=1.11; else if(n15=1) w15=131.49; t15=1.01; else w15=255.89; t15=0.74;for(n16=0;n163;n16+) if(n16=0) w16=58.06; t16=1.11;