2008C___地震搜索优化问题分析与评述

《2008C___地震搜索优化问题分析与评述》由会员分享，可在线阅读，更多相关《2008C___地震搜索优化问题分析与评述（6页珍藏版）》请在金锄头文库上搜索。

1、地震搜索优化问题分析与评述地震搜索优化问题分析与评述肖华勇 (西北工业大学应用数学系，西安，710072)摘要：本文介绍 2008 年高教社杯全国大学生数模竞赛 C 题“地面搜索”题的评卷情况，首 先概括地介绍了这个问题的背景、评卷要点、问题的解决方法和答卷中存在的问题。最后 给出了解决这个问题的一种优化路线和计算结果。 关键词：地面搜索；一笔画；横向搜索；纵向搜索1.地面搜索问题的综合评述地面搜索问题的综合评述 1.1 问题的背景 2008 年的 5.12 汶川大地震震惊了中国，也震惊了世界。在地震发生后，一个重要的 问题就是搜索和求援。特别是山村被掩埋后，与外界的通讯中断，更需要进行全面搜

2、索和 救援。如 5.12 大地震中，15 名空降兵在茂县灾区从 5000 米高空成功空降后，连续个昼 夜冒着多次余震，翻越了 4 座 3000 多米高的山峰，徒步 220 公里，先后在 7 个乡 55 个村 庄侦察灾情，向上级报告重要灾情 30 多批次，为指挥部指挥部队开进和部署抗震救灾提供 了科学的信息依据。 地震中的搜索问题是一个很复杂的问题，因为实际的地形很复杂，有河流、山川， 峡谷，有的地方还没有现成的道路，因此搜索难度很大。但在我们的竞赛中，不可能把问 题搞得如此复杂，只是借助地震的背景，提出优化路线的搜索问题。在实际的搜索中，只 要人力足够，通常采用的是地毯式搜索，这样可以保证把每

3、一片地方都搜索到。因此我们 的搜索问题主要基于地毯式的搜索，要求排成一排，把每一个地方都搜索到。1.2 评卷的基本要点地面搜索问题对于乙组的参赛学生来说，是一个易懂，好下手，方法灵活，越做越有味 的题目，因此选择该题的学生较多，这也说明不少学生对该题的喜爱吧。但对该问题的最 优路线与结果却又不是那么容易获得，有一定难度。在全国评卷过程中主要给出了以下的 评判要点： 对问题 1，为了使搜索时间短,可以综合考虑三个因素：按一笔画原则尽量不走重复路; 尽量不空走; 尽量少改变队形(每次改变队形要空走)。解题中应交待清楚具体的搜索方式 (如一字并排前进,每人搜索宽度为 220=40 米)、具体的行进路

4、线、算出完成搜索的时间 (空走与改变行进队形均需要时间)。 行进路线的选择可以不同。对自己的方案是否是好方案, 应有可信的讨论。应有明确 的计算,说明方案可行。最好对不同情况进行比较。 对问题 2，在问题一的基础上适当分配人员，分区搜索。要看其分区及行进线路是否 合理。应有明确的计算, 并给出解答。 两个问题在解答过程中，要注意讨论的完善性，数学表达的清晰性。 1.3 问题的解决方法概述 该题目有做头，每个参赛者有很大的发挥空间。这也许是该题的魅力所在。论文中发 现做法千奇百怪，其搜索方式也很多，有从内向外搜索的，有横向进行搜索的，有纵向进 行搜索的，有横向纵向结合搜索的，有先从中心点行进到边

5、界，然后横向或纵向进行搜索 的。有的直接进行数字计算，有的针对一般问题进行计算。有的建立一般的优化模型，然 后 LINGO 进行优化计算。这说明参赛者都广开思路，发挥了自己的智慧，得到了锻炼和 提高。1.4 存在的问题 有的队审题太偏，把人分开独自去搜索，这样不能保证发现目标后立刻向队长报告， 不符合题意。有的队把整个平面区域分成几个村庄，然后搜索这几个村庄，这样把整个区 域的搜索变成对几个离散点的搜索，把题目简化得太离谱了，显然也违背题意。 还有一种解法，是把问题考虑成如何用最少个数的半径为 20 米的小圆来覆盖矩形区域， 搜索路线变成沿小圆之间的连心线进行，每人执行完搜索任务后再沿直线路径

