地面搜索模型.doc

地面搜索的数学模型一、摘要5.12汶川大地震使震区地面交通和通讯系统严重瘫痪，在这种时间就是生命的情况下，制定快速、全方面的搜索救援方案是非常重要的。现在我们的任务就是在给定的条件下制定快速、全面、有效的搜索方案。我们认为进行快速、全面、有效搜索的指标分别为队伍拐弯数量最少和不走重复路，在这两个指标下，使得搜索的时候队伍拐弯数量尽可能少并且尽量少走重复路。对于问题1.1，我们先用极端法建立不考虑始点和终点位置的情况下建立的快速、全面搜索的模型，即模型一，模型一为完全符合我们衡量进行快速、全面搜索指标的数学模型，经过计算得到所用时间为，因为模型一为一种完全不考虑其它约束条件下的理想情况，所以我们把模型一的结果做为进行快速、全面搜索的下限，因此可以确定在考虑完所有约束条件的情况下，在内是不能完成对所给区域进行快速、全面的搜索的任务。得到这个结论后，我们就根据给定的所有约束条件建立模型二，模型二为符合拐点最少这一指标的数学模型，具体行径方案见正文，经过计算得出完成任务所要使用的时间为。在这个的基础上，我们又考虑到拐点最少不一定为最优的方案，所以我们又考虑另外一个指标，即不走重复路。因此我们建立模型三，具体行径路线见正文，经过计算得出所用时间为。经过与模型一、模型二比较得出最优方案为模型三。对于问题1.2，我们在问题1.1中模型三的基础上进行解决，行径路线与模型三相似，具体行径路线见正文，经过计算得出，增加2个人即可在内完成对给定区域进行快速、全面搜索的任务，并计算得其时间为。要解决问题1.2， 根据题目要求我们把50人分成三个队，分别为20人，20人，10人。在问题一进行快速、全面搜索的指标下进行地毯式搜索。按照他们队伍的可探测范围为其分配探测面积，结合方程思想，建立方程组，求出使三个队均同时到达集合点的最优方案，具体方案见正文，所用的时间均为。本文确立了两个衡量快速、全面搜索的指标，且在该指标下考虑了极端情况作为进行快速、全面搜索的时间下限。全文围绕这两个指标建立数学模型，使建立的数学模型达到最优。并且利用了文字与图形相结合的说明方式，思路清晰、易懂。关键字：快速、全面搜索指标，方程思想，极端法、地毯式搜索。二、问题重述5.12汶川大地震使震区地面交通和通讯系统严重瘫痪。救灾指挥部紧急派出多支小分队，到各个指定区域执行搜索任务，以确定需要救助的人员的准确位置。在其它场合也常有类似的搜索任务。在这种紧急情况下需要解决的重要问题之一是：制定搜索队伍的行进路线，对预定区域进行快速的全面搜索。通常，每个搜索人员都带有GPS定位仪、步话机以及食物和生活用品等装备。队伍中还有一定数量的卫星电话。GPS可以让搜索人员知道自己的方位。步话机可以相互进行通讯。卫星电话用来向指挥部报告搜索情况。下面是一个简化的搜索问题。有一个平地矩形目标区域，大小为11200米7200米，需要进行全境搜索。假设：出发点在区域中心；搜索完成后需要进行集结，集结点（结束点）在左侧短边中点；每个人搜索时的可探测半径为20米，搜索时平均行进速度为0.6米/秒；不需搜索而只是行进时,平均速度为1.2米/秒。每个人带有GPS定位仪、步话机，步话机通讯半径为1000米。搜索队伍若干人为一组,有一个组长，组长还拥有卫星电话。每个人搜索到目标，需要用步话机及时向组长报告，组长用卫星电话向指挥部报告搜索的最新结果。现在有如下问题需要解决：1假定有一支20人一组的搜索队伍, 拥有1台卫星电话。设计一种我们认为耗时最短的搜索方式。求出按照我们的方式搜索完整个区域所需的时间，并分析能否在48小时内完成搜索任务，如果不能完成，需要增加到多少人才可以完成。2为了加快速度，搜索队伍有50人，拥有3台卫星电话，分成3组进行搜索。每组可独立将搜索情况报告给指挥部门。设计一种我们认为耗时最短的搜索方式。求出按照我们的搜索方式搜索完整个区域所需的时间。三、问题分析问题1.1为队伍人数为20人，拥有1台卫星电话的情况下，要求我们制定我们认为耗时最少的搜索方案。我们认为队伍进行快速、全面搜索的两个指标分别为队伍拐弯最少和不走重复路。因为要进行全面的搜索，所以我们采用地毯式搜索，即每次搜索均走到边的尽头的方式。我们首先考虑在完全符合两项指标的极端情况下建立模型，即模型一，因为题目给定约束条件，模型一的理想化不能做到，所以我们建立符合拐点最少的模型，即模型二，并建立不走重复路的模型，即模型三，比较模型一与模型二，确定最优化模型。问题1.2在问题1.1的最优化模型的基础上进行求解，基本路线与模型三类似。问题2为队伍人数50人，3台步话机的情况下，要求我们制定我们认为耗时最少的搜索方案。我们把50人分成3队，分别为20人，20人，10人。我们认为耗时最少的快速、全面的方案为在满足问题1的全面搜索的情况下，使三个队伍同时到达集结点的方案即为耗时最少的方案。四、符号说明矩形区域的边长；矩形区域的宽；队伍一致排开的课探测范围；队伍搜索时的行径速度；队伍不搜索时的行径速度；队伍的人数；每个人的可探测半径；进行快速、全面搜索的总时间；队伍行径搜索的时间；队伍散开和集结的时间；队伍整体移动的时间；五、模型假设假设一：假设所要搜索的区域为均匀平滑的连续曲面；假设二：天气好坏不影响搜索进度；假设三：每个搜索人员所携带的GPS定位仪、步话机以及每个组的卫星电话都是无损坏的；六、模型建立与求解问题1.1解决：我们认为进行快速、全面搜索的两个指标分别为队伍拐弯最少和不走重复路。由于每个人的可探测半径，所以，个人一字排开可探测范围为，小于步话机通信半径。为了保证全方面的搜索，我们采用地毯式搜索的搜索方式，即每次行径至路的尽头的方式。我们根据搜索的两个指标分别建立模型一和模型二。首先我们考虑完全符合我们认为快速、全面搜索指标的模型，即模型一，模型一为不考虑队伍始点（出发点）和终点（集合点）位置的数学模型，现举其中一种方案供参考，方案如图1示。根据模型一，计算出进行快速、全面的搜索所用的最少时间为： （1）始点终点图1 因为模型一完全符合我们认为的快速全面搜索指标的情况，在题目要求下不能做到，所以我们把模型一的结果当做进行快速全面搜索的时间下限。由此可知，在内不能进行全面快速的搜索。因为模型一的理想化不能达到，所以我们根据题目要求建立模型二，模型二为考虑拐点最少这一指标的模型，具体方案如图2示，因为模型二只比模型一多出两个拐点，所以，我们认为模型二为符合题目要求下拐点最少的模型。根据模型二，计算出队伍在矩形区域中行径搜索用的最少时间为： （2）搜索之前队伍要散开，在搜索完毕之后队伍要集结，使用的时间为 （3）所以进行一次搜索所用的总时间 （4）7200m11200m1234567891011121314151617182021图2800m 因为衡量快速全面搜索的指标有两个，所以我们现在考虑拐点尽量少且不走重复路的模型，即模型三。方案如图3示，因为模型三与模型二相比只多出了5个拐点，且没有重复路，所以我们认为模型三即为拐点最少情况下不走重复路的模型。根据模型三，计算出队伍在矩形区域行径搜索的时间为： （5）所以队伍进行快速、全面搜索的总时间为： （6）将模型一、二、三进行对比，因为模型三使用的时间最少，所以我们认为模型三为进行快速、全面搜索的耗时最少的方案。 12 13 10 8 6 1 14 15 16 11 1 1 9 7 2 3 5 4说明： 表示出发点； 表示集合点。问题1.2解决：问题1.2可以在模型三的基础上进行解决。 在问题1.1求出的我们认为耗时最少的方案的情况下，要在内进行全面快速的搜索，我们首先考虑增加1人，具体搜索方案见附录1,队伍可探测范围为。 为保证用模型三的方案进行搜索，所以我们先把队伍整体下移，所用时间为： （6）队伍散开和集合的时间为： （7）按照模型三的搜索方式搜索，队伍在矩形区域行径搜索的时间为：（8）所以，队伍进行快速、全面的搜索所用的总时间为： （9）因为，所以增加1人仍不能满足小于的条件，现在我们考虑增加2人，则队伍可探测范围为 ，具体行径方案如图4所示。 5040m5600m 560m 6537891011121416 13 15 17 1 24 图4说明： 表示出发点； 表示集合点。为保证用模型三的方案进行搜索，所以我们先把队伍整体下移，所用时间为： （9）队伍散开和集合的时间为： （10）然后按照模型三的搜索方式进行搜索，具体方案如图4所示。队伍在矩形区域行径搜索的时间为（11）所以，队伍进行快速、全面搜索用的总时间为： （11）因为，所以我们的模型只要增加两人即可在内完成全面快速的搜索任务。由问题1.2的解决可知，模型三具有一般性，所以我们把模型三推广到矩形长为，宽为，在满足题目要求条件下队伍人数为的情形。即模型四，具体行径路线同模型三。因为队伍人数为，所以队伍的可探测范围为 （12）队伍散开与集合所用时间为： （13）队伍在矩形区域行径搜索的时间为：（14）其中，表示朝无穷大方向取整。因为，在保证模型三的行径路线的情况下，队伍要整体移动的时间很少，为了便于模型的建立，所以我们忽略队伍整体上下移动的时间。所以模型四为：(15)因为步话机的通信半径受限，所以如果步话机在队伍中任意位置时，人数；若步话机在队伍中间，则人数人。问题2的解决：根据题目要求，我们把队伍分成3个队，队伍人数分别为20人，20人，10人。三个队伍的可探测范围分别为：，。我们认为三个队伍在问题一快速、全面进行搜索的指标下进行地毯式搜索，且三个队伍同时到达集结点的方案为最优方案。按照他们队伍的可探测范围为其分配探测面积，因此我们建立模型五，模型五如图5示。模型五中的为未知数，所以我们结合方程思想，建立方程，求出使三个队均同时到达中点的最优方案。1724568313677354224615800m图5 说明：黑色箭头表示第一组人；蓝色箭头表示第二组人；其它的箭头表示第三组人； 表示出发点； 表示集合点。按照模型5的行径方式，要确认各个队伍同时到达终点的最少时间，必须求出图5中的具体值。因此，我们建立方程来求解： （14）解方程得。得到个队伍到达集结点后集结的时间为： (15)将代入（14）式，求出队伍进行快速、全面搜索的总时间为：（16）七、模型优缺