文档介绍：地面搜索的数学模型
摘要
本文主要讨论设计了搜索11200米×7200米的矩形目标区域的优化路径,以保证对预定区域进行快速全面的搜索。
问题一,我们讨论了如何使20人一组的搜索队伍在最短时间完成搜索任务。首先将其转化为图论问题,得到距离图(图5-3),然后建立满足完全搜索的0-1规划模型【模型一】,(图5-4),,不能够在48小时内完成搜索任务。
为保证在48小时内完成搜索任务,采用减少搜索道即增加道宽的方法确定增加的最少人数。根据模型一建立了【模型二】和动态规划模型【模型三】,得到最终的搜索路径(图5-7),增加的最少人数为3人,分为8道,。模型二、三具有通用性,可给出任意搜索道数的最短搜索时间及规定48小时内完成搜索需要增加的人数(表5-1)。另外考虑改变搜索起始点的位置,建立了通用模型【模型四】,结合模型三求得不同分道数下完成搜索任务增加的最少人数和完成时间(表5-2),由模型四也得到分8道和增加最少3人能完成搜索任务,,比模型二优。
问题二,讨论了如何将50人分三组并选择最佳搜索路径,使搜索时间最短。把矩形分三个区域,按均分道宽和不均分道宽讨论。
对于均分搜索,确立了两种方式(图5-10、5-11),建立【模型五】求得最短搜索时间分别为图5--。结论是采用均分搜索以图5-10的搜索方式最优,但浪费的人员较多。
对非均分搜索,引入搜索横径与道宽相对差异度q,人数均衡度r等因子作为限制条件,建立规划模型【模型六】求得人员分组为16人、17人、17人;所划区域宽分别为2304米、2448米、2448米;,还是避免不了人员的浪费。
考虑浪费人员,建立规划模型【模型七】,得到在50个人的基础上,可以最大限度减少5人仍能在原来时间上完成搜索任务。此模型通过改进可以得到在规定时间规定组数或完成的搜索的人员分配,安排多少人来完成任务,也可以在实现在规定人数的人员分组问题,是一个推广性较好的数学模型。
关键词:路线转换;距离图;0-1规划;动态规划
问题重述
。救灾指挥部紧急派出多支小分队,到各个指定区域执行搜索任务。在这种紧急情况下需要解决的重要问题之一是:制定搜索队伍的行进路线,对预定区域进行快速的全面搜索。通常,每个搜索人员都带有GPS定位仪、步话机以及食物和生活用品等装备。队伍中还有一定数量的卫星电话。GPS可以让搜索人员知道自己的方位。步话机可以相互进行通讯。卫星电话用来向指挥部报告搜索情况。
下面是一个简化的搜索问题。有一个平地矩形目标区域,大小为11200米×7200米,需要进行全境搜索。假设:出发点在区域中心;搜索完成后需要进行集结,集结点(结束点)在左侧短边中点;每个人搜索时的可探测半径为20米,;不需搜索而只是行进时,。每个人带有GPS定位仪、步话机,步话机通讯半径为1000米。搜索队伍若干人为一组,有一个组长,组长还拥有卫星电话。每个人搜索到目标,需要用步话机及时向组长报告,组长用卫星电话向指挥部报告搜索的最新结果。
现在有如下问题需要解决:
, 拥有1台卫星电话。请设计一种你认为耗时最短的搜索方式。按照你的方式,搜索完整个区域的时间是多少? 能否在48小时内完成搜索任务? 如果不能完成,需要增加到多少人才可以完成。
,搜索队伍有50人,拥有3台卫星电话,分成3组进行搜索。每组可独立将搜索情况报告给指挥部门。请设计一种你认为耗时最短的搜索方式。按照你的搜索方式, 搜索完整个区域的时间是多少?
二、符号说明
:为0、1变量,表示是否选择某条路,其形式为表示不选择,
表示选择走该路;
:表示从第点到第点的路程距离,两点间没有路的用无穷大表示,自己到
自己距离为0;
:搜索道的宽度;
:起点到终点的直线距离为5600米;
:各个组的起点到各自的搜索起点的距离;
:第组的人数();
:第组所搜索的区域的宽度。
:搜索完成的最短总时间。
三、条件假设
;
;
;
四、问题分析
问题一:
[1~3]方式,为保证时间最短,首先要求20人每秒搜索的面积尽可能大,所以须并排相切站队。由于每人步话机的通讯半径为1000米,为保证每个搜索队员搜索到