毕业设计地面搜索问题数学建模优秀论文.doc

地面搜索问题

摘 要
本文提出了救灾中，如何对指定的区域进行搜索的问题，根据题目中给出的条件，通过分析建立模型。
问题1是在有20个搜索人员的情况下,对指定的地点进行搜寻,要求在最短的时间内,巡查完指定的目标。
我们根据队员与组长之间相隔的距离是否在1000m以内建立解决这一问题的两个模型，在每一个队员与组长之间的距离都应该保持在1000m以内的约束条件下，建立模型1。在模型1中，把20名搜索队员排成一列，每两人之间相隔的距离为40m，因此该搜索队每次搜寻的半径为400m。横向搜索9次正好搜寻完整个目标区域，通过计算得出搜索完整个区域所要的总时间>48，要想在48 内完成整个搜索任务，需要增加3人。
假设队员与组长之间的距离不限定在1000m以内，但每一个队员至少与其他任意一个队员相隔距离不超过1000m，根据这一条件建立模型2。在模型2中，我们将11200×7200的目标区域分为11200×360的20个小区域，每一个队员横向搜索9次正好搜寻完各自分配到的区域，不难看出，离中心最远的队员搜索完指定的区域所需的时间最长，也就是说该队员搜索所需的时间即为完成整个搜索任务的总时间>48 ，为了能够在48 内完成整个目标区域的搜索任务，需要增加3人。
问题2中，我们把50人的搜索队分为甲、乙、丙3组，每一组的人数分别为10、20、20。通过分析可知，只有这三组同时完成搜索任务时，完成整个目标区域的搜索任务花费的总时间最短。通过计算，甲、乙、丙3组分配到的搜索区域分别为2264.21×7200、4648.65×7200、4287.14×7200。甲组每一个队员横向搜索18次可以将分配到的2264.21×720小区域搜索完毕，乙组每一个队员横向搜索9次可以将分配到的4648.65×360小区域搜索完毕，丙组每一个队员横向搜索9次可以将分配到的4287.14×360小区域搜索完毕。这3组人员同时完成搜索任务所需的时间。

关键词：
最优化，出队时间，搜索时间，调整时间，归队时间，目标区域，横向搜索

一、 问题的提出

随着社会的不断发展，人类解决了很多的问题，虽然人们还无法阻止自然灾害的奇袭，但是如何将自然灾害的损失以及人员伤亡减少到最小，已经成了各个国家关注的一大问题。在例如地震型类的灾害中，如何在最短的时间内对指定目标区域地区进行搜索救出受灾的人群，因此合理的规划搜索路线显得格外的重要。

二、问题的重述

给一个大小为11200米×7200米的平地矩形目标区域，对其进行全境搜索。假设：出发点在区域中心；搜索完成后需要进行集结，集结点（结束点）在左侧短边中点；每个人搜索时的可探测半径为20米，搜索时平均行进速度为0.6米/秒；不需搜索而只是行进时,平均速度为1.2米/秒。每个人带有GPS定位仪、步话机，步话机通讯半径为1000米。搜索队伍若干人为一组,有一个组长，组长还拥有卫星电话。每个人搜索到目标，需要用步话机及时向组长报告，组长用卫星电话向指挥部报告搜索的最新结果。
根据以上给出的信息解决以下问题：
1．假定有一支20人一组的搜索队伍, 拥有1台卫星电话。设计一种耗时最短的搜索方式。按照这种方式，搜索完整个区域的时间是多少? 能否在48小时内完成搜索任务? 如果不能完成，需要增加到多少人才可以完成。
2．为了加快速度，搜索队伍有50人，拥有3台卫星电话，分成3组进行搜索。每组可独立将搜索情况报告给指挥部门。请设计一种耗时最短的搜索方式。按照这种搜索方式, 搜索完整个区域的时间是多少?

三、问题的分析
首先根据题目中给出的有关数据，绘制出这个指定搜索范围的示意图如下：
11200m
7200m
集结点
点发出

搜索的过程就是对这些指定的地点进行地毯式的巡查，也就是说在这个指定的区域内，各个角落都需要巡查。为了确保搜索的时间最短，我们就应该使重复巡查的面积最小。因此问题1和问题2就成了最优化问题，也就是说该题的主要目的就是建立系统模型，求出最优解。

四、基本的假设

1）在进行搜索的过程中每一个人的体质一样，不会出现任何意外状况；
2）指定的地点地势平坦，不会出现沟壑山丘；
3）当搜索人员寻找到目标时，向有关人员汇报信息的时间忽略不计；
4）当搜索队员处于起始位置时，我们将整个搜索队看作为一个质点；
5）每一个队员都严格按照指定的路线进行搜索；
6）不考虑余震。

