当前位置:首页 >> >>

2011高教社杯全国大学生数学建模竞赛


2011 高教社杯全国大学生数学建模竞赛







我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨 询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。 我们知道,抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料 (包括网上查到的资料) ,必须按照规定的参考文献的表述方式在正文引用处和参考文献中 明确列出。 我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。如有违反竞赛规则的 行为,我们将受到严肃处理。

我们参赛选择的题号是(从 A/B/C/D 中选择一项填写) : 我们的参赛报名号为(如果赛区设置报名号的话) : 所属学校(请填写完整的全名) : 参赛队员 (打印并签名) :1. 2. 3. 指导教师或指导教师组负责人 (打印并签名): 日期:

B

山西大学 晋本阳 张南南 毋丹 李瑞娟 2011 年 9 月 12 日

赛区评阅编号(由赛区组委会评阅前进行编号):

2011 高教社杯全国大学生数学建模竞赛

编 号 专 用 页

赛区评阅编号(由赛区组委会评阅前进行编号):

赛区评阅记录(可供赛区评阅时使用): 评 阅 人 评 分 备 注

全国统一编号(由赛区组委会送交全国前编号):

全国评阅编号(由全国组委会评阅前进行编号):

交巡警服务平台的设置和调度
【摘要】本题是求解交巡警服务平台的设置和调度两个问题,这两个问题既各自独立,又相互依赖。总体
来说,交巡警服务平台的设置实际上就是研究如何分配各个平台所管辖的范围,也就是图论中的点覆盖问题, 但它又不是一般意义的点覆盖问题,而是一个推广了的点覆盖问题。交巡警服务平台的调度研究的则是怎样在 最短时间内分配各服务平台的警务人员到个交通要道的问题。题目共分为两个大问题,分别需要求解某市的某 个区(A 区)和该市整体的交巡警服务平台的设置和调度。针对不同的问题,我们设立了不同的数学模型。 问题一分为三部分,总体来说,是对 A 区各个服务平台的管辖范围及关键路线节点的调派进行研究。首先 我们从给出的各节点坐标和各节点的相邻关系等数据出发,通过 matlab 软件编写程序,先求得各相连节点之间 的街道长度,再利用求任意两点之间最短路的 Dijkstra 算法求得任意两个节点之间的最短路线,得到 A 区任意 两点最短路线距离矩阵。 针对问题一的第一部分,要求求得各交巡警服务平台的管辖范围,使得交警尽量能在三分钟之内到达事发 地点。该问题为推广的点覆盖问题,因为不仅要求各平台管辖与之相邻的节点和街道,还可能管辖与之不相邻 的节点和街道。所以我们通过修改点覆盖模型,依据工作量均衡原则对该区交通网络进行分配,建立了 0~1 规 划模型,最终得到合理的分配方案。 针对问题一的第二部分,要求在出现重大交通事故时快速调度 20 个交巡警服务平台的警力到达 13 个交通 要到的节点,要求一个平台的警力最多封锁一个路口。这既可以看做线性规划中的指派问题,又可以看做是偶 图中求最优匹配问题。为此,先虚拟 7 个交通要道节点,使得每个平台到这些虚拟节点的距离为0,构造出赋 权平衡偶图,建立整数规划模型,通过 lingo 软件编写程序求得调度方案。 针对问题一的第三部分, 要求增设 2~5 个服务平台解决工作量不均衡和有些地方出警时间过长的实际问题。 通过对工作量的分析建立基本的工作量函数,求得工作量向量,并根据一定的调整原则对原有方案进行优化。 问题二分为两部分,其中第一部分是把问题一中 A 区的平台设置方案扩展到全市,判定其是否合理。具体 来讲,是将全市的交通网络数据应用到问题一所建立的数学模型,求出服务平台设置方案,再依据工作量和出 警时间,对求出的方案进行分析和评价,并给出不合理部分的解决办法。 针对问题二的第二部分,要求警方在最短时间内围捕犯罪嫌疑人,先判断犯罪嫌疑人最可能出该区的路口 (即以最短距离出 A 区的几个路口) ,从而分配警力封锁之,同时,将剩余警力分配到 A 区其它的出城路口, 得到封锁 A 区的最佳围堵方案。如果犯罪嫌疑人逃出 A 区,利用问题一第二部分所给模型,求出犯罪嫌疑人出 市区各路口的最佳围堵方案。

