**大学2011数学建模竞赛暨全国大学生数学建模竞赛选拔赛题目A 题剪切线参赛队编号: CDSM 230摘要本文是对某区域道路网络在某时间段内N辆车从节点1出发到节点0进行分析研究并建立了相关数学模型。

某区域道路网络如图1所示,某时间段内，有N辆车从节点1出发，可设出在该时间段内各路段上通过的总车辆数情况（如图1），由该时间段内道路截面经过的车辆数与车辆在该路段行驶的速度的关系（可根据经验设出）可得出车辆经过各路段的速度，再由各路段的长度可得出车辆经过各路段所需的时间，从而可求出车辆经过7条路线（经分析从节点1到节点0共有7条符合要求的路线）分别所需的时间，所得时间中最长的即为N辆车从节点1到节点0所需要的总行驶时间，比较所有可能分法所需的总行驶时间，时间最短的分法即为有效的行驶路径。

可根据算法设计C++程序，得出有效的行驶路径。

在该算法中，N值取不同的值，可分别得出各条路径车辆数分配比例Xi，再由统计学估算出对任一N值，各条路径车辆数分配比例Xi。

最后利用所得的分配比例，对N=10000进行分配，得到比较近似的有效行驶路径（如图5）。

图1关键词：区域道路网络、有效行驶路径、车辆数分配比例Xi一、问题的重述某区域道路网络如图2所示，每条道路等级完全相同，某时间段内，有N辆车要从节点1出发，目的地是节点0（假设该时间段内，路网中没有其它车辆）。

在该时间段内，道路截面经过的车辆数越多，车辆在该路段行驶的速度就越慢。

（1）确定有效的行驶路径及其算法；（2）确定每条路径上的通过的车辆数，使N辆车从节点1到节点0的总行驶时间最小；（3）N=10000，请给出具体的计算结果。

注：横向路段长度是纵向路段长度的2倍。

图2某区域道路网络图解答：1、确定行驶速度与截面经过的车辆数的关系，能大概反应这种关系就可以；2、给出有效行驶路径（不走回头路的路径，具体定义要由学生给出）的算法；3、引入各条路径车辆数比例变量，描述各路段的截面车辆数，确定各路段内车辆的行驶速度；4、根据目标，建立规划模型（非线性）；5、求解，可以各自发挥，得到比较近似的解就可以。

二、基本假设(1)所计算的交通路段的交通状况正常，所有的车辆性能都处于优的状态，不发生车祸，抛锚，追尾等交通事故。

（2）不考虑由于驾驶员休息、车辆抛锚修理、加油等因素消耗的时间。

（3）进入车道的车辆之间的距离满足最小安全间距，且各车距相等。

（4）忽略发车时间，可理解为N辆车同时发出。

（5）各辆车的车速只与道路截面经过的车辆数有关，与其他因素无关，且车为匀速行驶。

设车速V与车辆数n的关系为：V=K/n（K为常数）。

（6）车辆不走回头路，可理解为行驶路线只能向右向下，即车辆距离目的地越来越近，这样经分析共有7条路线可走。

三、符号说明Q：道路的交通量,如下图3S：纵向路段长度； 2S：横向路段长度；t1：①→②→③→④→⑦→①路线消耗的时间；t2：①→②→③→⑥→⑦→①路线消耗的时间；t3：①→②→③→⑥→⑨→①路线消耗的时间；t4：①→②→⑤→⑥→⑦→①路线消耗的时间；t5：①→②→⑤→⑥→⑨→①路线消耗的时间；t6:①→②→⑤→⑨→⑨→①路线消耗的时间；t7: ①→⑧→⑨→⑨→①路线消耗的时间；X1：N在①处流向②的分配比例；X 2：n1在②处流向③的分配比例；X 3：n3在③处流向④的分配比例；X 4：n1-n3在⑤处流向⑥的分配比例；X 5：n3+n5-n4在⑥处流向⑦的分配比例。

四、模型的建立与求解1.模型的建立如图3，可计算出车辆经过各路段所需的时间，从而求出车辆经过7条路线分别所需的时间，所得时间中最长的即为N辆车从节点1到节点0的总行驶时间，比较所有可能分法所需的总行驶时间，时间最短的分法即为有效的行驶路径。

再由有效的行驶路径分别得出各条路径车辆数分配比例Xi。

具体如下：根据n1、n3、n4、n5、n6，求得t 1=(21n+23n+34n+64nn+)s/k；t 2=(21n+23n+26n+43nn-+64nn+)s/k；t 3=(21n +23n +264n n N --+43n n -+6453n n n n --+)s/k ； t 4=(21n +25n +26n +31n n -+64n n +)s/k ；t 5=(21n +25n +264n n N --+31n n -+6453n n n n --+)s/k ； t 6=(21n +253n n N --+264n n N --+31n n -+531n n n --)s/k ； t 7=(42n +253n n N --+264n n N --)s/k ；②求出t 1~t 7中的最大值。

③比较所有最大值，找出其中最小的，即为有效的行驶路径。

④根据有效行驶路径的n 1、n 3、n 4、n 5、n 6，求出车辆数分配比例X i ： X 1=n 1/N ；X 2=n 3/n 1；X 3=n 4/n 3；X 4=n 5/（n 1-n 3）；X 5=n 6/（n 3+n 5-n 4）。

