交巡警服务平台的设置与调度 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给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。

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

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

二、模型假设

（1）每个交巡警服务平台的职能和警力配备基本相同；

（2）警车的行驶速度恒定，不考虑实际交通状况的影响；

（3）交巡警服务平台接到报警后能立即出警，中间没有延误；

（4）每个节点只能被一个服务平台管辖；

（5）一个平台的警力最多封锁一个路口。

三、符号说明

四、问题分析

交巡警服务平台位置的选取以及划分交巡警服务平台的管辖范围是一件非常重要的事情。由于种种原因，现在交巡警服务平台的选址及管辖区域划分大多根据经验进行。缺乏科学系统的位置选取与管辖区划分，造成了警务资源浪费、突发事件处理不及时等多种问题。另外，警务资源是有限的，设置交巡警服务平台也要耗费大量的资源。所以如何科学的规划管辖区，合理的设立新的交巡警服务平台具有重大的意义。本文意在根据现有的城区道路图与交巡警服务平台位置，根据到达突发事件地点使用时间最少原则进行交巡警服务平台管辖范围划分，根据使用资金尽量少及各交巡警服务平台的工作量尽量一致的原则设立新的交巡警服务平台。

在问题一中有三个子问题需要解决。

（1）要对20个交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。即计算各交巡警服务平台与各个地点的距离。将巡警在3分钟内到达事发地转化为交巡警服务平台距离事发地距离不超过3km。这是典型的最短路模型。对于这个问题，我们采用Dijkstra算法。

（2）当重大突发事件发生后，要对中心城区A的20个交巡警服务平台的警力资源进行调度，对进出该区的13条交通要道实现快速全封锁，其关键在于合理调度警务资源使得封锁全部要道所需的总时间达到最小，也就是使得出警时间最长的服务平台所需的时间尽可能的小。实际中一个平台的警力最多封锁

一个路口，给出该区交巡警服务平台警力合理的调度方案，我们采用0-1模型进行求解，给出该区交巡警服务平台警力合理的调度方案。

（3）针对现有的中心城区A 的20个交巡警服务平台进行分析后，需要新增加2~5个服务平台以解决工作量不平衡和部分路口节点出警时间过长的问题。这属于交巡警服务平台选址问题。一方面考虑采用集合覆盖模型，目的是在满足所有节点3分钟内都有警方到达的条件下，使新增设的服务平台数目尽可能得小，从而降低了建设成本。另一方面也要考虑新增设服务平台后，能够解决服务平台工作量不平衡的问题，所以把尽可能均衡各个服务平台工作量作为第二个目标 。因此考虑需要建立一个两目标的0-1整数规划模型。

五、模型的建立和求解

问题1.1——A 区交巡警服务平台管辖范围的分配

为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h ）到达事发地。即计算各交巡警服务平台与各个地点的距离。将巡警在3分钟内到达事发地转化为交巡警服务平台距离事发地距离不超过3km 。

我们建立最短路模型：

3min t ≤，s v t =?，60/v km h =

即

3000s m ≤

求出离每个地点距离最短的交巡警服务平台，将这个地点分配给距离最短的交巡警平台管辖。

如何求每个地点之间的距离，我们运用了MATLAB 软件中的最短路函数——“graphallshortestpaths （）”函数。将题目附件中各节点坐标转化为矩阵，进而建立稀疏矩阵，然后利用最短路函数提取出符合3分钟路程要求的矩阵，最后进行整理，即可得所求。

模型的求解：

先用Dijkstra 算法求解出各交巡警服务平台到各个路口节点的最短距离，利用MATLAB 软件进行运算（运算程序见附件一），代入数据,求得管辖范围如下：

（原始表格见附件二）

把出警时间不超过3分钟，转化为服务平台距离所管辖的路口距离不超过3千米。由此检验得六个路口（ 28，29，38，39，61，92）不满足出警时间要求。