关键字:最短路线距离矩阵;推广的点覆盖;指派问题;0~1 规划;最优匹配问题;工作量函数

一、问题重述
“有困难找警察” ,是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大 职能。为了更有效地贯彻实施这些职能,需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交 巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的,如何根据城市的实际情况与需求合理地设 置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。 试就某市设置交巡警服务平台的相关情况,建立数学模型分析研究下面的问题: (1)附件 1 中的附图 1 给出了该市中心城区 A 的交通网络和现有的 20 个交巡警服务平台的设置情况示意 图,相关的数据信息见附件 2。请为各交巡警服务平台分配管辖范围,使其在所管辖的范围内出现突发事件时, 尽量能在 3 分钟内有交巡警(警车的时速为 60km/h)到达事发地。 对于重大突发事件,需要调度全区 20 个交巡警服务平台的警力资源,对进出该区的 13 条交通要道实现快 速全封锁。实际中一个平台的警力最多封锁一个路口,请给出该区交巡警服务平台警力合理的调度方案。

根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况,拟在该区内再增加 2 至 5 个平台,请确定需要增加平台的具体个数和位置。 (2)针对全市(主城六区 A,B,C,D,E,F)的具体情况,按照设置交巡警服务平台的原则和任务,分 析研究该市现有交巡警服务平台设置方案(参见附件)的合理性。如果有明显不合理,请给出解决方案。 如果该市地点 P(第 32 个节点)处发生了重大刑事案件,在案发 3 分钟后接到报警,犯罪嫌疑人已驾车逃 跑。为了快速搜捕嫌疑犯,请给出调度全市交巡警服务平台警力资源的最佳围堵方案。

二、问题假设及符号说明
问题假设:
1、交警从服务平台到事发地点所用时间只与路程有关,即不记上车下车时间、不记中间停留时间,警车到事发 地之间道路通畅,无特殊路况,能由最短路径到达事发地点; 2、每个服务平台一般管理整条街道,即不存在某条街道分成两个平台管理; 3、只在节点处增加平台; 4、交警在接到报警后立即行动,反应时间为 0; 5、所有案件处理时间为平均处理时间。

符号说明:
Ai :A 区交巡警服务平台 i Bi :B 区交巡警服务平台 i Ci :C 区交巡警服务平台 i Di :D 区交巡警服务平台 i Ei :E 区交巡警服务平台 i

j : 交叉路口节点
警车速度:v=60km/h t : 交警处理案件时间

dij : 1 ? i ? 20 ,j>20,i 平台到节点 j 所需最短距离

D ( dij )全市最短路线距离矩阵
A( aij )全市邻接矩阵,其中当 aij 为有限数时,表示节点 i 到节点 j 的街道长度,当 aij 为无穷大时,表示节 点 i 与 j 直接没有街道相连。

f i :i 节点的发案率
D1 ( dij ):A 区任意两点最短路线距离矩阵;

A1 ( aij ) A 区邻接矩阵;

B1 (bij ) : (i=1、2?20;j=1、2?20) 表示 20 个平台到 20 个节点的矩阵,其中前 13 个为各对应交通要到节点,
后 7 个为虚拟节点; ( xi , yi ):节点 i 的坐标

?1;平台i管辖节点j xij ? ? ?0;平台i不管辖节点j

wi : i 平台工作量

