《数学建模论文_城市小区便民服务点的设置与调度优化模型》由会员分享,可在线阅读,更多相关《数学建模论文_城市小区便民服务点的设置与调度优化模型(28页珍藏版)》请在金锄头文库上搜索。
1、.word格式,赛区评阅编号(由赛区组委会填写):2015高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则(以下简称为“竞赛章程和参赛规则”,可从全国大学生数学建模竞赛网站下载)。我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。我们知道,抄袭别人的成果是违反竞赛章程和参赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺,严格遵守竞赛章程和参赛规则
2、,以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为,我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会,可将我们的论文以任何形式进行公开展示(包括进行网上公示,在书籍、期刊和其他媒体进行正式或非正式发表等)。我们参赛选择的题号(从A/B/C/D中选择一项填写): 我们的报名参赛队号(12位数字全国统一编号): 参赛学校(完整的学校全称,不含院系名): 参赛队员 (打印并签名) :1. 2. 3. 指导教师或指导教师组负责人 (打印并签名): 日期: 年 月 日 (此承诺书打印签名后作为纸质论文的封面,注意电子版论文中不得出现此页。以上内容请仔细核对,如填写错误,论文可能被取消评
3、奖资格。), 专业.专注 .赛区评阅编号(由赛区组委会填写):2015高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅记录(可供赛区评阅时使用):评阅人备注送全国评阅统一编号(由赛区组委会填写):全国评阅随机编号(由全国组委会填写):(此编号专用页仅供赛区和全国评阅使用,参赛队打印后装订到纸质论文的第二页上。注意电子版论文中不得出现此页,即电子版论文的第一页为标题、摘要和关键词页。), 专业.专注 .城市小区便民服务点的设置与调度优化模型摘要随着经济不断增长,基础设施的需求不断增加,便民服务点作为城市基础化建设的重要组成部分仍需不断完善。由于人力、物力和资金等资源是有限的,如何根据城市
4、的小区实际分布情况与需求合理地设置小区便民服务点,分配各服务点的服务范围,充分利用有限资源为全市市民提供一个生活方便、优质的服务,是有关部门面临的一个实际问题。问题一:分配各便民服务点的服务范围(1)题目要求在全市12个便民服务点位置确定的情况下,按照尽量短时间内到达服务点和工作量均衡的原则为各便民服务点分配服务范围。对此问题本文用Floyd算法建立最短路径模型,利用MATLAB进行求解,得到每个服务点到居民点的最短路径。(2)我们对于120个居民点在最短时间到达服务点的问题,以所用时间最小为目标,建立0-1整型规划模型,借助LINGO进行求解,得出各条路径所需最短时间,结合(1)最后得到全市
5、现有每个便民服务点的服务范围如表1。问题二:对于确定需要增加服务点的具体个数和位置的问题由问题一的分配结果可知,在现有便民服务点的设置下:还有几个居民点不能在平均时间内到达服务点,即到达服务点时间过长我们根据便民服务点工作量的方差定义工作量不均衡度,结果显示:此时服务点的工作量不均衡度为6.5。为解决到达服务点时间过长和便民服务点工作量不均衡的问题。我们建立最优化模型,求解结果表明:在增加三个服务点的情况下,可以解决居民点到服务点时间过长的问题。在此基础上我们优化分配方案:在增加几个便民服务点的情况下,使服务点的工作量不均衡度降为多少。增加的三个服务点路口标号见表2。关键词:Floyd最短路径
6、算法 0-1整型规划模型 最优化模型 MATLAB LINGO, 专业.专注 .一、 问题重述某市为了方便市民生活,打算在市内小区设置便民服务点,为市民就近提供医疗卫生、缴费等公共服务,但由于人力、物力和资金等资源是有限的,如何根据城市的小区实际分布情况与需求合理地设置小区便民服务点,分配各服务点的服务范围,充分利用有限资源为全市市民提供一个生活方便、优质的服务,是有关部门面临的一个实际问题。问题一:为了提高便民服务点的服务效率,同时考虑每个服务点工作量的均衡性,该市打算将居民点划片服务,每个服务点面向一些居民点服务;建立数学模型,为各便民服务点分配服务居民点的范围,使其在所服务居民点范围内的
7、居民尽量在最短时间内到达服务点,同时又要使每个服务点的工作量尽可能的均衡。问题二:根据现有便民服务点的工作量不均衡和有些居民点到达服务点时间过长的实际情况,拟在该市内再增加1至3个服务点,请确定需要增加服务点的具体个数和位置。该市目前有120个居民点和12个便民服务点,居民点和便民服务点的网络分布情况见支持资料1,每个居民点位置、居民人口数和道路连接的数据信息见支持资料2;支持资料1:该市居民点和便民服务点的网络分布示意图。支持资料2:该市居民点位置、居民人口数和道路连接的相关数据表。二、问题的分析问题一:问题要求在市内的12个便民服务点位置确定的情况下,按照尽量短时间内到达服务点和工作量均衡
8、的原则为各便民服务点分配服务范围。本文引入赋权图中任意两顶点间的最短路理论中的Floyd算法和0-1整型规划模型进行求解。记为市内所有居民点的节点集合,为全市便民服务点的节点集合,为便民服务点到达居民点的最短距离。引入0-1变量,当居民点分配给便民服务点管辖是为1,当居民点不分配给便民服务点管辖是为0。即:由题目可知当相对较小时,居民点可能分配给便民服务点,也可能分配给其他可在较短时间内到达居民点的便民服务台,而不分配给,故有;当相对较大时,居民点不能在较短时间内到达服务点,故此时路口不能分配给便民服务点管辖,故此时。根据上述的分配原则及每个路口只由一个便民服务点进行管辖、每个便民服务点至少要
9、管辖一个路口,可首先利用Floyd算法计算出12个服务点到120个居民点的最短路径,然后建立0-1规划模型,并借助lingo进行区域划分。问题二:根据问题一(1)的分配方案可知此时每个便民服务点的工作量分别为:表1 按问题一的分配方案12个便民服务点的工作量编号123456工作量21946916编号789101112工作量412912612此时便民服务点的工作量不均衡度为6.3图1 居民点和便民服务点的网络布情况注:图中圆圈“* ”表示设置了服务点;距离单位:公里由问题一可知现有便民服务点的工作量极其不均衡且有些地方路径过长。针上述问题,题目要求再增加13个便民服务点来解决上述问题。本文建立优
10、化模型,然后利用lingo对模型进行增加的平台个数,可得到初步的分配方案,最后再引入工作量不均衡度,通过计算求解可确定增加便民服务点的数目与位置。三、模型的假设 假设每个便民服务点的职能和人力配备基本相同; 假设每个路口只由一个便民服务点进行管辖; 假设每个便民服务点至少管辖一个路口; 假设居民都按最短路径到达各服务点; 工作量:每个便民服务点所管辖范围内的所有居民点人数之和; 时间:居民到达服务点所需时间;四、符号说明第个居民点到第个便民服务点的最短距离第个居民点人数第个便民服务点第个居民点总人数新增点候选集居民点是否分配给便民点工作量距离目标值均方差五、模型的建立与求解5.1问题一(1):
11、服务范围的确定Floyd算法最短路径模型5.1.1模型建立:Floyd算法:根据问题一(1)的分析确定函数为目标函数: 约束条件: 5.1.2模型求解1.最短路径矩阵A的建立本文选用Floyd算法确定市内任意两个路口之间的最短路径矩阵。Floyd算法为:从任意节点到任意节点的最短路径不外乎2种可能,1是直接从到,2是从经过若干个节点到。所以,我们假设为节点到节点的最短路径的距离,对于每一个节点,我们检查是否成立,如果成立,证明从到再到的路径比直接到的路径短,我们便设置,这样一来,当我们遍历完所有节点,中记录的便是到的最短路径的距离。通过上述算法,利用数学软件MATLAB计算出各节点的最短路径,
12、组成一个最短路径矩阵。图2 偏差值与目标最优解的坐标图由图可看出在1500附近,目标函数值变动最小,为此我们选择1500为偏差限目标值:3518.575.1.3最终分配方案的确定从最短路径矩阵中,我们可以清楚看到如下问题:(1) 在仅满足分配标准时有些路口可以被多个路口管辖;(2)在仅满足分配标准时个别居民点离服务点距离过大;那么此时并不满足模型的要求必须对进行处理,以得到满足要求的最终分配方案。首先解决(1)中出现的问题,此过程我们利用数学软件MATLAB进行处理,相应的程序见附录。步骤一:由集合覆盖矩阵将120个居民点分为A、B、C三类:A类:已只由一个巡警服务台进行管辖;B类:可被多个巡
13、警服务台进行管辖;C类;还不能被任何巡警服务台进行管辖;步骤二:将A类中的路口直接分配给对其进行管辖的唯一的巡警服务台。步骤三:将B类中的路口按最近原则分配给距离它最近的巡警服务台。然后解决(2)中的问题。将任何服务点都不能在规定时间内到达的居民点按就近原则进行分配。表2最后得到最终的分配方案如下:服务平台管辖范围服务人数(人)最长距离A11,19,64,65,70,71,72,73,74,7,76,77,80,811610056.54864A22,42,43,66,67,68,69,78,791480068.19103A33,18,20,40,44,53,54,6313300115.0042