《2011高教社杯全国大学生数学建模竞赛.pdf》由会员分享，可在线阅读，更多相关《2011高教社杯全国大学生数学建模竞赛.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2011高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D 中选择一项填写）：B 我们的参赛报名号为（如果赛区设置报名号
2、的话）：所属学校（请填写完整的全名）：山西大学参赛队员(打印并签名)：1.晋本阳2.张南南3.毋丹指导教师或指导教师组负责人(打印并签名)：李瑞娟日期：2011 年 9 月 12 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：交巡警服务平台的设置和调度【摘要】本题是求解交巡警服务平台的设置和调度两个问题，这两个问题既各自独立，又相互依赖。总体来说，交巡警服务平
3、台的设置实际上就是研究如何分配各个平台所管辖的范围，也就是图论中的点覆盖问题，但它又不是一般意义的点覆盖问题，而是一个推广了的点覆盖问题。交巡警服务平台的调度研究的则是怎样在最短时间内分配各服务平台的警务人员到个交通要道的问题。题目共分为两个大问题，分别需要求解某市的某个区（A 区）和该市整体的交巡警服务平台的设置和调度。针对不同的问题，我们设立了不同的数学模型。问题一分为三部分，总体来说，是对A 区各个服务平台的管辖范围及关键路线节点的调派进行研究。首先我们从给出的各节点坐标和各节点的相邻关系等数据出发，通过matlab 软件编写程序，先求得各相连节点之间的街道长度，再利用求任意两点之间最短
4、路的Dijkstra 算法求得任意两个节点之间的最短路线，得到 A 区任意两点最短路线距离矩阵。针对问题一的第一部分，要求求得各交巡警服务平台的管辖范围，使得交警尽量能在三分钟之内到达事发地点。该问题为推广的点覆盖问题，因为不仅要求各平台管辖与之相邻的节点和街道，还可能管辖与之不相邻的节点和街道。所以我们通过修改点覆盖模型，依据工作量均衡原则对该区交通网络进行分配，建立了 01 规划模型，最终得到合理的分配方案。针对问题一的第二部分，要求在出现重大交通事故时快速调度20 个交巡警服务平台的警力到达13个交通要到的节点，要求一个平台的警力最多封锁一个路口。这既可以看做线性规划中的指派问题，又可以
5、看做是偶图中求最优匹配问题。为此，先虚拟 7个交通要道节点，使得每个平台到这些虚拟节点的距离为，构造出赋权平衡偶图，建立整数规划模型，通过lingo 软件编写程序求得调度方案。针对问题一的第三部分，要求增设25 个服务平台解决工作量不均衡和有些地方出警时间过长的实际问题。通过对工作量的分析建立基本的工作量函数，求得工作量向量，并根据一定的调整原则对原有方案进行优化。问题二分为两部分，其中第一部分是把问题一中A 区的平台设置方案扩展到全市，判定其是否合理。具体来讲，是将全市的交通网络数据应用到问题一所建立的数学模型，求出服务平台设置方案，再依据工作量和出警时间，对求出的方案进行分析和评价，并给出
6、不合理部分的解决办法。针对问题二的第二部分，要求警方在最短时间内围捕犯罪嫌疑人，先判断犯罪嫌疑人最可能出该区的路口（即以最短距离出A 区的几个路口），从而分配警力封锁之，同时，将剩余警力分配到A 区其它的出城路口，得到封锁A 区的最佳围堵方案。如果犯罪嫌疑人逃出A 区，利用问题一第二部分所给模型，求出犯罪嫌疑人出市区各路口的最佳围堵方案。关键字：最短路线距离矩阵；推广的点覆盖；指派问题；01 规划；最优匹配问题；工作量函数一、问题重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部
7、位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件 1 中的附图1 给出了该市中心城区A 的交通网络和现有的20 个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3 分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20 个交巡警服务平台的警
8、力资源，对进出该区的13 条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至 5 个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第 32 个节点）处发生了重大刑事案件，在案发3 分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全
9、市交巡警服务平台警力资源的最佳围堵方案。二、问题假设及符号说明问题假设：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:交警处
10、理案件时间ijd：120i，j20，i 平台到节点j 所需最短距离D（ijd）全市最短路线距离矩阵A（ija）全市邻接矩阵，其中当ija为有限数时，表示节点i 到节点 j 的街道长度，当ija为无穷大时，表示节点i 与 j 直接没有街道相连。if：i 节点的发案率1D(ijd)：A 区任意两点最短路线距离矩阵；1A(ija)A区邻接矩阵；1():ijB b（i=1、2,20;j=1、2,20）表示 20 个平台到20 个节点的矩阵，其中前13 个为各对应交通要到节点，后7 个为虚拟节点;(,iix y)：节点i的坐标1j0ijijx；平台 i 管辖节点；平台 不管辖节点iw：i平台工作量三、问
11、题的分析本题是研究如何合理的设置交巡警服务平台，分配各平台的管辖范围、调度警卫资源。以实现交巡警服务平台更快更好的服务群众的目标。本题给出了某市区的所有交通网络及各节点在比例图中的坐标，并说明了各相关联的节点及各节点的发案率，指出了现有交巡警平台所在节点位置及进出口市区交通要道所在节点位置。并给出了市区内各区面积和人口数量。题目设有两个问题，（1）问题分为三个部分，一部分要求为现有交巡警平台分配管辖范围，使得在其管辖范围内出现突发事件时，尽量能在三分钟之内有交警到达事发地点;二部分要求对于突发事件，需要调度 20 个交巡警服务平台的警力资源到13 个交通要道的最佳调度方案；三部分要求对于工作量
12、不均衡和有些出警时间过长的实际情况增加2 到 5 个服务平台使情况的得到改善。根据题意，需求交警在三分钟之内所到达的范围，初步分析应建立以平台为中心，三分钟所能到达距离为半径，画出每个平台所能覆盖到的范围。但分析到不是所覆盖的范围都可直线通过，而是有很多折线，据此，首先应该根据所给各节点在平面直角坐标系上的坐标资料求出相邻两点之间街道长度，因为所给数据过大，因此，应利用MATLAB软件编写相关程序求出每两个相邻节点之间街道的长度。再利用DIJKSTRA 算法通过MATLAB编写程序计算出每个节点到其他各个节点之间的最短路线的长度。在此基础上就可以开始问题一各部分求解：部分一分配各平台的管辖范围
13、，可通过设定目标所有平台所管辖的节点总路程最小（题目要求尽量使得三分钟内有交警到达事发地，实际计算中出现少量三分钟无法到达的点，所以对该约束进行转化使得到每个节点时间最小即可，本题中也即总时间最小即可即总路程最小），以及目标每个平台工作量尽量均衡即工作量最大的平台和工作量最小的交巡警平台工作量之差最小。即目标有两个，可把问题看做一多目标规划问题。并设定约束条件每个节点只能分配到一个服务平台，并通过设计LINGO 程序求解，得到各节点的分配方案。接下来再对未管辖的街道进行分配。原则是：该平台所管辖所有节点之间街道（即所管辖节点的诱导子图的所有边）一定是归本平台管辖；把两个端点属于不同平台管理的街
14、道，按工作量均衡的标准分配到工作量少的平台管理，从而得到各平台管辖范围。实际操作过程中，该模型较难实现，因此，我们的目标函数先忽略工作量均衡的目标，求出分配方案，在遵循工作量均衡原则，对此方案进行调整，得到最终答案。部分二把各平台与各节点之间的调度看做分配问题，建立分配问题的数学模型，虚拟7 个交通要道，并设虚拟的交通要道到各个平台之间的最短距离为0，把各平台到各交通要道的最短距离设为目标矩阵。通过 LINGO 软件编程求解，得出最优调度方案。对于部分三，可通过部分一中求解的范围分配方案求解工作量及出警时间。再拟设定增加2 到 5 个交巡警服务平台解决以上不太合理的情况。并再通过新设定的平台通
15、过修改的部分一中模型求解，得出答案，检验是否合理。（2）问题要求针对全市按设置交巡警服务平台的原则和任务分析现有交巡警服务平台的合理性。同样应先求出全市各节点之间的最小距离，该方法参照问题（1）中求解方案。同样再利用类似于问题一中部分一的求解模型求解。把全市分成的六个区域分别求解，各区域之间相连的路线参照问题一中部分一边际调整方案分配。并根据时间要求及工作量要求判定是否合理。对于围捕犯罪嫌疑人问题，也是指派问题模型。重要路口是指犯罪嫌疑人以最短路线出A 区的路口。首先判断并封锁这些重要路口，其次将剩余警力分配至A 区其余出城区路口，修改第一问建立的指派问题模型求出在A 区最短时间围堵罪犯的最佳
16、方案。如果犯罪嫌疑人已经逃出A 区，我们可以利用指派模型，输入全市各个出市路口和最短路线距离矩阵等数据，求出犯罪嫌疑人逃出市区的最佳围堵方案。四、模型的建立及求解问题一：根据坐标通过建立matlab 软件求解两相邻节点之间距离，并转化成实际中的距离。得到该市 A 区所有节点邻接矩阵1A(ija)。所编写的程序见附录一。根据上述所求得的数据通过matlab 软件利用dijkstra 方法求解任意两点之间最短距离。得到该市 A 区最短距离矩阵1D(ijd)，程序见附录二。对于问题一中部分一：根据题意，需要把92 个节点分配给20 个交通巡警平台，其中20 个节点已经设有交通巡警平台，必定受本节点所
17、设平台管辖，只需将剩余的72 个节点进行分配。而对于节点之间街道的分配，每个平台所管辖的节点之间的街道都由该平台管理。街道两端节点若被不同平台管理，按工作量大小将该街道分配给工作量小的平台管理。因此，范围的分配分为两步：1.节点的分配：根据交巡警服务平台分配原则建立多目标规划问题如下：209211min*60ijijijdx921minmax*2*min*2*6060ijijiijiijjddfxfx92111()01i=j=192ijjijijxDdx或；（1到20，到）由于该多目标规划较难实现因此，先不考虑工作均衡的目标即第二个目标函数，将该目标函数去掉。模型简化为：209211min*6
18、0ijijijdx92111()01i=j=192ijjijijxDdx或；（1到20，到）经 lingo 软件设计，（程序见附录三）求解得管辖范围分配方案：平台所管辖节点平台所管辖节点A1 67、68、69、71、74、75、76、78 A11 26、27 A2 39、40、43、44、70、72 A12 25 A3 54、60、62、63、64 A13 21、22、23、24 A4 57、60、62、63、64 A14 A5 49、50、51、52、53、56、58、59 A15 28、29 A6 A16 36、37、38 A7 30、32、47、48、61 A17 41、42 A8 33
19、、46 A18 73、80、81、82、83、84 A9 31、34、35、45 A19 77、79 A10 A20 85、86、87、88、89、90、91、92 表中分配方案为按时间计算管辖最优方案。只有部分节点即28、29、38、39、61、92 节点不能在三分钟之内到达，但选取的仍是最短路程的管辖点。2.街道的分配：分配原则：街道两端节点由同一平台管理的则该街道由管理这两节点的平台管理；街道两端节点由不同平台管理的由这两平台中工作量少的平台管理。通过初步分析，我门发现交巡警服务平台的实际工作量包括两部分，即其出警时间及所管辖节点发案率的乘积的累加，和它所管辖节点所有案件的处理时间累加。
20、因此写出公式929211*2*60ijijijjijjjdWfxf x t据该公式，得出每个平台工作量情况如下：平台 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.3
21、t 平台 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 根据以上值给出街道两
22、端由不同平台管理的街道分配放案，即交界处分配方案：8 号平台管理的交界处街道有3233、847、4655、3334、4646、89;9 号平台管理的交界处街道有3132；10 号平台管理的交界处街道有910、1011；11 号平台管理的交界处街道有1122；12 号平台管理的交界处街道有1227、1125、2425；14 号平台管理的交界处街道有2114、1614；15 号平台管理的交界处街道有2930、715、1531；16 号平台管理的交界处街道有3536、3437、3639、3839；17 号平台管理的交界处街道有4243、1740、3841、4281；18 号平台管理的交界处街道有73
23、74、7480、8485、8489；19 号平台管理的交界处街道有7677、7778、7879、7980；20 号平台管理的交界处街道有4192、8290。对于问题一中部分二：若出现重大交通事件，要求调度全区20 个交巡警服务平台的警力资源对进出该区的13 条交通要道实现快速全封锁，一个平台的警力最多封锁一个路口。把该问题看作一分配问题，建立01 规划的数学模型，求最优解。建立分配问题的数学模型：由于关键路线的节点不是连续的，因此，设立新变量ijy其中 y 中的 i 仍表示第i 号平台，j 取值为 120，1 表示调至12 号节点，2 表示调至 14 号节点，3 表示调至 16 号节点，4 表
24、示调至21 号节点，5 表示调至 22 号节点，6 表示调至23 号节点，7 表示调至24 号节点，8 表示调至28 号节点，9 表示调至29 号节点，10 表示调至30 号节点，11 表示调至38 号节点，12表示调至48 号节点，13 表示调至62 号节点，1420 表示虚拟的节点。所建立数学模型如下：202011minijijijzb y20120j 11;(120).1;(120)01;(120120)ijiijijyjstyiyij到到或到，到利用 lingo 软件编写程序，所编写程序见附录四。求解得到分配问题的解为：y(1,12)1.000000 0.000000 y(2,16)1
25、.000000 2.968200 y(3,9)1.000000 1.532600 y(4,14)1.000000 3.265000 y(5,10)1.000000 7.708000 y(6,13)1.000000 0.5000000 y(7,11)1.000000 3.805300 y(8,15)1.000000 4.751800 y(9,8)1.000000 10.49320 y(10,7)1.000000 0.5831000 y(11,2)1.000000 3.982200 y(12,5)1.000000 2.475800 y(13,4)1.000000 0.3500000 y(14,6)
26、1.000000 0.000000 y(15,3)1.000000 0.000000 y(16,19)1.000000 0.000000 y(17,1)1.000000 0.000000 y(18,18)1.000000 0.000000 y(19,20)1.000000 0.000000 y(20,17)1.000000 0.000000 即调用方案及所用时间（分钟）如下12 22 6.8825 16 14 2.9682 9 16 1.5326 14 21 3.2650 10 12 7.5866 13 23 0.5 11 24 3.8053 15 28 4.7518 8 30 3.0608
27、7 29 8.0155 2 38 3.9822 5 48 2.4578 4 62 0.3600 对于问题一中部分三，要求添加25 个交巡警平台解决实际中工作量不均衡和出警时间过长的问题。由于交巡警服务平台的实际工作量包括两部分即其出警时间及所管辖节点发案率的乘积的累加，和它所管辖节点所有案件的处理时间累加。因此，我们所设的评价是否更为合理的标准即W 是否更小。929211*2*60ijijijjijjjdWfxf x t调整原则Step1 交巡警平台必须在三分钟内赶到事发地Step2 工作量均衡（通过Excel 表格处理，Matlab 软件处理矩阵见附录五得出如下表格）平台1 2 3 4 5
28、6 7 8 9 10 工作量4.9927 5.2791 2.9784 3.5160 5.3048 1.25 5.1099 2.5758 4.3090 0.8000 平台11 12 13 14 15 16 17 18 19 20 工作量2.4134 2.0954 4.5461 1.25 2.8719 2.6623 2.7356 4.2185 1.7382 5.6076 由上述原则，step1中 28,29,38,39,61,92 这六个路口明显三分钟交警不能到达。Step2中 1，2，5，7，13，18，20 这五个平台工作量太多。综上我们可以增加五个平台具体位置为21，38，61,92,28，
29、（见附图一）问题二：要求判定全市的交巡警平台设置是否合理，该评价标准也建立在分配了交巡警服务平台所管辖范围的基础上，对各交巡警服务平台的是否能在较短时间内到达其案发地及工作量是否均衡来评价其是否合理。该问题类似于问题一中求解各平台所管辖范围和判断工作量是否合理的问题。只需求解出各平台所管辖范围，并比较最长出警时间是否大部分都在3 分钟之内，以及工作量是否比较均衡。通过问题一中建立的模型求解的本市各区分配方案如下：B 区分配方案：C 区分配方案D 区分配方案E 区分配方案平台所管辖节点B1 101103 B2 104112、117123、B3 113116、126、128、129、131、136
30、、154、B4 124、127、130、133、134、138142、145147、150、151 B5 135、137、143、144 B6 155165 B7 149、152、153 B8 125、132 平台所管辖节点C1 262265 C2 248252、255、258261 C3 189192 C4 254 C5 222226、273、276、277、283 C6 215、216、230、231、240、241244、246、253 C7 217、218、227229 C8 232239、245、247 C9 211214、219221 C10 183、193199、C11 1841
31、88、C12 200210 C13 284、286、287 C14 274、275、278282、285、288292、295、296 C15 268270、297316 C16 266、267、317319 C17 256、257、271、272、293、294 平台所管辖节点D1 347-350 370 371 D2 351-360 368 369 D3 367 D4 344 345 361 362 D5 364-366 D6 D7 343 346 D8 337 338 340 341 3421 D9 329-336 339 平台所管辖节点E1 E2 437 438 456 E3 427
32、432-436 457 E4 424-426 428-431 E5 F 区分配方案平台所管辖节点F1 550、551、555559、561、563565 F2 532535、543547、552554 F3 492509、516523、529、530 F4 512515、524528、536539、542 F5 573、575582 F6 562、566569、574 F7 486、490、491、531、548、549 F8 487489、460 F9 510、511 F10 540、545、570 F11 571、572 通过其分配方案利用matlab 编写的程序可求解市区内各个平台的出警
33、时间。分析其每个区域各个交巡警平台平均出警时间和最长出警时间分别为：区域平均出警时间最长出警时间A 区3.13 5.30 B 区2.93 9.82 C 区2.97 15.2 D 区3.03 16.06 E 区3.20 19.10 F 区2.70 8.48 也可根据题一中模型求解各区工作量得到结果如下：B 区B 区 1 平台1.894B 区 2 平台6.767B 区 3 平台4.698B 区 4 平台6.506B 区 5 平台2.824B 区 6 平台6.326B 区 7 平台2.088B 区 8 平台2.052C 区C 区平台 14.5619C 区平台 29.1097C 区平台 32.5325
34、C 区平台 42.0592E6 416 E7 458 459 E8 417-423 E9 387-396 E10 397-400 405 406 E11 401-404 407-415 E12 452-455 460-464 469 470 E13 465-468 471 472 E14 445 446 448-451 473 474 E15 440-444 447 C 区平台 56.9928C 区平台 68.9380C 区平台 74.2584C 区平台 88.6855C 区平台 95.7492C 区平台 106.1840C 区平台 114.3404C 区平台 128.2760C 区平台 13
35、3.3063C 区平台 1412.7508C 区平台 1519.4608C 区平台 165.3640C 区平台 175.7676D 区D 区平台 15.6936D 区平台 29.6177D 区平台 31.5077D 区平台 43.7891D 区平台 53.686D 区平台 60.7D 区平台 72.227D 区平台 84.5554D 区平台 98.0251E 区E 区 1 平台0.7E 区 2 平台2.3773E 区 3 平台2.2185E 区 4 平台4.9736E 区 5 平台0.7E 区 6 平台1.5508E 区 7 平台2.4833E 区 8 平台7.1031E 区 9 平台9.84
36、98E 区 10 平台5.0957E 区 11 平台11.0797E 区 12 平台9.2654E 区 13 平台5.4635E 区 14 平台7.2621E 区 15 平台4.4435F 区F区 1 平台9.2343F区 2 平台9.6443F区 3 平台21.9079F区 4 平台11.7441F区 5 平台7.8487F区 6 平台5.4259F区 7 平台5.3606F区 8 平台4.0567F区 9 平台2.4263F 区 10 平台2.9535F 区 11 平台2.2292从出警时间来看，平均出警时间都在三分钟周围，但最长出警时间C、D、E 区均超过了10 分钟，比较不合理，从工作
37、量的分配可看出，在六个区域内工作量的分配很不均匀，同一区域内工作量的分配有很大的悬殊，尤其是C、F 区，因此，本市交巡警平台的设置不太合理，应进一步给予优化。对于围堵问题，若P 点处发生的重大刑事案件，在案发三分钟后接到报警，巡警要实现最快最小范围的围堵。Step1 求出从 P 节点出 A 区的最短路径和时间以及相应的出口（我们称这些出口为重要出口）Step2 求出封堵重要出口的分配方案Step3 利用问题一中建立指派问题模型，求出剩余平台封堵非重要出口的最佳分配方案Step4 利用问题一中的指派问题的算法，求出全市服务平台封堵出入全市的路口以及时间。如果我们输入犯罪嫌疑人的平均逃亡速度，将输
38、出合理的围堵方案。五模型的评价优点：1.适用范围广，模型对于一些同类的图论问题同样适用。2.对模型的建立和求解做了详尽的讨论，在第一问中，对路段进行了均衡考虑，涉及了各个路口的发案率，并假设了每个平台处理问题时间都为t 3.运用分配问题的模型，点覆盖的推广，其中多次运用Matlab 软件对于问题求解有很大的帮助缺点:1.问题一中无法证明为最优答案，而仅仅是一个较优解。2.有的街道没有考虑工作量六参考文献1 王海英，图论算法及其MA TLAB 实现，北京航空航天大学出版社，2010.2。2 王树禾，图论及其算法，合肥：中国科学技术大学出版社，1990。3 钱颂迪，运筹学，.北京：清华大学出版社，1988。4 胡运权等，运筹学基础及应用，高等教育出版社，2008。5 卢开澄、卢华明，组合数学，清华大学出版社，2005。6 高俊斌，MATLAB5.0语言与程序设计，武汉：华中理工大学出版社，1998。7 张志涌、刘瑞桢、杨祖樱，掌握和精通MATLAB，北京航空航天大学出版社，1999。