三、问题的分析
本题是研究如何合理的设置交巡警服务平台,分配各平台的管辖范围、调度警卫资源。以实现交巡警服务 平台更快更好的服务群众的目标。 本题给出了某市区的所有交通网络及各节点在比例图中的坐标,并说明了各相关联的节点及各节点的发案 率,指出了现有交巡警平台所在节点位置及进出口市区交通要道所在节点位置。并给出了市区内各区面积和人 口数量。 题目设有两个问题, (1)问题分为三个部分,一部分要求为现有交巡警平台分配管辖范围,使得在其管辖 范围内出现突发事件时, 尽量能在三分钟之内有交警到达事发地点;二部分要求对于突发事件, 需要调度 20 个交 巡警服务平台的警力资源到 13 个交通要道的最佳调度方案;三部分要求对于工作量不均衡和有些出警时间过长 的实际情况增加 2 到 5 个服务平台使情况的得到改善。 根据题意,需求交警在三分钟之内所到达的范围,初步分析应建立以平台为中心,三分钟所能到达距离为 半径,画出每个平台所能覆盖到的范围。但分析到不是所覆盖的范围都可直线通过,而是有很多折线,据此, 首先应该根据所给各节点在平面直角坐标系上的坐标资料求出相邻两点之间街道长度,因为所给数据过大,因 此,应利用 MATLAB 软件编写相关程序求出每两个相邻节点之间街道的长度。再利用 DIJKSTRA 算法通过 MATLAB 编写程序计算出每个节点到其他各个节点之间的最短路线的长度。 在此基础上就可以开始问题一各部分求解:部分一分配各平台的管辖范围,可通过设定目标所有平台所管 辖的节点总路程最小(题目要求尽量使得三分钟内有交警到达事发地,实际计算中出现少量三分钟无法到达的 点,所以对该约束进行转化使得到每个节点时间最小即可,本题中也即总时间最小即可即总路程最小) ,以及目 标每个平台工作量尽量均衡即工作量最大的平台和工作量最小的交巡警平台工作量之差最小。即目标有两个, 可把问题看做一多目标规划问题。并设定约束条件每个节点只能分配到一个服务平台,并通过设计 LINGO 程序 求解,得到各节点的分配方案。接下来再对未管辖的街道进行分配。原则是:该平台所管辖所有节点之间街道 (即所管辖节点的诱导子图的所有边)一定是归本平台管辖;把两个端点属于不同平台管理的街道,按工作量 均衡的标准分配到工作量少的平台管理,从而得到各平台管辖范围。实际操作过程中,该模型较难实现,因此, 我们的目标函数先忽略工作量均衡的目标,求出分配方案,在遵循工作量均衡原则,对此方案进行调整,得到 最终答案。 部分二把各平台与各节点之间的调度看做分配问题,建立分配问题的数学模型,虚拟 7 个交通要道,并设 虚拟的交通要道到各个平台之间的最短距离为 0, 把各平台到各交通要道的最短距离设为目标矩阵。 通过 LINGO 软件编程求解,得出最优调度方案。 对于部分三,可通过部分一中求解的范围分配方案求解工作量及出警时间。再拟设定增加 2 到 5 个交巡警 服务平台解决以上不太合理的情况。并再通过新设定的平台通过修改的部分一中模型求解,得出答案,检验是 否合理。 (2)问题要求针对全市按设置交巡警服务平台的原则和任务分析现有交巡警服务平台的合理性。同样应先 求出全市各节点之间的最小距离,该方法参照问题(1)中求解方案。同样再利用类似于问题一中部分一的求解 模型求解。把全市分成的六个区域分别求解,各区域之间相连的路线参照问题一中部分一边际调整方案分配。 并根据时间要求及工作量要求判定是否合理。 对于围捕犯罪嫌疑人问题,也是指派问题模型。重要路口是指犯罪嫌疑人以最短路线出 A 区的路口。首先 判断并封锁这些重要路口,其次将剩余警力分配至 A 区其余出城区路口,修改第一问建立的指派问题模型求出 在 A 区最短时间围堵罪犯的最佳方案。如果犯罪嫌疑人已经逃出 A 区,我们可以利用指派模型,输入全市各个 出市路口和最短路线距离矩阵等数据,求出犯罪嫌疑人逃出市区的最佳围堵方案。

四、模型的建立及求解
问题一:根据坐标通过建立 matlab 软件求解两相邻节点之间距离,并转化成实际中的距离。得到该市 A

a 区所有节点邻接矩阵 A 1 ( ij

)。所编写的程序见附录一。

根据上述所求得的数据通过 matlab 软件利用 dijkstra 方法求解任意两点之间最短距离。得到该市 A 区最短 距离矩阵 D1 ( dij ),程序见附录二。

对于问题一中部分一:
根据题意,需要把 92 个节点分配给 20 个交通巡警平台,其中 20 个节点已经设有交通巡警平台,必定受本 节点所设平台管辖,只需将剩余的 72 个节点进行分配。而对于节点之间街道的分配,每个平台所管辖的节点之

间的街道都由该平台管理。街道两端节点若被不同平台管理,按工作量大小将该街道分配给工作量小的平台管 理。因此,范围的分配分为两步: 1.节点的分配: 根据交巡警服务平台分配原则建立多目标规划问题如下:

min ??
i ?1 j ?1

20

92

dij 60

* xij

