2011年全国数学建模竞赛试卷66组

1、摘要和巡警合一的警务模式，既能够对违法交巡警是交通分子起到震慑作用，降低率，又能够增加市民的安全感，同时也加快了接处警时间，提高了反应时效，为社会和谐提供了有力的保障。因此在城市中合理分配交巡警的资源安排交巡警使其全面发挥功能，使调度优化是十分重要的。在处理问题一时，本文首先对道路图创造了优化模型，该模型囊盖了市区的所有交巡公式，再由务管辖道路的类别，先分别对这几类进行了总结得出结论根据附件 2 中个点的坐标画出 A 区示意图，主要通过 CAD求出相邻 2 节点之间的距离，而后对各个交巡务的合理管辖区进行分配。得出 20 个交巡务的具体管辖区域范围。在处理问题二时，根据问题一中得出各个相邻节点

2、间的距离，根据 floyd算法，利用 C+语言编写程序算出交巡务和交通要道的最短距离，得到13*26 的表格，然后利用 lingo 原件求出最佳调度方案。在处理问题三时，本文定义了工作量的概念，利用第一问的结果，算出所有的工作量，然后工作量取出大于 90 的交巡务，然后对其合理安排 25 交巡务，用来解决交巡务的工作量不均衡和有些地方出警时间过长的实际情况。在处理问题四时考虑了城区交巡警数和该区平均率以及密度的定性关系，通过控制变量法分析出D 城区的数过少而需要增加。在处理问题五时，设逃犯逃跑速度为 60Km/h,可以分析出 3 分钟逃犯逃跑的最大距离，然后根据图形考虑其所有逃跑方案，在关键的

3、节点进行堵截。：交巡务工作量调度优化 管辖堵截一问题的提出与重述交巡警整合了资源，将刑事，治安管理，交通管理，服务群众4 项职能有机融合在一起。现代交巡警必将产生强大的司衡力、社会治安的驾驭力、打击于警务资源有限，用交巡警资源。的冲击力，为更好服务社会和谐提供保障。而现在某市由由附件 1 和附件 2 已知该市的数据,为更好地利需完成以下几个问题:（1） 根据附件 1 的示意图和附件 2 的数据，为各个交巡辖范围，使其尽量在 3 分钟内有交巡警能够达到案发地点。务分配管（2）（3） 需要确定（4） 析全市为对A 区 13 条要道进行快速，需要给出该区合理的调度方案。由于交巡警在各个的工作量不等，

4、对该区增加 2-5 个，分配的具体个数与位置。根据所给附件，根据交巡设置的合理性。务的配置原则和任务的合理性，分（5）在对给出的已知点发生刑事后，根据 进行搜捕。分布的位置，采用最佳的方案对罪犯进行，然后调集二模型的假设(1)只发生在节点处，道路中不发生。(2)某一交巡警的管辖范围内发生时，所管辖的其它节点不再发生。(3)在处理时不考虑堵车，红绿灯，并且是匀速行驶。(4)假设发生时，交巡警都在上。(5)假设交巡务对本节点的工作量为 0假设假设嫌疑人犯案后立即驾车逃跑，且速度与相同。接到后立即作出安排。三符号说明用一些符号来代替问题中涉及的一些基本变量，如为了便于描述问题，表 1 所示。其他一些

5、变量将在文中陆续说明。表 1四问题分析题目的第一问要求利用附件 1 的示意图与附件 2 的数据分配各个服务管辖的范围。从图中看出有 92 的节点，20 个以及各节点的连接情况，由于道路复杂，数据较题目的大,决定先用 CAD 画清道路示意图，找出各个相连接点的距离。由设计给出的模型分析计算。第二问，考虑数据庞大，用解决。用 C+语言根据 floyd 算法求出两点间的最短距离。然后利用 lingo 求出最佳调度方案。第三问，实质上是对第一问的扩展，定义工作量，建立优化模型，计算了各工作量，由就近原则分析。第四问， 制变量法分析出第五问，由附件 2 求出各区相应的密度与平均率，然后通过控分配的不均而

