数学建模教学优秀教学案例解析_交巡警服务平台的设置与调度_木仁.pdf

1引言 随着计算机软件功能的拓展 众多复杂的数学 建模方法均得到了很好的解决 1 同时也有部分典 型案例已经在实践当中得到广泛的应有 然而 由 于众多非数学专业学生及非重点院校学生们的数 学建模知识的欠缺及计算机应用能力的短板 大部 分数学建模方法均未得到很好的推广 在解决实际 问题时数学模型的建立及求解同等重要 只懂得其 中的一个往往不能很好的解决实际问题 过去的众 多数学研究工作者虽然具备了扎实的数学建模理 论基础 但由于计算机编程能力的缺乏不能求解出 复杂的数学建模问题 而新一代的数学研究工作者 虽然具备了一定的编程技巧 但由于数学建模理论 知识的欠缺往往不能很好的建立相关模型 这为众 多数学建模教学工作者提出了新的挑战 今后 应 该怎样推广数学建模教育 提高不同专业学生的创 新意识 特别是非数学类专业学生及非重点院校学 生们的数学建模能力及求解能力变的尤为重要 2 3 数学建模所涉领域众多 它不仅能够培养学生 们的创新能力 同时也能够为不同学科领域创造出 的经济社会价值 4 数学建模方法多样 需要掌握的 知识点较多 5 怎样通过数学建模的课程将众多数 学建模方法传授给学生们是数学建模教育工作者 的所追求的目标 6 对于众多重点院校的学生来说 许多数学建模方法都能够较快的接受 然而 对于 非数学类专业学生或非重点院校学生而言数学建 模方法的传授却是十分困难 特别是随着大范围的 扩招 使得非重点院校根本就不能够招收具有扎实 数学基础的学生 对于这些学生 应进一步探索传 授数学建模方法的方案 其中最为可行的方法就是 选择恰当的数学建模案例对不同的数学建模方法 进行全方面的解析 这使得数学建模案例的选取变 的十分重要 频繁的引进不同案例必然会导致大部 分学生在短时间内难以接受相关问题 如果能够通 过少数几个案例将众多数学建模方法传授给学生 那是最为理想的 2011 年全国大学生数学建模竞赛题目交巡警 服务平台的设置与调度题目是一个较为理想的数 学建模教学案例 所涉及到的数学建模方法包括 Matlab 作图 Matlab 编程 最短路问题 行遍性问 题 计算机模拟 线性规划 非线性规划 层次分析 方法 数据的统计分析 数据拟合 综合评价等众多 方法 以下对其进行深入的分析讨论 2问题的提出 由于警务资源是有限的 如何根据城市的实际 情况与需求合理地设置交巡警服务平台 分配各平 Vol 28 No 5 May 2012 赤 峰 学 院 学 报 自 然 科 学 版 Journal ofChifengUniversity Natural Science Edition 第 28 卷 第 5 期 上 2012 年 5 月 数学建模教学优秀教学案例解析 交巡警服务平台的设置与调度 木仁 1 2 白阿拉坦高娃3 崔 巍 1 1 内蒙古工业大学理学院数学系 内蒙古呼和浩特010051 2 内蒙古大学数学科学学院 内蒙古呼和浩特010021 3 赤峰学院数学与统计学院 内蒙古赤峰024200 摘要 随着全球经济社会的快速发展 数学建模已经成为了众多学科领域中的焦点问题 各种数学 建模方法的推广依然成为了数学建模教学的必要环节 一个优秀的数学建模案例不仅能够真实的反映现实 问题同时也能多方面体现数学建模方法 交巡警服务平台的设置与调度问题是一种较为理想的数学建模案 例 它不仅能够从多方面体现数学建模方法 培养学生们的创新意识 同时也可以推广到众多实际问题中应 用 关键词 Matlab 最短路 线性规划 0 1 整数规划 非线性规划 层次分析方法 拟合 中图分类号 O29文献标识码 A文章编号 1673 260X 2012 05 0017 05 基金项目 内蒙古自治区自然科学基金项目 批准号 2011MS1002 内蒙古大学 211 工程 创新人才培养项目资助 17 台的管辖范围 调度警务资源是警务部门面临的一 个实际课题 试就某市设置交巡警服务平台的相关情况 建 立数学模型分析研究下面的问题 1 附件 1 中的附图 1 给出了该市中心城区 A 的交通网络和现有的 20 个交巡警服务平台的设置 情况示意图 相关的数据信息见附件 2 请为各交 巡警服务平台分配管辖范围 使其在所管辖的范围 内出现突发事件时 尽量能在 3 分钟内有交巡警 警车的时速为 60km h 到达事发地 对于重大突发事件 需要调度全区 20 个交巡 警服务平台的警力资源 对进出该区的 13 条交通 要道实现快速全封锁 实际中一个平台的警力最多 封锁一个路口 请给出该区交巡警服务平台警力合 理的调度方案 根据现有交巡警服务平台的工作量不均衡和 有些地方出警时间过长的实际情况 拟在该区内再 增加 2 至 5 个平台 请确定需要增加平台的具体个 数和位置 2 针对全市 主城六区 A B C D E F 的具 体情况 按照设置交巡警服务平台的原则和任务 分析研究该市现有交巡警服务平台设置方案 参见 附件 的合理性 如果有明显不合理 请给出解决 方案 如果该市地点 P 第 32 个节点 处发生了重大 刑事案件 在案发 3 分钟后接到报警 犯罪嫌疑人 已驾车逃跑 为了快速搜捕嫌疑犯 请给出调度全 市交巡警服务平台警力资源的最佳围堵方案 具 体图及附件参见网站 中的 2011 年竞赛题目 3数学建模教学内容解析 在上一节中提出的问题所涉及数学建模方法 较多 本节中将对其进行详细的分析 并指出每一 问中可传授的数学建模方法 数学建模方法传授点之 一 Matlab 在数学建 模中的应用 Matlab 软件因其丰富的工具箱 目前已经成为 了数学建模领域最为得心应手的软件 7 同时 由 于 Matlab 在处理数据时与 Excel 文档 TXT 文档及 数据库文档等之间的特殊接口 使得数学建模者可 以随心所欲的读写和处理各项数据 在处理数据的 同时也可将部分内容可视化的显示出来 这使得研 究工作者对数据有了更为深层次的认识 在数学建 模时不仅需要将众多数据规范化 更需要数据结果 的可视化 而在这方面 Matlab 软件能够较为简便 的实现具体的目标 3 1数据的可视化显示方法 在题目中给出了各个节点的相关信息 其中 通过各节点的坐标 与该点连接的节点标号及节点 是否为交巡警服务平台等信息 可将各区的分布图 显示出来 此时 主要通过 Matlab 中的简单循环 语句及作图方法即可画出图形 其中绘制出的 A 区 图形如图 1 所示 在 A 区中已有 20 个交巡警服务 平台 图 1 中的圆圈就是 20 个交巡警服务平台 整 个城区图形及其围堵方案示意图如图 2 所示 图 2 中带有箭头的线段指出了围堵交巡警服务平台及 出口 3 2数据的读写及处理方法 在进行作图时需要将已有数据读到 Matlab 工 作区中使用 具体读取方法有以下三种 A直接将 Excel 数据拷到 Matlab 中的 m 文 件中 并赋给某一变量 B通过 Excel 的加载宏工具建立 Matlab 数据 与 Excel 数据之间的相互读取功能 C通过 Matlab 中的 xlsread 函数将 Excel 中 指定文件读至 Matlab 工作区 3 3Matlab 函数的编写与结果的存储 在计算节点与节点之间的最短路时首先需要 计算连接节点之间的距离 通过 Matlab 中已经读 入的数据及距离函数可计算获得连接节点之间的 距离 由于在求解最短路时需要使用该结果 故需 保存该数据 具体存储方案有 图 1A区的交通网络与平台设置的示意图 图 2城区的交通网络与平台设置的示意图 18 A直接将数据保存为全局变量以便随时进 行调用 B通过 Matlab 与 Excel 之间的接口将其放置 到 Excel 中 C通过 Matlab 中的 xlswrite 函数将数据写入 的 Excel 中 低版本的 Matlab 软件没有写入功能 需要使用 Matlab7 0 及以上版本 3 4利用工具箱求解数学模型 在 Matlab 工具箱中包含了众多数学建模现成 软件 其中常用且较容易使学生们学会的数学建模 软件主要有 A线性规划 Matlab 求解函数 linprog 线性规 划理论 8 在数学领域基本趋向于完备化的阶段 然 而 线性规划在实践当中的应用仍然没有得到普 及 主要原因在于懂得线性规划的研究工作者基本 都是科研工作者 很少有研究工作者将其投入到实 践当中应用 而相反需要用到线性规划的人并不知 道线性规划能够为其带来的经济社会价值或根本 不可能学会线性规划模型更不用说线性规划模型 的求解了 随着经济社会的发展 落后或发展中国家必然 将会从劳动密集型转化为技术进步型 而技术的进 步离不开数学建模众多方法 其中较易普及的便是 线性规划 毫不夸张的说现如今能够通过软件能够 解决复杂决策问题或不同类型决策问题的人过于 缺乏 其中包括众多教师 那么这一理论及实践的推 广就可想而知了 从而今后的数学教育特别是非重 点院校应该更加重视学生们的理论与实践的结合 及简单理论的深层次推广 而不是漫无目的的传 授多种复杂的理论 但部分教师特别是学基础数 学出身的教师过于迷醉与自己所学领域的探索 而并未考虑到在当今时代本可以盛行的优秀数学 理论及其求解方法的推广 这也在部分程度上体 现了作为大学数学老师所缺乏的各学科全面发展 的能力 B整数规划 Matlab 求解函数 在实践当中整 数规划的使用率也不比线性规划差多少 其中对 于大部分决策问题 0 1 规划可能更具实用性 本 文中提出的题目即是一个典型的例子 这一例子 还可以进一步推广到管理中心的选择问题等众多 问题 在 Matlab 中 0 1 整数规划的求解函数为 bintprog 对于普通类型的整数规划可通过线性规划 函数的四舍五入的方法获取 对于不满足约束条件 的特殊情况可进一步对变量进行约束的方法获取 较优的可行解 lingo 软件当中可直接通过变量的整数约束获 取整数规划问题的最优解 但 lingo软件的数据读 取及处理功能远不及 Matlab 软件 C非线性规划的 Matlab 求解 在 Matlab 中提 供了无约束优化问题的求解算法 而由于非线性规 划问题可通过引进辅助函数将其转化为无约束最 优化问题 D微分方程的 Matlab 求解 在 Matlab 中不仅 可以对微分方程进行数值计算 同时也提供了微分 方程的符号计算方法 E数据的统计描述 分析及模拟方法 F回归 插值与拟合 数学建模方法传授点之 二 最短路问题及行 遍性问题 为了给各个交巡警服务平台分配管辖范围 需 要计算各个节点之间的最短距离 由于已经得知了 与每个节点连接的节点标号及连接节点之间的距 离 故根据 Dijkstra 算法可获得某一顶点至各个节 点的最短距离的同时也可通过 Floyd 算法获得每 个节点之间的最短距离 算法的具体思想及方法参 见参考文献 5 交巡警不仅需要对管辖范围内的案件进行快 速的处理 同时为了避免案件的发生也需要对管辖 范围内进行定期的巡逻 而这一问题正是数学建模 方法中的行遍性问题 目前随着网购热潮的兴起 大部分快递公司急 需懂得快件的投放及管理的人才 在这一过程中管 理者必需懂得最短路问题及行遍性问题方能更加 全面快捷的投递快件 因此将部分数学专业学生培 养为该方面的人才是一个较好的出路 数学建模方法传授点之 三 线性规划问题 在不考虑交巡警服务平台的工作量的前提下 各个交巡警服务平台分配管辖范围的确定问题归 结为每个节点与服务平台之间的距离的最小化问 题 在得知各个节点之间的最短距离的前提下只需 通过 Matlab 循环语句就可以通过逐个比对分配管 辖方法 除了上述分配管辖范围的方法之外 还可以 0 1 建立线性规划模型对其进行求解 由于为各个 交巡警服务平台分配管辖范围 使其在所管辖的范 围内出现突发事件时 尽量能在三分钟内有交巡警 到达事发地 这一问题等价于为各个交巡警服务平 台分配管辖范围 使得从交巡警服务平台到各个节 点的距离总合最短的问题 从而 可建立如下 0 1 19 整数规划模型 min n i 1 m j n 1 dijxij s t n i 1 xij 1 j 1 2 m xij 0 或 1 1 上式中 xij表示第 j 个节点是否属于第 i 个交 巡警服务平台的管辖范围 如果属于则 xij 1 否则 xij 0 约束条件 n i 1 xij 1表示第 j 个节点必须属于某 一交巡警平台管辖范围 dij表示第 i 个节点到第 j 个节点的最短距离 对于重大突发事件 需要调度全区 20 个交 巡警服务平台的警力资源 对进出该区的 13 条 交通要道实现快速全封锁 实际中一个平台的警 力最多封锁一个路口 请给出该区交巡警服务平 台警力合理的调度方案 该问题转化为在 20 个 交巡警服务平台中选出 13 个交巡警服务平台 使得该 13 个服务平台到 13 条交通要道之间的 距离总合最短 从而针对这一问题建立如下 0 1 规划模型 min 20 i 1 13 j n 1 ddijyij s t 20 i 1 yij 1 j 1 2 13 13 i 1 yij 1 i 1 2 20 yij 0 或 1 2 上式中 ddij表示城区 A 中第 i 个交巡警服务 平台到第 j 条交通要道的出口节点之间最短距离 约束条件 20 i 1 yij 1表示第 j 个出口必须由某一交巡 警服务平台所封锁 13 i 1 yij 1表示第 i 个交巡警服 务平台至多封锁一个出口 同理如果该市地点 P 第 32 个节点 处发生了 重大刑事案件 在案发 3 分钟后接到报警 犯罪嫌 疑人已驾车逃跑 为了快速搜捕嫌疑犯 需给出调 度全市交巡警服务平台警力资源的最佳围堵方案 该问题等价于 80 个交巡警服务平台对 17 个出口 的围堵问题 为了尽快进行围堵 需要让围堵时所 行使的路线长度总和最小化 从而可建立出如下 0 1 规划模型 min 80 i 1 17 j n 1 dddijzij s t 80 i 1 zij 1 j 1 2 17 17 j 1 zij 1 i 1 2 80 dddijzij 3000 ddddj zij 0 或 1 3 上式中 dddij表示第 i 个交巡警服务平台至第 j 个出口的最短距离 ddddj表示第 32 节点至第 j 个 出口的最短距离 约束条件 dddijzij 3000 ddddj表 示第 i 个交巡警服务平台如果封锁第 j 个出口 则 第 i 个交巡警服务平台到第 j 个出口之间的距离再 加上 3 分钟的行驶时间 3000m 后的距离要小于等 于案发现场到第 j 个出口的距离 其它约束条件的 解释与 2 式类似 上述三个 0 1 整数规划模型并不复杂 但由 于数据量较大 很难通过人工输入系数矩阵 因 此 必需借助计算机工具计算出各个最短距离 然 后通过算法生成各个系数矩阵 其中存在着大量的 稀疏矩阵 通过循环语句可以较快生成 如果利用 Lingo 等线性规划软件进行求解 不 仅在数据的读写方面存在较多问题 且随着变量个 数的提高短时间内难以计算获得最终结果 数学建模方法传授点之 四 非线性规划问题 通过模型 1 分配出来的各个交巡警服务平台的工 作量并不均衡 每个交巡警服务平台的总发案率为 92 j 1 falixij i 1 2 24 为使各个交巡警服务平台的工作量均衡 需要 调整各个交巡警服务平台所管辖的节点或节点个 数 使得每一个服务平台的案发率尽量接近发案率 平均值 即与发案率平均值之间的差距总和最小 化 同时必须满足与交巡警服务平台之间的距离小 于 3000m 即 3 分钟内能够到达案发现场 从而建 立如下模型 min 24 i 1 falav1 92 j n 1 falixij s t 24 i 1 xij 1 i 1 2 92 dijxij 3000 i 1 2 24 j 1 2 92 xij 0 或 1 4 该模型等价于 20 min 24 i 1 falav1 92 j 1 falixij 2 s t 24 i 1 xij 1 i 1 2 92 dijxij 3000 i 1 2 24 j 1 2 92 xij 0 或 1 5 上述模型为二次规划模型 通过 Matlab 中的 quadprog函数加以求解 但 quadprog函数只能求解 一般情形下的二次规划 不能求解决策变量为 0 1 的二次规划 因此模型 4 和模型 5 还需要寻求 相关非线性规划理论求解方法 9 数学建模方法传授点之 五 数学模型的可行 求解方法 由于模型 5 是一个 0 1 二次规划模型 因此 当变量的个数相对较少时完全可以通过穷举法及 神经网络方法加以求解 由于通过最短距离容易得知与交巡警服务平 台距离小于 3000m 的所有节点 从而模型 5 可利 用人工分配的方法加以求解 但该方法只能近似获 得最优解 在求解模型 5 时可获得每个节点的最优分配 方案 将节点分配给距离最近的交巡警服务平台 但这必然会让部分交巡警服务平台的工作量过高 或过低 此时 可设定每个交巡警服务平台工作量 的上线 然后逐一将各个节点分配出去 在分配过 程中可根据最优分配方案及次优分配方案的差距 分配各个节点 数学建模方法传授点之 六 层次分析方法 在评价交巡警服务平台设置的合理性时 决策 者需要考虑众多因素 不同因素在不同程度上影响 着交巡警服务平台设置的合理性 同时每一个因素 又受到相应子因素的影响 在确定各个指标权重时 需要利用层次分析方法来确定 利用 Matlab 不仅可以较简单的计算出各个特 征值及特征向量 同时还可以用较简单的算法确定 各个指标的权重 相对其它众多软件 Matlab 是一 个较好的层次分析方法权重确定软件 数学建模方法传授点之 七 拟合 在确定交巡警服务平台平均应承担