数学建模班车的合理安排.docx

资源描述

数学建模班车的合理安排.docx

《数学建模班车的合理安排.docx》由会员分享，可在线阅读，更多相关《数学建模班车的合理安排.docx（33页珍藏版）》请在冰点文库上搜索。

数学建模班车的合理安排.docx

数学建模班车的合理安排

第十一届学科竞赛之数学建模竞赛

承诺书

我们仔细阅读了大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括、电子、网上咨询等）与队外的任何人研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

我们授权河大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）：

参赛队员（打印并签名）：

序号

姓名（打印）

所在学院（打印）

签名（手签）

郭廷桢

物理与机电工程学院

晓明

物理与机电工程学院

岳春烈

物理与机电工程学院

指导教师或指导教师组负责人（打印并签名）：

日期：

2015年5月24日

评阅编号（由竞赛组委会评阅前进行编号）：

第十一届学科竞赛之数学建模竞赛

评阅专用页

评阅编号（由竞赛组委会评阅前进行编号）：

评阅记录（供竞赛组委会评阅时使用）：

评

阅

人

评

分

备

注

评阅结果：

获奖等级：

班车的合理安排

摘要：

本文针对班车的合理安排,关于发车时间、线路、每条路线的运行时间、班次和各个车辆的耗油成本的问题建立相应的数学模型，在问题解决过程中采用了穷举算法和递归算法。

分析、建立模型、求解过程中，利用MATLAB对数据进行分析、处理，并用C语言实现某些算法，得出相应的结论。

问题1通过分析题中所给的数据，对线路1每天乘坐人数建立单因素方差分析模型，假设临界值为0.05，在MATLAB中用函数P=anoval（X）来计算概率值，得出P>>0.05，故认为问题1结果不存在显著的差异。

问题2根据题中所给数据，通过研究分析，建立派车最优化组合模型，再增加耗油成本变量，建立单目标最优化模型，再通过C语言运用穷举法求出最优解，得出每日最低耗油成本同时确定了班车的安排方式，其安排方式见表5.6所示。

对于问题3在问题2的基础上进一步考虑班车之间运行的相互影响，深入改善建立单目标最优化模型，采用C语言穷举法求出班车运行时的最低耗油成本，得出最佳行车组合方式，其安排方式见表5.9所示。

关键字：

优化模型、C语言穷举算法、MATLAB单因素方差分析、递归算法

1、问题重述

班车的合理安排是一个优化合理模型。

必须保证每位教职工有座且准时到达目的地，要考虑路线最佳车辆分配最为合理；也就是说在能保证老师被安全准时的前提下，车辆的安排要最省钱，也就最优分配；再分配过程中要考虑每辆车运送时间差是否满足运输时刻表的安排，同时也要考虑班车的座位是否满足需求。

如何在校车运行与节约资源取得最大效益，已经成为了困扰众多高校的问题之一。

本文就是为了解决这一问题而撰写的。

某高校地处市郊，共设立了五条不同方向的接送线路，从周一至周五每天用班车接送居住在市区沿途线路的教职工。

这五条线路市区与学校之间的平均运行时间依次分别需要45分钟，70分钟，60分钟，20分钟和50分钟。

目前学校配有五辆班车，分别是55座、45座、40座、33座和26座，根据经验和当前油价，这五辆班车的油耗大约分别是5元/分钟、4元/分钟、4元/分钟、3元/分钟和2元/分钟。

此外，由于周一至周五每日的课程安排不同，因此每日乘坐同一班次的教职工人数也是不同的。

（1）对各条线路而言，每日早晨07:

00从市区用哪一辆班车到学校，下午17:

40就用这辆班车回到市区。

（2）要求每班次的车都应当保证有充足的座位，即不能出现有人因座位不足而站着的情况。

（3）若校车到达终点站时，距离终点站返回学校下一班车时刻时尚早，或该终点站当日已经没有返回学校的班次，则空车返回学校或者视情况考虑安排到另一个线路的终点站再沿途接入学校。

2、符号说明

班车A:

55座，耗油5元/分钟；

班车B：

45座，耗油4元/分钟；

班车C：

40座，耗油4元/分钟；

班车D：

33座，耗油3元/分钟；

班车E：

26座，耗油2元/分钟；

S（i）:

星期一到星期五中每班次车最多人数

Fy：

A、B、C、D、E五辆车对应的价格/每分钟

Sj：

每条路线运行时长

：

因素A的效应平方和；

：

误差的平方和；

：

总和、

