2023年全国大学生数学建模竞赛全国一等奖论文

MACROBUTTONMTEditEquationSection2SEQMTEqn\r\hSEQMTSec\r1\hSEQMTChap\r1\h2023高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规那么.我们完全明白，在竞赛开始后参赛队员不能以任何方式〔包括、电子邮件、网上咨询等〕与队外的任何人〔包括指导教师〕研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规那么的,如果引用别人的成果或其他公开的资料〔包括网上查到的资料〕，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规那么，以保证竞赛的公正、公平性。如有违反竞赛规那么的行为，我们将受到严肃处理。我们参赛选择的题号是〔从A/B/C/D中选择一项填写〕：B 我们的参赛报名号为〔如果赛区设置报名号的话〕：20231854所属学校〔请填写完整的全名〕：南京理工大学参赛队员(打印并签名)：1.严润羽 2.于跃3.王谦指导教师或指导教师组负责人(打印并签名)：李宝成日期：2011年赛区评阅编号〔由赛区组委会评阅前进行编号〕：2023高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号〔由赛区组委会评阅前进行编号〕：赛区评阅记录〔可供赛区评阅时使用〕：评阅人评分备注全国统一编号〔由赛区组委会送交全国前编号〕：全国评阅编号〔由全国组委会评阅前进行编号〕：题目：交巡警效劳平台的设置与调度摘要第一题第一问：要求给出分配A区平台管辖范围的解决方案，本文先利用图论有关知识，用MATLAB软件实现Floyd算法，求出各平台到所有路口的最短路径矩阵，除以速度即得最短时间矩阵，然后在最短时间矩阵中分别按：1.最快出警时间原那么；2.同时兼顾出警时间和平台工作量均衡原那么〔方差最小〕，得到两个优化模型并求解。第一题第二问：求对A区13个出口实行快速封锁的最正确方案。这是一个优化问题，在满足约束条件〔每个路口由一个交巡警平台负责封锁，每一个交巡警效劳平台的警力最多只能封锁一个交通要道〕的根底上，使得封锁各个出口的时间中的最大值最小。由此建立的优化模型用LINGO编程，最后得出一个最正确方案。第一题第三问：先通过分析计算说明A区交巡警效劳平台的设置不合理，然后建立了一个0-1规划模型，将题目中的合理性要求〔每个平台的工作量均衡、各个地方的出警时间不能过长、增加的平台数为2至5个等〕作为约束条件，将增加的平台数最少作为目标函数，用LINGO求解，得出增加4个平台的最优方案。第二题第一问：将主城分成六个区，先根据附表中每个地区的案发率、人口、面积用MATLAB大概计算出每个地区的合理交巡警平台数的范围。然后在每个地区内，由这个范围，在原来平台的根底上增加、减少或更换一些平台，使得该地区的效劳平台满足一定的合理性要求，这个作为约束条件。在此根底上，要求对平台所做的变动最小，这个作为目标函数，构造出一个优化模型。通过LINGO得出最优方案，与原方案比拟，给出平台的修改方案。第二题第二问：求围堵方案，本文通过MATLAB编程，将嫌犯在一定时间t内能到达的点的集合B求出，并以B为根底进一步求出警察所需要封锁的点的集合C，且证明了只要警察在时间t内封锁C中所有点，就能完全围堵住嫌犯以便展开下一步搜捕工作。确定了这些点之后，运用第一题第二问的封锁优化模型，以总时间最小作为优化目标，以警察在时间t内封锁C中所有点为约束条件，用LINGO求得一个最正确围堵方案。关键词：交巡警效劳平台0-1规划floyd算法lingo一、问题重述“有困难找警察〞，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、效劳群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警效劳平台。每个交巡警效劳平台的职能和警力配备根本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警效劳平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警效劳平台的相关情况，建立数学模型分析研究下面的问题：〔1〕附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警效劳平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警效劳平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警〔警车的时速为60km/h〕到达事发地。对于重大突发事件，需要调度全区20个交巡警效劳平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警效劳平台警力合理的调度方案。根据现有交巡警效劳平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。〔2〕针对全市〔主城六区A，B，C，D，E，F〕的具体情况，按照设置交巡警效劳平台的原那么和任务，分析研究该市现有交巡警效劳平台设置方案〔参见附件〕的合理性。如果有明显不合理，请给出解决方案。如果该市地点P〔第32个节点〕处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警效劳平台警力资源的最正确围堵方案。附图1：A区的交通网络与平台设置的示意图附图2：全市六区交通网络与平台设置的示意图说明：〔1〕图中实线表示市区道路；红色线表示连接两个区之间的道路；〔2〕实圆点“·〞表示交叉路口的节点，没有实圆点的交叉线为道路立体相交；〔3〕星号“*〞表示出入城区的路口节点；〔4〕圆圈“○〞表示现有交巡警效劳平台的设置点；〔5〕圆圈加星号“〞表示在出入城区的路口处设置了交巡警效劳平台；〔6〕附图2中的不同颜色表示不同的区。二、问题分析此题主要在不同的要求下，研究交巡警平台的管辖范围分配问题和交巡警平台的优化设置问题，要考虑的因素主要有：警力到达路口的时间，各个交巡警平台间工作量的分配平衡性，平台效劳的群众数量等等。第一题第一问可以首先根据图论的相关知识和floyd算法求出各点间的最短距离〔时间〕矩阵，然后根据具体的要求〔时间最短、工作量均衡〕确定规划目标，用求解一般规划问题的方法求解得到最优方案。第一题第二问很明显是一个优化模型，对某一地区实现快速全封锁就是指在最短的时间内能够封堵所有出口，即封堵每一个出口所用时间中的最大值要最小，由此建立优化模型即可。第一题第三问也是一个优化模型，题目中提出的要求〔工作量均衡、出警时间尽量在3分钟以内、出警时间不能过长〕即为约束条件，目标函数定为增加的平台个数最少，因为这样可以防止资源浪费。第二题第一问的分析应该参加人口和面积因素，全市区分为六块，先分析计算出每个地区相应的一个平台数的合理范围，然后在每个地区内类似于第一题第三问的方法求出具体的修改方案。对于此题的最后一问即围堵方案的求解，难点在于如何定义已将犯罪嫌疑人围堵住，我们可以求解出嫌犯能逃到的范围，进而确定需要封锁的路口，从而将问题转化为与第一题第二问类似的问题，用求规划问题的方法也能求解出最正确方案。三、模型假设1〕假设城区所有道路畅通无阻；2〕假设相邻两个交叉路口之间的道路为直线；3〕假设所有事发现场均在城区路口节点上；4〕假设交巡警警车无故障发生；5〕假设交巡警警车在去事发地时匀速行驶；6〕假设有突发事件发生时交巡警立即接到报警；7〕假设每个平台的工作量等于其所管辖的路口的案发率之和。四、符号说明为了便于说明问题，我们用一些符号来代替问题中涉及的一些根本变量，如表一所示，其它一些变量将会在文中陆续说明。表一局部符号说明符号说明当=1时表示第个节点设置的交警平台管辖第个路口节点当=0时第个节点设置的交警平台不管辖第个路口节点第个路口节点的案发率第个交警平台的工作量表示各个节点第个交警平台到第个路口节点所用的时间五、模型的分析建立与求解5.1问题一的模型求各交巡警效劳平台分配管辖的范围的模型为了求出A区各交巡警效劳平台分配管辖的范围，须先求出任意两个节点之间的最短距离，求很多节点之间最短距离我们采用了图论中的floyd法。Floyd算法的根本思想：