五、基本符号说明

符号
意义

一个队的所有队员排成一列搜索的最大宽度

搜索队的队员数目

搜索完指定区域所需要的总时间

问题1中，搜索队在一个完整的搜寻的过程中第个阶段所需的时间

问题1中，增加队员后，在一个完整的搜索过程中第个阶段所需的时间

问题2中甲组搜寻人员在11200m的边上分配到的搜索长度范围

问题2中乙组搜寻人员在11200m的边上分配到的搜索长度范围

问题2中丙组搜寻人员在11200m的边上分配到的搜索长度范围

问题2中，搜索队在一个完整的搜寻的过程中第个阶段所需的时间

问题2中，甲、乙、丙三组搜索完分配的区域所需的总时间

每个队员在搜索时的可探测半径

六、模型的建立与求解
6．1 问题1模型1的建立与求解
模型1的假设：
假设在搜寻的过程中，每一个搜索人员与队长的距离皆在1000m以内。
6．1．1 模型1的建立
通过对此题的分析，决定了建立模型的基本思路。我们尝试着从不同的起点开始，用各种搜索的方式进行搜寻，经过计算，最后确定了以下的模型。题中要求搜索完指定地点所需的时间，我们依据题中的相关数据，绘制出搜索路径的草图如下所示：
点发出
点结集

搜寻人员从起点处行进到边界处后,所有队员所处位置的排列图形如下所示：
点结集
点发出

图中的一列圈代表着搜寻人员所处的位置，由上图可知，在不需要搜索行进的过程中，第一个队员到达他所处边界位置时所需的时间最长，因此可以计算出搜索队从出发点开始，不需搜索向前行进时所需的时间，即出队的时间

在搜寻的过程中，由于每一个队员的探测半径是20m，如果把这个搜索队的20名队员排成一列时，可以计算出这些队员一次所能探测的最大宽度

当搜索人员到达界位置以后,将按下图所示的路线进行搜索 ：
点结集
点发出

由题目中给出的数据可知，搜索时平均行进速度为0.6米/秒，因此可以计算出横向搜索完整个给定的目标区域所需要的时间

在此模型中，当搜寻队的人员每完成一次横向搜索时，为了使搜索人员能够进入下一个搜寻阶段，需要一段时间对此搜寻队中每一位队员的位置进行调整，因此得计算出在整搜索的过程中队员们完成调整所需要的时间

从题目中可以知道，当搜寻人员完成搜寻任务后，需要进行集结，并且集结点（结束点）在左侧短边中点。因此需要计算出，搜寻人员搜索完毕以后全部到达集结所需要的时间

6．1．2 模型1的求解：
（出队时间） (1)
（搜索时间） (2)
（调整时间） (3)
（收队时间） (4)
（总时间） (5)
(6)
根据以上列出的式子,计算出各个量的值如下:

由此得出的结果可知，该搜索队不能在48内完成搜索任务。

为了能够在48内完成任务，达到题目的要求，应该增加搜索人员的个数。根据以上模型建立的过程，我们可以知道,出队时间与搜索时间与搜索人员的数目无关,因此只有减少调整时间与收队时间，才能使得搜索完整个指定区域的时间在48以内。
即 ：
(1)
又因为
（出队时间） (2)
（搜索时间） (3)
（调整时间） (4)
（收队时间） (5)
（总时间） (6)
(7)
由以上的式子，经过分析可知道,要想缩短搜索时间，只能减少来回搜寻的次数，根据上式的求解，当搜索队员为20人时，需要来回搜寻9次，如果将搜寻的次数减少到8次，可以有效的缩短时间。
当在指定的区域内，左右方向来回搜索8次时,队员们的运行路线如下所示 ：
点结集
点发出

此时
（出队时间）
（搜索时间）
（调整时间）
（收队时间）

由以上的数据可知，增加搜索人数以后，当队员们左右方向来回搜索的次数为8时，满足题中的要求，由此可以得出人数

因此增加的人数为 ： 22.5-20=2.5 向上取整
按照模型1的思路，要想在48内将指定的区域搜索完毕，应该增加3人才能顺利的完成
6．2模型2的建立与求解 ：

模型2的假设
假设在搜寻的过程中，只需队员与队员之间的距离保持在1000m以内,不强调每一个队与组长的距离保持在1000m以内。

6．2．1 模型2的建立：

根据题中给出的有关信息及假设条件，将该搜索区域分成二十等分，并且由相应的队员承担。在此模型中，搜索人员行进的总路线图如下所示：
点结集
点发出

通过对该模型的分析，绘制出所有的搜索人员从出发点行进到边界处后排列的示意图如下所示：
点结集
点发出

由以上的图形，可以计算出搜索队从起始点出发，不需搜索向前行进时所需的时间，即出队时间：