；线路1每天每班次车所对应的人数；

Hy：

耗油量

Cz（i）：

班车A、B、C、D、E的车座个数

三、问题分析

本问题是合理优化模型。

必须保证每位老师有座并且准时到达目的地，且要考虑线路最佳车辆分配最为合理；具体就是在能保证老师被安全准时接送的条件下，车辆的安排要最省钱，也就是最优分配；在分配过程中要考虑每辆车运送时的时间差是否满足运输时刻表的安排。

为方便建模求解经过分析将班次和时间绑定起来在分析过程中就可以简化一个决策变量，方便分析。

为使每位老师都有座位我们把乘坐各班次的人数统计表中取其最大值，以保证每位老师都可以准时有座往返。

尽可能在不影响建模求解准确性的情况下，简化决策变量，并以表格形式给出。

3.1问题1的分析

问题1属于单因素实验方差分析的数学问题，解决此类问题一般用数学方法分析。

由附件中给出的数据特点分析，取出其中的最大值建立模型、编程、对其所要求的结果进行分析。

由于上述原因，建立单因素方差分析模型，对结果进行预测，并将结果进行比较。

对问题1的具体分析如下：

由于各个学校的排课时间不同，各教职工所居住的地方各不相同，因此，考虑线路1周一至周五教职工的乘车情况各不相同，现就此问题进行分析，将分析求出星期一至星期五平均每天运送的教职工人数差异。

3.2问题2的分析

由于许多城市交通拥挤，上班坐车不方便，经常遇到堵车或乘不上车等诸多问题，使得教职工不能按时到达指定的地点，现就此问题进行分析、讨论、建立数学模型,分配出合理的班次及路线。

对问题2的具体分析如下：

问题2属于最优组合的数学问题，解决此类问题用数学分析法排列组合最佳的分配组合方式。

运用穷举法和递归法解决排列组合的最优值。

3.3问题3的分析

对问题3的具体分析如下：

又考虑到车空返回时耗油成本问题，进行对问题的进一步优化，在问题二的基础上减少车的空泛情况在满足教职工人数和时间要求的基础上使得耗油成本达到最低，使问题更进一步得到优化。

在问题三中，对于到达终点站距离该终点站返回学校的下一班车发车时刻尚早，或该终点站当日已经没有返回学校的班次，这时不必非得空车返回学校，可视情况考虑安排到另一个线路的终点站，再沿途接人到学校这一类情况。

我们也可以确定一个新的分类方式与油耗成本计算方法。

在所有的问题中，我们都要考虑到各站点运行时间问题和座位满足问题。

同时也要考虑单位时间油耗成本问题。

4、模型的假设

在问题一的模型建立与数据处理计算中首先假设如表4.1中每天每班次车的人数都服从正态分布，即：

。

表4.1一星期中每天最多人数统计图

班次1

班次6

班次13

班次7

班次8

班次14

班次15

星期一

星期二

星期三

星期四

星期五

在问题二三的建模中我们假设：

1、沿途没有堵车现象出现；

2、每位教职工都能按时的在接送点等车并且上车时间忽略不计；

3、所给数据基本上真实有效无误差；

4、每位教职工临时有事请假不记。

图4.1市区与学校分布图

五、模型的建立与求解

5.1问题1的模型建立与求解

5.1.1问题1的模型建立

为了比较线路一中星期一到星期五每天运送的教职工人数是否存在显著差异，分别以

代表星期一至星期五每天总人数的平均值，我们需要检验假设（

）

表4.1中所有变量：

n=35，种类：

r=5，各种类对应变量：

n1=n2=n3=n4=n5=7，

表5.1单因素方差分析表

方差来源

平方和

自由度

均方和

F值

显著性

因子影响

随机误差

总和

要分析线路1星期一至星期五平均每天运送的教职工是否存在显著差异先求线路1每天所要运送的教职工人数S,首先验证S是否符合正态分布（这里显然是的）再以线路一每天所要运送的额教职工人数为检验变量进行单样本f检验。

5.1.1问题1的模型求解

在MATLAB中使用p=anova1（X）比较X中各列数据的均值是否相等。

此时输出的p是零假设成立时，数据的概率，当p<0.05称差异是显著的，当p<0.01称差异是高度显著的。

在MATLAB中输入如下程序：

X=[44253513271545

52204012381840

38153823451245

46183616431542

50203221391650];

A=X';

group=['星期一',;'星期二',;'星期三',;'星期四',;'星期五'];

p=anova1（A,group）;

所得结果如下所示：

