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

1、2011 高教社杯大学生数学建模竞赛承诺书仔细阅读了学生数学建模竞赛的竞赛规则.完全明白，在竞赛开始后参赛队员不能以任何方式（包括、电子邮件、网上等）与队外的任何人（包括指导教师）研究、与赛题有关。知道，别人的成果是竞赛规则的, 如果别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文处和参考文献中明确列出。郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。竞赛规则的行为，受到严肃处理。参赛选择的题号是（从A/B/C/D 中选择一项填写）：B的参赛报名号为（如果赛区设置报名号的话）：0868所属学校（请填写完整的全名）：哈尔滨市工程大学参赛队员 (打印并

2、签名) ：1.2.3. 指导教师或指导教师组(打印并签名)：日期： 2011 年 9 月 12 日赛区评阅（由赛区评阅前进行）：2011 高教社杯大学生数学建模竞赛页赛区评阅（由赛区评阅前进行）：赛区评阅（可供赛区评阅时使用）：（由赛区送交前）：评阅（由评阅前进行）：评阅人评分备注交巡务的设置与调度摘要本文针对交巡务的设置、管辖范围和调度警务资源问题，建立目标规划模型、层次分析模型和动态规划模型，并用LINGO求解，给出了一定方案。问题一：1）交巡务管辖范围的分配，运用层次分析模型，先从考虑3分钟出警可到达事发地，初步确定管辖范围，然后考虑工作量分配均衡问题，最终确定20个管辖范围；2）调度问

3、题，运用动态规划模型，转变成从20个已知中选出13个和另外13个已知被封路口组成一一对应且距离和最短问题，在8分钟内可以将13条出入A去的要道全部；3）增加个数和位置问题，运用比较模拟法，在第一问的基础上，已划分出20个管辖区进行相互比较，从而到出警时间长和工作量不均衡的辖区，进而增加4，提高工作效率。4 个新增位置问题二：1）分析该市现有交巡务设置方案的合理性，从的数量和位置上分别入手，首先构造一个评价标准，判断出的数量明显不够，需增加的位置进行验证，用LINGO29个；然后建立目标规划模型，对原解出他们是可行解。针对不合理的地方，给出了解决方案，即新增29个的位置分布图；2）调度方案，先确

4、定3分钟后嫌疑人的踪迹范围，进行3种情况分类，将交通网络简化成图论中几何路线问题，用最小距离法，确定方案，围堵时间：13分钟 ，最小面积：4平方公里。：交巡务，动态规划，调度优化，图论点序号XY29246337483153746639836291445380目录摘要1一、问题重述3二、问题分析3三、模型的建立与求解43.1 交巡务管辖范围43.1.1 模型的建立及求解4调度6模型的假设6定义符号说明7模型的建立及求解7增加个数及位置93.3.1 模型的建立及求解93.23.3务设置方案合理性103.4 交巡模型的假设10定义符号说明10模型的建立及求解11方案12模型的假设12模型的建立及求解

5、133.5四、模型的推广14五、模型的评价与优化14六、参考文献15一、 问题的重述有某一城市在市区的一些交通要道和重要部位设置交巡务。且假设每个交巡务的职能和配备基本相同。由于警务资源是有限的，须根据城市的实际情况与需求合理地设置交巡务、分配各的管辖范围、调度警务资源。现已知该市A 区及全市 6 区交通网络与有如下问题需要解决：设置示意图。交巡警的时速为 60km/h。（1） 请为该市中心城区 A 的交通网络和现有的 20 个交巡务分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在 3 分钟内有交巡警到达事发地。突发事件发生，需要调度全区 20 个交巡务的的资源，对进出该区的 13

6、条交通要道实现快速全。在实际中一个 的最合理的方案。，现须确定增加最多一个路口的情况下，给出调度交巡务拟在该区内再增加 2 至 5 个的具体个数和位置，以解决各交巡务的工作量不均衡和有些地方出警时间过长。（2） 针对全市的具体情况，按照设置交巡务的原则和任务，分析研究该市现有交巡务设置方案的合理性。如果有明显不合理，给出解决方案。该市地点 P（第 32 个节点）处发生了，在案发 3 分钟后接到，嫌疑人已驾车逃跑。给出调度全市交巡疑犯。务资源的最佳方案，以快速搜捕嫌二、 问题分析（1） 要确定各交巡务得管辖范围，首要考虑的一点是，在 3 分钟内有交巡警可以到达事发地，即其最远行程为 3 公里（极

7、个别道口节点除外）。以此条件能够初步确定各的管辖范围。接下来进一步思考工作量的分配问题，应尽量使个工作量均衡分配，从而可精确划分管辖范围。调度问题：13 交通条要道，即13 个出入A 区的路口。调度 20 个交巡务的进行，可转变成从 20 个已知待选点中选出 13 个点到另外 13 个已知点的最短距离一一对应且距离最小的图论问题。确定增加个数和位置问题：对现有交巡确定出新增务的工作量不均衡和出警的个数与位置。时间过长进行分析，通过图表对比，（2）分析该市现有交巡和位置进行分析，根据交巡务务设置方案的合理性问题：从的数量的原则和任务确定一个参考标准，比较算出该市应设置多少，进而建立目标规划模型，