可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个城市而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，...，n(n是城市的数目)，在检查d(ij)与d(ik)+d(kj)的值；在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k的最短距离。所以，假设有d(ij)>d(ik)+d(kj)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(ij)重写为d(ik)+d(kj)，每当一个k查完了，d(ij)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j之间的最短距离了。【8】我们采用Floyd算法，用matlab【4】编程求出A区每两个节点之间的最短距离，由警车速度60km/h，将最短距离转化为最短时间。求出任意两个节点之间的最短时间后有以下两个模型求出个平台的管辖范围：a.考虑时间最短模型用Floyd算法得出结果后，对每个节点分别筛选出到该节点所用时间最短的平台。得到的结果如表二：表二各交巡警效劳平台所管辖的节点及工作量交巡警效劳平台交巡警效劳平台所管辖的节点工作量〔次〕1167686971737475767810.32239*40434470729.733545565665.64457606263646.65549505152535658599.7662.5773032474861*9.6883346599313435458.210101.6111126274.612122541313212223248.514142.5151528*29*4.81616363738*5171741425.31818808182836.1191977793.42020848586878889909192*11.5表格中加星号的数字代表时间超过三分钟的节点。b.考虑时间尽量少和各个平台的工作量尽量均衡的模型用Floyd算法得出结果后，题目要求出警时间尽量小于三分钟，因此我们以时间尽量少为原那么，选出各平台到各个节点所用时间小于三分钟的所有情况〔如果某个节点到所有平台所用时间都大于三分钟，那么选择时间最短的那种情况〕。然后以各个平台的工作量尽量均衡为原那么利用非线性规划模型选出最优的一种组合。工作量尽量均衡以各平台工作量的方差来衡量。其中各平台的工作量为各平台所管辖的各节点的案发率之和。因此我们建立如下模型：step1.以时间尽量少为原那么筛选出各平台到各个节点所用时间小于三分钟的所有情况〔如果所用时间都大于三分钟就选择时间最短的那种情况〕。step2.以工作量尽量均衡为原那么，得到如下非线性规划模型：目标函数是各平台的工作量的方差最小，所以：目标函数为：min=约束条件：各个平台的工作量=各个平台工作量的平均值=每个节点只受一个平台管辖运用数学软件Lingo【2】编程求解得到的结果如表三：表三各交巡警效劳平台所管辖的节点交巡警效劳平台交巡警效劳平台所管辖的节点工作量〔次〕11687273757879807.52239*4071747.43344545570767.2445760626365667.355495253565.866505158596.477604861*6.5883546476.699323637456.210101.6111126274.612122541313212223248.514142.5151528*29*316.41616333438*6.917174142437181884858788897.519196467697781827.820208386909192*6.8表中加星号的数字代表出警时间超过三分钟的路口节点求重大突发事件该区交巡警效劳平台警力合理的调度方案的模型对于重大突发事件要对进出该区的13条交通要道实现快速全封锁，所用的时间长短取决于封锁各个节点时所用时间最长的那个节点，因此全面封锁时只需要使在所有封锁的节点中花费时间最长的那个节点的封锁时间尽量少。所以我们以在所有封锁节点中花费时间最长的那个节点的封锁时间尽量少为目标建立如下非线性规划模型：目标函数：封锁时间最短约束条件：每个交通要道的节点必须有一个交巡警效劳平台的警力来封锁：每一个交巡警效劳平台的警力最多只能封锁一个交通要道：运用数学软件Lingo编程求解得到的结果如表四：表四对于重大突发事件A区交巡警效劳平台警力调度方案交巡警效劳平台封锁节点使用时间〔分〕2626.044487.45166.236303.217298.0210127.5911223.2712236.4813242.3914213.2615284.7516146.7419387.64结论：封锁任意路口的最长时间为8.02分钟，即最快可以在8.02分钟时封锁所有13个交通要道。增加平台的具体个数和位置的模型现有的交巡警效劳平台的调度和分配只考虑了各平台到各节点的时间最短这个因素，没有考虑各效劳平台的工作量是否均衡。假设交巡警效劳平台的工作量为每个平台所管辖的所有节点的案发率之和，因此各平台工作量不均衡的主要原因是各平台所管辖的节点不合理。有些地方出警时间过长主要与交巡警效劳平台的分布不合理有关。因此增加效劳平台后应该使交巡警效劳平台的分布和每个交巡警效劳平台所管辖的节点分配更加合理一些。所以在确定增加平台的具体个数和具体位置时应该考虑各平台到各个节点的时间尽量少和各平台的工作量尽量均衡。在没有增加平台之前，依照最近原那么分配每个平台管辖的节点〔分配方案为第一小题第一问中模型一解得的方案〕：①各巡警效劳平台的工作量如下表五：表五：在没有增加平台之前各巡警效劳平台的工作量交巡警效劳平台12345678910工作量〔次〕10.39.75.66.69.72.59.658.21.6交巡警效劳平台11121314151617181920工作量〔次〕4.648.52.54.855.36.13.411.5各巡警效劳平台到各节点的时间超过三分钟的有六个，别为4.75分、5.70分、3.40分、3.68分、4.19分、3.60分，有三个超过了四分钟；从上述数据可以看出，工作量有些地方很大〔11.5〕，有些地方很小〔1.6〕，工作量很不均衡；六个节点的出警时间超过三分钟，所以此方案不是很合理。b.增加巡警效劳平台，如果增加的效劳平台个数太多，那么会使人力物力财力不到充分利用，造成了资源的浪费。因此我们以增加的效劳平台的个数最少为目标函数建立非线性规划模型。该模型的约束条件是各效劳平台的工作量在一定范围内，以及各效劳平台到各个节点的时间也在一定范围内。在考虑各效劳平台的工作量范围时，我们通过观察表五，先求出各个效劳台的平均工作量为6.225次，又因为增加效劳平台后导致平均工作量有所降低，所以我们把每个平台的工作量定在2.5次到6.5次之间。在考虑各效劳平台到各节点的时间范围时，我们假设各平台到该平台所管辖的路口节点所用的时间少于3分钟的路口节点总数占总路口节点数的95%以上，即超过三分钟的路口节点总数不得超过4个。同时为了防止有些地方出警时间过长的情况，必须使各交巡警效劳平台到所管辖的节点的时间不得超过4分钟。【6】假设在第个节点设置效劳平台，设，否那么。以增加的交巡警效劳平台数最少为目标建立如下的非线性规划模型：目标函数：；约束条件：①各个节点的工作量=②工作量尽量均衡，即每个平台的工作量在2.5次6.5次之间：即：③各交巡警效劳平台到所管辖的节点的时间不得超过四分钟：当时；④超过三分钟的路口节点不得超过4个〔表示超过三分钟的路口节点数〕：当时⑤在某个节点设置交巡警效劳平台时该平台管辖该节点：即运用数学软件Lingo编程求解得到的结果如表六：表六：增加交巡警平台的方案交巡警效劳平台交巡警效劳平台所管辖的节点交巡警效劳平台工作量1169747879806.322426875766.33354556465676.444606263665.855505253586.366515657595.57730476.18836454.9993233356.41010262.811112224275.9121225413132123614142.51515313.716163437465.617174143726.41818738287885.919197177834.62020848690916.12928292.74038394044706.3484849613.289818589924.8分析结果可知：在29、40、48、89这四个节点上增加了四个交巡警效劳平台，各个平台到各个路口节点的时间均不超过四分钟，且超过三分钟的路口节点不超过四个。各个效劳平台的工作量之间相差较小，相对均衡。与未增加平台相比拟，交巡警效劳平台的工作量不均衡和有些地方出警时间过长的实际情况都有了很大的改善。分析研究该市现有交巡警效劳平台设置方案的合理性模型假设：将全市按A、B、C、D、E、F区分开，分别进行分析改良。为判断现有方案的合理性并予以改良，我们首先算出各区所要增设的交巡警平台的数目，然后再用lingo找出满足一定约束条件下增设平台的具体编号。step1.分析各区的交巡警平台的数目的合理性由于平台的任务是：1.处理交通事故；2.效劳群众，因此决定各区平台数目的主要因素应该为：区内案发率之和与区内总人口数。【7】我们把每个区的2因素集中到矩阵A=124.500060.000066.400021.0000187.200049.000067.800073.0000119.400076.0000109.200053.0000其中第一列为区内案发率之和，第二列为区内人口之和，对A进行去量纲化处理后得到C=1.10751.08430.59070.37951.66520.88550.60311.31931.06211.37350.97140.9578由第一题的分析知，A区的平台数目是比拟合理的，因此我们选取A区的平台数目作为标准值来计算其余5个区的合理平台数目。在对平台处理事故和效劳群众赋予相同权重之后，可以得出每个区对应的一个因数，这个因数越大，那么代表此区内的合理平台数越多。因此各个地区的合理平台数除以此地区对应的因数应大致相同，通过这个方法得到6个区应该安排的平台大致数目如下:A:20,B:9,C27,D:15,E:21,F:17和原来各个地区的平台数相比，我们可以得出结论：每个地区都需增加一定数目的交巡警平台数。step2.求具体增加的平台数目以及设置地点如果增加的效劳平台个数太多，那么会使人力物力财力不到充分利用，造成了资源的浪费。因此我们以增加的效劳平台的个数最少为目标函数建立非线性规划模型。这个地区内的交巡警平台设置合理包括：平台工作量均衡以及每个路口的出警时间短。所以我们这个模型的约束条件为：每个平台的工作量均在某个范围内，以及到达每个路口的出警时间在一定范围内。模型如下：目标函数：；约束条件：①各个节点的工作量=②即每个平台的工作量在2到8之间：即：；③各交巡警效劳平台到所管辖的节点的时间不得超过七分钟：当时；④超过三分钟的路口节点不得超过路口总数的10%〔表示超过三分钟的路口节点数〕：当时；〔其中k为各个地区总的路口数〕⑤在某个节点设置交巡警效劳平台时，该平台管辖该节点：即。每个地区都用上述模型，通过LINGO软件编程，那么可以得到最优的平台设置方案和每个平台的管辖范围。最终结果为：A区：平台设置方案不变；B区增加1个平台：163；C区增加9个平台：分别为209、214、241、247、261、271、288、312、315；D区增加6个平台：分别为331、335、338、361、368、370；E区增加6个平台：分别为388、393、408、419、454、473；F区增加5个平台：分别为509、525、529、539、558、578。最正确围堵方案模型模型假设：嫌犯和警察开车的速度一样快；假设接到报警后分钟，嫌犯可能到达的所有路口的集合为〔此时嫌犯最多逃了+3分钟〕，而与中元素〔路口〕直接相邻，且嫌犯在t+3分钟内不能到达的路口的集合为，假设警察在分钟内可以到达中的每个路口，那么认为警察成功将嫌犯围堵在一定区域内〔证明如下〕，从而可以进行下一步的搜捕工作。证明：设接到报警后t分钟警察已经到达C集合中的点，而嫌犯经过t+3分钟的逃窜后必定在B集合中的某一点〔或该点到相邻某点的道路〕上，此时嫌犯的选择有且只有2个：1.去C集合中的某点，由于警察已经封锁C集合中所有点，嫌犯必定被抓；2.继续呆在B集合中的某点〔或该点到相邻某点的道路〕上，这种情况下嫌犯还要面临以上两个选择，嫌犯仍然无法逃脱警方包围。在以上2种情况中，嫌犯均无法逃脱警方的包围，因此可以认为警方成功围堵了嫌犯。实际操作中，根据不同的t，我们用Matlab程序〔见附录〕筛选出集合、，然后将问题转化为：寻找最小的t值，使得将C中任意一个路口封堵所需的时间均小于t分钟。在此约束的根底上，寻找最节约资源的方案〔即封堵时间总和最小〕。这是一个非线性规划模型，可以借助于Lingo软件实现。为了找出的最小值及最正确围堵方案，我们可以采取对t依次赋值，通过LINGO程序是否能输出可行解来判断“将C中任意一个路口封堵所需的时间均小于t分钟〞这个问题是否有解。假设有解，LINGO程序〔见附录〕输出的结果即为封堵住所有路口所需的最小总时间，以及具体哪一个平台封锁哪一个路口。此非线性规划模型如下：目标函数：封堵住所有路口所需的总时间最小，即Min约束条件：封锁C中任意一个路口的时间必须小于t：；对于C中的任意一个路口，有且仅有一个交巡警平台出警封锁：=1；③对于任意一个交巡警平台，最多只能封堵一个路口：1；其中t为常数，规定其精确到1分钟，在执行程序前由人为设定。t的设定：我们先设t=5，无可行解；t=15，有可行解，所以最小的t在5和15之间。再取中间的t=10，无可行解，那么最小的t在10和15之间。依此类推，最后得出t=10时无解，t=11时有解，说明最短在11分钟内警察可以封锁所有嫌犯可能出逃的路口，从而成功围堵嫌犯，最正确围堵方案如表七：表七：最正确围堵方案需要封堵的路口节点132485899092175178179182对应交巡警效劳平台131220181917175178179182到达路口所需的时间〔分〕03.590.451.823.655.480000需要封堵的路口节点186193212213221248252254275277对应交巡警效劳平台176168173174172321167169171170到达路口所需的时间〔分〕1.962.8210.211.654.675.563.812.226.412.23需要封堵的路口节点293370371372459471487491521528对应交巡警效劳平台18032032637214384374378477484到达路口所需的时间〔分〕5.757.8110.5704.2548.599.032.896.53需要封堵的路口节点530535544554563565567568对应交巡警效劳平台48147647816482475480485到达路口所需的时间〔分〕1.531.762.1310.718.261.381.664.89由表七可知：封堵任意路口所需的最长时间为10.57分钟，小于11分钟，此解可行。且消耗的封堵总时间最小，封堵范围最小，最节约社会资源。六、模型的讨论与改良1、建立模型时，考虑的约束条件越全面，得出的结果越准确。2、在建立局部模型时，人为的主观因素比拟大，结果的置信度可能会受到影响。3、在求解新增加的交巡警效劳平台的个数和具体位置时，我们可以考虑人口密度对新增平台的个数和具体位置的影响，这样得出的结果更具有说服力。七、模型的评价与推广1.模型的优点〔1〕本文所建立的模型具有一般性，能解决一些与此题类似的一些问题。〔2〕在建立模型时考虑的约束条件比拟全面，具有很强的代表性和合理性。〔3〕在求解围堵罪犯的最正确方案时，我们采用的模型可以求出罪犯以任意的速度匀速逃跑时的最正确围堵方案，具有较强的实用性。2.模型的缺点〔1〕在求解新增加的交巡警效劳平台的个数和具体位置时，我们采用的模型，人的主观因素比拟大，结果的置信度可能受到一定的影响。〔2〕在分析全市交巡警效劳平台设置的合理性时，没有找出哪些具体的不适宜的点，只是给出了一个比拟粗略的解决方案。3.模型的推广本文所建立的模型适用于评价局部选址问题是否合理，并且为局部选址问题提供一些算法。参考文献[1]姜启原，数学模型，北京，高的教育出版社，2003.08[2]谢金星，薛毅，优化模型与LINDO/LINGO软件，北京，清华大学出版社，2005.07[3]周建兴，岂兴明，矫津毅，常春藤，MATLAB从入门到精通，北京，人民邮电出版社，2023.04[4]郑阿奇，曹戈，MATLAB实用教程，北京，电子工业出版社，2023.05[6]柴干，方程炜，刘庆全，周家祥，道路交通紧急救援效劳点的优化选址，中国平安科学报，第十九卷第十期：160-165，2023.10[7]陈永洮，梅建波，南箔，GIS在多功能警务平台和警力配置中的应用，科学导刊，第24卷：103-104,2023[8]侠名，Folyd算法详解，附录Floyd函数function[D,path]=floyd(a)n=size(a,1);D=a;path=zeros(n,n);fori=1:nforj=1:nifD(i,j)~=infpath(i,j)=j;endendendfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendend1.1第一题第一问分配各平台管辖区域的matlab程序A=xlsread('location');A1=zeros(582,582);fori=1:582forj=1:582A1(i,j)=((A(i,1)-A(j,1))*(A(i,1)-A(j,1))+(A(i,2)-A(j,2))*(A(i,2)-A(j,2)))^0.5;end%A1:任意两点间的直线距离endLath=xlsread('lath');A2=inf(582,582);fori=1:928A2(Lath(i,1),Lath(i,2))=0;A2(Lath(i,2),Lath(i,1))=0;%A2:表示任意两点间直接连通关系的矩阵endA1=A1+A2;fori=1:582A1(i,i)=0;%A1:初始邻接矩阵endFtime=floyd(A1)/10;%Ftime:最短时间矩阵Af=Ftime(1:92,1:92);%Af:A区所有点对点全时间矩阵G=xlsread('Gl');%G:所有路口发生事故的次数Ag=G(1:92,:);%Ag:A区路口发生事故的次数At=Af(1:20,:);At1=At;fori=1:20forj=1:92ifAt(i,j)>3At1(i,j)=0;endendendtem=sum(At1);forj=21:92iftem(1,j)==0fori=1:20ifAt(i,j)==min(At(:,j))At1(i,j)=At(i,j);endendendendfori=1:20forj=21:92ifAt1(i,j)==0At1(i,j)=inf;endendendfori=1:20forj=1:20At1(i,j)=inf;endendfori=1:20At1(i,i)=0;%At1:筛选后20个平台对92个点的时间矩阵endAtt=zeros(20,92);fori=1:20forj=1:92ifAt1(i,j)<10Att(i,j)=1;endendendAt2=zeros(20,92);fori=1:20k=0;forj=1:92ifAt1(i,j)<10k=k+1;At2(i,k)=j;endendendAt3=zeros(92,20);fori=1:92k=0;forj=1:20ifAt1(j,i)<10k=k+1;At3(i,k)=j;endendendxlswrite('Att',Att)xlswrite('Alltime',At)xlswrite('time',At1)An=zeros(20,92);forj=1:92fori=1:20ifAt(i,j)==min(At(:,j))An(i,j)=1;%An:最快反响时间下平台对路口的直接分配关系矩阵，0代表不分配，1代表分配endendendAn1=zeros(20,92);fori=1:20k=0;forj=1:92ifAn(i,j)==1k=k+1;An1(i,k)=j;%An1:最快反响时间下的范围矩阵endendendxlswrite('answer1',An1)Agzl=An*Ag;Dy3=[];fori=1:20k=0;forj=1:92ifAn(i,j)==1&Af(i,j)>3k=k+1;Dy3(i,k)=j;endendendxlswrite('最短时间下工作量',Agzl)xlswrite('最短时间下大于3',Dy3)Ax=xlsread('x');Agzl=Ax*Ag;Dy3=[];fori=1:20k=0;forj=1:92ifAx(i,j)==1&Af(i,j)>3k=k+1;Dy3(i,k)=j;endendendxlswrite('优化后工作量',Agzl)xlswrite('优化后大于3',Dy3)优化工作量的lingo程序model:sets:supply/1..20/:c;need/1..92/:a;link1(supply,need):t,x;endsetsdata:@ole('D:\x.xls',x)=x;a=@ole('D:\a.xls',a);t=@ole('D:\time.xls',time); enddatamin=@sum(supply(i):(0.05*@sum(supply(i):c(i))-c(i))^2);@for(supply(i):c(i)=@sum(need(j):a(j)*x(i,j)));@for(need(j):@sum(supply(i):x(i,j))=1);@for(link1(i,j)|t(i,j)#ge#20:x(i,j)=0);@for(link1(i,j):@bin(x(i,j)));end1.2第一题第二问计算封锁交通要道方案的lingo程序model:sets:supply/1..20/;need/12,14,16,21,22,23,24,28,29,30,38,48,62/;links(supply,need):t,x;endsetsdata:@ole('D:/x12.xls',x)=x;t=@ole('D:/t1.xls',t);enddatamin=@max(links(i,j):t(i,j)*x(i,j));@for(supply(i):@sum(need(j):x(i,j))<=1);@for(need(j):@sum(supply(i):x(i,j))=1);@for(links(i,j):@bin(x(i,j)));end1.3第一题第三问计算增加平台个数和位置的lingo程序model:sets:supply/1..92/:c;point/1..92/:z,a;links(point,point):t,x;endsetsdata:@ole('D:\z13.xls',z)=z;@ole('D:\x13.xls',x)=x;@ole('D:\z13.xls',work)=c;a=@ole('D:\a.xls',a);t=@ole('D:\atime.xls',atime); enddatamin=n;@for(point(i):x(i,i)=z(i));m=@sum(links(i,j)|t(i,j)#ge#3:x(i,j));m<=4;@for(links(i,j)|t(i,j)#ge#4:x(i,j)=0);z(1)=1;z(2)=1;z(3)=1;z(4)=1;z(5)=1;z(6)=1;z(7)=1;z(8)=1;z(9)=1;z(10)=1;z(11)=1;z(12)=1;z(13)=1;z(14)=1;z(15)=1;z(16)=1;z(17)=1;z(18)=1;z(19)=1;z(20)=1;n=@sum(point(i):z(i));n>=22;n<=25;@for(links(i,j):x(i,j)<=z(i));@for(point(i):c(i)=@sum(point(j):a(j)*x(i,j)));@for(point(i):c(i)>=z(i)*2.5);@for(point(i):c(i)<=z(i)*6.5);@for(point(j):@sum(point(i):x(i,j))=1);@for(links(i,j):@bin(x(i,j)));@for(point(i):@bin(z(i)));@gin(n);end2.1第二题第一问解决现有方案不合理性的lingo程序A:sets:supply/1..92/:c;point/1..92/:z,a;links(point,point):t,x;endsetsdata:@ole('D:\21A\za.xls',z)=z;@ole('D:\21A\xa.xls',x)=x;@ole('D:\21A\ca.xls',work)=c;a=@ole('D:\21A\a.xls',a);t=@ole('D:\21A\time.xls',time); enddatamin=n;@for(point(i):x(i,i)=z(i));m=@sum(links(i,j)|t(i,j)#ge#3:x(i,j));m<=9;@for(links(i,j)|t(i,j)#ge#7:x(i,j)=0);z(1)=1;z(2)=1;z(3)=1;z(4)=1;z(5)=1;z(6)=1;z(7)=1;z(8)=1;z(9)=1;z(10)=1;z(11)=1;z(12)=1;z(13)=1;z(14)=1;z(15)=1;z(16)=1;z(17)=1;z(18)=1;z(19)=1;z(20)=1;n=@sum(point(i):z(i));@for(links(i,j):x(i,j)<=z(i));@for(point(i):c(i)=@sum(point(j):a(j)*x(i,j)));@for(point(i):c(i)>=z(i)*2);@for(point(i):c(i)<=z(i)*8);@for(point(j):@sum(point(i):x(i,j))=1);@for(links(i,j):@bin(x(i,j)));@for(point(i):@bin(z(i)));@gin(n);EndB:model:sets:supply/1..73/:c;point/1..73/:z,a;links(point,point):t,x;endsetsdata:@ole('D:\21B\zb.xls',z)=z;@ole('D:\21B\xb.xls',x)=x;@ole('D:\21B\cb.xls',work)=c;a=@ole('D:\21B\a.xls',a);t=@ole('D:\21B\time.xls',time); enddatamin=n;@for(point(i):x(i,i)=z(i));m=@sum(links(i,j)|t(i,j)#ge#3:x(i,j));m<=7;@for(links(i,j)|t(i,j)#ge#7:x(i,j)=0);z(1)=1;z(2)=1;z(3)=1;z(4)=1;z(5)=1;z(6)=1;z(7)=1;z(8)=1;n=@sum(point(i):z(i));@for(links(i,j):x(i,j)<=z(i));@for(point(i):c(i)=@sum(point(j):a(j)*x(i,j)));@for(point(i):c(i)>=z(i)*2);@for(point(i):c(i)<=z(i)*8);@for(point(j):@sum(point(i):x(i,j))=1);@for(links(i,j):@bin(x(i,j)));@for(point(i):@bin(z(i)));@gin(n);endC:model:sets:supply/1..154/:c;point/1..154/:z,a;links(point,point):t,x;endsetsdata:@ole('D:\21C\zc.xls',z)=z;@ole('D:\21C\xc.xls',x)=x;@ole('D:\21C\cc.xls',work)=c;a=@ole('D:\21C\a.xls',a);t=@ole('D:\21C\time.xls',time); enddatamin=n;@for(point(i):x(i,i)=z(i));m=@sum(links(i,j)|t(i,j)#ge#3:x(i,j));m<=15;@for(links(i,j)|t(i,j)#ge#7:x(i,j)=0);z(1)=1;z(2)=1;z(3)=1;z(4)=1;z(5)=1;z(6)=1;z(7)=1;z(8)=1;z(9)=1;z(10)=1;z(11)=1;z(12)=1;z(13)=1;z(14)=1;z(15)=1;z(16)=1;z(17)=1;n=@sum(point(i):z(i));@for(links(i,j):x(i,j)<=z(i));@for(point(i):c(i)=@sum(point(j):a(j)*x(i,j)));@for(point(i):c(i)>=z(i)*2);@for(point(i):c(i)<=z(i)*8);@for(point(j):@sum(point(i):x(i,j))=1);@for(links(i,j):@bin(x(i,j)));@for(point(i):@bin(z(i)));@gin(n);endD:model:sets:supply/1..52/:c;point/1..52/:z,a;links(point,point):t,x;endsetsdata:@ole('D:\21D\zd.xls',z)=z;@ole('D:\21D\xd.xls',x)=x;@ole('D:\21D\cd.xls',work)=c;a=@ole('D:\21D\a.xls',a);t=@ole('D:\21D\time.xls',time); enddatamin=n;@for(point(i):x(i,i)=z(i));m=@sum(links(i,j)|t(i,j)#ge#3:x(i,j));m<=5;@for(links(i,j)|t(i,j)#ge#7:x(i,j)=0);z(1)=1;z(2)=1;z(3)=1;z(4)=1;z(5)=1;z(6)=1;z(7)=1;z(8)=1;z(9)=1;n=@sum(point(i):z(i));@for(links(i,j):x(i,j)<=z(i));@for(point(i):c(i)=@sum(point(j):a(j)*x(i,j)));@for(point(i):c(i)>=z(i)*2);@for(point(i):c(i)<=z(i)*8);@for(point(j):@sum(point(i):x(i,j))=1);@for(links(i,j):@bin(x(i,j)));@for(point(i):@bin(z(i)));@gin(n);endE:model:sets:supply/1..103/:c;point/1..103/:z,a;links(point,point):t,x;endsetsdata:@ole('D:\21E\ze.xls',z)=z;@ole('D:\21E\xe.xls',x)=x;@ole('D:\21E\ce.xls',work)=c;a=@ole('D:\21E\a.xls',a);t=@ole('D:\21E\time.xls',time); enddatamin=n;@for(point(i):x(i,i)=z(i));m=@sum(links(i,j)|t(i,j)#ge#3:x(i,j));m<=10;@for(links(i,j)|t(i,j)#ge#7:x(i,j)=0);z(1)=1;z(2)=1;z(3)=1;z(4)=1;z(5)=1;z(6)=1;z(7)=1;z(8)=1;z(9)=1;z(10)=1;z(11)=1;z(12)=1;z(13)=1;z(14)=1;z(15)=1;n=@sum(point(i):z(i));@for(links(i,j):x(i,j)<=z(i));@for(point(i):c(i)=@sum(point(j):a(j)*x(i,j)));@for(point(i):c(i)>=z(i)*