图5.1单因素方差分析的ANOVA表格

ANVOA表格共包含6列，每列的意义如下：

第一列为source项，即方差来源；第二列给出每一项来源的平方和SS；第三列给出每一项来源的自由度df，即包含的数据总数；第四列给出每一项来源的均方MS=SS/df；第五列给出F比，也就是MS的比率。

图5.2矩阵X箱线图

从图5.1中可以看出，P>0.05，所以线路1星期一至星期五平均每天运送教职工人数不存在明显的显著差异。

5.2问题2的模型建立与求解

5.2.1问题2的模型建立

（1）为使我们建立模型方便计算，我们简化表格减少决策变量，因为首先虑班车的座位是否满足需求，对一星期之中每班次车乘坐人数取最大值，所以得如下表格

表5.2每班次车对应最多人数表

班次

人数

班次

人数

表5.3每日班车发车时刻及班次编号

线

路

方

向

发车

时刻

班次

编号

发车

时刻

班次

编号

发车

时刻

班次

编号

发车

时刻

班次

编号

上行

07:

09:

13:

下行

09:

12:

15:

17:

上行

07:

12:

下行

12:

17:

上行

07:

12:

下行

17:

上行

07:

下行

12:

17:

上行

07:

下行

17:

（2）建立模型，首先考虑每班次的车都应当保证有充足的座位，再对剩余的进行排列组合，根据耗油费最少解出最优解。

表5.4班次1-5与班次15-19最多人数

班次1

班次2

班次3

班次4

班次5

人数

班次15

班次16

班次17

班次18

班次19

人数

在07:

00时五条路线要同时发车，且学校只有五辆校车，要同时从五条线路发车，再考虑满足座位需求的情况下，再对运费进行计算，则有唯一的派车方式，班次1，2,3,4,5分别派出A,E,D,C,B车，同理考虑满足座位需求的情况下，班次15到班次19也已经确定了派车安排方式。

表5.5班次6-14最多人数

班次6

班次7

班次8

班次9

班次10

班次11

班次12

班次13

班次14

在09:

00时线路一需派出一车而其它线路距离派车时刻尚早，且五辆车都处于空闲状态，因此考虑空车返回问题，乘坐班次6的教职工有25人，所以派出E车是最合理的。

同样的班次7的情况和班次6类似，乘坐的人数为13。

E车在班次6时被派出，返校时间为09:

45，时间不冲突，故班次7派出E车。

班次8到班次13时间间隔比较小，因此应优先考虑时间问题。

同时班次8和班次13应同时考虑，班次8不需要空车返回，所以班次8排出的车的座位必须满足班次13乘坐的教职工的需求。

因此，只需考虑班次11，13的座位满足问题。

班次11，13均需运载35人，可派出班车A,B,C；班次9,10，12可派出五辆车的任一辆。

考虑到每条路线的运行时间和每辆车的运行成本，班次8派出A车，班次11可派出B车（或者C车）。

班次9运行时间最久，因此派出E车。

班次10运行时间短可派出C车（或者B车），班次12派出D车，而班次14时间间隔大，需空车返回，只需考虑座位满足和成本问题，可派出E车。

5.2.2问题2的模型求解

穷举法是指在一个有穷的可能的解的集合中，枚举出集合中的每一个元素，用题目给定的约束条件去判断其是否符合条件，若满足条件，则该元素即为整个问题的解；否则就不是问题的解。

如上式所示，若有n个变量，则设立n重for循环，对应的变量为n1,n2,n3,...再依据限制条件求解x、y、z、...分别对应的值。

求解问题2的模型C语言重点程序：

for（x=2;x<=4;x++）

for（y=2;y<=4;y++）

for（z=2;z<=4;z++）

