数学建模地面搜索作业.doc

地面搜索摘要为了制定搜索队伍的行进路线，对预定区域进行快速的全面搜索，本文建立了路线的平行搜索模型，利用一笔画的方法，确定行进路线，再对模型进行多次优化，以使得重复区域和拐角数目减小，从而得到用时最少的行进路线。针对问题一，影响搜索时间的因素有：队形，拐角方式，搜索路线。考虑到一台卫星电话的制约条件影响，将二十人一字排开，进行平行式的搜索，可将搜索效率达到最大。拐角方式有直穿式和对角式，经计算的两种拐角方式的用时相同。将搜索区域简化为的方格，结合一笔画的思想，尽量走长边以减少拐弯，考虑路线数目的奇偶以减少重复路线，综合各因素，画出最优搜索路线。通过搜索路线的路程，计算得到搜索完整个区域的时间是49.6296小时，无法在48小时内完成搜索任务，增加一个人后重新确定最优搜索路线，计算搜索时间为49.1944小时，仍无法在48小时内完成搜索任务。增加两个人后，计算搜索时间为47.5926小时，可以在48小时内完成搜索任务。针对问题二，为使得各组以一条直线的排列方式行走的区间长度都应尽量是直线长度的整数倍，又考虑路线数目奇偶的基础上进行细致的分配，使其满足重复区域最少，拐角数目最少，以三组的时间均衡为原则，得到搜索方案为：将50人分为20人、20人、10人三组进行对称性搜索，20人的两组分得的区域位于纵向边缘的两侧，10人组在其中间的区域搜救，即为耗时最短的搜索路线，最短搜索时间为19.9832小时。关键词：路线设计 拐角搜索 直穿搜索 最短时间1、 问题的重述地面搜索5.12汶川大地震使震区地面交通和通讯系统严重瘫痪。救灾指挥部紧急派出多支小分队，到各个指定区域执行搜索任务，以确定需要救助的人员的准确位置。在其它场合也常有类似的搜索任务。在这种紧急情况下需要解决的重要问题之一是：制定搜索队伍的行进路线，对预定区域进行快速的全面搜索。通常，每个搜索人员都带有GPS定位仪、步话机以及食物和生活用品等装备。队伍中还有一定数量的卫星电话。GPS可以让搜索人员知道自己的方位。步话机可以相互进行通讯。卫星电话用来向指挥部报告搜索情况。下面是一个简化的搜索问题。有一个平地矩形目标区域，大小为11200米7200米，需要进行全境搜索。假设：出发点在区域中心；搜索完成后需要进行集结，集结点（结束点）在左侧短边中点；每个人搜索时的可探测半径为20米，搜索时平均行进速度为0.6米/秒；不需搜索而只是行进时,平均速度为1.2米/秒。每个人带有GPS定位仪、步话机，步话机通讯半径为1000米。搜索队伍若干人为一组,有一个组长，组长还拥有卫星电话。每个人搜索到目标，需要用步话机及时向组长报告，组长用卫星电话向指挥部报告搜索的最新结果。现在有如下问题需要解决：1假定有一支20人一组的搜索队伍, 拥有1台卫星电话。请设计一种你认为耗时最短的搜索方式。按照你的方式，搜索完整个区域的时间是多少? 能否在48小时内完成搜索任务? 如果不能完成，需要增加到多少人才可以完成。2为了加快速度，搜索队伍有50人，拥有3台卫星电话，分成3组进行搜索。每组可独立将搜索情况报告给指挥部门。请设计一种你认为耗时最短的搜索方式。按照你的搜索方式, 搜索完整个区域的时间是多少?2、 模型的假设1.搜索仪器始终保持正常工作2.搜索区域平整，两点高差忽略不计3.队员工作时，不受其他不量因素的影响4.队员搜索过程中的速度保持不变5.队员向队长报告时间忽略不计6.搜索队员搜索时不间断休息7.假设小组队员并排进行搜索，队员之间的距离严格按照40m3、 符号说明符号含义第i组人员数目搜索总时间正常搜索所用时间搜索队伍转弯所浪费的时间搜索队伍重复路程所浪费的时间4、 问题的分析与求解模型一1. 搜索行进队列的设计步话机通讯半径1000米的限制决定了各组人员必须在距离组长1000米的范围内作为一个整体进行搜索，在搜索中为了便于组长指挥调度及尽量避免重复行进，我们采取了组长在中间和组员一起成一字形的拉网式搜索队形。相当于以一条长，宽40米的类似矩形块行进。2. 转弯方式的设计要在基于队形尽量保持的条件下避免重复又不能有人等待，我们想到2中转弯方式。(1)直穿转弯具体转弯方式如图1所示：图1 直穿转弯示意图可以得到转弯浪费的时间为（s）(2)对角转弯具体转弯方式如图2所示：图2 对角转弯示意图可以得到转弯浪费的时间为max(成员所走对角线长度)/1.2（s）以上两种方式即每个成员都直接走到目标区域边缘，然后全队人员以队列形以1.2m/s走至下一区域起点，依次循环。通过计算发现，直穿式与对角式转弯方式浪费的时间相等，即一次转弯浪费（以20人为例）为666.7（s）。3. 行进路线的设计目标区域是一个矩形图，转弯处只考虑和的弯角，而由于转弯会出现时间的浪费，因此尽量减少转弯也是路线设计原则之一。(1)在这里我们首先考虑减少重复路线的原则，因此设计路线时将其简化为一笔画问题，以此我们设计了如图3所示路线：图3 无重复路线设计图 由图可得计算公式为其中为搜索每个方块的时间，而搜索每个方块的时间都是666.7s。而总共有个搜索方块。为转弯浪费的时间，每次转弯浪费的时间都是666.7s图中总共有16个转弯点。通过计算我们可以计算得出为178666.7s，即49.6296h。(2)追求无重复会使路线复杂不利用实际操作，考虑尽量减少转弯点的原则，我们又设计了如图4所示路线：图4 少转弯点路线设计图注：对于一些必要的重复路段采用1.2m/s快速行进。由图可得计算公式为： 其中为重复路程所浪费时间。 该图中有10个转弯点，个搜索方块通过计算我们可以计算得出为178666.7s，即49.6296h。这与前一种方式时间相同，但都大于题目中小于48h的要求，故我们需要增加人数。4. 需要增加人数的判断(1)增加1人的情况21人为一组的情况下，一个搜索方块的边长会增加40米，由于总的搜索区域不变，所以整个搜索区域中会出现的完整搜索方块及三种矩形搜索方块，同时转弯浪费时间也会变化，因此我们重新设计了行进路线，如图5所示：图5 21人一组情况下路线设计图通过计算公式可以得到为177100s，即49.1944h。但结果仍然不满足问题一的要求。(2)增加2人的情况 22人为一组的情况下，一个搜索方块的边长会增加80米，由于总的搜索区域不变，所以整个搜索区域中会出现的完整搜索方块及三种矩形搜索方块，同时转弯浪费时间也会变化，因此我们又重新设计了行进路线，如图6所示：图6 22人一组情况下路线设计图 通过计算公式可以得到为171333.3s，即47.5926h。满足问题一的要求。模型二1. 各组人数确定原则(1) 整数倍原则 将的目标区域划分为的小方格，则横向纵向分别有280和180个小方格，为了减少重复的路线，应该每组每次走的路线都能让全员工作，即各组以一条直线的排列方式行走的区域长度和宽度都尽量是直线长度的整数倍。(2) 长边原则 鉴于具体路线设计的复杂性，而50不能被3整除，我们想到分配时有两组分组相等的趋势，且设其人数为，这两个组分别记为和，则另一组记为，人数为。基于问题一的分析，各组进行搜救时应尽量走长边以减少拐弯，鉴于此我们假设和两组人分得的区域位于纵向边缘的两侧，在其中间的区域搜救。(3) 时间均衡原则 设各组完成搜索任务所用时间为。则完成整个搜救任务的时间，所以各个组完成任务的时间应尽量接近，当相等时即取得该方案下的最短时间。 由以上3个原则，知和都应该是180和280的公约数，计算得，所以确定各组的人数分别为20、20、10。这样的结果刚好也能充分利用问题一的模型，给问题的解决带来方便。根据三项原则确定两种方案如下。2.方案一(1)行走路线的确定在无重复路线的情况下，方案路线如图7所示：图7 三组时的搜索路线(1)设计图(2)模型求解：20人组，转向8次，“直穿”42格，20号外拐5次，内拐3次，20人组搜索用时：20人组空走用时所以20人组总用时为19.638小时。 10人小组，转向35次，“直穿”69格 ，1号外拐19次，内拐16次；10号外拐16次，内拐19次，10人小组搜索区域用时为搜索完后的归队空走用时为10人组总用时为20.137小时。综上，方案一总用时为20.137小时。3.方案二 (1)行走路线的确定 各个分组的区域应与人数呈正比例关系，可以先粗略的在长边方向分成3个规则的矩形区域，即各个子区域面积分别为11200800，11200800，11200400.然而简单计算发现这样的分区中由于各区域中路线数目的奇偶性，路线设计中出现了大量重复行走，因为沿长边方向走到最后的出路与集结点相背，至少需要重复1.511200米的长度。时间为3.89h，若用走短边的方式仍要有这个长度的重复。我们在考虑路线数目奇偶性的基础上对所分区域做如下细致分配，使其满足重复区域最少，拐弯最少，如图8所示：图8 三组时的搜索路线(2)设计图(2)模型求解 中间一组的探测时间。 从图中可以看出组与组路线相似且都没有重复路线，但组比组区域面积大，所以，计算。 因为，所以 综上所述，方案一中没有重复路线但是拐角较方案二多，方案二的拐角较少，但是有重复路线。经计算可以得出方案二的搜索时间更短，方案二的路线为最优搜素路线。最短搜索时间为19.9832小时。五、模型的评价优点：1.问题一中的模型采用先分析后计算的方法，较快的确定出最优路线。 2.问题二中的模型采用两种方案对比的方法，更加全面的证实了模型的可信度。 3.对问题进行了合理简化，便于问题求解。 4.对于现实问题具有一定的指导作用缺点：假设情况与实际情况相比过于简单化，需在理想条件下才能无较大误差完成。六、模型的推广1. 将本题中的模型结合实际