到达最近的交巡警服务平台的时间超过3分钟的6个路口如下表：

问题1.2——A 区交巡警服务平台警力调度方案

对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进

出该区的13条交通要道实现快速全封锁。要求得该如何分配警力资源封锁路口我们使用0-1整数规划模型。

设ij x 表示第i 个交巡警服务平台调度到第j 个交通路口的情况，即：

???=个交通路口

个平台调度到第第，个交通路口个平台没有调度到第第j i 1j i ,0ij x

其中

1,2,,20i =1,2,,92j =

根据对问题的分析，要实现对要道的快速全封锁，所以模型的目标是使封锁所有要道的总时间最短，其关键在于控制封锁要道所需时间最长的服务平台的出警时间，使之达到最小值。

设?表示封锁要道所需时间最长的服务平台的出警时间

A ij 表示20个交警平台到13个交通路口的距离 封锁要道所需时间最长的服务平台的出警时间最短：

min ?； 在13个交通路口上，每个路口都必须有一个交巡警：

∑===20

1

13....1j 1i ij

x

；

每个交巡警服务平台至多只能去一个路口：

∑==≤13

1

20....11j ij

i x

；

每个交巡警到达路口的距离均小于最后一个到达路口的交警平台与该路口的距离：

13....120....1==≤*j i A x ij ij ?

。

建立模型如下：

目标函数： min ?;

.st ：????

?????==≤*=≤==∑∑==13

....120. (120)

....1113....1j 1

13

1

20

1j i A x i x x ij ij j ij i ij ?

模型的求解：

我们利用lingo 软件进行目标函数的求解。 主程序如下：

（具体程序见附件三）

由程序结果可得如下表格： 封锁方案表格

下图是所求得各巡逻点到个路口的时间表：

取其中的最大值为8.01546.故控制封锁要道所需时间最短约为8.01分钟。

问题1.3——拟增A 区交巡警服务平台

对于拟增A 区交巡警服务平台，首先分析现有的交巡警服务平台的分布，发现存在交巡警服务平台工作量不均衡和部分交通路口出警时间过长的问题。这就要求新增加几个服务平台后，使得各个交巡警服务平台的工作量尽可能相同以及使各个交通路口出警时间都被控制在3分钟内。

新建服务平台需要成本，所以需要合理确定服务平台的选址，使需要建立的服务平台的数目最小。由此，我们参考集合覆盖模型（在一定的区域内，设置最小数量的设施来覆盖其中所有的点），建立了一个两目标0-1整数规划模

型。（见附件四）

目标函数： 9292

11

min j ij ij i j c d x ===∑∑

约束条件：

???=个交通路口

个平台调度到第第，个交通路口个平台没有调度到第第j i 1j i ,0ij x

