交巡警服务平台的设置与调度的问题2011年B题

承诺书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B

我们的参赛报名号为（如果赛区设置报名号的话）：S13036

所属学校（请填写完整的全名）：河南科技学院

参赛队员（打印并签名）：1

2.

3.

指导教师或指导教师组负责人（打印并签名）：数学建模指导小组

日期：2011年9月12日赛区评阅编号（由赛区组委会评阅前进行编号）：

编号专用页

赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：

全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：

交巡警服务平台的设置与调度模型

摘要

“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。本文研究的是交巡警服务平台的设置与调度问题，目的是为了使交巡警服务平台的调度方案达到最佳问题一首先我们通过建立网格模型求解关于某市中心城区A的交警服务台的分配管辖范围问题，采用了floyd的算法得到任意两点之间的距离，再根据两点之间的邻接矩阵运用Matlab软件求出A区任意两路口之间的距离，然后通过网络各点间最短距离的矩阵算法求出网络图中任意连通的两点之间的最短路径；最后通过网格算法得出分配交巡警服务平台的管辖范围(如表1)；对于服务平台警力的合理调度问题，建立分配问题的混合整数线性规划模型，采用矩阵作业算法得出有效地警力的调度方案：10→12,16→14，9→16,14→21,13→22,12→23,11→24,7→28,5→29,8→30,2→38，6→48,4→62（从服务台到各个出口）。可以达到快速全封锁。紧接着本文根据平台选择原则并对相关数据进行分析处理得到应加的平台数为4，且在分别在29,40,48,90节点处；

问题二在分析研究该市现有交巡警服务平台设置方案的合理性的问题中本文采用了模糊层次综合法，通过建立模糊层次综合模型，继而对因素权重进行求解以及归一化的处理分别对A B C D E F六区进行评价，最后得出A D E是相对比较合理的，B C F区域中存在明显不合之处，通过权重分析在分别在B C F区中在各增加一个服务平台能够得到合理改善。在最后的围堵问题中本文采用逐步跟随以及全局考虑的思想对犯罪嫌疑人实现了快速围堵的目的。在文章的最后，本文就本篇论文模型的优缺点进行了评价并对其推广进行了说明。

关键词：网格模型floyd的算法Matlab软件模糊层次综合法

一、问题重述

“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：

一、(1) 根据该市中心城区A相关的数据信息为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。

(2) 对于重大突发事件，怎样调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。

(3) 根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。

二、(4) 针对全市的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，请给出解决方案。

(5) 如果该市地点P(第32个节点)处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。

二、问题分析

在问题(一)中当各交巡警服务平台所管辖的范围内出现突发事件，我们只需要考虑最短路径即可，但是数据量过大，我们分别运用floyd算法和Matlab软件选择最短路径，得出平台所管辖范围。第二小问需要从20个平台中找出13个平台分派到13个交通要道去，这是一个木桶理论问题，即求众多组合中最大时间最小化问题，我们可以通过建立解混合整数线性规划模型决这个问题。第三小问由于各平台的工作范围分布不均匀，且各节点的发案率差异，导致各平台工作量的不平衡，且部分地区出警时间过长，不利于维护地方的治安稳定，因此需要增加部分平台，从而改善治安环境。

问题(二)第一小问需要对全市所有区的交巡警平台布置做出分析评价，这里数据非常大，我们采取可以采取模糊层次综合模型来解决这个问题。第二小问要设计追捕逃犯的路线，这就要根据逃犯的速度分情况考虑，可以采用动态优化

三、模型假设

（1）假设材料中所给的数据真实可靠；

（2）假设图中任意两路口之间的道路为直线；

（3） 假设警车以60km/h 的速度匀速行驶，并且在执行任务的过程中不会出现

故障；

（4） 假设不考虑交通堵塞、红绿灯问题；

（5） 假设在整个路途中，转弯处不需要花费时间；

（6） 假设出警时道路恒畅通(无交通事故、交通堵塞等发生)，警车行驶正常。

四、符号说明

i x ：各路口点的横坐标 i y ：各路口点的纵坐标 b

:任意两路口间的距离

B:任意两坐标之间的直线距离

C ：邻接矩阵

五、模型的建立与求解

5.1 问题一

5.1.1 第一小问

Step1：首先由题中所给出的数据，我们可以根据解析几何中两点之间的距离公式：

(,)b i j =

（i,j ∈1,2,3,…92）,

用Matlab 软件计算求出任意两坐标点之间的直线距离，并得到关于ij b 的矩阵B 。

11

11

9292

n n nn b b B b b ??? ?= ? ???

Step2:根据题中所给的分布图我们可以人工的得到各路口的邻接情况，来得到其邻接矩阵C ，方便以后的求解。其中直接相连的两路口之间用1表示，反之用0来表示。

1111

9292

n n nn c c C c c ??? ?= ? ???

Step3:由于我们需要求出任意两路口之间的实际距离，需用Matlab 软件

先算出各相邻路口之间的距离，该过程可以有B 点乘C 来计算得到：

1

9

292

n

n n n f f

F B C f f ?

??

?=?= ? ???

Step4:因为D 中未相邻两路口的值为0，在后面求解最小距离是会使其一直为0，所以把不相邻的路口中得ij d 数值该为无穷（inf ）得到一个新的 矩阵

11119

292

n n n n e e E e

e ?

??

?= ? ???

Step5:通过matlab ，运用Floyd 算法求出任意两点间最短距离，得出最短距离矩阵D(具体程序祥见附件)；

111

19

292

n n n n d d

D d

d ?

??

?= ? ???

图1交巡警平台管辖区域

5.1.2 第二小问

1.0.ij i j x ?=?

?第服务台到第个出口第i 服务台不到第j 个出口

i=1...20;j=1,2,3 (13)

则走过最大路程为：

},m a x i j i j

i j

z c x

=

限定条件为：

13

11,1,2,...20()ij

j x

i =≤=∑既每个服务台只能到一个路口

20

1

1,1,2...13()

ij

i x

j ===∑既每个路口要有服务台到达

运用矩阵作业法直接从距离表格得出矩阵

1111

1320

n m m n r r R r r ??? ?= ? ???

， 联立目标函数求解得出最佳警力调度方案。

得出结果为（从平台到路口）：10→12,16→14，9→16,14→21,13→22,12→23,11→24,7→28,5→29,8→30,2→38，6→48,4→62。

5.1.3 第三小问

针对现有交巡警平台设置中出现的问题，拟增2至5个平台，在此我们提出几点选择新平台位置的原则：

1、平台管辖区域内工作量合适

2、尽量在3分钟内到达事故发生现场

3、案发率高的区域适当增加平台数

（1）对于原则一：

由于现有交巡警服务平台的工作量不均衡和有些地方出警时间过长，拟增加2~5个平台。根据问题一及问题二的结果（表1及表2），统计出A去20个平台管辖区域内的节点个数，以及当有突发事件时，各平台需要封锁的出入口个数。得出每个平台的工作量，

平台1内有节点9个，平台20内有节点9个，平台5内有节点8个，平台2有内节点6个，平台4和平台7内节点各有5个，这几个平的工作量较大。我们可以优先考虑从这几个平台管辖的区域内再拟增加平台。

（2）对于原则二：

由问题一中得出的各节点到平台的最短距离的最小值矩阵C可知，节点

28,29,38,39,61,92距离最近平台的路程已经超过30毫米，当发生重大事件时交巡警不能在3分钟内到达，因此也应当优先考虑在这几个节点处增设平台。

（3）对于原则三：

由附件2筛选统计出A区这6个节点的案发率，在此我们不考虑前20个节点所在位置的案发率，因为前20个节点处均设有平台。交巡警不能在3分钟内达到的6个节点的案发率如下表5所示：