{

if（x!

=y&&x!

=z）

{

if（y!

=z）

{

hy2=sj[1]*fy[x];

hy3=sj[2]*fy[y];

hy4=sj[3]*fy[z];

hy=hy2+hy3+hy4;

if（hy

min=hy;

}

（3）在处理决策变量后将数据输入所编程序中，得到结果：

图5.2VisualC++运行结果

经过对数据处理和考虑座位、时间间隔、耗费等综合因素情况下，得出既方便老师又节约的最佳每日班车的合理安排表：

表5.6每日班车的合理安排表

车次编号

时间

车辆代号

起点

方向

线路

终点

耗费（元）

00-7:

终点一

上行

线路一

学校

225

00-8:

终点二

上行

线路二

学校

140

00-7:

终点三

上行

线路三

学校

180

00-7:

终点四

上行

线路四

学校

表5.6每日班车的合理安排表（续）

00-7:

终点五

上行

线路五

学校

200

10-8:

学校（空）

下行

线路一

终点一

00-9:

终点一

上行

路线一

学校

50-10:

学校

下行

线路一

终点一

12:

10-12:

学校

下行

线路一

终点一

225

10:

40-11:

终点一（空）

上行

线路一

学校

12:

10-13:

学校

下行

路线二

终点二

140

12:

10-12:

学校

下行

线路四

终点四

11:

30-12:

学校（空）

下行

线路二

终点二

280

12:

40-13:

终点二

上行

线路二

学校

280

11:

40-12:

学校（空）

下行

路线三

终点三

180

12:

40-13:

终点三

上行

线路三

学校

180

13:

00-13:

终点一

上行

线路一

学校

225

14:

40-15:

终点二（空）

上行

路线二

学校

140

15:

50-16:

学校

下行

线路一

终点一

17:

40--

学校

下行

线路一

终点一

225

16:

55-17:

终点一（空）

上行

路线一

学校

17:

40--

学校

下行

线路二

终点二

140

17:

40--

学校

下行

线路三

终点三

180

17:

40--

学校

下行

线路四

终点四

17:

40--

学校

下行

线路五

终点五

100

5.3问题3的模型建立与求解

（1）对于到达终点站距离该终点站返回学校的下一班车发车时刻尚早，或该终点站当日已经没有返回学校的班次，这时不必非得空车返回学校，可视情况考虑安排到另一个线路的终点站，再沿途接人到学校这一类情况下，在问题2的基础上，修改已建立的模型。

表5.7班次1-5与班次15-19最多人数

班次1

班次2

班次3

班次4

班次5

人数

班次15

班次16

班次17

班次18

班次19

人数

在07:

表5.8班次6-14最多人数

班次6

班次7

班次8

班次9

班次10

班次11

班次12

班次13

班次14

在09:

从终点一到终点三之间的时间为10分钟，而班次12的返校时间为12:

40时间不冲突，而且五天之最多的人数为15人，考虑耗油量最小，所以派E车，剩余的班次8,9,10,11,12,13因为其时间间隔较小，所以优先考虑时间问题，又因为班次13和11在这五天之最多的人数分别为40,班次8所以应在A、B、C,三辆车之间选择，考虑耗油量问题，经穷举递归算法编程得到班次8选择B车，班次13又与B在同一条线路上而且班次13人数较多所以选择B车在13:

00时原路返回，班次9和班次11也可通过与班次8和13同样的思路得到其应该派C车。

（2）在处理决策变量后将数据输入所编数学模型，得到结果：

图5.3C/C++运行结果

经过对数据处理和考虑座位、时间间隔、耗费等综合因素情况下，得出既方便老师又节约的最佳每日班车的合理安排表：

表5.9最佳每日班车的合理安排表

车次编号

时间

车辆代号

起点

方向

线路

终点

耗费（元）

00-7:

终点一

上行

线路一

学校

225

00-8:

终点二

上行

线路二

学校

140

00-7:

终点三

上行

线路三

学校

180

00-7:

终点四

上行

线路四

学校

00-7:

终点五

上行

线路五

学校

200

10-8:

学校（空）

下行

线路一

终点一

00-9:

终点一

上行

路线一

学校

50-10:

学校

下行

线路一

终点一

12:

10-12:

学校

下行

线路一

终点一

180

表5.9最佳每日班车的合理安排表（续）

12:

10-13:

学校

下行

路线二

终点二

280

12:

10-12:

学校

下行

线路四

终点四

12:

40-13:

终点二

上行

线路二

学校

280

12:

30-12:

终点一

终点三

12:

40-13:

终点三

上行

线路三

学校

120

13:

00-13:

终点一

上行

线路一

学校

180

15:

50-16:

学校

下行

线路一

终点一

17:

40--

学校

下行

线路一

终点一

225

16:

55-17:

终点一（空）

上行

路线一

学校

17:

40--

学校

下行

线路二

终点二

140

17:

40--

学校

下行

线路三

终点三

180

17:

40--

学校

下行

线路四

终点四

17:

40--

学校

下行

线路五

终点五

100

六、误差分析

对给的参考数据我们为保证每位老师都有座位对其取了最大值，这样有可能不能使得资源最优配置。

模型是建立在一系列假设的基础上，所得的结果与实际问题存在一定的偏差。

展开阅读全文