6、进行再分配。结合附件 1 图 5.可以分析出 3 分钟逃犯逃跑的最大距离，然后根据图形求出逃犯可能逃跑的路线，然后进行堵截。五模型的建立与求解问题一由假设可知都在且所有的事件都发生在节点上。在接警后赶到事发现场受到时间的限制。其赶到事发现场的时间必须控制在 3 分钟之内。将整个区域分成若干区域，每个管辖一定的范围。由于道路节点较多，先简化模型，由于速度为 60Km/h，由距离公式符号意义v速度t时间s距离n案发率p工作量i标号L数A城区面积h密度m平均率S=v*t，则在 3 分钟内行走了 3Km。先以各个为中心，3Km 为半径画圆。现在再分两种情况进行。图 1 1图 12对于图 1，由于在 3

7、Km 半径区域内没有节点，则其管辖范围为其本身。对于图 2，在 3Km 半径区域内有 3 个节点 1,2,3，但节点 2 在折线处。通过在个CAD 上测得距离 S1+S23Km，故点 2 不在其管辖的范围内。以上是对单的局部分析，下面对两个进行区域性的分析。图 13对图 3，对于图 14区域比如点 2，由于 SA23Km,SB23Km，则把节点 2划分归给B管辖。对于图 4，节点 1 同在A 和B 的管辖范围(SA13Km，SB13Km），那么，根据交巡警设置的原则中的快速出警原则城区接警后确保快速到达现场。采用就近原则，因为 SA1SB1，所以把节点 1 分配给A 管辖。画出 A以上面所述的

8、模型为依据，根据各个节点的坐标，利用 CAD区的示意图如图 15，并找出附件 2 所给出的每 2 个相连节点的距离见附录 1。通过CAD 找出各个的3Km 圆形区域然后再按照以上模型分类求出各个交通的范围。图 15用以上模型得出各个交通表 2下表 2 是所管辖的节点范围。注：（）表示该节点距交巡务超过了 3Km。问题二题中说要对 13 条交通要道实现快速，也就是说各个交巡务的警力到达所有交通要道的时间越短越好。由此，可以建立模型：将 13 条交通要道的节点、30、38、节点的标号所管辖的区域的标号节点的标号所管辖的区域的标号167,68,69,71,73,74,75,76,781126,272

9、（39）,40,43,44,70,721225354,55,65,661321,22,23,24457,60,62,63,64,14无549,50,51,52,53,5615（28）,（29）658,591636,37,（38）730,32,47,48,（61）1741,42833,461880,81,82,83931,34,35,451977,7910无2084,85,86,87,88,89,90,91,（92）48、62巡为 1、2、3、4、5、6、7、8、9、10、11、12、13，以 i 来表示，交1-20 以 j 来表示，用 bij 来表示每个交巡务到每个交通务要道的最短距离。令 y

10、=bij 即为某案各个交巡务的到所有交通要道的距离的和取出所有 y=ymin 的方案，找到每个方案中的 bijmax，bijmax 最小的方案即为最佳方案。首先，路径问题，要求解出所有的 bij（i，j 中每个数只能用一次），这是个最短可以用 floyd 算法来解决，具体来说，假设求从顶点 vi 到 vj的最短路径。如果从 vi 到 vj 有弧，则从vi 到 vj 存在一条长度为 costi,j的路径，该路径不一定是最短路径，尚需进行 n 次试探。然后，考虑路径（ vi，v1 ，vj）是否存在（即判别弧（ vi， v1 ）和（ v1 ，vj ）是否存在）。如果存在，则比较（vi，v1）和（v1

11、，vj）的路径长度，取长度较短者为从 vi 到 vj的中间顶点的序号不大于 1 的最短路径。然后依次类推。以C 语言为载体利用 floyd 算法编写出了一段程序（见附录 2），将 A 区所有节点的坐标输入，则出所有的 bij，呈一个矩阵，列表如下：表 3bij89101112131190.01195.16120.8358.81118.548.852172.29177.44103.1139.82103.160.353151.17156.328260.9481.9843.934162.27155.3581.0348.6173.963.55113.07106.1531.8394.2124.7652.

12、55bij12345671222.36160.2892.87192.93210.96225.02228.932204.64141.373.88173.95191.97206.03211.213183.52127.6760.26160.32178.35192.41190.094219.97150.0982.67182.73200.76214.82226.545176.28129.762.28162.35177.5191.55182.856176.5913062.59162.65177.8191.86183.167149.15109.0141.6141.66150.36164.42155.7281

13、40.9394.3426.92126.99142.14156.19147.59130.1182.7415.33115.39131.32145.38136.681075.87127.7669.5795.1177.0891.1382.441137.9183.37113.9550.7232.746.7538.05120119.5145.4386.8568.8364.7735.921359.7759.73127.1527.089.06523.8514119.5067.4232.6550.6864.7383.5915170.3132.9865.56165.63171.51185.56176.871614

14、5.4367.420100.07118.09132.1515117218.92149.0381.62181.68199.71213.77225.4918242.47185.14117.73217.79235.82249.88249.0419225.47169.61102.2202.26220.29234.35232.0420269.46212.13144.71244.78262.81276.86276.03得到 bij 的矩阵后，来求解最佳调度方案，这是一个最优化问题，用 lingo利用 0-1 规划来编写程序求解（程序见附录 3），将 bij 矩阵输入，出最佳方案为 13-1,16-2,3-

15、3,14-4,10-5,11-6,12-7,15-8,7-9,5-10 ，1-11,8-12,19-13.其中“-”前面的数字为交巡务的标号，“-”后面的数字为交通要道的。将交通要道的还原成交通要道节点的后，13-12,16-14,3-16,14-21,10-22,11-23,12-24,15-28,7-29,5-30,1-38,8-48,19-62.即节点 13 处交巡处交巡务的务去的去节点 12 处的交通要道，节点 16节点 14 处的交通要道，节点 3 处交巡务平台的去节点 16 处的交通要道，节点 14 处交巡务去的去节点 21 处的交通要道，节点 10 处交巡务去的节点 22 处的交

16、通要道，节点 11 处交巡务去的节点 23 处的交通要道，节点12 处交巡务的务去的节点 24 处的交通要道，节点 15 处交巡节点 28 处的交通要道，节点 7 处交巡务的去节点 29 处的交通要道，节点 5 处交巡务的去节点 30 处的交通要道，节点 1 处交巡务的去节点 38 处的交通要道，节点8 处交巡的务去的去节点 48 处的交通要道，节点 19 处交巡务节点 62 处的交通要道。利用该 lingo 程序还可以得到 bijmax 为 80.15，即在最佳方案中，最晚所经过的距离为 80.15mm*100000=8.015km，因为到达应的节点的速度为 60km/h,即 1km/min

17、.且 t=s/v=8.015/1=8min，于是若应用该最佳方案，可在 8min 时该区的 13 条要道。问题三由假设中点到其所属定义的工作量的概念 P=S*N，即等于某节点的案发数与该节的距离乘积之和。现在引入这个概念。由于该问是第一问的扩展以及再优化。根据第一问各个所管辖的节点建立一个模型如下：6113.37106.4632.1494.5225.0653.37785.780.155.8373.5312.979.928102.28104.9330.6158.8530.9986.77997.76107.2434.9247.2641.9993.3710141.95151.4479.11101.5

18、86.19147.6111186.33195.82123.5145.88130.57191.9912217.81227.3154.98177.36162.05223.4713228.08237.57165.25161.21172.32213.3214180.5189.17114.84101.48121.91153.591547.5257.0144.0197.551.09118.116113.08121.7547.4334.0654.586.1717186.57195.24120.9247.56127.9978.2118210.12215.27140.9483.67136.9967.341919

19、3.12198.26123.9476.39119.9950.3420230.11223.19148.87110.66141.864.49图 31A 所管辖的节点有1,2,3,4，如图 31 的附件 2 的第一个表格的数据可以得出其各个点的案发率 n，现在在模型上假设 4 个节点的案发率分别为 n1，n2，n3，n4 则PA=SA1*n1+SA2*n2+SA3*n3+SA4*n4A 的工作量PA 为：由此用 excel 算出其各个表 4初始的工作量P。的工作量表格的标号工作量的标号工作量的标号工作量184.7822.815141.62128.7962.41648.8358.51001723.84

20、61.21123.91832.6562.11228.61911.4640.6138920112.3783.1140的工作量后不仅原拟在此 3 个工作量大的管辖范围内增加考虑到增加的工作量减少而且新增加的的工作量也不能过大，由数学模型中的最优化算法 但有一个特殊节点 7得出应分别相应的增加了40，29 以及 91，由图 15 知7 至 61 距离过长，为保证 617 至 61 的节点 48 上加一个事发后又交巡警能够快速赶到处理在。则增加后的工作量如下图表 5增加后的工作量表格图 33即节点 29,40,48,91 后的各个由图表可以看出增加了 4 个的工作量都降低到了 90 以下。问题四首先知

21、道对于设置交巡务的原则是：警情主导警务的原则：根据管区道路交通流量，拥堵状况，治安复杂情况，案发率高低，科学确定管控区域。快速出警原则：接警后确保快速到达现场。方便与安全原则：按照醒目，规范，方便群众和确保安全的原则，科学设置。结合当地区域的特征，分布，交通状况，治安状况等情况，在充分考虑现有和财力并确保安全的条件下科学确定的数量和具置。标号工作量标号工作量标号工作量184.7962.41723.8244.71001832.6358.51123.91911.4461.21228.62010.44562.113892913.3640.61404031.98783.11504833.72822.8

22、1648.69150.4由附件 2 中的表格可以得到各区的交巡务数 M，数L，面积A，率n。设密度为h，则有 h=L/A 平均率。现整理表格如下：率为 m=n/i。从而得出各区的密度和平均表 6从附件中只求得各个区的平均率和其对应的密度可以根来据控制变量法先来定性的分析：由于 BCDEF 五区的密度接近，那比较这五区的平均区平均率接近率，很明显D 区最高，但其对应也接近，B，F 区也都接近。由此数却是最少，C，E推出D 区的交巡警数过少需要增加 5-8 台。问题五假设方接到嫌疑人犯案后立即驾车逃跑，且速度与相同，都为 60km/h，警嫌疑人从 P 点，即节点嫌疑人已经行驶了 3km，我后立即派

23、逃犯。根据题中所述，32 出发，可能向任意方向逃窜。经过 3 分钟后，们以 32 节点为圆心，3km 为半径做一个圆，可以判断出 3 分钟后嫌疑人必然还在这个圆的范围内。由图可以分析出若嫌疑人想逃出圈外，所走路线可以为以下几种： 7-15,31-15,30-29,30-A 区外， 48-A 区外， 48-61 ，47-6,47-5,46-55,45-3,36-39,36-16，34-10.一共 13 种情况。尽量把嫌疑人在A 区内，所以先来尚未逃离A 区的情况。六个城区的标号交巡警的数平均率密度A201.352.73B70.910.2C161.220.22D81.30.19E141.160.1

24、8F101.010.19若嫌疑人选择了 7-15 或 31-15 两条路线的话，15 节点交巡务的不需移动就可以堵住嫌疑人。若嫌疑人选择了 30-29 这条路线的话，嫌疑人可以从 29 或 28 节点逃出 A 区，若要从 A 区调动，只有调 15 节点交巡务的。因为 28、29 节点都通向 A 区外，也许调动 A 区外的会更好，因此先搁置这种情况。若嫌疑人选择了 47-6 这条路线的话，因为经计算从节点 32 到节点 6 距离是 3.9km，也就是说 6 节点交巡务的可以在嫌疑人经过 6 节点之前6 节点，从而。若嫌疑人选择了 47-5 这条路线的话，因为经计算节点 32 到节点 5 距离也为

25、大约 3.9km，也就是说 5 节点交巡务的可以在嫌疑人经过5 节点之前5 节点，从而。若嫌疑人选择了 45-3 这条路线的话，3 处不移动便可对嫌疑人进行。若嫌疑人选择了 36-39 这条路线的话，可以就近调 2 节点交巡务平台的到节点 39 进行。因为经计算节点 32 到节点 39 距离是 6.2km，而节点 2 到节点 39 距离是 3.7km，且 2 处出动之前嫌疑人已经走了 3km，因此 2 处出动时嫌疑人距离节点 39 为 3.2km,小于 3.7km，所以不能在此住嫌疑人。当嫌疑人到达 39 节点时，2 处正在 40-39的，所以嫌疑人若走 39-40 这条路的话会被。因此嫌疑人

26、只能选择 39-38，到达 38 后，他有两个选择，一个是走 38-41，一个是走 38-A区外。若是选择 38-41可以调动节点 17 交巡务的到 41 节点，显然要比嫌疑人先到达 41 节点，从而进行。于是，嫌疑人只剩下一个选择，就是走 38-A 区外。若嫌疑人选择了 48-61 这条路线的话，可以调 4 处到节点 62，1 处到节点 63 进行。若嫌疑人经过 62，显然 4 处比他先到该节点。若嫌疑人走 61-60-57-4-63 的话，因为节点 32 到节点 63 距离为 8.6km，刨去 1 处接到报案前走的 3km，剩 5.6km,节点 1 到节点 63 距离为 3.5km，小于

27、5.6km，所以 1 处能先赶到 63 对嫌疑人进行。若嫌疑人走61-60-57-4-39，则 2 处早已到 39 节点。若嫌疑人选择了 36-16 这条路线的话，因为节点 32 到节点 16 的距离为3.3km，超过了 3km，所以当嫌疑人到达节点 16 时该处交巡务的警力早已准备好对其。若嫌疑人选择了 34-10 这条路线的话，10 节点交巡务的不需移动就可以堵住嫌疑人。综上所述，在 A 区内，派 3、5、6、10、15 处不动，2 处到 39 节点，4 处到 62 节点，1 处到 63 节点进行，可以最大限制的将嫌疑人在 A 区。此时，嫌疑人可以通过 28、29、30、48、38 五个节

28、点离开A 区。若嫌疑人从节点 38 离开 A 区到 F 区，则将到达节点 561。F 区离节点 561最近的交巡务在节点 475，经计算，得节点 32 到节点 561 距离为 29.5km，出去出警前行驶的 3km，剩 26.5km，节点 475 到节点 561 的距离为 20.7km，小于 26.5km，所以可以先到节点 561 进行。若嫌疑人从节点 28 或 29 离开A 区到D 区，则将分别到达节点 371 或 370，接下来这两种情况都有两个选择，即是去节点 369 还是节点 349.所以只要从 D区调封堵住节点 369 和节点 349 即可。封堵节点 349 可以用最近的 320 节

29、点处的交巡务的，而封堵节点 369 可以用 321 节点处的交巡务平台的若。嫌疑人从节点 29 离开 A 区到 C 区，则将到达节点 239，先搁置这种情况，再下一段会有解答，先看从节点 30 和 48 到 C 区的情况。仔细观察C 区与 A 区相邻的区域，会发现节点 234、235、237、239、253、273、171、228 所包围的区域是一个封闭的区域，也就是说，只要派封堵这8 个节点即可住嫌疑人假设的是嫌疑人从 30 或 48 到达C 区，即分别到达 237 节点或 235 节点，此时可以派 173 节点交巡务的警力节点 235，从而只留下一个节点 237 供嫌疑人选择。根据就近原则，派节点 169 的253 节点，派节点 170 的节点 273，派节点172 的节点 228，派节点 171 的171 节点，派节点 168 的更先到达