⑤改变N ，得出不同有效行驶路径下的分配比例X i ，对X i 进行统计处理，得出较为平均的车辆数分配比例，运用该比例进行车辆分配，可得出比较近似的有效行驶路径。

2.模型的求解基于以上模型，用C++程序实现，算法的具体流程图如下（图4）：YN已知各条路线上通过的车辆数n i (i=1,3,4,5,6) 分别求出7条路径总行驶时间t 1~t 7 求出t 1~t 7中最大的数值并存入到数组t []中，同时将对应的n i 存入到数组N i []中，(i=1,3,4,5,6)。

n i(i=1,3,4,5,6)是否符合条件? 找出数组t []中最小的数开始3.模型的实现程序设计如下：#include<stdio.h>#include<math.h>#define N 10 /* 定义总车辆数N */#define M 43000#define MAX(a,b) ((a)<(b)? (b):(a))void main(){ int n1,n3,n4,n5,n6,N1[M],N3[M],N4[M],N5[M],N6[M];/*引入各条路线上通过的车辆数ni及对应存放的数组Ni[]*/unsigned long i=0,j=0,k;float t[M],t1,t2,t3,t4,t5,t6,t7,c1,c2,c3,c4,c5,c6,c;/*定义各条路径的行驶时间t1~t7*/for(n1=0;n1<=N;n1++) /*利用循环判定ni*/for(n3=0;n3<=n1;n3++)for(n4=0;n4<=n3;n4++)for(n5=0;n5<=n1-n3;n5++)for(n6=0;n6<=n3+n5-n4;n6++){t1=2*sqrt(n1)+2*sqrt(n3)+3*sqrt(n4)+sqrt(n4+n6); /*计算各条路径的行驶时间*/t2=2*sqrt(n1)+2*sqrt(n3)+2*sqrt(n6)+sqrt(n3-n4)+sqrt(n4+n6);t3=2*sqrt(n1)+2*sqrt(n3)+2*sqrt(N-n4-n6)+sqrt(n3-n4)+sqrt(n3+n5-n4-n6);t4=2*sqrt(n1)+2*sqrt(n5)+2*sqrt(n6)+sqrt(n1-n3)+sqrt(n4+n6);t5=2*sqrt(n1)+2*sqrt(n5)+2*sqrt(N-n4-n6)+sqrt(n1-n3)+sqrt(n3+n5-n4-n6);t6=2*sqrt(n1)+2*sqrt(N-n3-n5)+2*sqrt(N-n4-n6)+sqrt(n1-n3)+sqrt(n1-n3-n5);t7=4*sqrt(N-n1)+2*sqrt(N-n3-n5)+2*sqrt(N-n4-n6);c1=MAX(t1,t2);c2=MAX(t3,t4); c3=MAX(t5,t6);c4=MAX(c1,t7);c5=MAX(c2,c3); c6=MAX(c4,c5);t[i]=c6;N1[i]=n1;N3[i]=n3;N4[i]=n4;N5[i]=n5;N6[i]=n6;i++;}c=t[0]; /*找出数组t[]中最小的数*/for(j=1;j<i;j++)if(c>t[j]) c=t[j],k=j;printf("n1=%ld n3=%ld n4=%ld n5=%ldn6=%ld",N1[k],N3[k],N4[k],N5[k],N6[k]);/*输出最小的时间t对应数组Ni[]中的ni*/printf("\n");4.模型的运用(1)针对以上程序，结合计算机的处理能力，分别改变N=5~16，分别得出有效行驶路径的n1、n3、n4、n5、n6及Xi，统计Xi得出平均的车辆数分配比例（如图5）图5则X1=0.6263，X2=0.5458，X3=0.6792，X4=0.9514，X5=0.8444。

由此可得出有效行驶路径的分配车辆数：n1=N⨯X1；n2=N-n1；n3=n1⨯X2 ；n4=n3⨯X3；n 5=(n1-n3)⨯X4；n6=（n3+n5-n4）⨯X5；(2)当N=10000时，n1=10000⨯0.6263=6263；n2=10000-6263=3737；n 3=6263⨯0.5458=3418；n4=3418⨯0.6792=2322；n5=（6263-3418）⨯0.9514=2707；n6=（3418+2707-2322）⨯0.8444=3211。

具体分配如图6：图6五、模型的评价与总结1.优点①采用C++程序设计，简化了计算，程序简单易懂。

②根据N=5~16计算出的不同组X i，运用统计学计算出平均的车辆数分配比例，使结果比较科学，误差相对较小。

③计算结果具有普遍意义，即任给一个N，利用所求得的X i，均可给出一个比较合理的有效路径。

2.缺点①在假设时，各辆车的车速与道路截面经过的车辆数的关系可能不够合理。

②由于计算量过大，给计算机软件带了难度，C++程序的运行计算可能存在误差，需要内存更大的计算机来运行。

③X i是根据N在某些具体取值时得出的统计量，用其计算时，与实际的最优解会存在一定的偏差。

这些方面，希望老师批评指正。

参考文献：(1)《C语言程序设计》清华大学出版社（武雅丽王永玲解亚利等编著）(2)《数学规划及应用》第2版冶金工业出版社（范玉妹徐尔周汉良编著）(3)《运筹学》中国人民大学出版社（吴振奎王全文主编）。