min{max{?
j ?1

92

dij 60

*2* fi * xij } ? min{

dij 60

*2* fi * xij }

? 92 ?? xij ? 1 j ?1 ? ? ? D1 ? (dij ) ? ? xij ? 0或1;(i=1到20,j=1到92) ? ?
由于该多目标规划较难实现因此,先不考虑工作均衡的目标即第二个目标函数,将该目标函数去掉。模型 简化为:

min ??
i ?1 j ?1

20

92

dij 60

* xij

? 92 ?? xij ? 1 j ?1 ? ? ? D1 ? (dij ) ? ? xij ? 0或1;(i=1到20,j=1到92) ? ?
经 lingo 软件设计, (程序见附录三)求解得管辖范围分配方案: 平台 A1 所管辖节点 67 、 68、 69 、71 、74 、 75、 76 、 78 39、40、43、44、70、72 54、60、62、63、64 57、60、62、63、64 49 、 50、 51 、52 、53 、 56、 58 、 59 30、32、47、48、61 33、46 31、34、35、45 平台 A11 所管辖节点 26、27

A2 A3 A4 A5 A6 A7 A8 A9 A10

A12 A13 A14 A15 A16 A17 A18 A19 A20

25 21、22、23、24 28、29 36、37、38 41、42 73、80、81、82、83、84 77、79 85、86、87、88、89、90、91、 92

表中分配方案为按时间计算管辖最优方案。只有部分节点即 28、29、38、39、61、92 节点不能在三分钟之 内到达,但选取的仍是最短路程的管辖点。 2.街道的分配: 分配原则:街道两端节点由同一平台管理的则该街道由管理这两节点的平台管理;街道两端节点由不同平 台管理的由这两平台中工作量少的平台管理。 通过初步分析,我门发现交巡警服务平台的实际工作量包括两部分,即其出警时间及所管辖节点发案率的 乘积的累加,和它所管辖节点所有案件的处理时间累加。因此写出公式

Wi ? ? f j *
j ?1

92

dij 60

*2* xij ? ? f j xij t
j ?1

92

据该公式,得出每个平台工作量情况如下: 平台 1 0.23+9.4t 平台 2 0.43+9.7t 平台 3 0.18+5.6t 平台 4 0.22+6.6t 平台 5 0.45+9.7t 平台 6 0+2.5t 平台 7 0.31+9.6t 平台 8 0.08+5t 平台 9 0.21+8.2t 平台 10 0+1.6t 平台 11 0.11+4.6t 平台 12 0.1+4t 平台 13 0.3+8.5t 平台 14 0+2.5t 平台 15 0.47+4.8t 平台 16 0.16+5t 平台 17 0.09+5.3t 平台 18 0.22+8t 平台 19 0.04+3.4t 平台 20 0.36+10.5t 现根据假设给处理时间赋值,令 t= 0.5 得出各个平台工作量的值(实际生活中 t 值可调整) 平台 1 4.93 平台 1 5.28 平台 1 2.98 平台 1 3.52 平台 1 5.3 平台 1 1.25 平台 1 5.11 平台 1 2.58 平台 1 4.31 平台 1 0.8 平台 1 2.41 平台 1 2.1 平台 1 4.55 平台 1 1.25 平台 1 2.87 平台 1 2.66 平台 1 2.74 平台 1 4.22 平台 1 1.74 平台 1 5.61 根据以上值给出街道两端由不同平台管理的街道分配放案,即交界处分配方案: 8 号平台管理的交界处街道有 32~33、8~47、46~55、33~34、46~46、8~9; 9 号平台管理的交界处街道有 31~32; 10 号平台管理的交界处街道有 9~10、10~11; 11 号平台管理的交界处街道有 11~22; 12 号平台管理的交界处街道有 12~27、11~25、24~25; 14 号平台管理的交界处街道有 21~14、16~14;

15 号平台管理的交界处街道有 29~30、7~15、15~31; 16 号平台管理的交界处街道有 35~36、34~37、36~39、38~39; 17 号平台管理的交界处街道有 42~43、17~40、38~41、42~81; 18 号平台管理的交界处街道有 73~74、74~80、84~85、84~89; 19 号平台管理的交界处街道有 76~77、77~78、78~79、79~80; 20 号平台管理的交界处街道有 41~92、82~90。

对于问题一中部分二:若出现重大交通事件,要求调度全区 20 个交巡警服务平台的警力资源对进出该
区的 13 条交通要道实现快速全封锁,一个平台的警力最多封锁一个路口。把该问题看作一分配问题,建立 0~1 规划的数学模型,求最优解。 建立分配问题的数学模型:由于关键路线的节点不是连续的,因此,设立新变量 yij 其中 y 中的 i 仍表示第 i 号平台,j 取值为 1~20,1 表示调至 12 号节点,2 表示调至 14 号节点,3 表示调至 16 号节点,4 表示调至 21 号节点,5 表示调至 22 号节点,6 表示调至 23 号节点,7 表示调至 24 号节点,8 表示调 至 28 号节点,9 表示调至 29 号节点,10 表示调至 30 号节点,11 表示调至 38 号节点,12 表示调至 48 号节点, 13 表示调至 62 号节点,14~20 表示虚拟的节点。所建立数学模型如下:

min z ? ?? bij yij
i ?1 j ?1

20

20

? 20 ?? yij ? 1;( j ? 1到20) ? i ?1 ? 20 s.t. ?? yij ? 1;(i ? 1到20) ? j?1 ? y ? 0或1;(i ? 1到20,j ? 1到20) ? ij ?
利用 lingo 软件编写程序,所编写程序见附录四。 求解得到分配问题的解为:
y( 1, 12) y( 2, 16) y( 3, 9) y( 4, 14) y( 5, 10) y( 6, 13) y( 7, 11) y( 8, 15) y( 9, 8) y( 10, 7) y( 11, 2) y( 12, 5) y( 13, 4) y( 14, 6) y( 15, 3) y( 16, 19) y( 17, 1) y( 18, 18) y( 19, 20) y( 20, 17) 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 0.000000 2.968200 1.532600 3.265000 7.708000 0.5000000 3.805300 4.751800 10.49320 0.5831000 3.982200 2.475800 0.3500000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

即调用方案及所用时间(分钟)如下 12→ 22 6.8825 16→ 14 2.9682

9→ 16 14→ 21 10→ 12 13→ 23 11→ 24 15→ 28 8→30 7→29 2→38 5→48 4→62

1.5326 3.2650 7.5866 0.5 3.8053 4.7518 3.0608 8.0155 3.9822 2.4578 0.3600

对于问题一中部分三,要求添加 2~5 个交巡警平台解决实际中工作量不均衡和出警时间过长的问题。由 于交巡警服务平台的实际工作量包括两部分即其出警时间及所管辖节点发案率的乘积的累加,和它所管辖节点 所有案件的处理时间累加。因此,我们所设的评价是否更为合理的标准即 W 是否更小。

Wi ? ? f j *
j ?1

92

dij 60

*2* xij ? ? f j xij t
j ?1

92

调整原则 Step1 交巡警平台必须在三分钟内赶到事发地 Step2 工作量均衡(通过 Excel 表格处理,Matlab 软件处理矩阵见附录五得出如下表格) 平 台 工 作 量 平 台 1 4.9927 2 5.2791 3 2.9784 4 3.5160 5 5.3048 6 1.25 7 5.1099 8 2.5758 9 4.3090 10 0.8000

11 平台 B1 B2 B3 B4 B5 B6 B7

12

13 所管辖节点 101~103

14

15

16

17

18

19

20

104~112、117~123、 113~116、126、128、129、131、136、154、 124、127、130、133、134、138~142、145~147、150、151 135、137、143、144 155~165 149、152、153 2..0954 4.5461 1.25 2.8719 2.6623 2.7356 4.2185 1.7382 5.6076

工 作 量

2.4134

由上述原则,step1 中 28, 29, 38, 39, 61, 92 这六个路口明显三分钟交警不能到达。 Step2 中 1,2,5,7,13,18,20 这五个平台工作量太多。 综上我们可以增加五个平台 具体位置为 21,38,61, 92, 28, (见附图一)

B8

125、132

问 题 二:要求判定全市的交巡警平台设置是否合理,该评价标准也建立在分配了交巡警服务平台所管辖范围的基础
上,对各交巡警服务平台的是否能在较短时间内到达其案发地及工作量是否均衡来评价其是否合理。该问题类 似于问题一中求解各平台所管辖范围和判断工作量是否合理的问题。只需求解出各平台所管辖范围,并比较最 长出警时间是否大部分都在 3 分钟之内,以及工作量是否比较均衡。 通过问题一中建立的模型求解的本市各区分配方案如下: B 区分配方案: C 区分配方案 平台 C1 C2 C3 平台 C4 E1 C5 E2 C6 E3 C7 E4 C8 所管辖节点 262~265 248~252、255、258~261 189~192 254 所管辖节点 222~226、273、276、277、283 437、230 438、231 456、240、241~244、246、253 215、216 427、227~229 432-436 457 217、218 424-426 232~239 、245、428-431 247 211~214、219~221 416 183、193~199 、 458 459 184~188 、 417-423 200~210 E 区分配方案 D 区分配方案

E5 C9 E6 C10 E7 C11 E8 C12 E9 C13 E10 C14 E11 C15 C16 C17 平台 D1 D2 D3 D4 D5 D6 D7 D8 D9

387-396 284、286 、287 397-400 405 、 406 274、275、278~282 285、288~292、295、296 401-404 407-415 268~270 、297~316 266、267、317~319 256、257、271、272、293、294 所管辖节点 347-350 351-360 367 344 345 361 362 364-366 343 346 337 338 340 341 3421 329-336 339 370 371 368 369

E12 E13 E14 E15 平台 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11

452-455 465-468 445 所管辖节点

460-464 469 470 471 472 446 448-451 473 474

F 区分配方案

440-444 447

550、551、555~559、561、563~565 532~535、543~547、552~554 492~509、516~523、529、530 512~515、524~528、536~539、542 573、575~582 562、566~569、574 486、490、491、531、548、549 487~489、460 510、511 540、545、570 571、572

通过其分配方案利用 matlab 编写的程序可求解市区内各个平台的出警时间。分析其每个区域各个交巡警平 台平均出警时间和最长出警时间分别为: 区域 A区 B区 C区 D区 E区 F区 平均出警时间 3.13 2.93 2.97 3.03 3.20 2.70 最长出警时间 5.30 9.82 15.2 16.06 19.10 8.48

也可根据题一中模型求解各区工作量得到结果如下: B区 B 区 1 平台 B 区 2 平台 B 区 3 平台 B 区 4 平台 B 区 5 平台 B 区 6 平台 B 区 7 平台 B 区 8 平台 C区 C 区平台 1 C 区平台 2 C 区平台 3 C 区平台 4 C 区平台 5 C 区平台 6 C 区平台 7 C 区平台 8 C 区平台 9 C 区平台 10 C 区平台 11 C 区平台 12 4.5619 9.1097 2.5325 2.0592 6.9928 8.9380 4.2584 8.6855 5.7492 6.1840 4.3404 8.2760 1.894 6.767 4.698 6.506 2.824 6.326 2.088 2.052

C 区平台 13 C 区平台 14 C 区平台 15 C 区平台 16 C 区平台 17 D区 D 区平台 1 D 区平台 2 D 区平台 3 D 区平台 4 D 区平台 5 D 区平台 6 D 区平台 7 D 区平台 8 D 区平台 9 E区 E 区 1 平台 E 区 2 平台 E 区 3 平台 E 区 4 平台 E 区 5 平台 E 区 6 平台 E 区 7 平台 E 区 8 平台 E 区 9 平台 E 区 10 平台 E 区 11 平台 E 区 12 平台 E 区 13 平台 E 区 14 平台 E 区 15 平台 F区 F 区 1 平台 F 区 2 平台 F 区 3 平台 F 区 4 平台 F 区 5 平台 F 区 6 平台 F 区 7 平台 F 区 8 平台 F 区 9 平台 F 区 10 平台 F 区 11 平台

3.3063 12.7508 19.4608 5.3640 5.7676 5.6936 9.6177 1.5077 3.7891 3.686 0.7 2.227 4.5554 8.0251 0.7 2.3773 2.2185 4.9736 0.7 1.5508 2.4833 7.1031 9.8498 5.0957 11.0797 9.2654 5.4635 7.2621 4.4435 9.2343 9.6443 21.9079 11.7441 7.8487 5.4259 5.3606 4.0567 2.4263 2.9535 2.2292

从出警时间来看,平均出警时间都在三分钟周围,但最长出警时间 C、D、E 区均超过了 10 分钟,比较不 合理,从工作量的分配可看出,在六个区域内工作量的分配很不均匀,同一区域内工作量的分配有很大的悬殊, 尤其是 C、F 区,因此,本市交巡警平台的设置不太合理,应进一步给予优化。 对于围堵问题, 若 P 点处发生的重大刑事案件, 在案发三分钟后接到报警, 巡警要实现最快最小范围的围堵。 Step1 求出 从 P 节点出 A 区的最短路径和时间以及相应的出口(我们称这些出口为重要出口) Step2 求出封堵重要出口的分配方案 Step3 利用问题一中建立指派问题模型,求出剩余平台封堵非重要出口的最佳分配方案

Step4 利用问题一中的指派问题的算法,求出全市服务平台封堵出入全市的路口以及时间。 如果我们输入犯罪嫌疑人的平均逃亡速度,将输出合理的围堵方案。

五.模型的评价
优点: 1. 适用范围广,模型对于一些同类的图论问题同样适用。 2. 对模型的建立和求解做了详尽的讨论,在第一问中,对路段进行了均衡考虑,涉及了各个路口的 发案率,并假设了每个平台处理问题时间都为 t 3. 运用分配问题的模型,点覆盖的推广,其中多次运用 Matlab 软件对于问题求解有很大的帮助 缺点: 1. 问题一中无法证明为最优答案,而仅仅是一个较优解。 2. 有的街道没有考虑工作量

六.参考文献
[1] [2] [3] [4] [5] [6] [7] 王海英,图论算法及其 MATLAB 实现,北京航空航天大学出版社,2010.2。 王树禾,图论及其算法,合肥:中国科学技术大学出版社,1990。 钱颂迪,运筹学,.北京:清华大学出版社,1988。 胡运权等,运筹学基础及应用,高等教育出版社,2008。 卢开澄、卢华明,组合数学,清华大学出版社,2005。 高俊斌,MATLAB5.0 语言与程序设计,武汉:华中理工大学出版社,1998。 张志涌、刘瑞桢、杨祖樱,掌握和精通 MATLAB,北京航空航天大学出版社,1999。


相关文章:
2011高教社杯全国大学生数学建模竞赛题目(含有ABCD四题...
2. 3. 指导教师或指导教师组负责人 (打印并签名): 日期:年月日 赛区评阅编号(由赛区组委会评阅前进行编号) : 2011 高教社杯全国大学生数学建模竞赛 编号 专...
2011高教社杯全国大学生数学建模竞赛_图文
2011高教社杯全国大学生数学建模竞赛_工学_高等教育_教育专区。全国大学生数学建模竞赛答案参考 2011 高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了...
2011高教社杯全国大学生数学建模竞赛C题论文
2011高教社杯全国大学生数学建模竞赛C题论文_理学_高等教育_教育专区。该论文是我们小组原创的,不足地方请多谅解 摘要:本文对第一个问题做出了合理的假设,建立了...
2011高教社杯全国大学生数学建模竞赛A题
2011高教社杯全国大学生数学建模竞赛A题_理学_高等教育_教育专区。数学建模 2011 全国赛 A题 2011 高教社杯全国大学生数学建模竞赛 承诺书 我们仔细阅读了中国...
2011年高教社杯全国大学生数学建模竞赛优秀论文_图文
2011年高教社杯全国大学生数学建模竞赛优秀论文 - 2011 高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全...
2011高教社杯全国大学生数学建模竞赛A另一份
2. 3. 指导教师或指导教师组负责人 (打印并签名): 日期: A 年 月 日 赛区评阅编号(由赛区组委会评阅前进行编号): 2011 高教社杯全国大学生数学建模竞赛 ...
2011高教社杯全国大学生数学建模竞赛B题参考答案
2011高教社杯全国大学生数学建模竞赛B题参考答案_理学_高等教育_教育专区。2011高教社杯全国大学生数学建模竞赛B题参考答案(整理版),整个模型建立和求解,并附有...
2011高教社杯全国大学生数学建模竞赛B题论文
2011高教社杯全国大学生数学建模竞赛B题论文 - 摘要 本文就某市的实际情况与需求,合理的建立了有关交巡警服务平台设置与调 度的模型,通过图论模型、规划模型以及...
2011高教社杯全国大学生数学建模竞赛B题(题目改变)参考...
2011高教社杯全国大学生数学建模竞赛B题(题目改变)参考答案_学科竞赛_高中教育_教育专区。2011年全国大学生数学建模交巡警服务平台的设置与调度优化分析摘 要本文综合...
2011高教社杯全国大学生数学建模竞赛A,B答案
2011 高教社杯全国大学生数学建模竞赛 A,B 题评阅要点 2011 高教社杯全国大学生数学建模竞赛 A 题评阅要点 [说明]本要点仅供参考,各赛区评阅组应根据对题目的...
更多相关标签: