文档介绍：交巡警服务平台的设置与调度
摘要
在充分理解题意的基础上,,、Floyd程序、二分匹配的方法得到最优的解决方案.
针对问题一的第一小问,我们先用图论覆盖理论,将A区每个平台为圆心,3km为半径的圆形范围所覆盖的区域为初步管辖范围,然后再深入考虑到圆形领域内的折线问题,最终用Floyd的最短路算法对模型进行进一步的精确认证, 输出任意节点到平台的最短时间,统计小于3min的节点(详见附录2图),可找到大于3min的6个相应节点,再用临近原则将这6个节点归划于与各自节点最近的那个平台管辖.
针对问题一的第二小问,先利用排列组合的思想,将13个交通要道编号1-13,再从20个交巡警服务平台中选出13个进行全排列,一共有A种不同情况,算出每种情况中13个时间的最大值,再从所有各种情况的时间中取最小值,这样得到的时间就是最快封锁13个交通要道的时间.
针对问题一的第三小问,根据题意设出最优原则,结合Excel中的5张工作表以及一问中所画的区域覆盖图,我们将发案率、距离、与其它平台的覆盖率、人口密度规定为决定增加平台这4个因素作为原则,并按重要的顺序对4个因素进行排序,给每个因素一个权值,综合计算可以得到一个衡量值,再结合程序(2)可以得到所需增加的4个平台所处节点标号.
针对问题二的第一小问我们使用最优化思想,将A区的情况推广到全市的其他五个区域,并对A区出现的不合理情况分类,采取对应的措施.
针对问题二的第二小问我们首先使用图论的树模型,由嫌疑犯和各个平台警方在相应的时间所到达的节点的集合作比较,从中找到一个最小的覆盖,使嫌疑犯的可能到达的节点包含在内,这样就得到了我们要的答案,但是由于编程难以实现,我们就采用了二分匹配的方法,并用相应的算法,得到了最优的调度方案.
关键词: Floyd算法二分匹配最优化覆盖问题模型
目录
第一部分问题重述···············································3
第二部分问题背景···············································3
第三部分问题分析···············································3
第四部分模型的假设与符号说明···································5
第五部分模型的建立与求解·······································7
第六部分模型结果和结果分析·····································18
第七部分对模型的评价···········································18
第八部分参考文献······································