在此模型中，各个队员从起始点出发，到达划分后指定的位置以及他们在这些规定的目标区域内进行搜索，行进路线的示意图如下所示：

由题目中给出的数据可知，搜索时平均行进速度为0.6米/秒，因此可以计算出搜索完整个给定的目标区域所需要的时间，即搜索时间：

当搜寻队的人员将指定的区域搜索到边界时，为了使搜索人员能够进入下一个搜寻阶段，需要一段时间对此搜寻队进行调整，因此得计算出巡查完这个固定区域所需要的时间，即调整时间：

每一个队员搜索完毕划分以后指定的区域，回到集结地点所需要的时间，即归队时间：

6．2．2 模型2的求解：

根据以上列出的式子，计算出各个量的值如下：

由此得出的结果可知，该搜索队不能在48内完成搜索任务。
根据题目给出的要求，以上的模型求解的结果不能满足要求，因此需要增加搜救人数。
由上式的求解可知，当搜索队员为20人时，需要来回搜寻9次，按照以上建立的模型，只有通过增加人数来减少所用时间。要想在48内完成该搜索任务，只能通过搜救的次数，从而有效的缩短时间。
假设左右方向来回搜救的次数为8次，从出发点开始，搜索队员行进到边界处的路线图及排列位置如下所示 ：
点结集
点发出

此时
由图可知，可以搜索人员不需要搜索直接向指定的边界位置行进的时间，即出队时间：

又题目中已经给出搜索时平均行进速度为0.6米/秒，因此我们可以计算出搜索完整个给定的区域所需要的时间，即搜索时间：

当任意队员搜索完一个来回时，为了能够进入下一轮的搜索中，需要一段时间进行调整，因此需要计算出搜索过程中调整的总时间，即调整时间：

每一个搜索队员将指定的目标区域搜索完毕时，必须回到集结点，为此需要计算出队员集结完毕的时间，即归队时间：

因此可以计算出搜索完整个目标区域所需的总时间T：

满足题中要求，由此得出所需要的总人数：

由此得到增加的人数为：

但人数必须为整数，把向上取整。因此,按照模型2的思路，要想在48内将指定的区域搜索完毕，应该增加3人才能顺利的完成此项任务。

6．3 问题2模型的建立与求解

6．3．1 模型的建立

根据题目中给出的数据以及该问题的要求，将50个搜索队员分成甲、乙、丙三个组，其中每一组人数分别为10、20、20。由于乙、丙两组的人数都为20人，因此可以利用问题1中模型2的解题思路，对此题进行求解。
首先根据题意，假设：甲组搜寻人员在11200m的边上分配到的搜索长度，乙组搜寻人员在11200m的边上分配到的搜索长度，丙组搜寻人员在11200m的边上分配到的搜索长度，因此可以绘制出这3组个搜寻队分配搜索区域后的示意图，如下所示：

根据上图各组分配到的搜寻区域以及所拥有的搜索人员个数，通过分析，制定各组搜索人员的搜寻路线如下所示：

根据以上的图形，可以分别计算出甲、乙、丙3组队员搜寻完指定的区域所需的总时间。

甲组：
该组搜索队员从出发点开始，不需搜索向前行进时所需的时间，即出队的时间

由于搜索时平均行进速度为0.6米/秒，因此可以计算出该组搜索完该给定的目标区域所需要的时间，即调整时间：

当该组的成员搜索完一个来回时，需要一段时间进行调整，从而进入下一个搜索阶段，分析该组的路线图，可以算出该组成员进行调整的时间：

该组的队员将整个指定的区域搜索完毕以后，回到集结点的时间，即归队时间：

因此，该组成员搜索完分配到的整个区域所需的总时间为：

乙组：
该组搜索队从出发点开始，不需搜索向前行进时所需的时间，即出队的时间

由于搜索时平均行进速度为0.6米/秒，因此可以计算出该组搜索完这给定区域所需要的时间，即搜索时间：

当该组的成员搜索完一个来回时，需要一段时间进行调整，从而进入下一个搜索阶段，由以上的图行，可以算出该组成员进行调整的时间

当该组的队员将整个指定的区域搜索完毕以后，回到集结点的时间，即归队时间：

因此，该组成员搜索完分配到的整个区域所需的总时间为：

丙组：
该组搜索队从出发点开始，不需搜索向前行进时所需的时间，即出队的时间

由于搜索时平均行进速度为0.6米/秒，因此可以计算出该组搜索完这给定区域所需要的时间，即搜索时间：

当该组的成员搜索完一个来回时，需要一段时间进行调整，从而进入下一个搜索阶段，为此可以算出该组成员进行调整的时间

