《数学建模论文校车安排问题的数学模型论文》由会员分享，可在线阅读，更多相关《数学建模论文校车安排问题的数学模型论文（17页珍藏版）》请在金锄头文库上搜索。
1、重庆科技学院课程论文题 目 校车安排问题 院 （系） 专业班级 学生姓名 学号 指导教师 职称 评阅教师 职称 2012 年 1 月 2 日1目 录摘要1关键词11问题重述21.1 问题背景22问题分析22.1 研究意义22.2 研究现状22.3 存在问题22.4 解决方法23模型假设24符号约定35模型建立与求解45.1 计算各点间的最短路程45.1.1 数据分析45.1.2 模型建立与计算45.2 建立 个乘车点使各区人员到最近乘车点的距离最小的一般模型5n5.2.1 模型建立55.2.2 模型求解55.3 考虑每个区的乘车人数建立 个乘车点使各区人员到最近乘车点的距n离最小的一般模型 6
2、5.3.1 模型建立65.3.2 模型求解65.4 建立 3 个乘车点的车辆安排 75.4.1 建立模型75.4.2 模型求解85.5 建议 86模型分析与评价 97模型的推广 9参考文献 9附录102摘要：本文针对高校新校区校车运行的安排问题，通过合理的抽象假设，把校车安排问题抽象成由点线构成的网络模型，将问题转化为 n-重心问题的求解。在问题解决过程中使用了佛洛依德算法，分析、建模、求解过程中利用MATLAB、Excel 对数据进行分析处理，并用 C 语言实现某些算法，最终得出结论。1. 仅考虑距离因素时：设立两个乘车点时，乘车点应设在区域 18 和区域 31；设立三个乘车点时，乘车点应设
3、在区域 15、区域 21 和区域 31。2. 综合考虑距离及教师总体满意度时：设立两个乘车点时，乘车点应设在区域 19 和区域 32；设立三个乘车点时，乘车点应设在区域 15、区域 21 和区域 32。3. 为使教师及工作人员尽量满意，至少需要安排 54 辆校车：其中区域 15 安排校车 17 辆；其中区域 21 安排校车 18 辆；其中区域 32 安排校车 19 辆。4. 通过对问题的求解可知当乘车点适当增加时，教师及工作人员的满意度上升，可在学校条件允许的情况下在合适位置适当增加乘车点。关键词：弗洛伊德算法；总体满意度；n-重心问题。31、问题重述1.1 问题背景许多学校都建有新校区，常常
4、需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。（1） 、建立 个乘车点，使各区人员到最近乘车点的距离最小，该将校车乘n车点应建立在哪 个点。（2） 、考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪 个点。 （3） 、建立 3 个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客 47 人。2、问题分析2.1 研究意义许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由
5、于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。如何有效的安排车辆及让教师和工作人员尽量满意。2.2 研究现状许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。2.3 存在问题如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。由于受到车辆数目的限制，即车辆花费的限制。还有乘车点的限制。我们只能在现有的条件下合理的安排乘车点和乘车数目使教师和工作人员尽量满意。2.4 解决方法老校区的 50 个区域的大小、形状与问题的求解无关，可将 50 个区域抽象为 50 个点，区域间的连接道路抽象为点的连线，据此建立网络模型，用佛洛依德算法求出任意两点间最短路径的
6、距离，将问题的求解转化为 n-重心问题，由模型逐步求解得到乘车点的位置。3、模型假设（1）假设老校区的教师和工作人员分布在 50 个区，各区的距离见附录A。各区人员分布见附录 B。4校 区 人 数 分 布 图0102030405060708090100123456789101121314151617181920212232425262728293031323343536373839404142434454647484950（2）50 个区域抽象成 50 个点，附录 1 中标注距离的点间可以直接相通，未标注距离的点间无法直接相通，需通过其它点间接到达。（3）假设任一教师和工作人员的满意程度随距离
7、的增加递减（4）乘车点只设在点上。（5）校车只在起始站点载人。4、符号约定A：点间距离的邻接矩阵；B：各点的最短距离矩阵:i 点到 j 点的最短距离；ijd:i 到 j 的只以(1.k)集合中的节点为中间结点的最短路径的距离；kij:各个点到乘车点的总距离；na,21DL:最短总距离；min:乘客个体满意度；:某点到乘车点所走距离；d:所有点中到乘车点的最大距离；D5:所有乘客的总体满意度；F：重新安排乘车点的人员安重排前所走的路程；Los:某区域的教师人数；m:教师及工作人员总人数；M: 距乘车点的平均路程.E5、模型建立与求解5.1 计算各点间的最短路程5.1.1 数据分析首先对题目所给的
8、各区距离做统计分析，用 Excel 表格建立对应各点距离的邻接矩阵 A，即.505021250211aaaaLMO其中 为点 i 到点 j 的距离。当 =，表示 i 点和 j 点不直接相通。ijaij5.1.2 模型建立与计算用弗洛伊德算法计算任意两点间的最短距离。弗洛伊德算法的原理是动态规划，设 为从 i 到 j 的只以(1.k)集合中kijd的节点为中间结点的最短路径的长度, 若最短路径经过点 k，则：1-kj-ikij若最短路径不经过点 k，则： 1-kijijd因此，有： 1-kj-i1-kijkijmnd，弗洛伊德算法的 C 语言实现见附录 E。把邻接矩阵 A 作为弗洛伊德算法的输入
9、矩阵，程序输出各点间最短距离矩阵 B（结果见附录 C）及取最短距离时各6点间的走法（结果见附录 D） 。5.2 建立 个乘车点使各区人员到最近乘车点的距离最小的一般模型n5.2.1 模型建立为网络中 i 点到 j 点最短路径的权，表示 i，j 两点的最短距离；ijd为网络中 i 点的权，表示 i 点的人数，因为不考虑人数对乘车点的影响，in固取 ，i,j （1，50） 。i问题的模型为特殊情况（ ）的 n-重心模型：1in501501miijijdf5.2.2 模型求解任取 n 个互异点 为乘车点，则从各点到乘车点的总路程为：naa,21L501, ,m2121i iaiaia nn dDLL
10、则取 50 个点的组合 做 ，分别计算 ，取使得50Cnaa,21 naD,21L取最小值的 点即为所求乘车点。即：naD,21L na,21LnaD,min21L., 5021,2121互 异 ，nnaaLL取 n=2，3，计算结果，算法的 C 语言实现见附录 E。程序计算得：n=2 时，求得乘车点应设在区域 18 和区域 31；n=3 时，求得乘车点应设在区域 15、区域 21 和区域 31。75.3 考虑每个区的乘车人数建立 个乘车点使各区人员到最近乘车点的距离最n小的一般模型5.3.1 模型建立为网络中 i 点到 j 点最短路径的权，表示 i，j 两点的最短距离；ijd为网络中 i 点
11、的权，表示 i 点的人数，i，j （1，50） 。in 问题的模型为 n-重心模型： 501miniijdf假设任一教师和工作人员的满意程度随距离的增加递减，即去乘车点的距离越大越不满意，则当所有人走的总距离最短时整体的满意度最大。定义 为乘客个体满意度,有： 10,1Dd其中 d 为某点到乘车点所走距离，D 为任意两点最短距离的最大值。定义 F 为所有乘客的总体满意度，有： MmdF1其中 m 为某点的人数，M 为所有教师人数。定义 E 为教师及工作人员至乘车点的平均路程，即： dE5.3.2 模型求解任取 n 个点 为乘车点，所有人到乘车点的总路程为：naa,21L 501, ,m2121
12、i iaiaiaa nn dndDLL则取 50 个点的组合 做 ，分别计算 ，取使得50Cnaa,21L naD,21L8取最小值的 点即为所求乘车点。即：naD,21L naa,21LnaD,mi21L., 5021,2121互 异 ，nnaaLL取 n=2，3，计算结果，算法的 C 语言实现见附录 E。程序计算得：n=2 时，求得乘车点应设在区域 19 和区域 32，总体满意度 F=77.94%；距乘车点的平均路程 E497。n=3 时，求得乘车点应设在区域 15、区域 21 和区域 32，总体满意度F=82.70%；距乘车点的平均路程 E390。5.4 建立 3 个乘车点的车辆安排5.
13、4.1 建立模型此问题为 n-重心问题的进一步引申，以车辆数和总体满意度为双目标函数；任取 3 个点 为乘车点，所有人到乘车点的总路程为：321,a501, 321321 ,mi iaiaia dndnD分别找出此时到 点距离最近的 个点，计算这 个点的总人数 。iaikikiS（i=1，2，3）则取 50 个点的组合 做 ，分别计算 ，取使得 取最350C321,a321,aD321,a小值的 点即为所求乘车点。即：321,a 321,mina对 取余得到车载满后的剩余人员数 ，即：iS iMod47 iis重新安排乘车点的人员安重排前所走的路程为： 3150)(minj iajDodLos93,21j重安排乘车点的人员所走的最短路径 为：minD321)(i501min jjj iaaMod .,323,2, 互 异且， jjjj重新安排后所走总路径的最小值为: LosDminimin