表3 案发率

由以上三个设置平台位置的原则，得出应在1，20,5,2,7和4 这6个工作量大的平台所管辖区域内的节点中，以及在平台28，29 ，38 ，39 ，61,92中新增2至5个平台。综合以上各因素，我们考虑新增平台若能既是工作量大的平台管辖域内的节点，又能保证其管辖范围内包括后面6个未能被准时到达的平台，则资源会得到合理的利用。

我们以A区20号平台为例，在20号平台管辖区域内的节点有84,85,86,87,88,89，90,91,92。根据问题一得到的各节点间最短距离矩d,求出20号管域内各节点分别到节点29,39,38,28,,92,61的最短距离矩阵.

由以上求出的各平台内节点到29,39,28,38,92,61节点的最短距离，可以得出节点92,38,39，61可以被新建的平台在3分钟内到达。各平台到这三个节点的距离如下图2所示：

图2 各平台到这三个节点距离

按照距离最短原则

1.在节点90处建立平台；

2.虽然再节点39处到节点38的距离比较短，但是再节点40处建立平台，其管

3.域内包括了两个节点38,39。故我们选择在节点40处建立新平台。

现在剩下28,29,这两处节点不能在3分钟内被交巡警到达。由于29,28d =9.49<30,且在节点29的案发率比较高，因此我们选择在节点29处建立新的平台；

新增4个平台，分别分布在节点29处，节点40处，节时，点48处，节点90处。由此可使A 区所有节点在其所属的平台内，当有突发事件交巡警均能在3分钟内到达，而且缓解了原有一些平台工作量大，不均衡的问题，是资源得到了合理的利用。

5.2 问题二

5.2.1 第一小问 模糊层次综合模型：

模糊层次综合法是将模糊综合评价法与层次分析法(AHP)相结合的一种系统评价方法。即模糊综合评价法中的权重分配集是由层次分析法确定的。模糊层次综合评价法所建立的数学模型如下:

T

F C S

=?

式中, F 为系统总得分; C 为系统评价矩阵; S 为各因素安全等级加权值。

C A B =

式中, A 为各因素权重分配集, 由各因素的影响大小决定; B 为总评价矩阵。

i i i B A R =

式中, Ai 为各因素对应子因素的权重分配集, 由层次分析法确定各子因素的影响大小; Ri 为各因素对应的评价矩阵, 由若干专家或小组对各子因素状况按评价集投票得出。

服务站设置方案涉及的因素从横向看, 应该包括服务范围、出警时间、工作量等诸多因素;从纵向上看, 涉及到案发率、管辖范围等诸多因素。服务站设置方案合理性层次结构如图所示。

图3 服务站设置方案合理性层次结构

采用层次分析( AHP) 确定服务平台设置方案评价指标因素的权重值, 计算各指标因素相对权重, 把对权重的判断定量化。由表服务平台状况属性的3个对象, 建立综合因素评价集 V= (V1, V2, V3)) , 同理表明影响因素 V1属性的 3个对象可以建立 1 个次级综合因素评价集 V1= (C1 , C2 , C3) ;表明影响因素V2状况的次级综合因素评价集 V2= (C4 , C5, C6) ; 表明工作量因素 V3 状况的次级综合因素评价集 V3=(C7, C8, C9) 。由于篇幅有限, 这里只给出 S- V 各评价指标因素( V1, V2, V3)的各因素权重计算的过程。

先考虑A 区，采用层次分析法确定评价集 V 中各因素对系统S 的权重1,3,5， 建立判断矩阵递阶层次结构的构成, 确定了上下之间元素关系, 可对同一层次的各个元素关于上 1 层次中某一准则的重要性进行两两比较,构造出判断矩阵。对服务站来说,通过大量数据的分析研究和深入实地的调研,参照表 1, 对 V 中的各因素的比较进行评价打分,得出 S- V 判断矩阵

1351/3121/51/3

1?? ? ? ??

?

表4 标度及含义对照

标度 含义 1 2个因素相比，具有同样重要性

3 2个因素相比，1个比另1个明显重要 5 2个因素相比，1个比另1个稍微重要 7 2个因素相比，1个比另1个强烈重要 9 2个因素相比，1个比另1个极端重要 2

4 6 8 上述两相邻判断的种植 （1）求因素权重

用方根法求因素权重向量近似值'i W :'1/41(135)W =?? 1.97=；

'

1/4

2(1/312)

W =??0.90=;'

1/4

3(1/51/31)

W =??0.508

=。

（2）归一化处理

