地面搜索问题的优化模型—数学建模论文.doc

地面搜索问题的优化模型摘 要 本文针对地面搜索过程中人员安排和路线选择问题，建立了优化模型，并给出了相应算法，用LINGO软件编程，在确保所有地点都不遗漏且不重复的情况下，合理安排人员和线路，使得搜索用时最短 问题一的求解中，把20个搜索队员排成一行，向前搜索从局部和总体两个方面对人员行进和路线选择在局部方面，考虑到人员行进中90度和180度转弯的情况，给出了两种转弯策略，并计算出这两种转弯的情况需要多耗费的时间；在总体方面，把需要进行搜索的区域分割成的126个方格，利用一笔画原理，判断出这些方格可以用一条不重复的线路走完考虑到转弯需要多耗费时间，建立了以转弯次数最少，并且从起始点开始不重复行走到达集结点的模型，利用LINGO软件进行编程求解，得到了最少转弯的模型考虑到具体情况，对上述模型得到的路线进行适当调整，得到最终的搜索线路安排图根据图表，计算出20个队员进行搜索需要50.117小时，无法在48内完成搜索任务 考虑到队员和组长距离不超过1000米，设计一种让20名搜索队员组成的队伍和新增人员组成的队伍进行交替行进的模型，以确保让整个搜索过程控制在48小时以内最后给出了该行进模型的相应算法，通过计算，得出增加2个队员可以确保搜索在48小时内完成。

问题二的求解中，首先对50名人员分3组进行分析，由于矩形区域被分割后形成的小区域恰好能被20人组成的一个队列一次搜索覆盖，以及10人组成的一个队列一个来回的搜索覆盖，于是3组可分为：2个队伍为20人，1个队伍为10人随后进行队伍搜索区域的划分，根据各个队伍人数确定该组分配到的方格的数量，划分出各个队伍的搜索区域然后对三个区域进行搜索路径的优化求解，改进问题一的模型，求出三个区域的搜索路径再根据实际情况，对路径进行适当修改，得出20人的2个队伍，需要19.816小时，10人的队伍需要20.294小时根据先完成搜索任务的队伍能否有足够的时间来帮助未完成搜索任务的队伍提早完成任务的时间要求，判断出该解是可以接受的于是得到50人进行搜救的时间为20.294小时最后，对文中的模型进行了优缺点的分析关键词：搜索模型；最优路径；一笔画；遍历网格；转弯策略一、问题重述有一个平地矩形目标区域，大小为11200米×7200米，需要进行全境搜索假设：出发点在区域中心；搜索完成后需要进行集结，集结点（结束点）在左侧短边中点；每个人搜索时的可探测半径为20米，搜索时平均行进速度为0.6米/秒；不需搜索而只是行进时,平均速度为1.2米/秒。

每个人带有GPS定位仪、步话机，步话机通讯半径为1000米搜索队伍若干人为一组,有一个组长，组长还拥有卫星每个人搜索到目标，需要用步话机及时向组长报告，组长用卫星向指挥部报告搜索的最新结果现在有如下问题需要解决：1．假定有一支20人一组的搜索队伍, 拥有1台卫星请设计一种你认为耗时最短的搜索方式按照你的方式，搜索完整个区域的时间是多少? 能否在48小时内完成搜索任务? 如果不能完成，需要增加到多少人才可以完成2．为了加快速度，搜索队伍有50人，拥有3台卫星，分成3组进行搜索每组可独立将搜索情况报告给指挥部门请设计一种你认为耗时最短的搜索方式按照你的搜索方式, 搜索完整个区域的时间是多少?二、模型假设1. 假设搜索必须完全，不存在遗漏情况2. 假设如果发现需要救助的人员，只需报告组长，不影响其搜索速度3. 假设救援人员进食休息的时间不计4. 队员间不能间接向组长报告情况5. 假设每组队员只能向本组组长报告6. 假设队员的身体和心理状态不影响进度7. 假设搜索区域地面状况不影响搜索速度8. 假设设备在搜索过程中都正常工作三、 符号说明 20人排成队列的长度 增加的人数 不搜索时候行进的速度 搜索时候行进的速度 搜索需要花费的时间 搜索时间的各个组成部分 表示矩形分割后的区域的标号 表示标号为的区域的各个方向的连接数 表示1个180度转弯需要多耗费的时间 表示1个90度转弯需要多耗费的时间四、问题分析 本题针对一块矩形区域进行全境搜索问题,在保证全部搜索到的情况下，使搜索时间最短，我们将20人看成排成一排的整体,并将大的矩形区域划分为126个以800米为边长的正方形小区域，根据图论中的一笔画问题,以转弯最少为约束条件进行LINGO编程，计算出搜索路径.当队伍增加为3时，先根据人数比例进行大体的区域划分，然后在根据问题1的求解方法，计算出三个队的最优路径。