8、验证已有位的可行性，对明显不合理的地方，给出解决方案。问题：案发后 3 分钟，确定出嫌疑人可能逃逸到的地方，进行分类讨论，进而设计方案，运用图论最短路径法，确定方案。三、 模型的建立与求解3.1 交巡务管辖范围3.1.1 模型的建立及求解运用层次分析法为交巡务分配管辖范围，首先考虑交巡警可在 3 分钟到达事发地，即最远行程 3 公里，初步确定各的管辖范围。再考虑由于各节点的发案率不同，导致工作量的不同这一问题，进一步确定各的管辖范围。图表1 各3 分钟能到达地方分布图：表示3 分钟能到达地方。由于各初定管辖范围内的发案率不同，仅考虑最远行程是不够的，还要考虑各区的工作量是否均衡，在平衡各区工作

9、量后，最终确定各交巡围，如下图：务的管辖范交巡务管辖范围分布图：表示交巡务管辖范围分布表3.2调度3.2.1 模型的假设分区原则。交巡追求最优原则。交巡口。务只自己管辖范围内的道口。在一定范围内选择最短路径，用最少的时间务路3.一一原则。一个交巡务只一个道口。4.交巡警以平均速度 60km/h 行驶，无堵车、抛锚等意外停车。交巡警所在节点序号管辖节点序号交巡警所在节点序号管辖节点序号11、67、68、69、71、73、741111、26、2722、40、43、44、70、721212、2533、54、55、65、66、 、 、4、57、60、62、63、641414、2155、49、52、53

10、、561515、28、2966、47、50、51、58、59、 、 、7、30、48、611717、41、4288、32、33、45、461818、81、82、83、84、89、9099、31、34、35、371919、75、76、77、78、79、8010102020、85、86、87、88、91、923.2.2 定义符号说明U： V：被节点集合， 道口节点集合，Y：其它节点集合，d(，d(： 到 的距离，3.2.3 模型的建立及求解。在给定的交通网络中，每个顶点代表一个路口，每一条线段代表一条公路，把交通网络简化、抽象成几何图形，把问题转化成求从 20 个交巡务待选点中选出 13 个点到另

11、外已知 13 个定点的最短距离问题。和被封道口交通网络的简化图说明：1)：表示出入A 城区的路口节点。2)：表示交巡务的设置点。3)4)5)：表示设有交巡图形中数字表示节点序号。务的出入A 城区的路口节点。线段上数字表示相邻两节点的距离，为毫米，比例尺为 1:100000。目标函数：mind(= d(+= d(+= d(+U=1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19， 20（节点）V=12，14，16，21，22，23，24，28，29，30，38，48，62（节点）用 LINGO经计算结果如下：到结论：最快 8 分钟内完成。3.3增加个数

12、及位置3.3.1 模型的建立及求解A 区发案率分布A 区新增分布图：新增加的交巡务A 区新增5 个，位置如下：3.4 交巡务设置方案合理性3.4.1 模型的假设1.每个交巡务的配置基本相同。2.接到无延迟出警。3.4.2 定义符号说明点序号XY29246337483153746639836291445380A(k),B(k),，F(k):A 区，B 区，F 区的节点3.4.3 模型的建立及求解1.个数合理性评判标准该市设置方案由上表对比可看出：该市的平均处理率、管辖路程、节点覆盖数均大于指标，明显数量设置不合理，应增加个数。增加数目后设置方案增加后，几个指标接近标准指标，从而确定该方案合理。2

13、.位置评判目标函数：总时间=巡逻时间+出警处理时间约束条件：，i，j 在同一区路程发案率节点数数平均处理率平均管辖路程平均覆盖节点数15306.43674.55821096.114km5.3路程发案率节点数数平均处理率平均管辖路程平均覆盖节点数15306.43674.5582808.4312519km7.3平均处理率平均管辖路程平均覆盖节点数615km5.5V=60km/h简化模型后：将已知 80 个的信息代入上式，经 LINGO 计算是可行解，说明该市现安排的交巡务的位置合理。综上给出新的解决方案，即新增 29 个位置分布图，如下：29 个：新增加位置3.5方案3.5.1 模型的假设1.嫌疑

14、人驾车逃逸始终在行驶。2.嫌疑人车速与交巡速相当（60km/h）。3.交巡警在过程中，无堵车、撞车、抛锚等意外事件。4.交巡警不可跨区追捕、。3.5.2 模型的建立及求解嫌疑人驾车行驶 3 分钟后，以节点 32 为圆心，半径为 3 公里画圆，确定区、3他可能出现的地方，他不会超出此范围，区，如下图：此区域分为三个部分，1 区、2进而对此进行，对每一种情况给出方案，采用图论最小距离进行。1 区3 区本文使用筛选、排除法，有效地减少了数据的处理，建立常见的规划模型，很方便地求出结果。对于复杂的交通网络问题转化为数学中常见的图论问题，化繁为简，主次分明，使计算方便快捷。5.2 缺点：1 本文几处采用近似计算，对