6、行进至集结 点。把整个问题变成一个圆的完全覆盖问题，导致搜索过程不能保证题中要求每个人搜索 到目标，就用步话机及时向组长报告。这里的报告是直接报告，而不是通过他人间接报告。 因此每个人和队长的距离不能超过 1000 米，而不是每个人 1000 米内有一个人就可以了。 该种解法获得的结果在第一问中增加的人数远远超过最优人数，第二问中完成任务的最少 时间也远大于最优时间。尽管这种解法的一些论文数学表达严谨细致，但因题目理解偏离 实际，没能获得一个好奖，实在有些遗憾。2 地面搜索问题的优化路线地面搜索问题的优化路线2.1 问题分析与假设从实际中的搜索问题出发，我们需要假定队伍排成一排进行搜索，每次搜

7、索形成一个 矩形（带形）区域。由于整个区域是矩形，因此搜索方式可采用横向或纵向进行搜索，而 不要采用斜向搜索。对每个小矩形区域，队伍搜索方式是从头搜索到尾，每个部分都搜索到，搜索的宽度为， 为队伍人数。而且要保证每个队员搜索到目标后立刻报告给对40ll 长，不能通过其它队员传递，因此对每个队伍的人数是有限制的。 在搜索过程中，我们的目标是尽量快速搜索完整个区域，因此在搜索中尽量不走重复 路线，尽量不空走，尽量少拐弯。在搜索过程中，采用横向或纵向搜索，并尽可能将二者 结合起来，使搜索完成的时间尽量少。至于倒底采用横向还是纵向，需要根据实际的数据 分别进行计算，最后确定出最优路线。在第 1 问中，

8、通过计算可以得到当采用横向并结合 一次纵向搜索，可使搜索完成的时间尽量少。另外，要注意的是，整个区域搜索完成的时 间，不会超过队伍没有任何空走和拐弯的理想情况下的时间，该时间是搜索完成时间的下 限。当计算出 20 人在 48 小时不能完成搜索搜索时，需要增加人数，增加人数后需要重新 考虑搜索方式。对第 2 问，将 50 人分成 3 组。分组后涉及两个问题，一个是考虑三个组的人数如何分 配，另一个是考虑每个组搜索的区域如何划分。总的原则是三个组分配的人数如果多则区 域较大，人数少则区域较小。各组在自己区域里类似问题 1 采用尽量不走重复路线，尽量 不空走，尽量少拐弯的原则，以达到尽量早搜索完自己