(i=1,2,...,92 j =1,2, (92)

且

1jj

x

= 92

1

2225jj j x =≤≤∑

每个交通路口都有一个平台管辖：

92

1

1ij

i x

==∑

所有平台到其所管辖的交通路口最短距离中的最大值不超过距离偏差a ,即各个交通路口出警时间都被控制在3分钟内： max(

*)ij

ij

d x a

≤ (i=1,2,...,92 j=1,2, (92)

模型的求解：

第三个子问题所建立的是双目标的0-1整数规划模型，第一目标为增加的服务平台最少，第二目标为各个服务平台每天的服务强度方差最小。为了求解模型，先只考虑第一目标，然后再在第一目标最优的情况下给出第二目标最优的解。

在lingo 软件中运行程序，从24至30范围内取出若干个偏差限与所对应的目标函数值。

由结果，增加5个平台，标号与坐标分别为： 29（246,337）;39（371,333）;48（315,374）;51（348.5,380.5）; 88（444.5,383）

由于该模型发案率的均衡性不是很好，增加的5个平台不一定是划分A 区的最优解。因此要进行进一步的分析处理。将25个平台代入1.1的模型中，与原A 区的划分结果相比较（以d ij >30的节点个数的多少为标准），逐个去掉平台个数，再重复以上操作，最终得出结果。

使用和求A 区偏差限相同的方法分别确定增加5个平台、4个平台、3个平台时的偏差限，即最好均衡性分别为 1.9、1.85、1.85，并设计表格进行对

比，表格如下：

权衡均衡性、最优解及增加点个数所需花费的资源，增加四个点数是最节省资源且效果最好的。故：

交巡警服务平台增加四个，它们分别为：

A29 A39 A48 A88

六、模型的评价

6.1模型的优点：

（1）对于问题一的第一个子问题：题目规定以最短时间为目标，可转化为最短距离不超过3km。可是对于有一些节点，无论怎样安排都不能达到警方到达事故现场为3分钟之内。我们对于这些节点单独处理，并根据已知条件计算出这几个节点应该属于哪个交巡警服务平台。

（2）对于问题一的第三个子问题：该问题要求确定增加2-5个交巡警服务平台的方案。一方面，根据限制条件，巡警到达其管辖节点应在3分钟之内。另一方面，应平均合理安排各个交巡警服务平台的工作量，不至于出现某个服务平台工作量过大而某个平台工作量过小的情况。

6.2模型的缺点：

对于问题一的第一个子问题，建立的模型目标单一，并没有考虑到各个服务平台交巡警工作梁的不均衡性。在分配结果中可以看到，部分交巡警的工作量很小而部分交巡警的工作量很大。这显然是不合理的。事实上，可以建立一个多目标规划问题，以交巡警到达事故现场和工作量的方差为目标，使得分配管辖范围的方案更加合理。

七、模型的推广

本文所提供的模型可以推广到任何一个市区甚至更广范围内的交巡警服务平台的设置与调度问题的解决中。也可以广泛应用于社区卫生室、公共卫生间、消防救火中心等社会服务部门的选址问题。在实际运用中有很高的实用性及通用性。

八、参考文献

[1]殷代君，广义最大覆盖模型在应急设施选址中的应用研究，中外企业家，

2010年第3期：169-170,2010。

[2]卓金武，MATLAB在数学建模中的应用，北京：北京航空航天大学出版社，2011。

[3]韩中庚，数学建模方法及其应用，北京：高等教育出版社，2009。

[4]谢金星，薛毅，优化建模与lingo软件，北京：清华大学出版社，2005。

附件一：

function [list,AdjMatrix,distance] = getList()

edge = csvread('edge.csv');

range = size(edge);

%删除非A区的边

for i =range:-1:1

if (edge(i,1)>92)||(edge(i,2)>92)

edge(i,:) = [];

end

end

node = csvread('node.csv');

S = edge(:,1);%起点向量

E = edge(:,2);%终点向量

range = size(S);

W = zeros(range,1);%权向量

for i=1:1:range

a = [node(S(i,1),1),node(S(i,1),2)];

b = [node(E(i,1),1),node(E(i,1),2)];

distance = norm(a-b);

W(i,1) = distance;

end

%建立稀疏矩阵

AdjMatrix = sparse([S;E],[E;S],[W;W],92,92);

%求最短路径矩阵

distance = graphallshortestpaths(AdjMatrix,'directed',false); %提取出符合3分钟路程要求的矩阵

A = distance(1:20,21:92);

[rangeI,rangeJ] = size(A);

for i=1:1:rangeI

for j=1:1:rangeJ

if A(i,j)>30

A(i,j) = NaN;

end

end

end

%整理

list = zeros(72,1);

for i=1:1:72

Max = 0;

R = NaN;

for j=1:1:20

if A(j,i)>Max

Max = A(j,i);

R = j;

end

end

list(i,1) = R;

end

T = linspace(1,20,20)';

list = [T;list];

end

附件三：

title 0--1;

sets:

p/1..13/:a;

l/1..20/:b;

link(l,p):c,d;

endsets

data:

d=222.36,160.28,92.87,192.93,210.96,225.02,228.93,190.01,195.16,120.8 3,58.81,118.50,48.85,

204.64,141.30,73.88,173.95,191.97,206.03,211.21,172.29,177.44,103.11, 39.82,103.10,60.35,

183.52,127.67,60.26,160.32,178.35,192.41,190.09,151.17,156.32,82.00,6 0.94,81.98,43.93,

219.97,150.09,82.67,182.73,200.76,214.82,226.54,162.27,155.35,81.03,4 8.61,73.96,3.50,

176.28,129.70,62.28,162.35,177.50,191.55,182.85,113.07,106.15,31.83,9

4.21,24.76,52.55,

176.59,130.00,62.59,162.65,177.80,191.86,183.16,113.37,106.46,32.14,9 4.52,25.06,53.37,

149.15,109.01,41.60,141.66,150.36,164.42,155.72,85.70,80.15,5.83,73.5 3,12.90,79.92,

140.93,94.34,26.92,126.99,142.14,156.19,147.50,102.28,104.93,30.61,58 .85,30.99,86.77,

130.11,82.74,15.33,115.39,131.32,145.38,136.68,97.76,107.24,34.92,47. 26,41.99,93.37,

75.87,127.76,69.57,95.11,77.08,91.13,82.44,141.95,151.44,79.11,101.50 ,86.19,147.61,

37.91,83.37,113.95,50.72,32.70,46.75,38.05,186.33,195.82,123.50,145.8 8,130.57,191.99,

0.00,119.50,145.43,86.85,68.83,64.77,35.92,217.81,227.30,154.98,177.3 6,162.05,223.47,

59.77,59.73,127.15,27.08,9.06,5.00,23.85,228.08,237.57,165.25,161.21, 172.32,213.32,

119.50,0.00,67.42,32.65,50.68,64.73,83.59,180.50,189.17,114.84,101.48 ,121.91,153.59,

170.30,132.98,65.56,165.63,171.51,185.56,176.87,47.52,57.01,44.01,97. 50,51.09,118.10,

145.43,67.42,0.00,100.07,118.09,132.15,151.00,113.08,121.75,47.43,34. 06,54.50,86.17,

218.92,149.03,81.62,181.68,199.71,213.77,225.49,186.57,195.24,120.92, 47.56,127.99,78.21,

242.47,185.14,117.73,217.79,235.82,249.88,249.04,210.12,215.27,140.94 ,83.67,136.99,67.34,

225.47,169.61,102.20,202.26,220.29,234.35,232.04,193.12,198.26,123.94 ,76.39,119.99,50.34,

269.46,212.13,144.71,244.78,262.81,276.86,276.03,230.11,223.19,148.87 ,110.66,141.80,64.49 ;

enddata

min=@max(link(i,j):c(i,j)*d(i,j));

@for (link(i,j):@bin(c(i,j)));

@for(p(j): @sum(l(i):c(i,j))=1);

@for(l(j): @sum(p(i):c(j,i))<=1);

附件四：

model:

sets:

type/1..20/;

a/1..92/:c;

benefit(a,a):d,x;

endsets

min=@sum(benefit(i,j):d(i,j)*x(i,j)*c(i));

@for(benefit:@bin(x));

@sum(a(i):x(i,i))>=22;

@sum(a(i):x(i,i))<=25;

@for(a(i):

@sum(a(j):x(i,j))=1);

@for(a(i):

@for(a(j):(x(i,j)*d(i,j))<29));

@for(a(j):@sum(a(i):x(i,j))=@if(x(j,j)#eq#0,0,@sum(a(i):x(i,j)))); @for(type(i):x(i,i)=1);

data:

d=@ole('G:/short.xls',data1);

c=@ole('G:/short.xls',data2);

enddata

end

data1为92*92的两两节点的最短距离，

data2为92个节点的发案率。

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.先来先服务