五、模型的建立与求解5.1 求解问题一5.1.1建立队伍前进和转弯模型： 由于每个搜索队员的搜索半径为20米，为了简化模型，把20名搜索队员排成一条直线，其中队长处于中间，这样就更好的保证了队员与队长的通讯： 总长为800米共20个 图(1-1) 搜索时候可以把20人组成的队列看作一条长800米的直线，搜索方向是沿着直线的垂线的方向，直线行进的速度为搜索的速度如下图所示，直线向其垂线方向进行时，会形成一个矩形轨迹，见图(1-2) 800米移动方向 图(1-2) 但需要进行转弯时，分为2种情况，180度转弯和90度转弯：1、180度转弯：图(1-3) 如图(1-3)所示，原直线沿着AB 边向右移动，当到达CD边时，整体向上移动，使得原CD边与EC边重合，然后EC边继续向左边运动，搜索遇难人员由 得， 即过180度的弯需要多耗费的时间2、90度转弯CDoAB图(1-4)如图(1-4)所示，原直线沿着AB 边向右移动，当到达CD边时，直线上处于C点的人向O点运动，D点上的人向C点运动，点，直线中间的人员依然可以找到合适的路径向OC边移动，使得CD与CO重合，然后CO边继续向上边运动，搜索遇难人员。

容易得出，该调整过程也需要的时间，即由以上2个转弯模型，可以得出，转弯的时间为5.1.2建立搜索路线模型：如表(1-1)所示，把矩形区域划分为如下小块，并且标号为：表(1-1)123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126 根据图论中关于奇顶点个数为偶数就能一次走完全程而不重复行走的原理，判断出这些方格可以用一条不重复的线路走完 由于出发点在矩形区域中央，即和交线的中点处，设定搜索队首先进入区域，然后在搜索完全部区域后，最后回到，过程是一笔画成的，没有重复，由于在转弯时，需要额外花费时间来进行调整，所以，当转弯数为最少时，是该题目的最优解答。

如表(1-1)可以看出：矩形中的各个小区域在前后左右有另外的小区域与其相邻（边界的区域较特殊，可能某个方向没有相邻的区域）把各个小区域看成一个点，如果要进行一笔画，则除了开始点只有一个出口和结束点只有一个入口，每个点均有两个接口与其他区域连接 （1）一个点有上下左右四个方向，用字母表示这个点在方向上是否与其它点连接，1为连接，0为不连接，分别表示上下左右四个方向以2个特殊的点为例，如： 点：由于在顶角，则其上边和左边必定没有连接，所以，， 点：由于在下边沿，则其下边必定没有连接，所以 全面的表示出这些点的特征，表达式为：（2）由于每个点的连接个数只能为2个（除外）， 所以，（3）如果有2个点，一个点的左边与另一个点连接，则另一个点的右端必定与该点连接基于这个原则，得到如下表达式： （4）为了判定在一个点处是否转弯，只要判定该点的2个接口是否为上和下，或者左和右，当一个为上，一个为下，可以说明该点处不转弯；当一个为左，一个为右，也可以说明该点处不转弯用表达式来表示如下： 当时，为不转弯 根据以上（1）（2）（3）（4）四点，可以转化为一个优化问题的求解。

目标函数：约束条件：，用LINGO编写程序（见附录），可以得到对应的上下左右四个方向是否有连接的数据，根据数据可以表示出其路线图为了方便观看，用线路图表示路线如图(1-5):图(1-5) 如图(1-5)可知，通过LINGO软件解决了不重复和弯角最小的问题，可是其没有解决一笔画问题，在图中出现了一个闭合的路径，不和其他路径进行相连接，由于程序为我们解决了不重复和弯角最小的问题，我们如果进行适当的微调，对最优结果的影响是很微小的观察图形，对那个闭合路径进行修改，使得他和其他路径相连接 对图像的调整结果如下：图（1-6） 如图(1-6)所示该路线经过了所有的区域，一共需要转弯17个，则转弯所需的时间为 除转弯外的时间外，其余时间设都为搜索前进，为 得， 由于在开始搜索时，所有队员都处在矩形区域中央，即左边沿的中点处，为了让队员排列成一条直线，则所有队员向两边散开，使其均匀分布在左边沿，这一过程需要耗费的时间为得， 在搜索结束时候，所有队员都均匀分布在的下边沿，为了让他们到达集合地点（的左边沿的中点），需要耗费的时间为得，则所以搜索完整个区域的时间是50.117小时，不能在48小时内完成搜索。

5.1.3建立增加人数的模型 为了满足能够在48小时内搜索完成搜索任务，决定增加人数为，这个人的作用就是为了帮助原20个人的队伍分担部分搜索区域，来达到原20人的队伍能在48小时内完成搜索任务的目的队伍搜索区域的时间包括，其中是最有可能进行优化的数据，也是可以减少幅度最大的时间因素让增加的个人在这段时间里发挥作用，来减少建立模型：只考虑队员搜索所有路线的时间，由于不转弯所以队员行进路线可视为一条直线把原20人和新增加的个人分为2个队伍，只要个人的队伍离原20人的队伍距离不超过1000米，就可以和组长保持连续，但两队伍的搜索是独立完成的ABCDE 图（1-7） 如图(1-7)，可以把行进路线分割为一大一小交替的段落其中A为原20人队伍搜索的区域，B为增加。