大学生数学建模竞赛A题参考答案.pdf

《大学生数学建模竞赛A题参考答案.pdf》由会员分享，可在线阅读，更多相关《大学生数学建模竞赛A题参考答案.pdf（15页珍藏版）》请在三一文库上搜索。

1、2018 高教社杯全国大学生数学建模竞赛题目 给出 8种主要重金属元素在该城区的空间分布，并分析该城区内不同区域重金 属的污染程度。 (2 通过数据分析，说明重金属污染的主要原因。 (3 分析重金属污染物的传播特征，由此建立模型，确定污染源的位置。 (4 分析你所建立模型的优缺点，为更好地研究城市地质环境的演变模式，还应收 集什么信息？有了这些信息，如何建立模型解决问题？ 题 目 A 题 城市表层土壤重金属污染分析 摘要： 本文研究的是某城区警车配置及巡逻方案的制定问题，建立了求解警车巡逻方案的 模型，并在满足 D1的条件下给出了巡逻效果最好的方案。 在设计整个区域配置最少巡逻车辆时，本文设计

2、了算法1：先将道路离散化成近似 均匀分布的节点，相邻两个节点之间的距离约等于一分钟巡逻路程。由警车的数目, 将全区划分成个均匀的分区，从每个分区的中心点出发，找到最近的道路节点，作 为警车的初始位置，由Floyd 算法算出每辆警车3 分钟或 2 分钟行驶路程范围内的节 点。考虑区域调整的概率大小和方向不同会影响调整结果，本文利用模拟退火算法构 造出迁移几率函数，用迁移方向函数决定分区的调整方向。计算能满足D1 的最小车辆 数，即为该区应该配置的最小警车数目，用MATLAB 计算，得到局部最优解为13 辆。 在选取巡逻显著性指标时，本文考虑了两个方面的指标：一是全面性，即所有警车 走过的街道节点

3、数占总街道节点数的比例，用两者之比来评价；二是均匀性，即所有 警车经过每个节点数的次数偏离平均经过次数的程度，用方差值来大小评价。 问题三：为简化问题，假设所有警车在同一时刻，大致向同一方向巡逻，运动状 态分为四种：向左，向右，向上，向下，记录每个时刻，警车经过的节点和能够赶去 处理事故的点，最后汇总计算得相应的评价指标。 在考虑巡逻规律隐蔽性要求时，文本将巡逻路线进行随机处理，方向是不确定的，采 用算法 2 进行计算，得出相应巡逻显著指标，当车辆数减少到10 辆或巡逻速度变大 时，用算法 2 计算巡逻方案和对应的参数，结果见附录所示。 本文最后还考虑到4 个额外因素，给出每个影响因素的解决方

4、案。 关键词：模拟退火算法； Floyd 算法；离散化 参赛队号 11*02 队员姓名 * 佳 *梅 * 巍 一 问题的重述 110警车在街道上巡逻，既能够对违法犯罪分子起到震慑作用，降低犯罪率，又能 够增加市民的安全感，同时也加快了接处警时间，提高了反应时效，为社会和谐提供 了有力的保障。 现给出某城市内一区域，其道路数据和地图数据已知，该区域内三个重点部位的 坐标分别为： 预分区的优点在于使警车的初始位置尽可能均匀地分散分布，警车的初始停靠 点在一个分区的中心点附近寻找得到，比起在整个区域随机生成停靠点，计算效率明 显得到提高。 预分配之后，需要对整个区域不断地进行调整，调整时需要考虑调整

5、方向和调整 概率。 警车调整借鉴的是模拟退火算法的方法，为了使分区内包含道路节点数较多的分 区的初始停车点调整的概率小些，而分区内包含道路节点数的少的分区内的初始停车 点调整的概率大些，我们构造了一个调整概率函数, 1） 1）式中，均为常数，为整个区域车辆数，为第分区内覆盖的节点数， 为时间，同时也能表征模拟退火的温度变化情况：初始温度较高，区域调整速度较 快，随着时间的增加，温度不断下降，区域调整速度逐渐变慢，这个调整速度变化也 是比较符合实际情况的。 由式 1）可以得出调整概率函数，假设在相同的温度时间）的条件下，因为 总的车辆数目是定值，当时，即第分区内的节点数大于第分区的节点数 时，分

6、区调整的概率大些，分区的调整概率小些。分析其原因：当分区内包含了较 多的节点个数时，该分区的警车初始停靠位置选取地比较合适了，而当分区内包含的 道路节点数较少时，说明警车的初始停靠位置没有选好，需要更大概率的调整，这样 的结论也是比较客观的。 对于所有分区外未被覆盖的道路节点和很多节点称之为节点群），用来调整警车 位置迁移的方向，其分析示意图如图5 所示。调整方案目标是使未被覆盖的节点数尽 量的少。在设计调整方向函数时，需要考虑：1）节点群内节点的数目；2）警车距 离节点群的位置。优先考虑距离，所以在公式2）中，用距离的平方来描述调整方向 函数。 因为某一个区域范围内的未被覆盖节点数，整个区域

7、未被覆盖的节点总数，分区域 与未被覆盖的节点或节点群的距离等几个因素会影响到调整的方案，所以要综合考虑 这些因素。于是设计了区间调整函数， 式中，表示第个分区内未被覆盖的节点数，表示第分区域与未被覆盖的节 点或节点群的距离，表示未被覆盖的节点和节点群个数。 现在简要分析第分区按区间调整函数的调整方案，当某两节点群的节点数目相 等，但是距离不等时，如，由区间调整公式可知，该区间向节点群方向调整。 当某个分区与两个节点群的距离相等，但节点群的内节点个数不相等，如时， 由4）可知，该分区域会想节点群方向调整。 注意在整个调整过程中，调整几率控制是否调整，调整方向函数控制调整的方向， 寻找在这种调整方

8、案下的最优结果。 图 5 调整分区域示意图 3）在 step3 中，使用 Floyd 算法计算出警车初始停靠点到周边各节点的最短距离, 目的是当区域内有情况发生时，警车能在要求的时间限制内到达现场。 4）为求出较优的警车停靠点，采用模拟退火算法，算出局部最优的方案。 5.1.4警车的配置和巡逻方案 使用 MATLAB 编程实现算法1 得到，整个区域配备13 辆警车，这些警车静止在初 始停靠点时，能满足D1要求。警车的初始停靠位置分别为道路交叉节点6，25，30， 37，82，84，110，111，126，214，253，258，278 处。每个警车所管辖的交叉点原 始 的 交 叉 节 点 ）

9、如 图6所 示 ， 求 解 的 分 区 结 果 见 附 录 所 示 。 图 6 满足 D1条件下的区分划分图 13 个分区共覆盖了252 个交叉点，另外的55 个原始交叉点没有被这些分区域覆 盖： 137，138，151，159，167，168，170，174，175，186，188，189，211，215， 226，242，255，260，261，262，263，267，270，271，272，275，282，283 ， 284，287，288，289，292，296，297，299，304，305，307。在这种分区方案下，这 些 点中 ， 每 两 个 相 连 的 点 间的 道 路 离 散

10、 值 长 度 占 整个 区 域 总 的 长 度 的 比 值为 。因此，在整个区域配置13 辆警车，每个警车在初始停靠点静 止不动，当有案件发生时，离案发现场最近的警车从初始停靠点赶到现场。 5.2评价巡逻效果显著的指标 110 警车在街道上巡逻是目的是为了对违法犯罪分子起到震慑作用，降低犯罪 率，又能够增加市民的安全感，同时还加快了接处警接受报警并赶往现场处理事件） 时间，提高了反应时效，为社会和谐提供了有力的保障。巡警在城市繁华街道、公共 场所执行巡逻任务 , 维护治安 , 服务群众 , 可以得良好的社会效应 1 。 在整个区域中，因为案发现场都在道路上，道路上的每一点都是等概率发生的， 因

11、此警车巡逻的面越广，所巡逻的街道数目越多，警车的巡逻效果就越好，对违法犯 罪分子就越有威慑力，警车也能更及时地处理案件。 我们采用全面性来衡量巡逻的效果显著性，即用警车巡逻所经过的街道节点数占 区域总节点数的比值。当警车重复经过同一条街道同一个离散点时，仅记录一次。 3 ） 式中，表示警车经过的离散点数，代表整个区域总的离散点数。值越大，表 明警车所经过的街道数目越多，所取得的效果越显著。 同时考虑到在巡逻过程中可能会出现这样的情况：在相同的时段内，警车会多次 巡逻部分街道，而一些街道却很少巡逻甚至没有警车到达，这样会造成一些巡逻盲 区。分布很不均衡。这样就可能出现巡逻密度大的街道上的违法犯罪

12、分子不敢在街道 上作案，而流窜到巡逻密度稀疏的街道上作案，因此在相同的警车数目条件下，密度 不均衡的巡逻方式的巡逻效果的效果较差，而密度较均衡的巡逻方式所取得的巡逻效 果会更好些。我们引入一个巡逻的不均匀度来衡量巡逻效果的显著性，考虑到方差能 表示不均衡度，于是我们用方差的大小来表征不均衡，方差越大，巡逻密度越不均 衡，所取得的巡逻效果越差。 4） 问题 1 所给出的满足 D1条件下的警车数目为13 辆，这时每辆警车在初始停靠点静 止不动，只有该管辖区域内发生了案件时，警车才从初始停靠点赶到案发现场处理案 件。当警车在巡逻状态时，所需要考虑的问题就更复杂一些，如当节点运动时，警车 还能否达到

13、D1的要求，警车的运动方向如何等问题，但基本算法思想与问题1 类似， 所得的算法 2 的框图如图 7 所示， 为了简化问题，我们假设各分区警车的巡逻时候，尽量保证所有的警车的行驶方向 相一致，且警车都走双行道，即当警车走到某个节点后，它们又同时返回初始停靠 点，警车的行驶方向有四种方式，如6 所示。 在图 6 中，数字 1 代表走巡逻走的第一步， 2 表示朝 1 的巡逻方向相反的方向巡 逻。在具体程序实现时，四种巡逻方向任意选择，但是尽量保证所有的警车向同一个 方向巡逻。 图 6 各警车巡逻方向图 我们用 MATLAB 编程对这种巡逻方式进行计算，所得的车辆数目为18 辆，综合评 价指标为，其

14、结果巡逻方案见附件中的“1193402-Result3.txt”所示。 5.4在满足问题三的基础上讨论D3条件，警车的巡逻方案和评价指标 巡逻的隐蔽性体现在警车的巡逻路线和时间没有明显的规律，主要目的是让违法 犯罪分子无可乘之机，防止他们在非巡逻时间实施违法犯罪活动，危害人民的生命和 财产安全。 为了使巡逻的规律具有隐蔽性，这就需要警车在巡逻时至少具有两条不同的路 线，时间最好也是不相同的。因此，考虑到隐蔽性时，只需要在问题2 的基础上加上 一个随机过程即可。对于其评价指标，因为警车有几条可选的巡逻路线，当相同的路 线在同一时间内重复出现时，重新将所设定的方案再执行一遍，我们用这个时间间隔 来

15、衡量隐蔽性的程度，当循环周期越大，表明可选的巡逻方案越多，其规律就越具 有隐蔽性，而循环周期越小时，表明巡逻方案比较少，其隐蔽性较差。在巡逻状态 时，最差的隐蔽性巡逻方案是巡逻方案只有一个，并且时间固定，这样的巡逻方案没 有任何隐蔽性可言。 5.5 整个区域为 10 辆车时的巡逻方案 由第三问的结果可知，10 辆车的数量是不能把整个区域完全覆盖的，其算法与算 法 2 类似，不同的是此时车的数目已经固定了，要求使D1,D2 尽量大的满足，我们求 得的评价指标值为，所得的巡逻方案见附件中的“1193402-Result5.txt”所 示。 5.6 平均行驶速度提高到时的巡逻方式和评价指标值 问题六

16、的分析方法与具体实现与问题三一致，但是警车的接警后的平均速度由原来 的提高到，于是各分区的覆盖范围也增大了，将数值带入问题3 的算 法 中 求 解 ，计 算 得 的 指 标 值 为， 其 巡 逻 方 案见 附 件 中 的 “ 1193402- Result6.txt”所示。 图 7 算法 2 框图 六模型的分析和评价 在求解满足 D1 的条件下，整个区域需要配备多少辆警车问题中，采用分区巡逻的 思想，先分析能使各区管辖范围达到最大值时的规律，由特殊到一般层层进行分析， 逻辑严密，结果合理。 在求解区域和警车数目时，在初步设定警车停靠点位置的基础上，用模拟退火算 法思路构造函数来确定调整的概率大

17、小，综合考虑了影响区间调整的因素后构造了 函数来确定分区的调整方向，当分区按照这两个调整函数进行调整时，各分区能管 辖尽可能多的道路节点，所取得效果也比较理想。 参 考 文 献 1 中小城市警察巡逻勤务方式的探讨，俞详，江苏公安专科学校学报，1998 年第 1 期 2Matlab7.0从入门到精通，求是科技，人民邮电出版社； 3 不确定车数的随机车辆路径问题模型及算法，运怀立等，工业项目，第10 卷第 3 期，2005年 5 月； 4 随机交通分配中的有效路径的确定方法，李志纯等，交通运输系统项目与信息，第 3 卷第 1 期，2003 年 2 月。 附录 图 问题三巡逻路径 图 问题五巡逻路径 图 问题六巡逻路径