9、的区域。而最后的目标是把整个区 域搜索完才算完成任务，因此我们应该尽量使三个组同时搜索完。 为了分析求解问题需要给出如下假设： （1）假设区域是连续的，每个地方都要搜索。(2）假设每个队员搜索到目标后都直接用布话机报告给队长，而不是间接报告。(3) 假定每次转弯都需要行走一个队长.。(4) 假定每个人的行走或搜索速度完全一样。 （5）假定搜索队伍能够完全按照设计路线搜索或行走。 （6）假定队伍都是排成一排搜索，而不管是横向搜索还是纵向搜索。(7) 假定分组后各组独立搜索，互不影响。 2.2 问题解答概要问题 1 队伍排成一排搜索，由于每个队员的搜索半径为 20 米，相邻两个队员的距离则为 40

10、 米。20 人搜索的矩形区域宽度为米20 40800 搜索完所有区域的最少人数估计： k=总面积/(搜索宽度搜索速度总时间)(人)11200 720019.42040 0.6 48 3600k 20 人队伍搜索外所有区域的最少时间为： T=总面积/(总人数搜索宽度搜索速度)(小时)11200 720046.6720 40 0.6 3600T 任何方式的搜索，其所花时间都不能少于该时间。 为了使搜索时间短,我想应考虑综合三个原则:按一笔画原则尽量不走重复路;尽量不空走;尽 量少拐弯（每拐一次弯就空走一个队长） 。20 人的一种最佳搜索路线见图 1。队伍所花时间包括搜索时间，拐弯时间和空走时间。横

11、向搜索的矩形为 7200/800=9 个，矩形长度为 11200-800=10400 米。 纵向搜索一个矩行区域，长度为 7200 米。矩形宽度都为队伍长度 800 米。搜索所花时间为：小时19 (11200800)/0.6/36007200/0.6/360046.667T 拐弯 10 次，所花时间为：小时210 800/1.2/36001.852T 空走时间为小时3(11200/2800)/1.2/36001.111T 总时间为小时12346.667 1.852 1.11149.63TTTT在计算过程中可不考虑队伍打开和收拢所花时间。 无论采用何种方式，21 人在 48 小时内不能完成搜索任

12、务。而 22 人采用图 2 所示方式 在 48 小时可以完成任务。图 1 20 人的一种最佳搜索路线图图 2 22 人的一种最佳搜索路线图纵向搜索的矩形为 7200/880=13 个，矩形长度为 7200-880=6320 米，宽度为 880 米。最后一个(标号为 18)的矩形长度为米。11200 12 880640 横向搜索一个矩形，长度为 11200 米，宽度 880 米。搜索完 11 号矩形进入 12 号矩形需要行走的距离为：DA=米。但7200/2880 480在 18 号矩形空走返回时，不需要走最后 80 米，因此 DA 段的 80 米被抵消，实际空走距离 恰好为宽的一半（3600

13、米） 。 搜索的距离为：米112007 (7200880)3 (112007 880)6 (7200880 4)92640d 搜索所花时间为：小时1/0.6/360042.889Td拐弯 17 次，所花时间为：小时217 880/1.2/36003.463T 空走时间为小时37200/2/1.2/36000.8333T 总时间为小时12342.8893.4630.833347.19TTTT因此 22 人在 48 小时内可完成任务。问题 2 将 50 人成 3 组，三组人数为 20:10:20。三组搜索路线图如图 3 所示。第 1 组 20 人， 搜索第 1 区，搜索路线从 A 点出发，依次搜索

14、 I1、I2、I3、I4、I5，搜索完直接到达集结 地 B。第 2 组 10 人，搜索第 2 区，搜索路线从 A 点出发，依此搜索 1,2,8，回到 A 点后 行进到集结地 B。第 3 组 20 人，搜索第 3 区，搜索路线从 A 点出发，依次搜索 S1、S2、S3、S4、S5，搜索完直接到达集结地 B。图 3 三组最优分区图第 1 组 20 人，队长 800 米，搜索的距离为：米11200/23 (11200800)7200/240400d 搜索所花时间为：小时1/0.6/360018.7Td拐弯 4 次，所花时间为：小时24 800/1.2/36000.74T 空走只有开始进入第 1 个矩

15、形这段，时间为小时31200/1.2/36000.28T 总时间为19.72 小时12318.70.740.28TTTT第 3 组与第 1 组完全相同。 第 2 组 10 人，队长 400 米，搜索的距离为：米5600 26 (5600 1200)240040000d 搜索所花时间为：小时1/0.6/360018.52Td拐弯 7 次，所花时间为：小时27 400/1.2/36000.648T 空走为最后从 A 到 B 这段，时间为小时35600/1.2/36001.296T 总时间为小时12318.520.648 1.29620.46TTTT由于第 1 组和第 3 组搜索完所花时间为 19.

16、72 小时，第 2 组搜索完所花时间为 20.46 小时。 因此搜索完整个区域所花时间为 20.46 小时。 另外，由于第 2 组比第 1 组多花时间 0.74 小时，因此还可以优化。可让第 2 组中间 6 个小矩形左移一段距离，让 I1 和 S1 横向距离增大一些，这样第 2 组搜索距离减少一点， 第 1 组和第 3 组搜索距离增大一点，使得三组同时搜索完，这样可使总的时间再减少一些。 可将第 2 组的 6 个矩形左移距离为优化变量，目标为三个小组同时搜索完。可解得x米，三个小组搜索完所花时间都为 19.82 小时。这样三个小组分工搜索后，可在230x 20 小时内完成搜索。致谢：在出题目过程中，得到全国专家组的帮助。特别是在编写参考解答和问题讨论过 程中，与孙山泽老师和姜启源老师有过多次深入讨论，获得很大帮助，在此一并表示