将权重向量近似值作归一化处理：''''11123/()W W W W W =++=0.58；

'

'

'

'

22123/()W W W W W =++=0.27； '

'

'

'

33123/()

W W W W W =++=0.15；即权重集为W=

（0.58,0.27,0.15），A=（0.58,0.27,0.15）。 （3）层次分析法

确定评价集1V 、2V 、3V 中各因素对系统S 的权重

建立1V 、2V 、3V 判断矩阵如下，同2.2.1节的步骤求出各因素权重1A 、2A 、

3A 。

1V -（1C 、2C 、3C ）判断矩阵：

1121121/21/2

1?? ? ? ??

?

2V -（4C 、5C 、6C ）判断矩阵：

1

221/2111/21

1??

?

? ??

?

3V -（7C 、8C 、9C ）判断矩阵：

1

231/2131/31/3

1?? ? ? ??

?

最后求得：1A =(0.4,0.4,0.2 ),2A =(0.5,0.25,0.25 ),3A =(0.5,0.33,0.17 )。 （4）求各因素综合评价矩阵'i B

将i A 与i R 这2个模糊子集合成得相应的各因素综合评价矩阵，即

i i i B A R =

；结果如表

2所示。将'i B 归一化后，得i B ：

1B =（0.19,0.33,0.17） 2B =（0.14,0.32,0.38）

3B =（0.35,0.27,0.24）

将i B 组合建立总评价矩阵B,即B=123(,,)T B B B

0.190.330.170.14

0.320.380.350.27

0.24B ??

?=

? ??

?

（5）求服务平台的合理性矩阵C

由C=A B,而A=（0.58,0.27,0.15），则归一化后得： C= A B=（0.19,0.32,0.26） 求服务平台的合理性总得分

对各等级都按百分制评分可求系统的总得分：

F=C T S =0.19*90+0.32*75+0.26*60=72.1

同理得到B=56.4,C=54.2，D=77，E=82，F=51。 参照表5可知，B 、C 、F 不合理。

5.2.2 第二小问

由于发生了突发事件，本文假设犯罪嫌疑人的逃跑车速为匀速60(km/h)；犯罪嫌疑人对市区非常熟悉；犯罪嫌疑人在追捕的过程中不下车且在没有突发事件再次发生；犯罪嫌疑人对本市的交巡警服务平台非常熟悉。

从P 点出发，在没出A 之前，分析各路口之间的连接路可得一下路程关系连接图

图4 各路口之间连接图

经对案发地点各路口以及其连接路和犯罪嫌疑人的逃跑车速的综合分析：犯罪嫌疑人在三分钟后的行驶路程为3千米，因为犯罪嫌疑人对本市的交巡警服务平台非常熟悉，由32节点出发和实际情况相结合可得到其最有可能的逃跑路线如下：32→33→34→31→36→39，32→7→30→237，32→7→30→48→235；且其此时犯罪嫌疑人最有可能所在的路段为:36→39，30→237，48→235。为了预防犯罪嫌疑人出现在预料之外的路段和减小围捕范围先做出一下调度：首先把城市的各主要进出干道进行封锁，然后把15号警力调到28处，7号警力调到30处，4号警力调到62处，475号警力调到661处，把离371处最近的交巡警服务平台的警力调到371处，把离369处最近的警力调到369处，167号警力调到252处，169号警力调到253处，173号警力调到235处，179号警力调到273处，其他没有调到的则在各自的交警巡平台处待命，在本区出口附近的则封锁进出口。等所有的封锁全部完成后，再对犯罪嫌疑人可能所在的路段地区进行收缩围堵，如此逐渐减小范围，可以在最卡快得时间内对犯罪嫌疑人进行搜捕。

六、模型的评价与推广

模型优点：

1、模型的建立思路简单清晰，灵活性高，适用于多类问题的使用。假设合理贴近实际，数据计算精准有效，并多次作图显示，说服力强。

2、在模型求解最短距离过程中使用MATLAB软件编程，把大量的运算交给计算机处理，大大减少了运算的时间，也提高了计算的准确性。

3、在应用模糊层次分析法对全市服务平台设置合理性分析时，采用加权平均型进行评价，避免了指标的偏大偏小造成结果不易分辨的情况。

4、文中多用矩阵表示多个因子之间的关系，清晰明了，简便直观，灵活高效，便于扩展，易于编程时直接使用。

模型缺点：

1、由于文中数据量过大，部分数据的四舍五入可能给结果带来一定的误差。

2、实际生活中存在大量不定因素，假设中难以考虑周全，或多或少影响了实际结果。

模型推广：

本模型较好的解决了交巡警平台的管辖范围划分和围堵罪犯问题，有效地改善了交巡警执行任务的效率，平衡了各个服务台的工作量，提高了城市各处的安全性。在科技迅速发展的今天，人口迅速增长，城市加速扩张，交巡警平台的设置是平安城市的最好保障。该模型也可运用到其他最优路径或选址问题中去，比如关于消防救援工作最优路径问题、安全事故应急救援问题、旅游交通的最优路径问题等。

参考文献：

[1]：钱湔.运筹学[M].北京：科学出版社，2000，322-430

[2]：肖雁，符卓，李育安.问题及其应用前景探讨[J]. 带软时间窗口的车辆路径中国运筹学会第六届学术交流会论文集，下卷，634－638

[3]:薛定宇，陈阳泉.初等运用数学效果的matlab求解[M].北京:清华大学出版社，2004.,8

[4]：石辛民，郝正清.基于matlab的适用数值计算[M].北京：清华大学出版，北京交通大学出版社，2006,2、

[5]：孙霞林. 用最优化选择原则求最短路径及长度[A] .湖北师范学院学报：

[6]: 张玉成孙俊逸应用最优化选择原则求最短路径及长度[A].《湖北大学学报：自然科学版》 1993 第1期

[7]: 孟凡江,高树喜,杨新安,王瑶.多路径分配的车流径路优化模型[A].《辽宁工程技术大学学报:自然科学版》2008 第A01期

附录：

附录1：

C=zeros(92);

A=[ 413 403 383.5 381 339 335 317 334.5 333 282 247 219 225 280 290 337 415 432 418 444 251 234 225 212 227 256 250.5 243 246 314 315 326 327 328 336 336 331 371 371 388.5 411 419 411 394 342 342 325 315 342 345 348.5 351 348 370 371 354 363 357 351 369 335 381 391 392 395 398 401 405 410 408 415 418 422 418.5 405.5 405 409 417 420 424 438 438.5 434 438 440 447 448 444.5 441 440.5 445 444];

B=[359 343 351 377.5 376 383 362 353.5 342 325 301 316 270 292 335 328 335 371 374 394 277 271 265 290 300 301 306 328 337 367 351 355 350 342.5 339 334 335 330 333 330.5 327.5 344 343 346 342 348 372 374 372 382 380 377 369 363 353 374 382.5 387 382 388 395 381 375 366 361 362 359 360 355 350 351 347 354 356 364.5 368 370 364 370 372 368 373 376 385 392 392 381 383 385 381.5 380 360];

for i=1:92

for j=1:92

C(i,j)=((A(i)-A(j))^2+(B(i)-B(j))^2)^(1/2);

end

end

disp(C)

附录2：

A=zeros(92);

d=[];%初始矩阵

for m=1:8

for i=1:92

for j=1:92

A(i,j)=d(i,1)+d(1,j);

for k=2:92

if A(i,j)

A(i,j)=A(i,j);

else

A(i,j)=d(i,k)+d(k,j);

end

end

end

end

if A==d

break

else

d=A;

end

end

disp(A)

附录3：

（3）load t.txt;%载入组合数据

load distance.txt;%载入20个平台与13个路口最距离ll=zeros(77520,1);

suffer1=zeros(13,13);%存放一个组合的所有数据

for i=1:77520

max=0;

suffer2=t(i,:);

for j=1:13

for p=1:13

suffer1(i,p)=distance(suffer2(j),p); if suffer1(i,p)>max %求最远距离

max=suffer1(i,p) %更新

end

end

end

ll(i)=max;

end

save 'll.txt' ll -ascii; %存入ll.txt

B题 交巡警服务平台的设置与调度

2011高教社杯全国大学生数学建模竞赛题目 （请先阅读“全国大学生数学建模竞赛论文格式规范”） 题目B题交巡警服务平台的设置与调度 摘要： 本文研究的是某城区警车配置及巡逻方案的制定问题，建立了求解警车巡逻方案的模型，并在满足D1的条件下给出了巡逻效果最好的方案。 在设计整个区域配置最少巡逻车辆时，本文设计了算法1：先将道路离散化成近似均匀分布的节点，相邻两个节点之间的距离约等于一分钟巡逻路程。由警车的数目m,将全区划分成m个均匀的分区，从每个分区的中心点出发，找到最近的道路节点，作为警车的初始位置，由Floyd算法算出每辆警车3分钟或2分钟行驶路程范围内的节点。考虑区域调整的概率大小和方向不同会影响调整结果，本文利用模拟退火算法构造出迁移几率函数，用迁移方向函数决定分区的调整方向。计算能满足D1的最小车辆数，即为该区应该配置的最小警车数目，用MATLAB计算，得到局部最优解为13辆。 在选取巡逻显著性指标时，本文考虑了两个方面的指标：一是全面性，即所有警车走过的街道节点数占总街道节点数的比例，用两者之比来评价；二是均匀性，即所有警车经过每个节点数的次数偏离平均经过次数的程度，用方差值来大小评价。 问题三：为简化问题，假设所有警车在同一时刻，大致向同一方向巡逻，运动状态分为四种：向左，向右，向上，向下，记录每个时刻，警车经过的节点和能够赶去处理事故的点，最后汇总计算得相应的评价指标。 在考虑巡逻规律隐蔽性要求时，文本将巡逻路线进行随机处理，方向是不确定的，采用算法2进行计算，得出相应巡逻显著指标，当车辆数减少到10辆或巡逻速度变大时，用算法2计算巡逻方案和对应的参数，结果见附录所示。 本文最后还考虑到4个额外因素，给出每个影响因素的解决方案。 关键词：模拟退火算法；Floyd算法；离散化

交巡警服务平台的设置与调度

承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）：建模指导组 所属学校（请填写完整的全名）：江西财经大学 参赛队员(打印并签名) ：1. 罗冰 2. 林鹏 3. 刘昶 指导教师或指导教师组负责人(打印并签名)： 日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：

编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：

交巡警服务平台的设置与调度 摘 要 随着经济社会的发展和物质文化的进步，警察在日常生活中扮演着愈来愈重要的角色，肩负着刑事执法、治安管理、服务群众的重任。但警务资源是有限的，因此，如何根据城市的实际情况与需求对其进行合理的规划，已成为目前十分实际且重要的课题。 本文以交巡警的出警时间和工作量为目标，建立双目标规划模型，并以此模型对服务平台的设置进行综合评价，得出警务资源分配方案。 针对问题（1）的第一个小问，基于题中所给有巡警至少在3分钟内到达事发地的要求，规划出各个路口节点所属的巡警服务平台，并对其中出现的共属情况通过最短距离来进行划分，从而分配出各个巡警服务平台的管辖范围。然后再对结合考虑各个巡警服务平台的工作量，对模型进行了优化，提升了各个巡警服务平台工作量均衡度 针对问题（1）的第二个小问，面对重大突发性事件的警力调度问题，我们通过建立最小最大模型，通过Lingo 编程求出封锁制定交通要道总体调度时间的最小值，从而达到了出警迅速的目标。 针对问题（1）的第三个小问，我们建立了以交巡警出警时间长短和工作量大小为目标的双目标规划模型 '2'1)(min T w Q D w F i +=，'')(T Q D i 、分别为无刚量化后的工作量目标函数与时间目标函数，i w 为权值秋且121=+w w 。利用此线性加权法求解的结果来衡量现平台设置合理程度，然后使用遍历搜索求解出A 区所需增加平台的具体个数和位置。 针对问题（2）的第一个小问，人口密度与出警时限呈现反相关，设定每个区域的出警时限。根据双目标规划模型评价六个区域交巡警服务平台的设置合理程度。对于各区应增加的平台数及其位置，则使用问题（1）第三小问建立的模型进行处理。 针对问题（2）的第二个小问，我们通过以案发地为辐射点，将3分钟内嫌疑犯可能到达的路口节点和他们之间的街道归并为一个集合，分析3分钟以后嫌疑犯的活动范围，搜寻它附近的巡警服务平台进行调度，从而给出调度全市交巡警服务平台警力资源的最佳围堵方案。 关键词：平台设置、调度、双目标规划、出警时间、线性加权法、遍历搜索

操作系统期末试卷(含答案)

操作系统复习题1 一、判断题 1.分时系统中，时间片设置得越小，则平均响应时间越短。（） 2.多个进程可以对应于同一个程序，且一个进程也可能会执行多个程序。（） 3.一个进程的状态发生变化总会引起其他一些进程的状态发生变化。（） 4.在引入线程的OS中，线程是资源分配和调度的基本单位。（） 5.信号量的初值不能为负数。（） 6.最佳适应算法比首次适应算法具有更好的内存利用率。（） 7.为提高对换空间的利用率，一般对其使用离散的分配方式。（） 8.设备独立性是指系统具有使用不同设备的能力。（） 9.隐式链接结构可以提高文件存储空间的利用率，但不适合文件的随即存取。（） 10.访问控制矩阵比访问控制表更节约空间。（） 二、选择题 1.在设计分时操作系统时，首先要考虑的是（A）；在设计实时操作系统时，首先要考虑的是（B）；在设计批处理系统时，首先要考虑的是（C）。 A,B,C ：（1）灵活性和适应性；（2）交互性和响应时间；（3）周转时间和系统吞吐量；（4）实时性和可靠性。 2.对一个正在执行的进程：如果因时间片完而被暂停执行，此时它应从执行状态转变为（D）状态；如果由于终端用户的请求而暂停下来，则它的状态应转变为（E）状态；如果由于得不到所申请的资源而暂停时下来，则它的状态应转变为（F）状态。D,E,F:（1）；静止阻塞（2）；活动阻塞（3）；静止就绪（4）；活动就绪（5）执行。 3.我们如果为每一个作业只建立一个进程，则为了照顾短作业用户，应采用（G）；为照顾紧急作业用户，应采用（H）；为能实现人机交互，应采用（I）；而能使短作业、长作业和交互作业用户满意时，应采用（J）。 G,H,I,J：（1）；FCFS调度算法（2）；短作业优先调度算法；（3）时间片轮转算法；（4）多级反馈队列调度算法；（5）基于优先权的剥夺调度算法。 4.由固定分区发展为分页存储管理方式的主要推动力是（K）；由分页系统发展为分段系统，进而发展为段页式系统的主要动力分别是(L)和(M)。 K,L,M:（1）提高内存利用率；（2）提高系统吞吐量；（3）满足用户需要；（4）更好地满足多道程序进行的需要；（5）既满足用户需求，又提高内存利用率。 5.在存储管理中，不会产生内部碎片的存储管理方式是（N）；支持虚拟存储器，但不能以自然的方式提供存储器的共享和存取保护机制的存储管理方式是（O）。 N：(1)分页式存储管理；(2)分段式存储管理；(3)固定分区式存储管理；(4)段页式存储管理。 O：（1）段页式存储管理；（2）请求分区页式存储管理；（3）请求分段式存储管理；（4）可变分区存储管理；（5）固定分区存储管理；（6）单一连续分区式存储管理。 6.磁盘调度主要是为了优化（P），下列算法中能避免磁盘粘着的现象的是（Q）。P：（1）寻道时间；（2）旋转延迟时间；（3）传输时间。 Q：（1）SSTF;（2）FCFS;（3）SCAN;（4）CSCAN;（5）FSCAN。 7.文件系统中，目录管理最基本的功能是（R），位示图的主要功能是（S），FAT表的主要功能是（T）。 R，S，T：（1）实现按名存取；（2）提高文件存储空间利用率；（3）管理文件存储器的空闲空间；（4）指出分配给文件的盘块（首个盘块除外）的地址；（5）管理文件存储器的空闲空间，并指出分配给文件的盘块（首个盘块除外）的地址。8.文件系统采用多级目录结构，可以（U）和（V）。 U,V：（1）缩短访问文件存储器时间；（2）节省主存空间；（3）解决不同用户文件的命名冲突；（4）方便用户读写文件；（5）提高检索目录的速度。 9.计算机系统中信息资源的安全包括（W）、（X）和（Y）三个方面，其中程序被删除属于（W）方面的威胁，数据被非法截取属于（X）方面的威胁，消息被更改属于（Y）方面的威胁。W,X,Y：（1）保密性；（2）完整性；（3）可用性；（4）方便性。 三、填空题 1.操作系统最基本的特征是（1）和（2），最主要的任务是（3）。 2.引入进程的主要目的是（4），进程存在的唯一标志是（5）。 3.（6）是指通过破坏死锁产生的必要条件来防止死锁的发生。引起死锁的四个必要条件中，（7）是不应该被破坏的，但对某些特殊的资源（如打印机），该条可通过（8）来破坏；而其他能被破坏的三个必要条件分别是（9）、（10）和（11）。 4.虚拟存储器管理的基础是（12）原理，在请求分页管理方式中，页表中的状态位用来只是对应页（13）修改位用来只是对应页（14），引用位则是供（15）使用；而在请求分段系统还增加了增补位，它用来指示（16）。 5.设备驱动程序是（17）与（18）之间的通信程序如果系统中有3台相同的单显和2台相同的彩显则必须为它们配置（19）种设备驱动程序 6.廉价磁盘冗余阵列可组成一个大容量磁盘系统，它利用（20）技术来提高磁盘系统的存取进度，而利用（21）技术来增加磁盘系统的可靠性 7.包过滤防火墙工作在（22）层，采用代理服务技术的防火墙则工作在（23）层 文件系统对文件存储空间采用（23）分配方式，它通过（24）来管理空闲的文件存储空间。 四、问答题 1.假设某多道程序设计系统中有供用户使用的内存100k，打印机1台。系统采用可变分区管理内存：对打印机采用静态分配，并假设输入输出操作的时间忽略不计：采用最短剩余时间优先的进程调度算法，进程剩余执行时间相同时采用先来先服务算法；进程调度时机在执行进程结束时或有新进程到达时。现有一进程序列如下： 假设系统优先分配内存的低地址区域，且不需移动已在主存中的进程，请： （1）给出进度调度算法选中进程的次序，并说明理由。 （2）全部进程执行结束所用的时间是多少 2.请用信号量解决以下的过独木桥问题：同一方向的行人可连续过桥，当某一方向的行人必须等待：另一方向的行人必须等待：当某一方向无人过桥是，另一方向的行人可以过桥。 3.提高内存利用率的途径有哪些 4.何谓脱机输入/输出技术 5. 将目录文件当作一般数据文件来处理有什么优缺点 操作系统复习题1答案 一、判断题 1、错 2、对 3、错 4、对 5、对 6、错 7、错 8、错 9、对10、错 二、选择题 1、A ：(2)；B：(4)；C：（3）。 2、D：（4）；E:(3)；F:(2)。 3、G：（2）；H:（5）；I:（3）；J：（4）。 4、K：（1）；L：（3）；M：（5）。 5、N：（2）；O：（2）。 6、P：（1）寻道时间；Q：（5）。 7、R：（1）；S：（3）；T：（5）。8、U：（3）；V：（5）。9、W：（3）；X：（1）；Y：（2）。 三、填空题 （1）并发；（2）资源共享；（3）管理资源；（4）使程序能够正确地并发执行；（5）进程控制快PCB；（6）预防死锁；（7）互斥条件；（8）SPOOLing技术；（9）

交警服务平台的设置与调度

交巡警服务平台的设置与调度 摘要 //本文以。。。。为理论基础，综合利用（机理分析）和（参数辨识）的一般原理建立数学模型。并利用SPSS进行数据统计分析，研究了。。。。的。。。规律，并利用。。。等。。。方法，针对。。。。，做出了。。。// 名称、思想、软件、结果、亮点详细说明。 本文针对交巡警服务平台的设置与调度问题，在合理的假设下，对 问题1要求为A区各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地 问题2要求当发生重大突发事件时，在一个平台的警力最多封锁一个路口的前提下，调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁，给出该区交巡警服务平台警力合理的调度方案。 问题3要求根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，确定需要增加平台的具体个数和位置。 （第1段）首先简要叙述所给问题的意义和要求，并分别分析每个小问题的特点（以下以三个问题为例）。根据这些特点我们对问题1用。。。。。。。。的方法解决；对问题2用。。。。。。。。的方法解决；对问题3用。。。。。。。。的方法解决。 （第2段）对于问题1我们用。。。。。。。。数学中的。。。。。。。。首先建立了。。。。。。。。模型I。在对。。。。。。。。模型改进的基础上建立了。。。。。。。。。模型II。对模型进行了合理的理论证明和推导，所给出的理论证明结果为。。。。。。。。。，然后借助于。。。。。。。数学算法和。。。。。。软件，对附件中所提供的数据进行了筛选，去除异常数据,对残缺数据进行适当补充,并从中随机抽取了3组数据（每组8个采样）对理论结果进行了数据模拟，结果显示，理论结果与数据模拟结果吻合。（方法、软件、结果都必须清晰描述，可以独立成段，不建议使用表格）（第3段）对于问题2我们用。。。。。。。。 （第4段）对于问题3我们用。。。。。。。。 如果题目单问题，则至少要给出2种模型，分别给出模型的模型进行比较，优势较大的放后面，这两个（模型）一定要有具体结果。 （第5段）如果在……条件下，模型可以进行适当修改，这种条件的改变可能来自你的一种猜想或建议。要注意合理性。此推广模型可以不深入研究，也可以没有具体结果。

大二-操作系统-试卷1及答案

《操作系统》试题（A卷） 1、操作系统的基本类型主要有。 A.批处理系统、分时系统及多任务系统 B.实时系统、分时系统及批处理系统 C.单用户系统、多用户系统及批处理系统 D.实时系统、分时系统及多用户系统 2、下列选项中，不是操作系统关心的主要问题。 A.管理计算机裸机 B.设计提供用户程序与计算机硬件系统的界面 C.管理计算机系统资源 D.高级程序设计语言的编译器 3、用户可通过建立和撤消进程。A.函数调用 B.宏指令 C.系统调用 D.过程调用 4、操作系统中，可以并发运行的基本单位是，同时，它也是核心调度及资源分配的基本单位。 A.作业 B.函数 C.进程 D.过程 5、若信号S的初值为2，当前值为-1，则表示有等待进程。 A.0个 B. 1个 C.2个 D.3个 6、进程从运行态到等待态可能是。 A.运行进程执行了P操作 B.进程调度程序的调度 C.运行进程的时间片用完 D.运行进程执行了V操作 7、要预防死锁发生，可破坏死锁的四个必要条件之一，但破坏条件是不实际的。 A.互斥 B.保持和等待 C.非抢占 D.循环等待 8、某系统中有3个并发进程，都需要同类资源3个，试问该系统不会发生死锁的最少资源数是个。

A. 6 B. 7 C. 8 D. 9 A.SPOOLing技术 B.覆盖技术 C.通道技术 D.虚拟存储技术 9、所谓临界区是指。 A. 一个缓冲区 B. 一段数据区 C. 同步机制 D.一段程序 10、N个进程共享某一临界资源，则互斥信号量的取值范围 为。 A.0～1 B.－1～0 C.1～（N-1） D.1～－（N-1） 11、虚拟存储技术的基础是程序的理论。 A.局部性 B.全局性 C.动态性 D.虚拟性 12、在请求式分页存储管理中，若采用FIFO页面替换算法，则当可供 分配的帧数增加时，缺页中断的次数。 A.减少 B.增加 C.无影响 D.可能增加也可能减少 13、TLB在计算机系统中是用于的。 A.存储文件信息 B.与主存交换信息 C.地址变换 D.存储系统程序 14、如果文件采用直接存取方式且文件大小不固定，则宜选择 文件结构。 A.直接 B.连续 C.链接 D.索引 15、操作系统采用了以空间换时间的技术。

操作系统试题7答案

操作系统试题5答案 一、填空题：（每空2分，共20分） 1、接口 2、访管中断结构 3、并发性动态性 4、系统调用 5、虚拟内存自动覆盖技术 6、高速寄存器 7、缺页中断 8、多缓冲（或缓冲池） 二、单项选择题（每空1分，共10分） 1、D 2、A 3、B 4、D 5、C 6、A 7、D 8、B 9、A 10、A 三、判断并改错（在括号内填上“√”或“╳”，错误的题要改正过来。每 题2分，共20分，做错不倒扣） 1、（×）虚拟存储器容量取决于内存与外存两者之和的容量。 2、（√） 3、（√） 4、（×）消息缓冲是一种直接通信方式，也是一种高级通信 5、（×）页式算法不能实现内存共享 6、（×）SPOOLING 系统是同外部设备联机的假脱机系统 7、（×）通道程序由I/O处理机执行。 8、（√） 9、（√） 10、（×）文件目录放在外存中。 四、简答题。（每题5分，共20分） 1、答：在系统中某个进程提出资源请求后，使得若干进程在无外力作用下永远不能前进（继续运行），系统处于停滞状态，这种现象称为死锁。处于死锁状态的进程称为死锁进程。死锁大多是由于并发进程共享临界资源引起的，死锁与时间相关。

产生死锁的根本原因是（1）系统资源不足；（2）进程运行推进的顺序不合适；（3）资源分配不当之处。 2、答：分页是将一个进程的逻辑地址空间分成若干个大小相等的页（或称页面），内存空间分成与页相同大小的物理块（或称页框）。在为进程分配内存时，以块为单位进行分配，每页分配一块。系统为每个进程建立一张页面映射表（简称页表），记录相应页在内存中对应的物理块号。 分段是将程序的地址空间被分成若干个段，每段采用连续的地址空间。这样程序的逻辑地址就形成一个二维地址，由段号和段内地址两部分组成。 系统为每段分配一个连续区域（相当于一个分区），各段可以存放在不同的分区中，即段与段之间的地址是不连续的。系统为每个进程建立一张段表，记录该段在内存中的起始地址和段长。 分页和分段都采用离散分配方式，但两者有显著的差别。 （1）页是信息的物理单位，分页是系统的需要，是为了提高内存的利用率；段是信息的逻辑单位，目的在于更好地满足用户的需要。 （2）页的大小固定，且由系统确定，一个系统只能有一种大小的页面；段的长度不固定，决定于用户的程序。 （3）分页的作业地址空间是一维的，单一的线性地址空间；分段的作业地址空间是二线的，一个地址包括段号和段内地址。 3、答：请求分页技术和简单分页技术之间的根本区别是： 请求分页技术在作业运行之前，只要求把作业当前所需要的一部分页面装入主存，其它部分放入辅存，当需要其它的页面时，再把所需页面调入主存，从而实现了存储扩充，使得小内存可以运行大作业。 简单分页技术在作业运行之前，要把全部作业都装入主存，没有实现存储扩充。 4、答：I/O控制是指对整个I/O操作的控制。其主要任务是： （1）对用户进程I/O请求命令的处理 （2）进行设备分配，缓冲区分配 （3）启动通道指令程序或驱动程序进行真正的I/O操作 （4）分析中断，响应中断，中断处理 五、问答题/计算题/证明题/算法设计题（每题10分，共30分）。 1、答：临界资源：同一时间只准一个进程使用的资源。硬件、软件 临界区：进程访问临界资源期间所执行的那段程序。 进程进入临界区的调度原则是： ① 如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。

交巡警服务平台的设置与调度 11年B题

全国大学生数学建模竞赛 承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：西北大学 参赛队员 (打印并签名) ：1. 张舒岱 2. 刘羽 3. 张成悟 指导教师或指导教师组负责人 (打印并签名)： 日期：2014 年8 月10日

全国大学生数学建模竞赛 编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：

交巡警服务平台的设置与调度 摘要 交巡警服务平台位置的选取以及划分交巡警服务平台的管辖范围对于处理突发事件有非常大的影响。现阶段，一般依据经验选取服务平台位置及划分管辖区域。所以如何科学合理处理的交巡警服务平台的设置与调度问题具有十分重要的现实意义。 本文研究了交巡警服务平台的设置与调度问题。具体讨论了在给定的区域A内，如何合理的设置交巡警服务平台的管辖区域；发生特殊事件时应如何调动服务平台警力以快速封锁区域A；应该增加多少数量交巡警服务平台以及在哪个位置增加。 本文建立最短路模型、0-1整数规划模型，利用MATLAB软件解决了分配各平台管辖范围、调度警务资源以及合理设置交巡警服务平台这三个方面的问题。 在解决分配各平台管辖范围问题时，本文建立了最短路模型。通过求解各个路口到交巡警平台的距离是否满足最低时间限制，解决交巡警服务平台分配管辖范围的问题。本文在MATLAB软件上运用Dijkstra算法进行求解，给出了中心城区A的20个服务平台的管辖范围，并求得到达最近的交巡警服务平台的时间超过3分钟的6个路口。 在解决调度警务资源快速封锁城区的问题时，本文建立了0-1整数规划模型。以封锁城区所用时间最少为限制条件，利用lingo软件编程求解，给出了该区交巡警服务平台警力合理的调度方案，并求得对13个交通要道实现全封锁最短需要8.01分钟。 在解决交巡警服务平台的选址问题时，本文建立了双目标0-1整数规划模型。考虑到建设新的服务平台需要投入更多的成本和警务资源，还需平衡各个服务平台的工作量。因此，以增加服务平台数最小和服务平台工作量方差最小为目标，建立了双目标0-1整数规划模型。解出增加的服务平台数为4个，新增的服务平台具体位置为A29,A39,A48,A88。 本文所提供的模型考虑到均衡各个交巡警服务平台的工作量和新建服务台的成本，使结果更加合理符合需求，可以推广到任何一个市区甚至更广范围内的交巡警服务平台的设置与调度问题的解决中。也可以广泛应用于社区卫生室、公共卫生间、消防救火中心等社会服务部门的选址问题，对实际有指导意义。 关键词：Dijkstra算法双目标0-1整数规划模型 Lingo编程

操作系统试卷及答案1

操作系统试卷及答案1 以下是为大家整理的操作系统试卷及答案1的相关范文，本文关键词为操作系统,试卷,答案,，您可以从右上方搜索框检索更多相关文章，如果您觉得有用，请继续关注我们并推荐给您的好友，您可以在教育文库中查看更多范文。 20XX年操作系统考试试题 一、填空题（每空1分，共12分） 1操作系统具备处理并发活动的能力，其最重要的硬件支持是____________。2所谓操作系统虚拟机的概念，是指

____________________________。3unIx系统进程控制块由____________和____________两部分组成。4常用的资源分配策略有优先调度和____________算法。5p操作可以使进程由运行状态变为____________状态。 6当采用资源有序分配方法时，它破坏了产生死锁的四个必要条件中的________条件。 7文件目录采用树型结构而不采用简单表结构的最主要原因是____________。8在请求分页系统中，为支持淘汰一页的功能实现，在页表中应增加_____和____两个数据项。 9常用的设备分配技术有独占分配、共享分配和_______________技术。 10文件系统中的链接技术，指的是在_____________________之间进行链接。二、选择填空 （）1．________不是实时系统的基本特征。A．安全性b．公平响应c．实时性D．高可靠 （）2．在用户程序中要将一个字符送到显示器上显示，应使用操作系统提供的________接口。 A．系统调用b．键盘命令c．原语D．子程序调用 （）3．并发进程失去封闭性特征，是指_______。 A．多个相互独立的进程以各自的速度向前推进b．并发进程的执行结果与速度无关c．并发进程执行时，在不同时刻发生的错误D．并发进程共享公共变量，其执行结果与速度有关

交巡警服务平台的设置与调度2011年数学建模国家一等奖

交巡警服务平台的设置与调度 摘要：伴随着社会的高速发展，为了能更好地贯彻实施警察肩负的刑事执法、治安管理、交通管理、服务群众这四大职能，造福百姓，需要在市区的一些交通要道和重要地理位置设置交巡警服务平台。而当每个交巡警服务平台只能和警力配备相同，警务资源有限时，如何根据城市的实际情况与要求合理的设置交巡警服务平台、分配个平台的管辖范围、调度警务资源是一直困扰警务部门的重要问题。这也是本论文需要解决的问题。 针对问题一，根据题目所给的A区交通网络图及相关数据，运用基于matlab的floyd算法，构造邻接矩阵，编程算出权矩阵，求出任意两点间的最短路径，按最大相应量的差额绝对值最小化原则从而确定每个交巡警服务平台的可控分配管辖范围。 由前一小问可以得到每个服务平台到各个节点的最短路，再由AutoCAD 准确计算出每段道路的路径长度，从而引入计算几何的相关理论，建立出巡警调度模型以及基于模糊数学的评价指标，设计出可行性最高的调度方案。 新增平台的个数以及设置，采取运筹学知识和lingo软件，分析影响辖区内各种案件发生率的因子，确定出合理的平台设置个数方案。 针对问题二，根据题目所给的整个城市交通网络图，在第一问的基础上考虑的范围更多。从应急点（题目中所说的路口节点）的具体情况出发。由于应急点周围的环境、经济状况、人口密度、案发率等不同，应急点对候选交巡警服务设施点的应急响应时间满意程度也不同。鉴于此，本文考虑了在规定服务设施数目的情况下，建立了应急选址的时间满意覆盖模型[8]，通过粒子群优化算法，目标使应急点总的满意程度最大。从而对全市六区现有的交巡警服务平台的合理性进行综合评价。 为了快速搜索嫌疑犯，在问题一的第二小问的基础上我们可以通过增加不确定因素、扩大搜索范围等建立深度优先搜索模型[]进行分析处理。 关键字：交巡警服务平台图论Dijkstra算法Floyd算法规划选址问题时间满意度覆盖问题粒子群优化法模糊数学

交巡警服务平台的设置与调度的优化模型

湖南工业大学 课程设计 资料袋 学院（系、部）2011~2012 学年第 2 学期 课程名称图论及其应用指导教师职称 学生姓名ake555 专业班级学号 题目交巡警服务平台的设置与调度的优化模型 成绩起止日期2013 年6月16 日～2013 年 6 月21 日 目录清单

课程设计任务书 2012—2013学年第2学期 学院专业班级 课程名称：图论及其应用 设计题目：交警服务平台和调度设计问题 完成期限：自2013 年 6 月16 日至2013 年 6 月21 日共 1 周

指导教师（签字）：年月日系（教研室）主任（签字）：年月日

图论及其应用课程设计说明书 2013年6 月21 日 目录

一、问题描述 (5) 二、模型假设 (6) 三、符号说明 (6) 四、模型建立与求解 (6) 五、模型评价 (15) 六、体会心得 (16) 七、参考文献 (16) 八、附件 (16) 交巡警服务平台的设置与调度的优化模型 一问题描述 随着人们社会经济的迅猛发展，人们生活的质量的提高，安全意识以深入人心，作为社会秩序的维护者警察对社会稳定起着巨大的作用

.警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。 试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：问题一：附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。要求为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。 问题二：对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，通过求解给出该区交巡警服务平台警力合理的调度方案。 问题三：根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，通过分析计算需要增加平台的具体个数和位置。 问题四：针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理的地方，给出解决方案。 问题五：如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。 二模型假设 1．出警时道路恒畅通（无交通事故、交通堵塞等发生），警车行驶正常；2．在整个路途中，转弯处不需要花费时间； 3．假设逃犯驾车逃跑的车速与警车车速相当 三符号说明

交巡警服务平台的原则和任务分析

针对全市（主城六区A ，B ，C ，D ，E ，F ）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。 考察是否合理主要从交巡警服务平台工作量及出警时间方面考虑。 一、定义工作量为G ，案发率为P ，人口数为K ，城区面积为D ，城区内交通要道总路程为S ，时间为t ，各城区平台数为Q 。 总工作量G 除了与 0G P s =?有关外，还与各城区的交通压力有关，交通 压力用城区人口数K 与城区总路程S 的比值来表示，即 2K G S = ，还要考虑人口 密度对交巡警工作量的影响，用城区总人口K 与城区面积D 与城区的平台数Q 的乘积的比值来表示，即 3K G D Q = ?，用层次分析法确定这三部分的系数1C 、2C 、 3C ，得出总工作量的公式为： 1123 K K G C G C C S D Q =++?

其中1G 是各城区交巡警服务平台工作总量与平台数的比值，即各城区交巡警平台的平均工作量。 针对 1G 、2G 、3G 我们分开来分析 （1 ）先分析 1G ，计算1G 我们可以应用问题一中设计好的编程，利用MATLAB 计算出这 六个城区平台的平均工作量，得出结果如下： 城区 A B C D E F 平均工作 量1G 34.468 30.012 62.318 34.123 43.712 52.316 1G 是工作量的一部分，从这里局部就可以看出不合理性的存在。 （2）分析 2G ， 2K G S ，我们称之为交通压力。 通过EXCEL 处理我们可以得出如下表格 城 区 A B C D E F 人口数K 60 21 49 73 76 53 城区 总路 1600.231 603.546 2412.908 604.675 1723.987 1654.762

《操作系统》试卷及答案

卷号：A 二O11-二O12 学年第 1 学期期末考试 操作系统试题 （09级计算机各专业用）闭卷 题号一二三四五六七八九十题分30 20 15 20 15 得分 第一部分基础部分 一、单项选择题（每小题2分，共30分） 1．批处理系统的主要缺点是。 A．CPU利用率低B．不能并发执行 C．缺少交互性D．以上都不是 2．进程的时间片结束后，将使进程状态从。 A．运行状态变为就绪状态B．运行状态变为等待状态 C．就绪状态变为运行状态D．等待状态变为就绪状态 3．判别计算机系统中是否有中断事件发生，通常应是在。 A．进程切换时B．执行完一条指令后 C．执行P操作后D．由用户态转入核心态时 4．在可变分区存储管理中，最优适应分配算法要求对空闲区表项按进 行排列。 A．地址从大到小B．地址从小到大 C．尺寸从大到小D．尺寸从小到大 5．对磁盘进行移臂调度的目的是为了缩短时间。 A．寻道B．延迟C．传送D．启动6．一种既有利于短小作业又兼顾到等待时间的作业调度算法是。A．先来先服务B．轮转C．最高响应比优先D．均衡调度 7．作业调度程序是从处于状态的作业中选取一个作业并把它装入主存。 A．输入B．后备C．执行D．完成 8．在单处理器的多进程系统中，进程什么时候占用处理器和能占用多长时间，取决于。 A．进程相应的程序段的长度B．进程总共需要运行时间多少 C．进程自身和进程调度策略D．进程完成什么功能 9．在多进程的并发系统中，肯定不会因竞争而产生死锁。 A．打印机B．磁带机C．磁盘D．CPU 10．一作业8:00到达系统，估计运行时间为1小时，若10:00开始执行该作业，其响应比是。 A．2 B．1 C．3 D．0.5 11．一个进程是。 A．由协处理器执行的一个程序B．一个独立的程序 C．一个独立的程序 + 数据集D．一个独立的程序 + 数据集 + PCB结构12．页式存储管理中的逻辑地址格式是地址。 A．一维B．二维C．三维D．以上说法均不正确 13．设有三个进程共享一个资源，如果每次只允许一个进程使用该资源，则用PV 操作管理时互斥信号量S的可能取值是。 A．1，0，-1，-2 B．2，0，-l，-2 C．1，0，-1 D．3，2，1，0 14．文件系统采用多级目录结构可以。 A．节省存储空间B．解决命名冲突 C．缩短文件传送时间D．减少系统开销 15．有关资源分配图中存在环路和死锁关系正确的说法是。 A．图中无环路则系统可能存在死锁B．图中有环路则系统肯定存在死锁C．图中有环路则系统可能存在死锁，也可能不存在死锁 D．以上说法都不对 二．判断题（每小题2分，共20分） 1．进程被创建后的初始状态为“就绪状态”。 2．P/V操作是在信号量上定义的两个操作，P操作意味着释放资源，V操作意味着申请资源。 3．吞吐量是指每单位时间内所完成的作业个数。 总分核分人

交警服务平台

2011高教社杯全国大学生数学建模竞赛题目（请先阅读“全国大学生数学建模竞赛论文格式规范”） B题交巡警服务平台的设置与调度 “有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。 试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题： （1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。 对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。 根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。 （2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。 如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后

2012-2013-1B《操作系统》试卷及答案

操作系统期末试题（B）卷 一、单项选择题(每小题2分，共30分) 1. 当CPU执行操作系统代码时,称CPU处于________。 A.执行态 B.目态 C.管态 D.就绪态 2. 操作系统是一种。 A．系统软件 B．系统硬件 C．应用软件 D．支援软件 3. 在UNIX操作系统中,把输入输出设备看作是________。 A.普通文件 B.目录文件 C.索引文件 D.特殊文件 4. 在一个可变式分区管理中，最坏适应分配算法宜将空闲区表中的空闲区按 _______的次序排列。 A. 地址递增 B. 地址递减 C. 大小递增 D. 大小递减 5. 在下列文件中,不便于文件增、删操作的是________。 A.索引文件 B.连续文件 C.Hash文件 D.串联文件 6. 在可变式分区存储管理中，某作业完成后要收回其主存空间，该空间可能与相邻空闲区合并，修改空闲区表，使空闲区数不变且空闲区起始地址不变的情况是。 A. 无上邻空闲区无下邻空闲区 B. 有上邻空闲区无下邻空闲区 C. 有下邻空闲区无上邻空闲区 D. 有上邻空闲区有下邻空闲区 7. 进程从运行状态到阻塞状态可能是由于________。 A.进程调度程序的调度 B.现运行进程的时间片用完 C.现运行进程执行了P操作 D.现运行进程执行了V操作 8. 银行家算法在解决死锁问题中是用于的。A.预防死锁 B.避免死锁 C.检测死锁 D.解除死锁 9. 在段页式存储系统中，一个作业对应。 A．多个段表 B. 一个段表，一个页表 C. 一个段表，多个页表 D. 多个段表，多个页表 10. 一作业9:00到达系统,估计运行时间为1小时。若10:00开始执 行该作业,其响应比是。 A. 2 B. 1 C. 3 D. 0.5 11. 资源的静态分配算法在解决死锁问题中是用于。 A. 预防死锁 B. 避免死锁 C. 检测死锁 D. 解除死锁 12. 在一个单处理机系统中，若有4个用户进程，在非管态的某一时刻，处于就绪状态的用户进程最多有个。 A. 1 B. 2 C. 3 D. 4 13. 若信号S的初值为2,当前值为-3,则表示有_________等待进程。 A.0个 B.1个 C.2个 D.3个 14. 采用随机存取法来读写盘上的物理记录时，效率最高的是。 A. 连续结构文件 B. 索引结构文件 C. 串连结构文件 D. 其他结构文件 15. 既考虑作业等待时间，又考虑作业执行时间的调度算法是。A．响应比高者优先B．短作业优先 C．优先级调度D．先来先服务 二、判断题(每小题2分，共20分) 1.可变分区法可以比较有效的消除外部碎片，但不能消除内部碎 片。（）

交巡警服务平台的设置与调度

交巡警服务平台的设置与调度 【摘要】警察是现代社会中不可或缺的社会角色，肩负着执法、治安与服务群众等重要职能。为了更好地履行这些职能，交巡警服务平台要合理地分布在城市的各个地区，这样不仅可以及时响应出警到达案发现场，在遇到突发事件时也可以通过联合调度高效地行动起来。 该论文就交巡警服务平台的设置与调度等实际问题，针对所提出的5个问题分别给出具体的解决方案并给出结果： 对于问题1要给A区的每个服务平台分配管辖范围，即分配其管辖的节点。我们根据“就近原则”来分配管辖的节点，保证尽量在3分钟内有交巡警到达事发地。对此，借助MATLAB编程采用“Floyd最短路径算法”确定距离每个节点最近的服务平台，从而得到每个服务平台的管辖范围。 对于问题2的合理的调度方案的确定，我们在“快速封锁”的原则下，通过调度警力使得A区在最短时间内被全封锁。20个服务平台对13个路口进行全封锁，而且每个服务平台最多封锁一个路口，这可划归于一个0-1规划问题，因此可用LINGO编程求得各种可选调度方案中13个路口封锁时间的最大值取值最小时的调度情况。 对于问题3增加平台的个数与位置的确定，我们的目的是使各个服务平台的工作量达到均衡状态而且出警时间过长的问题得到有效解决。为此，我们在出警时间过长的节点或附近尝试增加新的服务平台，然后计算方差来衡量工作量的均衡程度，比较增加2至5个服务平台时的方差，以此确定方差最小的情况为最后的可选方案。这个过程仍然借助MATLAB程序来完成，采用“模拟退火法”来确定工作量达到均衡时新增平台的个数与位置。 对于问题4对全市服务平台设置方案的合理性的讨论，我们借助问题1和问题3的解决方法来确定各区服务平台的管辖范围与新增服务平台的个数与位置。同时对模型进行优化，考虑到有些服务平台的工作量过少的情况，撤消一些现有的服务平台。借助MATLAB程序，可以给出一个较合理的解决方案，即给出各个分区的服务平台的调整方案。 对于问题5围堵方案的确定，可将全市的交通网看作一张图，各个节点看作顶点。同时根据必要的假设：嫌疑犯一直朝远离事发点P点的方向逃跑，而且不走回路。这时，将P点看作树根，嫌疑犯的可能的逃跑路线便成为一个树，有可能经过的节点便是枝和叶。这样，就能根据图论的知识，通过MATLAB与LINGO程序，利用“追捕算法”来对各个分支道路进行有序的封锁排查，进而求得最佳的围堵方案。 关键词：Floyd最短路径算法、0-1规划、模拟退火法、平台的设置与调度、图论、追捕

B《操作系统》试卷及答案

操作系统期末试题(B)卷 一、单项选择题(每小题2分,共30分) 1、当CPU执行操作系统代码时,称CPU处于________。 A、执行态 B、目态 C、管态 D、就绪态 2、操作系统就是一种。 A.系统软件 B.系统硬件 C.应用软件 D.支援软件 3、在UNIX操作系统中,把输入输出设备瞧作就是________。 A、普通文件 B、目录文件 C、索引文件 D、特殊文件 4、在一个可变式分区管理中,最坏适应分配算法宜将空闲区表中得空闲区按 _______得次序排列。 A、地址递增 B、地址递减 C、大小递增 D、大小递减 5、在下列文件中,不便于文件增、删操作得就是________。 A、索引文件 B、连续文件 C、Hash文件 D、串联文件 6、在可变式分区存储管理中,某作业完成后要收回其主存空间,该空间可能与相邻空闲区合并,修改空闲区表,使空闲区数不变且空闲区起始地址不变得情况就是。 A、无上邻空闲区无下邻空闲区 B、有上邻空闲区无下邻空闲区 C、有下邻空闲区无上邻空闲区 D、有上邻空闲区有下邻空闲区 7、进程从运行状态到阻塞状态可能就是由于________。 A、进程调度程序得调度 B、现运行进程得时间片用完 C、现运行进程执行了P操作 D、现运行进程执行了V操作 8、银行家算法在解决死锁问题中就是用于得。A、预防死锁B、避免死锁C、检测死锁D、解除死锁 9、在段页式存储系统中,一个作业对应。 A.多个段表 B、一个段表,一个页表 C、一个段表,多个页表 D、多个段表,多个页表 10、一作业9:00到达系统,估计运行时间为1小时。若10:00开始执行该作业,其响应比就是。 A、2 B、1 C、3 D、0、5 11、资源得静态分配算法在解决死锁问题中就是用于。 A、预防死锁 B、避免死锁 C、检测死锁 D、解除死锁 12、在一个单处理机系统中,若有4个用户进程,在非管态得某一时刻,处于就绪状态得用户进程最多有个。 A、1 B、2 C、3 D、4 13、若信号S得初值为2,当前值为-3,则表示有_________等待进程。 A、0个 B、1个 C、2个 D、3个 14、采用随机存取法来读写盘上得物理记录时,效率最高得就是。 A、连续结构文件 B、索引结构文件 C、串连结构文件 D、其她结构文件 15、既考虑作业等待时间,又考虑作业执行时间得调度算法就是。 A.响应比高者优先 B.短作业优先 C.优先级调度 D.先来先服务