1、2011 高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从 A/B/C/D 中选择一项填写）： 我们的参赛报名号为（如果赛区
2、设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011 高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1交巡警服务平台设置的优化模型摘要警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部
3、位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：问题一：(1)根据附件中的图与数据，为城区 A 中各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在 3 分钟内有交巡警（警车的时速为 60km/h）到达事发地。(2)对于重大突发事件，需要调度全区 20 个交巡警服务平台的警力资源，对进出该区的 13 条交通要道实现快速全封锁。实际中一个平台的警力
4、最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。(3)根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加 2 至 5 个平台，请确定需要增加平台的具体个数和位置。问题二：(1)针对全市（主城六区 A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。(2)如果该市地点 P（第 32 个节点）处发生了重大刑事案件，在案发 3 分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。关
5、键词：交巡警服务平台设置 最短路问题 Floyd 算法 MATLAB 编程21 问题重述为了更有效地贯彻实施警察的执法、治安等职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台，每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。现在就某市设置交巡警服务平台的相关情况，需要我们建立数学模型分析研究下面的问题：（1）附件 1 和附件 2 中，分别给出了该市中心城区 A 的交通网络和现有的 20 个交巡警服务平台的设置情况示意图以及相关的数据信息。现要求为各交
6、巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在 3 分钟内有交巡警（警车的时速为 60km/h）到达事发地。对于重大突发事件，需要调度全区 20 个交巡警服务平台的警力资源，对进出该区的 13 条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的情况，拟在该区内再增加 2 至 5 个平台，需要确定增加平台的具体个数和合适位置（2）针对全市（主城六区 A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方
7、案的合理性。如果有明显不合理，请给出解决方案。如果该市地点 P（第 32 个节点）处发生了重大刑事案件，在案发 3 分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。2 模型的假设（1） 题中所提供的数据为真实数据。 （2） 只考虑交巡警平台对路口节点的管辖情况，不考虑对路口节点之间公路的管辖情况（3）出警时道路保持理想畅通（无交通事故、交通堵塞等发生） ，警车行驶正常3（4）在遇到紧急情况时，所有警员以 60km/h 的速度匀速赶赴事发路口。（5）警员必须沿着附件 2 给的路线走，且走的路程都是最短路程。（6）交巡警平台接到报警信号
8、后不考虑反应时间，立马行动；且转弯处不需要花费时间3 符号的说明符号 含义 单位L 从交巡警平台到达出事地块所行使的最大距离 kmt 从交巡警平台到达出事地块的出警时间 minv 恒定的车速 Km/hijD任意两点间的最短距离 mmijC路线起终点之间的距离 mmijE全市所有路口节点到这 80 个交巡警服务平台的最小距离 mmijS一个 282 行 2 列的矩阵 无4 问题的分析4.1 问题一的分析本问题要求根据附件 2 的数据为各交巡警服务平台分配管辖范围，进而给出该区交巡警服务平台警力合理的调度方案；然后结合现实条件，分析如何在A 区增加服务平台，使交巡警服务平台工作量和出警时间更合理化
9、，并找出要增加交巡警服务平台的区域，确定其具体位置。首先结合附件 2 中全市交通路口的节点数据和路线表格，利用 MATLAB 编程算出 A 区路口节点的起终点的路线距离 ，运用 Floyd 算法，计算得到任意两节点间的最短距离ijC（92*92）矩阵，A 区 92 个节点的散点图见图 41（程序见附录一）ijD4200 250 300 350 400 450260280300320340360380400 A之图 41（1） 对第一段话的分析本段所要解决的是 20 个交巡警服务平台管辖范围的划分问题。划分原则是交巡警服务平台到达所管辖路口节点的时间最少，即距离最短。利用任意两节点间的最短距离，
10、找出 2192 路口节点分别到 120 交巡警服务平台的距离的最小值，这样，路口节点就归该距离最小的交巡警服务平台管辖；然后算出每个交警平台所管辖范围的总发案率，绘制成表格。（2）对第二段话的分析发生重大突发事件时，需要调度全区 20 个交巡警服务平台的警力资源，对进出该区的 13 条交通要道实现快速全封锁。该题同样使用 MATLAB 解决最短路的编程问题。除去交巡警服务平台所在的路口节点 12、14、16，只剩下 17个交巡警服务平台和 10 个要封锁的路口节点，即是找 17 个交巡警服务平台分别到 10 个要封锁的路口节点最短距离。根据实际条件：一个平台的警力最多封锁一个路口，因此若有一个
11、交巡警服务平台同时达到两个以上的路口节点距离最短，就找附近的最短距离代替，通过统计最短距离，算出到各个路口的时间，从而确定交巡警服务平台警力合理的调度方案。（3）对第三段话的分析由于现有交巡警服务平台工作量不均衡和部分路口节点出警时间过长，导致了交巡警平台调度的不合理。此问中我们通过在合适的路口节点增加适当数目交巡警服务平台，使交巡警服务平台的设置方案趋于合理化。这里我们给出两种方案，第一，在工作量大和出警时间长的交巡警服务平台上增加警点，这需要运用第一问的结果，交巡警平台的管辖范围，在管辖范5围内，找出工作量大，出警时间长的警点（不超过五个） ，增加平台即可。第二，找出工作量大，出警时间长的
12、警点之后，在其附近路口节点增加交巡警平台，这里要用到 Floyd 算法中的路径矩阵，即找出警点到警点最短路之间的路口节点的标号，统计出现路口节点标号的次数，在路口节点标号重复的次数较高的位置增加交巡警平台。4.2 问题二的分析研究该市现有交巡警服务平台设置方案是否合理可以从两个部分着手：工作量是否均衡；有些地方出警时间是否过长（或距离是否过大） 。首先根据附件二中的数据，利用 MATLAB 编程算出 A、B、C、D 、E、F区路线起终点的距离 ，运用 Floyd 算法，计算得到全市任意两节点间的最短ijC距离 （ 582*582 矩阵） ，全市 582 个节点的散点图见图 42（程序见附录二）
13、ijD0 50 100 150 200 250 300 350 400 450 5000100200300400500600 之之图 42然后用 MATLAB 画图分析该市 80 个交巡警平台的工作量是否均衡。 定义工作量为以下三种情况：工作量=负责节点的数目；工作量=发案率之和；工作量=发案率距离之和。编写程序（程序见附录五）分别可以得到工作量与负责节点的数目、发案率之和、发案率距离之和的条状图。如果图中纵轴方向高度波动较小 ，则此时工作量相对均衡，即现有交巡警平台设置方案合理，否则即为不合理，所以需要我们给出解决方案。P 点发生重大刑事案件，案发三分钟后报警，交巡警平台按案发 5 分钟后，
14、6犯罪嫌疑人可能到达的所有路口节点部署第一道防线，根据警力，再部署案发10 分钟，15 分钟或者更短的时间间隔里部署更密集的第二道、第三道防线，由此得出调度全市交巡警服务平台警力资源的最佳围堵方案5 模型的建立与求解5.1 问题一的模型建立与求解由题和附图 1 知，A 区设有 92 个交叉口的节点，20 个交警服务平台设置点，13 个入城区的路口节点。则平常的路口节点（除去交警服务平台设置点）共有72 个。如图 3-1，其中 120 表示 20 个交警服务平台设置点， （程序见附录三）200 250 300 350 400 45026028030032034036038040012345678
15、91011121314151617181920图 5-1首先计算出 A 区起终点的路线距离 ijC1、根据附件 2 中所给的起点和终点的路线，结合各个节点的坐标位置，用 MATLAB 计算出两点之间的直线距离，得到 92*92 距离矩阵：121212nnnSSSS 2、根据附件 2 中的路线，我们可以得到各节点的邻接矩阵：7121212nnnAA 即如果两个点相邻，则邻接矩阵中相对应的元素的值为 1，否则为 0；例如：8 和 9 这两个点相邻，那么 = =1。89A3、根据 Floyd 算法，为了求出任意两节点之间的距离，需要得到相邻两个节点的直线距离。可以利用距离矩阵的元素 与 的点乘积得到
16、个各路(,)Sij(,)Aij线间的距离矩阵： 121212.*nnnCCSA 4、我们可以将 C 中不相邻点间距离 0 改为无穷大（Inf）从而得到标志点与标志点间的权值矩阵： ，nnnWW 212211即如果 8 和 9 之间不相邻，也即不能直接到达，那么 C 中的 =0 和89A=0 都将变成 和 等于无穷大（Inf ） ，否则则等于 C 中相应元素的数98A898A据。其次计算得到任意两节点间的最短距离 。有了上面的理论，去除大于 92ijS的数据，即不是 A 区的路段，结合各个节点的坐标位置，运用 Floyd 算法、MATLAB 编程很容易就可求得任意两节点间的最短距离 。ijD5、
17、运用 Floyd 算法求出任意两点间最短距离，得到最短距离矩阵 ：121212nnnDD 8（1） 为各交巡警服务平台分配管辖范围在 MATLAB 中编写程序（见附录四）即可筛选出附录一中 120 列到 2192 行的最小的最短距离，并记下此刻相对应的位置。分析整合数据就可得到表 5-1表 51交警平台编号交巡警平台位置标号管辖范围的节点个数管辖范围两点间的距离所管辖的此节点的发案率总发案率67 16.194 0.868 12.071 0.969 5 1.171 11.403 1.173 10.296 0.974 6.265 1.175 9.3005 0.876 12.836 1.178 6.
18、4031 0.8A1 1 101 0 1.710.339 36.822 1.440 19.144 1.743 8 1.744 9.4868 1.170 8.6023 0.972 16.062 0.8A2 2 72 0 2.19.754 22.709 0.955 12.659 165 15.24 0.766 18.402 0.8A3 3 53 0 2.25.657 18.682 0.860 17.392 0.762 3.5 1.263 10.308 1.464 19.363 0.8A4 4 64 0 1.75.849 5 1.250 8.4853 1.151 12.293 0.852 16.594 0.653 11.708 1.456 20.837 0.5A5 5 958 23.019 1.19.7
