全国数学建模大赛B组答案之欧阳数创编.pdf
欧阳数创编2011高教社杯全国大学生数学建模竞赛时间：2021.03.02创作：欧阳数承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人 （包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资 料），必须按照规定的参考文献的表述方式在正文引用处 和参考文献屮明确列岀。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公 正、公平性。如有违反竞赛规则的行为，我们将受到严肃 处理。我们参赛选择的题号是（从A/B/C/D屮选择一项填 写）：B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）:欧阳数创编欧阳数创编参赛队员（打印并签名）：1.2.3.指导教师或指导教师组负责人（打印并签名）：期：2011年_月2日赛区评阅编号（由赛区组委会评阅前进行编号）：欧阳数创编日欧阳数创编2011高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人 nnnnnnnnnn评备注欧阳数创编全国统一编号（由赛区组委会送交全国前编号）:全国评阅编 号（由全国 组委会评阅 前进行编 号）:欧阳数创编交巡警服务平台的设置和调度摘要“有困难找警察”,是家喻户晓的一句流行语。警察肩负着刑事执 法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这 些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。本 文通过定性与定量分析.建立优化模型，为交巡警服务平台的设置和调度 提供参考。在第一个问题中，选择Dijkstra最短路径算法，利用Mat lab软件， 先根据城区A交通路口的路线，求出表示各节点之间是否直接相连的(M矩阵，然后根据城区A各节点坐标求出城区A各节点距离的权值矩阵(若两节点内无路则权值为无穷大),接着把权值矩阵化为最短距离矩 阵。根据需要变化最短距离矩阵，建立0-1规划模型，U标是使得出警时 间最短(转化为出警距离最短计算)，列出最优化方程，最后利用Ling。 软件进行求解，得出服务平台管辖路口节点以及堵截路口的最合理方案。 综合考虑交巡警服务平台的发案率和出警时间，采用动态加权平均的方法 算出各个交巡警服务平台的忙碌值。然后进行排名。取大于平均值的前九 名，在城区A增加25个服务平台时，综合这些节点周用交通节点的密 集程度，决定在A区增加三个服务平台，分别为A20附近的节点90(440.5, 381.5) , AK A2和A3区域内的节点67 (401, 359) , A4和A5区域内的节点56 (354, 374)。在第二个问题中， 首先对各城区现有平台设置的合理性进行评佔。 引 入负荷距离法、方差分析法，求得方差、偏差距离、单位平台处理案件数等参数，得出结论：城区C、F服务平台的负担太大，而且警力配置不均 匀；城区D、E服务平台的地理分布与发案的地理分布相差较大，不能及 时赶到发案地点。再针对各个地区的不同情况(人口.面积、发案率.平 台分布疏密程度)，经过科学分析，得出方案为：C区增加节点305 (200, 487)、节点300 (206, 507)、节点207 (333, 511 )为三个新 服务平台，F区增加节点506 (358, 195)、节点522 (371, 244)为两 个新的服务平台；D区中位于坐标为(70, 377)的服务平台D3移动到节 点360 (76.355) , E区中位于坐标为(90, 198)的服务平台E15移动到 节点422 (74, 198)。最后通过比较调度前后的该城区的偏差距离、方 差、单位平台处理按键数的变化，评估解决方案的合理性。在围堵犯罪嫌疑人的时候，采用画树状图的方法，以三分钟为一个层 次，结合概率知识。无论他选择从哪条路出城，得出的围堵方案都能在报 警后六分钟之内抓住犯罪嫌疑人。具体方案为：第一个三分钟出动服务平 台A5、A6、A10、A15、A16、A2、A3、A4、A17、C8、C6、C4、C7和F1,分别派往节点5、6、10、15、16、3、55、60、41、232、244、240、242、561进行围堵。第二个三分钟出动服务平台C2、C3、D1和D2,分别派往节点248、168、349、369进行围堵。如果第一个三分钟时 已经围堵到了犯罪嫌疑人， 那就不用出动第二个三分钟的四个平台，可以 节省警力，而且能确保抓住犯罪嫌疑人。关键字：DijkstraDijkstra 最短路径算法 o_io_i 规划负荷距离法方差树状图1问题的重述“有困难找警察”,是家喻户晓的一句流行语。警察肩负着刑事执 法、治欧阳数创编欧阳数创编安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这 些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每 个交巡警服务平台的职能和警力配备基本相同。山于警务资源是有限的， 如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台 的管辖范围、调度警务资源是警务部门面临的一个实际课题。以给出的条件为例，一共有五个问题需要解决。问题一： 为各交巡警服务平台分配管辖范用， 使其在所管辖的范围内 出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60knVh）到达事发地。问题二：对于重大突发事件，需要调度全区20个交巡警服务平台的 警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平 台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度 方案。问题三：根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平 台的具体个数和位置。问题四：针对全市（主城六区A, B, C, D, E, F）的具体情况， 按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平 台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方 案。问题五：如果该市地点P（第32个节点）处发生了重大刑事案件， 在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑 犯，请给岀调度全市交巡警服务平台警力资源的最佳圉堵方案。2模型的假设（1）交通路口之间的路线都是直线；（2）每条路都是双向的；（3）每个交巡警服务平台的警力相当；（4）每个交巡警服务平台出警速度均为60km/h,不存在堵车等现象;（5）每个交巡警服务平台最多只能封锁一个路口；（6）犯罪嫌疑人对逃跑路线的选择是随机的；（7）犯罪嫌疑人逃跑时所行路线不会重复；（8）犯罪嫌疑人最终LI的为逃出该市，不会在城区内躲藏：（9）犯罪嫌疑人行车速度与警车速度一致，同为60km/h；（10）警方通讯时间忽略不计。3模型的符号说明符号意义节点i的忙碌值案发地理重心的横坐标欧阳数创编欧阳数创编案发地理重心的纵坐标偏差距离从节点i到节点J的权值城区A每两个节点的最短距离矩阵参考附件2全市交通路口节点数据的第个节点节点的横坐标DiyEfijGG节点的纵坐标城区A出入口节点与20个交巡警服务平台的最短距离矩阵节点到节点。的距离平台地理重心的横坐标平台地理重心的纵坐标节点j的出警时间城区各个服务平台案件处理数的方差节点，的案发率i城区A各节点距离的权值矩阵平台是否管辖节点丿（是则为1，否则为0）平台是否负责堵截节点丿（是则为1，否则为0）G、1儿S2y.4.对问题的分析问题一中，我们首先明确最后得出的结果是城区A内20个交巡警 服务平台与交通路口的路线的对应关系。路线即两个路口节点之间的部 分，所以我们将问题转化为求各交巡警服务平台与路口节点的对应关系，则服务平台管理从平台到该节点的最短路径。对Matlab对原始数据进行 处理，用传统的Dijkstra最短路径算法求出城区A每两个路口节点的最短 路径的距离。然后运用线性0-1规划模型，列出优化方程，用Lingo软件 进行求解。问题二中，可以参考对问题一的分析，最后得出结果应为城区A内20个交巡警服务平台与13个出入市区的路口的对应关系。由于一个平台 的警力最多封锁一个路口，也就是每个路口必须指派一个平台的警力，属于指派问题，可以用匈牙利算法解决。匈牙利算法是0整数规划的特殊 形式，所以可以列出优化方程用Lingo软件求解。问题三中，经过统计各个交警服务平台的工作量和出警时间，可以 看出有的服务平台的工作量比较大，而有的服务平台出警时间过长。为了 有一个统一的评价，我们对工作量和出警时间做了动态加权平均，建立出综合评价模型。然后对服务平台排名，排在前儿名的就是工作量和出警时 间相对较大和较长的。所以我们就应该在这些服务平台周圉增设服务平 台。问题四中，从三个角度评估平台分布的合理性。第一个角度考虑到警察肩负着刑事执法、治安管理、交通管理、服 务群众四大职能，希望服务平台尽量与相应案发地点的距离达到最小。 这 里我们参考负荷距离法，引入“平台地理重心”和“案发地理重心”两个 自定义概念，两者分欧阳数创编欧阳数创编别代表平台分布位置与案发地点分布位置，以这两个 重心之间的距离（称为“偏差距离”）为评价标准，距离越小，则该地的平台分布越合理。分别求出六城区的偏差距离，并结合各城区的面积与人 口，进行讨论.评估。第二个角度通过求解每一个城区各个服务平台案件处理数的方差， 然后比较各城区之间的方差，方差越大表示该区警力分配越悬殊，以此评 估服务平台分布的合理性。第三个角度简单地比较各城区单位平台处理案件数，然后判断那些 城区警力资源紧张，需要增设服务平台。最后综合以上三个角度，作出相应的对策。5.模型的建立与求解求解的过程分为三部分。第一部分是对原始数据进行处理，作出求解时可以直接使用的数据 表格。第二部分是针对问题的分析建立模型，得出优化方程。第三部分利用软件对模型进行求解，得出最终结果。5.15.1 问题一5.1.1数据的处理首先从附件2提取三部分的数据：1、城区A各路口节点（共92个）横纵坐标；2、涉及城区A路口节点的路线；3、20个交巡警服务平台对应的路口节点标号。根据以上数据，根据92个路口节点的横纵坐标，制作每两个节点之间 距离的矩阵。如果两节点之间没有路可以贯通则用 s 表示，得出矩阵W。心为矩阵W中的元素，人为节点i到节点j的距离，则有：兀，如=(/,;)xx(Z,j)j7=1 (6)1313工儿1，丿T，2,./,/=,(7)Xj. =0或，/, J = l,2,.n,(8)523模型的求解用Lingo软件编程(程序参考附录3),运行求解，得出一下结果，见 表2o表2 A区出口与对应的封锁平台序号 出入A区的路口标号负责交巡警平台编号112A12欧阳数创编欧阳数创编2345678910111213141621222324282930384862A9A16A14A10A13AllA15A8A7A2A5A4说明：交巡警服务平台A14虽然离交通节点14最近，但为了使全局 最优，我们选择了让平台A14去封锁更远一些的交通节点21,服务平台A13到交通节点22和23的距离都比较近，但山于一个服务平台最多只能 封锁一个路口所以选择了A13去封锁较远的交通节点23。5.35.3 问题三531531 数据的处理首先根据问题一求出的20个服务平台的分布范围和题U附表中的各个点 的发案率，求出每个服务平台每天的工作量，即所管辖的范用内的发案率 之和，见表3。然后再根据每个服务平台跟它所管辖的交通节点的距离之和求出每个平台 的出警时间，因为速度一定，可以用距离表示时间的长短，见表3表3平台的案发率与出警时间平台序号发案率123456789101112131415出警时间89.7691898.1174769. 0096369.24489113.1455084. 8429917. 5770140.77558025.4330317.8885464.992250104.523751. 3233118.3488610.39. 75.66.69. 72.59.658.21.64.648.52.54.8516175. 3欧阳数创编欧阳数创编18196. 13.411. 530.9491214.32099121.936820532模型的建立和求解(1)确定增加平台的个数首先对发案率和出警时间进行动态加权平均。对于一个服务平台来说工作量大要比出警时间长更重要，更能影响服务平台的工作效率。所以我们将工作量的权重定为0.6,出警时间的权重定为0.4。计算他们的忙碌值讣算公式为:B. = 0.6V +0.4必J = 1,2，,20;汁算出他们的综合排名，如表4所示。表4各服务平台的忙碌值和排名平台忙碌值排名平台n11A112OA9A8A7A6A5A4Ao21111611o9.9 6 .6315L 31125219Al14Al5Al7Al6Al38A忙碌值排名44.8 6o67.65我们由表4可以知道,交巡警服务平台A20、A5、A2、A15、AK A4、A7、A13、A3这些点是排名靠前的，所以拟定在这些点周围增加平台。我们将这些点表示在图1上，我们增加的平台最好能减轻至少一个点的工 作量和出警时间，所以我们将这些点分为六个区域。欧阳数创编欧阳数创编400380任务较轻的平台 交通节点 任务较重的平台360340EE32030028026200250300350400450X/mm图1A区的交通节点与平台设置示意图由图1可知，我们可将排名靠钱的点分为儿个区域，A20与其所管 辖的范围为第一个区域，Al、A2和A3及其他们管辖范围为第二个区 域，A4和A5及其管辖范围为第三个区域，A15为第四个区域，A7为第 五个区域，A13为地六个区域。再综合来看A15虽然排名翥前，但由于它管辖的区域节点数太少， 而且发案率比较低，所有在其周围增加服务平台成本高。A7、和A13的 排名比较黑后，管辖的范圉也不是很大，所以决定也不再在这两个区域增 加平台。所以为了尽量减少成本，而且使忙碌值尽量小，所以决定只在A区增加三个平台最好。（2）确定增加平台的位置要确定增加的平台的位置，我们采用重心法。重心法是一种选择销售中心位置，从而使销售成本降低的方法。 它把销售成本看成运输距离和运输数量的线形函数。此种方法利用地 图确定各点的位置，并将一坐标重叠在地图上确定各点的位置。这里 采用这种方法给交巡警服务平台选址。这里用A20管辖的第一个区域为例，将20, 84, 85, 86, 87, 88,89, 90, 91, 92的节点的横纵坐标（2，%）以及案发率（匕），使用公 式：工(9)可以得出重点坐标O为(443.287, 385.1261 ),同理可得另外两个区域的重点欧阳数创编欧阳数创编为:(400.0391, 351.3574)、(360.6503, 377.5613)。(10)然后我们再在途中寻找离这三个重心较近且能分担工作量和出警时间的交通节点，即为我们要求的增加的平台的位置A20附近的节点90(440.5, 381.5) , Al、A2和A3区域内的节点67 (401, 359) , A4和A5区域内的节点56(354, 374)。5.4问题四5.4.1负荷距离法分析5.4.1.1模型的引入首先讲述负荷距离法的基本思想。单一设施选址中要用到多种分析方法： 定性与定量分析方法， 以即将 定量与定性分析相结合的选址度量法等方法。负荷距离法就是一种单一设 施选址的方法。负荷距离法(load-distance method)的LI标是在若干个候 选方案中，选定一个口标方案，他可以使总负荷(货物、人或其他)移动 的距离最小。我们首先定义“平台地理重心”,它是一个城区所有交巡警服务平台 所在节点的横、纵坐标分别取其平均值得到的一个坐标，它代表该城区服 务平台的平均位置。然后我们参考负荷距离法以及加权平均法，定义“案发地理重心”o在一个城区中，以各个路线节点的案发率为权数，对该城区所有路线节点的横、纵坐标进行加权平均，得到一个坐标，它代表该城区发案的平均位 置。最后我们求得城区内平台地理重心与案发地理重心的绝对距离，以该距离的大小评价现有各城区交巡警服务平台设置方案的合理性。5.4.1.2模型的建立与求解对于任意一个城区内任意一路线节点9 = 1，2, ，582),它的重点坐标为(g.)直接引用公式(9)、(10)。其中岭为节点的案发率，所求得的坐标(Cr，CJ为案发地理重心。对于一个共有n个服务平台的城区内， 平台节点色(i=l.n),它的重 点坐标为(Gl，Gv)o欧阳数创编欧阳数创编G,二XAn（11）九Gy = -r zn（12）所求得的坐标为平台地理重心。各区的偏差距离 =.根据上述计算方法，可以得出如下表格：表5各城区平台地理重心与案发地理重心分布情况城区ABCDE平台地理审心G,341.40150. 31269. 4761.00187. 57388. 59G,344.4096. 44438. 82353. 33206. 33272. 91案发地理重心C、:352. 01154. 31257. 5172. 36174. 54379. 88348. 43101. 36442. 29338. 42207. 35267. 19偏差距离d11. 356. 3512. 4518. 7513. 0610. 42F5.4.1.3模型的评价根据表格，理论上时希望所有的服务平台都向特定的方向（从平台地 理重心到案发地理重心的方向）都移动相应的偏差距离。但是山于实际再 该处不一定有节点，而且落实到局部不一定适用。该模型给移动平台的方 向与距离提供一定的参考。542城区内各服务平台案件处理数方差的分析5.4.2.1模型的建立在概率论和统计学中，一个随机变量的方差描述的是它的离散程度， 也就是该变量离其期望值的距离。在概率论和统计学中，一个随机变量的 方差描述的是它的离散程度，也就是该变量离其期望值的距离。首先明确标是求每一个城区各个服务平台案件处理数的方差，并把 它们的方差进行比较，对现有交巡警服务平台设置方案的合理性进行评 价。这里以城区A为例：参考城区A各交巡警平台的管辖范圉（表1）,将每个服务平台（A1-A20）平均每日处理案件总数目作出统计，结果如表6所示。表6城区A各交巡警服务平台每日处理案件数量交巡警平台序号 平均每日处理案件数量A1A2A3A4A510.39. 15.66.69.7A6A72.59.6欧阳数创编欧阳数创编A8A9A10AllA12A13A14A15A16A17A18A1958.21.64.648.52.54.855. 36. 13.411. 5A20然后求出所有服务平台平均每日处理案件总数U的方差，结果为：7.8185-用同样的方法得出城区BF各个服务平台案件处理数的方差厂，得 出如下表格：表7各城区服务平台案件处理数的方差城区S2A7.8185B13.5325C30.3288D11.3467E16.8864F24.28025.421模型的评价这里所求的城区各个服务平台案件处理数的方差，它代表一个城区内 所有服务平台处理案件数U的离散程度，这个方差值越大，则代表这个城 区的警力分配不均衡，应该进行调配。如图我们看到城区C、F的值很大，说明这两个城区有的服务平台 过于繁忙，有的服务平台则有资源闲置的情况发生。应该对这些地区的服 务平台进行调整。5.4.3城区情况综合分析543模型的建立与评价参考附件2全市交通路口节点数据与六城区的基本数据，统计各区人 口密度、平台个数、总案发率并求出单位平台处理案件数，作出联合表格 如下：表8各城区案发情况全市六个城区A各区平台个数208单位人口密度2.7272727270.2038834950.2217194570.1906005220.1759259260.193430657发案率124.566.4187.267.8119.4109.2单位平台处理案件数6. 2258.311. 011764717.5333333337. 969.927272727BCDEF1791511欧阳数创编欧阳数创编根据表格数据我们得知， 一个地区的发案率与该地人口密度呈正相 关关系。而发案率高的城区我们应该分配更多的警力。 山各城区单位平台 处理案件数我们可以得知C、F城区的服务平台工作量过大，而A城区则 偏小，可以将A城区一部分警力分配到警力不足的城区。544解决方案及其评价根据5.4.K 5.4.2以及5.4.3的分析，可以看出C区、F区服务平台 负担过重，并且存在警力分配不均衡的现象，应该相应增加平台个数进行 调整；D区、E区的偏差距离过大，应该相应调整服务平台的位置，使偏 差距离降低。5.441增加平台的方案这里参考问题三在A区增设点解决方法与附录1中全市六区交通网 络与平台设置的示意图，并遵循以下两个原则：1尽量在服务平台分布比 较稀疏的区域；2.尽量在负担大的服务平台附近的区域。 最后我们定出C区增加节点305 (200, 487)、 节点300(206, 507)、 节点207 (333, 511)三个服务平台，F区增加节点506 (358, 195)、 节点522 (371,244)两个服务平台。我们用各服务平台处理案件数H的平均数来评价这个解决方案。服务平台增加后，C区与F区单位平台处理案件数分别为9.36、8.4,比原来的11.01176471、9. 927272727要小，更接近平均水平,有效 减轻服务平台负担。而C区与F区各个服务平台案件处理数的方差变为17.5594、12.1292,相比原来的30.3288、24. 2802有显著的降低。也就是 说增加了以上服务平台后，城区C、F警力分配更加平均，平台负担不均 衡的现象得到改善。5.44.2移动平台的方案根据偏差的距离与方向，我们把相应的点都移动，结合实际情况，参 考与附录1中全市六区交通网络与平台设置的示意图，把平台设在服务平 台稀疏的区域。最后决定：D区中位于(70, 377)的服务平台D3移动到 节点360 (76. 355) , E区中位于(90, 198)的服务平台E15移动到节点442 (74, 198)。移动后，D区与E区的偏差距离从18.75、13.06分别变为16.43、12,说明服务平台更接近于案发的地点。5 5 5 5 问题五551551 模型的建立问题五是一个圉堵问题，各节点间形成复朵的道路网络，还要考虑时间问题。所以我们决定用树状图的方法，再加上各个节点到P32的距离，就可 以得出最佳围堵方案。我们利用三分钟时段来考虑我们围堵的方案。 我们釆用树状图来描述犯 罪嫌疑人的逃跑路线。我们还要结合犯罪嫌疑人的时间来看。我们用树状图表示出犯罪嫌疑人在A区、C区、D区和F区的逃跑路欧阳数创编欧阳数创编线示意图。见图2和图三。说明：(1)图中的直线长度只表示方向，不表示路程的长度，具体的 按到P32的最短距离见附录4(2)由于犯罪嫌疑人逃到D区和F区的路线比较少，就把他们两的 路线示意图融合到A区的图中区了。图2在A区D区和F区可能逃跑的路线欧阳数创编欧阳数创编图3在C区里可能逃跑的路线第一、当犯罪嫌疑人先逃跑三分钟他途经的距离为3km。他可能已经 经过的点为7、33、31、30、47、34、8、46、9、45、36、48三分钟后 接到命令，立即进行道路封锁和围堵，每个平台封锁一个节点，三分钟时 可以立即封锁的路口为交巡警服务平台（A5, 5）、（A6, 6）、（A10, 10）、（A15, 15） .（A16, 16）。这些路线圉堵到犯罪嫌疑人的概率为0.50o而且此时犯罪嫌疑人从A区逃到E区和B区的路线全 都被封锁，大大缩小了搜捕范围。我们已经封锁了的点在树状图中就不用 在考虑了。因为服务平台到达交通节点的时间为三分钟左右，所以我们就 以三分钟为一个时间段考虑嫌疑犯逃跑的距离。第二.当犯罪嫌疑人逃跑六分钟时他途经的距离为6kmo可能到达 的节点为图中的55、61、237等。在A区交巡警在这三分中内可以封锁 的交通节点为A区（A2：3）、（A3： 55）、（A4： 60）、（A17：41） , C区（C8： 232）、（C6： 244）和D区（D1： 349）。此时围堵 到犯罪嫌疑人的概率为0.62o同时还有正在赶去圉堵的服务平台有A区的（A1, 40）、（A19： 4） , C区的（C2： 248）、（C3： 168）.欧阳数创编欧阳数创编（C4： 240）、（C5： 273）（C7： 242）、，D区的（D2： 369） , F区的（F1： 561）。第三、当犯罪嫌疑人逃跑九分钟时他途经的距离为9kmo可能达到 的节点为图中的38、39、244等。在A区交巡警能在三分钟到六分钟成 功封锁的交通节点为（A1： 40）、（A19： 4） , C区的（C2： 248）（C3： 168） .（C4： 240） ,（D2： 369）和（F1： 561）。此时犯罪嫌疑人从A区逃到D区和F区的路线也全都封锁了，范围就更小了。而且 此时在A区内所有可能的逃跑路都已经成功围堵。此时成功围堵到的概 率为1.552方案的改进对于上面的方案因为存在随机性。因为各个服务平台和发出命令的总部是一直保持联通， 可以随时知道是否抓到了犯罪嫌疑人。 所以有的服务 平台离封锁节点近的，且离P32这个点比较远时，就可以在刚开始围堵 的三分钟不出动，只是在服务平台待命，如果三分钟后没有围堵到犯罪嫌 疑人，这些警力再出动。第一个三分钟出动的服务平台（A5： 5）、（A6： 6）、（A10：10）、（A15： 15） x （A16： 16）、（A2： 3）、（A3： 55）、（A4：60）、（A17： 41 ）、（C8： 232）、（C6： 244）、（C4： 240）、（C7： 242）和（F1： 561）。第二个三分钟出动的服务平台（C2： 248）、（C3： 168）、（D1： 349）和（D2： 369）。6.模型评价与优化在问题一中，无法使所有解都满足在3分钟内有交巡警（警车的时速 为60km/h）到达事发地，但是路径已经满足最短，无法再进一步优化。 但是实际问题中，交巡警是在路段进行巡逻的，而不是固定在交巡警服务 平台。我们可以让交巡警尽量分散警力，形成警力网，一旦有一个地区发 案，可以及时发现，并通知其他交巡警赶来。在问题三中，权重的分配可以随着条件的变化而进行修正。在问题四中提出的负荷距离法，当两者重心相距十分近的时候，案发 地点与服务平台的距离仍然有可能很大。所以还要根据具体情况进行分 析，这种方法的适用性必须结合实际才可以使用。在问题五中，犯罪嫌疑人行车速度有可能回比出警速度更快，警方堵 截会更加困难，这个时候模型就需要作出调整。7.参考文献1韩中庚，数学建模方法及其应用M,北京：高等教育出版社，20052韩中庚，数学建模竞赛一一获奖论文精选与点评，北京：科学出版 社，20073汪小帆，李翔，陈关荣，复杂网络理论及其应用，北京：清华大学出 版社，2006.44姜启源，数学模型（第二版），北京：高等教育出版社，19925王海英,图论算法及其MATLAB实现，北京：北京航空航天大学出版社,2010.26韩中庚，数学建模方法及其应用，北京：高等教育出版社，2005.6谢金星，优化建模与LINDO/LINGO软件，北京：清华大学出版社，2005.7欧阳数创编欧阳数创编8盛骤，谢式千，潘承毅，概率论与数理统讣，北京：高等教育出版 社，2008. 68.附录：附录1求连通图最短距离矩算法阵的MATLAB实现$连通图中各定点最短距离的讣算Function D = shortdf(W)$对于W(iz j),若两顶点间存在弧，则为弧的权值，否则为inf;当时，W(i, j ) =0n=length(W);D=W;m=l;while mD(i,m)+D(m,j)D(i, j)=D(i,m)+D(mz j);令距离进行更新endendendm=m+1;endD;附录2问题一的lingo程序model:sets :node/192/:y;tp/120/net(tpz node) :d,x;endsetsdata :d=.!数据过多，省略不表。欧阳数创编欧阳数创编enddatamin=sum(net:d*x);Qfor (net:bin(x);for (node(i) :sum(net(jz i) :x (j,i)=1); end附录3问题二的lingo程序model: sets :tp/1.20/;ex/113 /;net(ex,tp):x,d;endsetsdata :d=f!数据过多，省略不表。enddatamin=sum(net:x*d);Qfor (net:bin(x);for (ex(i) :sum(tp(j) :x (i,j)=1); for (tp(i) :sum(ex(j) :x (j,i)1); end3分钟内节点78949分钟30与32的距离11.4018附录内到P32的距离483到6分钟24. 303813. 375517. 690331323317. 232711.704705. 099与12.665432的距离21.93338. 768226. 93328. 641222.67624. 208节点3435536454647欧阳数创编欧阳数创编615163749051525355565961173232233234235236237245247节点2310428383940445457586063646566671712166到9分钟欧阳数创编39. 074141.386333. 015732.03243. 768247. 253551.061455. 36260. 476452. 103959. 60523. 97693. 303846. 596857. 203451. 695850. 460541.281740. 914235. 914256. 12128.7397与32的距离85. 879464.762987. 968761.881888. 904864.947361. 947379.624976.392662.153869. 287161. 787177. 426586. 340685. 833680. 002683. 164987. 407676. 267785. 8724欧阳数创编22822923023123824124224324424689. 07489. 729378.067469. 056664.198580. 32874.406275. 067468.121265. 4619488560561:86. 235564. 031987. 9692021.03.02创作：欧阳数欧阳数创编时间