该组的队员将整个指定的区域搜索完毕以后，回到集结点的时间，既归队时间：

因此，该组成员搜索完分配到的整个区域所需的总时间为：

又因为只有在这3个组的队员同时将分配的区域搜索完毕时，才能有效的节省时间，使得总的搜寻的时间最短。

6．3．2 模型的求解：
根据上面的分析，列出方程组如下：

即

用Matlab软件对以上的方程组进行求解（程序见附录）
得出：
=2264.21m
=4648.65m
=42487.14m
将这些计算得到的结果代入：中，得出的结果为：

也就是说，搜索队50名队员，分成甲、乙、丙3组后，如果按此种模型进行搜寻，将整个目标区域搜索完毕花费的总时间为21.2450

七、模型的改进

7．1 问题1
7．1．1 模型1的改进
根据模型1中搜索完整个目标区域所需的总时间T与各个搜索阶段所需的时间之间的关系
即：
（出队时间） (1)
（搜索时间） (2)
（调整时间） (3)
（收队时间） (4)
（总时间） (5)
其中：
由此可以知道，当搜索队的人数一定时，净搜索完整个目标区域的时间一定，因此要想缩短总时间，就应该尽量减少搜寻过程中的出队时间、调整时间 和最后的收队时间。
在模型2中，我们把把调整时间已经减少到了几分钟，大大减少了非搜索时间，从而达到减少总的搜索时间的目的。
7．2 问题2模型的改进
从建立的模型中可以知道，该模型是在模型2基础上进行演变而来的。对所有的搜索队员进行分组处理后，由于人员数目的上升，在搜寻的过程中，出队时间与收队时间也会随之增加，因此要想减少搜索的总时间，就应该从缩短出队时间和收队时间入手。

八、模型的评价

8．1 问题1

8．1．1 模型1的评价
在该模型中，我们假设的是每一个搜索人员与组长的距离都保持在1000m的范围内，因此当每个队员在搜索时可探测半径一定时，搜索人员的数目也会有一定的限制，如果队员的人数超过，则此模型就不适用了。但当搜索人员的人数在以内时，用此模型，可以很清晰的用图形表述出搜索路线，从而便捷的算出整个搜索过程中所花费的总时间。

8．1．2 模型2的评价
此模型是在搜寻的过程中，只需队员与队员之间的距离保持在1000m以内,不强调每一个队与组长的距离保持在1000m以内的约束条件下建立的。因此，此模型没有人员的限制，因此适用性比较广泛。但是在求解此模型时，首先得根据搜索人员的数目，对整个给定的目标区域进行等分，从而求得每一个队员所需要的搜索面积，然后分析这些队员在这些分配的区域内搜索的路径，算出往返搜寻的次数，从而确定从出发点开始行进到边界处的方向，即根据往返搜寻的次数，决定从出发点往那走，才能使得最后到达集结点处整个搜索的时间最短。这样计算时步骤就比较复杂。

8．2 问题2

8．2．1 模型的评价
此模型是在问题1模型2的基础上进行演化而来的，因此问题2出现在此，就给解决这一问题带来了很大的便利，我们只需要根据问题1中模型2的思路，建立求解问题的模型，从而获得所要求的解，并且分组模型运用的也比较广泛。
不过这个模型的计算比较复杂。首先要根据给定的人数对这些队员进行分组处理，决定每一组的人员数目。随后，根据每一组的人员个数确定从出发点行进的方向以及他们的搜索面积。而如何决定他们的搜索面积是一个非常复杂的求解过程。因此当搜索队的人数发生变化时，我们所要考虑的问题比较多。

九、参考文献

[1] 求是科技，《MATLAB7.0从入门到精通》 北京：人民邮电出版社，2006.3
[2] 工程数学学报编辑委员会，《工程数学学报》，第22卷第七期：《工程数学学报》编辑部，2005.12
[3] 杨启帆 何勇 谈之奕 ，《数学建模竞赛—浙江大学学生获奖论文点评》，浙江：浙江大学出版社，2005.7
[4] 陈汝栋 于延荣 ，《数学模型与数学建模》 北京：国防工业出版社，2006.1
[5] 逢山开路的最优问题 资料室 M O22/W184
[6] 2008年全国大学生数学建模竞赛论文格式规范

十、附录

问题2模型的程序：

clear all;
clc;
syms x y z;
[x,y,z]=solve('sqrt((5600-z)^2+3580^2)/1.2+15*y+sqrt((3600-(9*40-20))^2+x^2)/1.2-30*x-8288.8=0','x+y+z-11200=0','15*z+sqrt((3600-(9*40-20))^2+(x+y)^2)/1.2-30*x-2750=0','x','y','z')

x =

2264.21

y =

4648.65

z =

4287.14
17