高教社杯全国大学生数学建模竞赛B题参考答案Word文档格式.docx
《高教社杯全国大学生数学建模竞赛B题参考答案Word文档格式.docx》由会员分享，可在线阅读，更多相关《高教社杯全国大学生数学建模竞赛B题参考答案Word文档格式.docx（38页珍藏版）》请在冰点文库上搜索。
平台的坐标
第
条道路，起点到终点一步可达的距离
各个节点的最短路距离
分配矩阵
中间过渡矩阵
出口到平台的距离
案发率距离
增加节点矩阵
计数
每行中除了0以外的最小值
每行中除了0和mm的最小值
三、模型建立及求解
、为了模型的建立与分析，先模拟出道路图
图1A区交通图
程序：
lp1003
图2全市交通图
shitu
、问题1的模型建立及求解：
此问要求我们利用数据及附图，将各路口节点划分给最适合的服务平台，并要求各服务台管辖的范围内有突发事件发生时，尽量能在3分钟内有交巡警到达事发地（此时交巡警的行驶距离为3km），换算到比例图上，也就是30mm。
本题，不考虑其他因素，只注重唯一因素——距离。
所以，我们第一步用floyd算法求出各个节点之间的最短距离D。
、根据题中所给的各个节点的坐标，用matlab计算出任意两点之间的距离，得到92*92的邻接距离矩阵：
其中
分两种情况：
当第i个节点与第j个节点相邻时，
为两个节点的相邻距离。
不相邻时，
为一个充分大的数。
②、运用Floyd算法，求出任意92个节点到任意92个节点的最短距离，得到最短距离矩阵，根据问题需要，我们截取所得矩阵前20行，即任意20个服务平台间到任意72个节点（没有建立平台的节点）的最短距离矩阵
：
因为服务平台的编号为1到20，所以取D的前二十行，后七十二列为观察对象。
在观察对象中，取出每列的最小值，计入到原本为设为全0的
的矩阵A的相应的位置。
对于每一列而言，每列的最小值是最有可能小于3分钟的，如果最小值都不满足这个条件，那么对于这列对应的节点而言，就不存在三分钟可以到达的平台。
pingtai
由此，最后每个节点都会归属于某个服务平台，用matlab编程得出结果并绘制了管辖区域图如表1
服务平台编号
管辖范围（节点编号）
管辖容量
1
1、67、68、69、71、73、74、75、76、78
10
2
2、39、40、43、44、70、72
7
3
3、54、55、65、66
5
4
4、57、60、62、63、64
6
5、49、50、51、52、53、56、58、59
9
6、47
7、30、32、48、61
8
8、33、46
9、31、34、35、45
10、26
11
11、27
12
12、25
13
13、22、23、24
14
14、21
15
15、28、29
16
16、36、37、38
17
17、41、42
18
18、80、81、82、83
19
19、77、79
20
20、84、85、86、87、88、89、90、91、92
表1服务平台管辖范围
、调度方案的求解
本题，我们使用运筹学中的指派方法来解决。
如果发生重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全面封锁。
在全面封锁时，既需要使用最短的时间，还必须保证一个平台的警力只能封锁一个路口，这样就必然会多出7个平台。
先根据给出的数据，设立出指派问题的条件矩阵C。
C为
，其中前十三列是A区13个出口到二十个平台的最短路距离，剩余的七列用零补齐。
得到C之后，使用linprog算法，就得到我们需要的调度方案。
zhipai
根据前一问的解答我们可以得出任意服务平台
到任意出口
的最短距离
，引入0-1变量
据此我们建立关于服务平台调度的目标函数Z：
约束条件：
第一个约束表示要求每个服务台只能去1个或0个出口。
第二个约束表示每个出入路口有且仅有一个服务平台的警力支持。
综上，我们利用linprog编程得出了最优调度方案（程序见附件），结果见表2：
平台编号
出口编号
38
62
48
30
29
22
24
23
21
28
距离:
mm
39
104
82
77
32
47
表2出口平台调度方案
通过分析这些线路，我们知道线路最长的组合为8号平台到达29号节点，它所花的时间即为封锁路口的最终时间，且这个时间约为10分钟。
、平台增加个数及位置的求解
本问要求在第1小问的前提下，根据服务平台的工作量不均衡及出警时间的不合理来增加服务平台的具体个数及位置，使整个交巡警服务平台系统趋于合理化。
在第一小问中，我们选择D每一列的最小值，把该节点划分给离他最近的平台管辖。
但这样的话，一方面会导致一部分的平台管辖的节点过多，其辖区内部的总案发率过高，而现实中，各平台辖区案发率应该相差不大。
另一方面，少量节点到每个平台的最短距离都大于30mm，即到任何平台的时间都超过3min，所以，我们就需要增设一些平台。
对于平台添加的原则是添加平台后使得所有节点都有平台可以在三分钟内到达。
首先，我们以距离出发，选择D前二十行中，其最小值大于30的列，把这些节点之间的距离从D中提取出去，组成一个方阵。
在这个方阵中，选择两节点之间距离小于30mm，小于30说明此两点可以在3min内到达彼此。
故可以任意删去一列，删去先出现的列。
现在得到需要添加的最多平台数就是上面剩下的那些列对应的节点n。
提取这些节点D中所在行，加上之前的20行，组成一个新的最短距离矩阵B。
其中A,B均为20+n*92的矩阵，A是全0阵，B是D中的一部分，进行五次迭代，出现我们需要的平台及对应的辖区。
迭代的规则是：
在B中选取每列的最小值，赋给A中相应的行列位置。
找到A中不为0的位置对应的案发率，把每个位置的距离数字乘以各自的案发率，并除去速度10，平台自身案发率*加上。
所得数字为每一个平台的判断数。
逐行判断，如果某行的判断上数大于所有节点案发率平均数*2的话，就把该行中的最大数字在B中置为0。
重复上述三步，五次。
图3迭代前综合指标曲线分布与直方图
2、43、44、70、72
5、49、50、51、52、53、56、59
6、58
7、30、32、47、48
9、34、35、45
15、31
16、36、37
17、41、42、92
18、80、81、82、83、91
20、84、85、86、87、88、89、90
29、28
2
39、38、40
61
表3调整后服务平台管辖范围
lp1015,zengjia
、问题2的模型建立及求解：
、全市交巡警服务平台合理性评价及方案设定
1、首先需要强调的是：
各个区的平台是不能跨区的
各个平台的辖区是不能重合的
满足这两点后，设定全市交警服务平台合理性评价：
警情主导警务原则：
根据管区道路交通流量、拥堵状况、治安复杂情况、发案量高低，科学确定平台管控区域；
快速处警原则：
城区接警后确保快速到达现场
方便与安全原则：
按照醒目、规范，方便群众和确保安全的原则，科学设置平台。
平台设置在遵循上述三大原则的基础上，应当结合辖区地域特征、人口分布、交通状况、治安状况和未来城市发展规划等实际情况，在充分考虑现有警力和财力并确保安全的条件下，科学确定平台的数量和具体位置。
在评价合理性的时候，我们引入了最大覆盖率：
被平台三分钟覆盖的节点数在区总节点数中占的比重。
所以对该市各个区分别进行Floyd算法，得到各自的最短路矩阵。
在平台所在的行中进行每列的最小值选择。
最小值小于30mm，就是被覆盖。
用这种方法分别得到六个区的最大覆盖率，即：
区域
A
B
C
D
E
F
最大覆盖率
表4区域覆盖率
fugai
由表中覆盖率可以看出，A区，B区的平台设置较为合理，其余几个区的平台设置较为不合理其中E区最差。
对覆盖率较差的区，可以进行平台设置的调整，调整的方案有三种：
不变动原有平台的个数与位置，添加若干个新的平台。
不变动原有平台的个数，改变平台的位置。
改变平台的个数，也改变平台的位置，以合理的标准去设置合适的平台
2、调整方案：
在此我们选取E区，采取方案
加以调整。
调整的具体实施：
在E区的最短距离矩阵中取出每行的最小值和次小值，并取出最多的十五个，对应的十五个节点就是新的调整以后的平台。
运行程序后得到新的平台设置为：
405、408、412、423、429、435、436、444、455、457、461、462、467、472、474
这十五个平台覆盖了75个节点，调整后E区的覆盖率为：
，比旧的平台设置要更为合理。
LP1017
、最佳围堵方案的确定：
在该题目中，首先需要有两点假设：
嫌疑人驾车逃逸速度和警察追堵速度一直，均为60km/h
嫌疑人逃逸时不走重复路段
此时调用的平台是没有改动之前原市区图中设立的平台点，警方在案发后3分钟才接到报警，假如警察用了
分钟追堵住嫌疑人，那么嫌疑犯逃跑时间是
分钟。
能把嫌疑人追堵住，就是在他还没到，但可以到的所有节点都已经被警察提前到了。
也就是说，嫌疑犯逃跑时间是
分钟逃到的节点，可以被距离他最近的平台在
分钟以内到达，这样，嫌疑人就是
分钟中成功被追堵住。
我们先对全市进行floyd，算出最短距，并提取出32行的那行数据，赋给K。
然后
从1开始，直到我们认为足够长的时间，定为6分钟，每次增加分钟不断迭代。
每次都找到嫌疑人在
分钟，和
分钟之间可以到达的节点，然后检测这些节点到区内最近平台的时间是否在
分钟，若是，则成功追堵；
如不是，则继续迭代，知道出现第一个满足。
p
四、模型的评价
模型优点
1、对题目所给数据大部分都进行了合理的应用和处理，对于实际问题理解的较为到位。
2、模型建立的思路简单清晰，算法较为灵活、执行效率教高。
3、模型能应用于其他种类的应急设施设置，整个模型有很好的通用性。
模型缺点
1、整个模型我们都化为了一个点的模型，如案发地点我们假定都在节点上，这在现实中是不可能的，可以进一步将点离散化，更为密集。
2、对模型的建立与求解，我们坚持的核心因素是三分钟到达节点，标准比较单一。
3、模型中我们没有考虑人口密度的问题，在实际中这是一个很重要的参考因素。
参考文献
[1]姜启元，《数学模型》第四版，北京：
高等教育出版社，2011年
[2]王沫然，《MATLAB与科学计算》，北京：
电子工业出版社，2003年
[3]胡运权《运筹学》，北京，清华大学出版社，第三版，2009年
fork=1:
1:
928
n1=daolu（k,1）;
n2=daolu（k,2）;
ifn1<
=92
ifn2<
a=jiedian（n1,2）;
b=jiedian（n1,3）;
c=jiedian（n2,2）;
d=jiedian（n2,3）;
plot（[ac],[bd]）;
holdon
end
x1=jiedian（1:
20,2）;
y1=jiedian（1:
20,3）;
plot（x1,y1,'
ro'
）;
forn=1:
92
x=jiedian（n,2）;
y=jiedian（n,3）;
plot（x,y,'
.'
form=1:
t=churu（m,2）;
a=jiedian（t,2）;
b=jiedian（t,3）;
plot（a,b,'
r*'
n1=daolu2（k,1）;
n2=daolu2（k,2）;
=92&
n2<
a=jiedian2（n1,2）;
b=jiedian2（n1,3）;
c=jiedian2（n2,2）;
d=jiedian2（n2,3）;
plot（[ac],[bd],'
g'
'
linewidth'
2）;
else
=165&
n1>
92&
n2>
y'
=319&
166&
166
=371&
320&
320
k'
=474&
372&
372
m'
=582&
475&
475
c'
r'
x1=jiedian2（1:
y1=jiedian2（1:
x1=jiedian2（93:
100,2）;
y1=jiedian2（93:
100,3）;
x1=jiedian2（166:
182,2）;
y1=jiedian2（166:
182,3）;
x1=jiedian2（320:
328,2）;
y1=jiedian2（320:
328,3）;
x1=jiedian2（372:
386,2）;
y1=jiedian2（372:
386,3）;
x1=jiedian2（475:
485,2）;
y1=jiedian2（475:
485,3）;
582
x=jiedian2（n,2）;
y=jiedian2（n,3）;
t=churu（m,1）;
a=jiedian2（t,2）;
b=jiedian2（t,3）;
a=jiedian2（32,2）;
b=jiedian2（32,3）;
k^'
）
zuiduanju
functionD=zuiduanju（）
a=jiedian;
b=daolu;
count=1;
n=length（a（:
1））;
fori=1:
length（b（:
1））
ifb（i,1）<
&
b（i,2）<
c（count,:
）=b（i,:
count=count+1;
length（c（:
1））d（i）=sqrt（（a（c（i,1）,2）-a（c（i,2）,2））^2+（a（c（i,1）,3）-a（c（i,2）,3））^2）;
%A区路口两节点的距离
c=sort（c,2）;
aa=zeros（n）;
aa（c（i,1）,c（i,2））=d（i）;
t=aa+aa'
;
M=max（max（t））*n^2;
%M为充分大的正实数
t=t+（（t==0）-eye（n））*M;
%Floyd算法求最小矩阵
path=zeros（n）;
n
forj=1:
ift（i,j）>
t（i,k）+t（k,j）
t（i,j）=t（i,k）+t（k,j）;
path（i,j）=k;
length（t（:
=M
t（i,j）=0;
D=t;
functionA=pingtai（）
D=zuiduanju（）;
A=zeros（20,72）;
f=jiedian（:
4）;
fork=21:
ifD（i,k）==min（D（1:
20,k））
A（i,k-20）=D（i,k）;
ifA（k,:
）==0
fori=21:
ifD（k,i）==min（D（k,21:
92））
A（1:
20,i-20）=0;
A（k,i-20）=D（k,i）;
co=0;
q=zeros（2,20）;
fprintf（'
到第%i平台时间最近的节点有：
\n'
k）;
q（1,k）=k;
q（2,k）=f（k）*;
72
i
升级会员 