年全国大学生数学建模竞赛封面.pdf

2008200820082008 年全国大学生数学建模竞赛封面年全国大学生数学建模竞赛封面年全国大学生数学建模竞赛封面年全国大学生数学建模竞赛封面 承 诺 书承 诺 书承 诺 书承 诺 书 选择题号选择题号选择题号选择题号 在方格内打 我们承诺我们承诺我们承诺我们承诺 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则 我们完全明白 在竞赛开始后参赛队员不能以任何方式 包括电话 电子邮件 网上咨询等 与队外的任何人 包括指导教师 研究 讨论与 赛题有关的问题 我们知道 抄袭别人的成果是违反竞赛规则的 如果引用别人的成果 或其他公开的资料 包括网上查到的资料 必须按照规定的参考文献的 表述方式在正文引用处和参考文献中明确列出 我们郑重承诺 严格遵守竞赛规则 以保证竞赛的公正 公平性 如有违反竞赛规则的行为 我们将受到严肃处理 学校名称学校名称学校名称学校名称 温州大学城市学院 学生姓名学生姓名学生姓名学生姓名 陈 胜 薛良赞 涂一波 指导教师指导教师指导教师指导教师 数模组 只能填 1 名 否则为 数模组 全国大学生数学建模竞赛浙江赛区组委会制全国大学生数学建模竞赛浙江赛区组委会制全国大学生数学建模竞赛浙江赛区组委会制全国大学生数学建模竞赛浙江赛区组委会制 二二二二 八年九月八年九月八年九月八年九月 甲甲甲甲组组组组 A B 乙乙乙乙组组组组 C D 2008 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 编编编编 号号号号 专专专专 用用用用 页页页页 赛区评阅编号 由赛区组委会评阅前进行编号 赛区评阅记录 可供赛区评阅时使用 评 阅 人 评 分 备 注 全国统一编号 由赛区组委会送交全国前编号 全国评阅编号 由全国组委会评阅前进行编号 1 有限区域地面搜索问题的研究 摘要 本文首先建立了一个在保证全面搜索 每个队员与组长的距离不超过 1000m 的约束条件下完成整个搜索任务最短用时的抽象优化模型 为了将模型具体化 我们采用了 修剪草坪 式的搜索方案 将小组的成员 等间距 探测仪半径的 2 倍 地排成一排 保证每个队员与组长相距不超过 1000m 最短用时问题就转换为最少重复覆盖问题 在此基础上设计了 4 种覆 盖方法 算得最短用时 49 63 小时 为了在 48 小时内完成该任务 在保证每个 队员与组长相距不超过 1000m 的前提下必须减少搜索的次数 基于此 需要增 加 3 个人 我们给出最优搜索方案并求出最短的搜索时间为 44 58 小时 将参加搜索的队员增加到 50 人 分成三组进行搜索 在最短的时间内完成 搜索任务 实际是有限区域上的任务均衡分配问题 三个组分配的任务多少与其 任务区域位置 该组的人数有关 任务区域位置离集结点越远 分配的任务应越 少 小组人数越少 分配的任务也应越少 由于整个搜索区域是对称的 组数为 奇数 在分配任务时应尽量使其中 2 组的人数相等 我们从理论上和具体的搜索 用时两个方面证明了按照 20 10 20 的队员分配方案完成整个搜索任务的用时 最短 并进一步寻找按 20 10 20 队员分配的的最优搜索方案 得出 50 人 分 成三组进行搜索的最短用时 20 37 小时 关键词关键词关键词关键词 抽象优化模型 修剪草坪 式搜索 覆盖 2 一 问题重述 5 12 汶川大地震使震区地面交通和通讯系统严重瘫痪 救灾指挥部紧急派 出多支小分队 到各个指定区域执行搜索任务 以确定需要救助的人员的准确位 置 现在需要制定搜索队伍的行进路线 对预定区域进行快速的全面搜索 将具体问题简化为如下的搜索问题 对一个大小为 11200m 7200m 的平地 矩形目标区域进行全境搜索 出发点在区域中心 搜索完成后需要进行集结 集 结点 结束点 在左侧短边中点 每个人搜索时的可探测半径为 20m 搜索时平 均行进速度为 0 6m s 不需搜索而只是行进时 平均速度为 1 2m s 每个人带有 GPS 定位仪 步话机 步话机通讯半径为 1000m 搜索队伍若干人为一组 有一 个组长 组长还拥有卫星电话 每个人搜索到目标 需要用步话机及时向组长报 告 组长用卫星电话向指挥部报告搜索的最新结果 需要解决两个问题 1 假定有一支 20 人一组的搜索队伍 拥有 1 台卫星电话 设计一种我们认 为耗时最短的搜索方式并确定按该种方式搜索完整个区域的时间 如果不能在 48 小时内完成搜索任务 算出需要增加到几人才可以完成搜索任务 2 假如搜索队伍有 50 人 拥有 3 台卫星电话 分成 3 组进行搜索 每组可 独立将搜索情况报告给指挥部门 设计一种我们认为耗时最短的搜索方式并确定 搜索完整个区域的时间 二 模型假设 1 地震之后地面搜索路径无堵塞状况 2 搜索区域无余震 次生灾害发生 3 每人带的食物和生活用品等装备充足 4 假定在搜索时将所有队员排成一排 以便无论组长在什么位置每个队员都 能及时向组长报告 三 符号说明 a 平地矩形目标区域的长边 b 平地矩形目标区域的短边 N 参加搜索的人数 c 所有人排成一排的长度 n 线路经过 n 次转弯 1 v 搜索时平均行进速度 2 v 不需搜索而只是行进时的平均速度 T 搜索所需时间 R 20 搜索仪可探测的半径 0 S 需要搜索的整个区域面积 i t 第i个人从区域中心搜索到集结点所用的时间 1 i l 任意时刻第i个队员与组长的距离 3 i S 第i个人完成的搜索面积 四 模型建立及求解 问题一分析问题一分析问题一分析问题一分析 1 第 1 小问要解决的问题是 N 个人在始终保持与组长相距 1000m以内的 条件下如何在最短的时间内以最快的速度搜索完整个区域 根据这一问题 建立 如下的抽象优化模型 12 120 1 1 1000 N N ii i i max t t t S v v tS l 目标函数 约束条件 这个抽象模型很难求解 在假设 4 下 采用 修剪草坪 式的搜索前进 将 耗时最短 的目标转化为 在满足探测仪搜索的面积全部覆盖整个搜索区域 的前提下 20 个人排成一排前进的时候重复搜索的面积最小 为解决这个问题 我们尝试了多种搜索方案 在保证全面搜索 每个队员与组长的距离不超过 1000m 的约束条件下 要 求用时最短 则需要转弯越少越好 以下是关于转弯问题的两种方案 方案一 图 1 图 2 假设 10 个人排成一排 图 1 每个格子是 400m 400m 当 区域拐弯到 区 域 区域 路径只要行进 388m就能使整个区域全部搜索到 已知人的探测范围 在 20m以内 如果只行进 380m 区域 右上角 如图 2 所示 会存在一个盲区 因为 1 41R R 所以为了搜索到所有的面积范围 行进路线增加达到 388m 当他 们走到拐弯处时 行进路径只要 388m就可以完成区域 的完全搜索 4 图 3 将区域 模拟成图 3 10 个人从左往右行进 388m 行进速度是 0 6m s 然 后往下方移 移动到相对应的位置 速度为 1 2m s 经 maple 计算得到如下 9 个人的移动距离 x 9370 1675297 x 8337 6151655 x 7312 x 6295 1338679 x 5288 5550207 x 4292 9573349 x 3307 8701025 x 2331 8794962 x 1363 1859028 其中最大距离为370 2m 搜索队伍搜索好 区域往下行进所花费时间 T 370 2 1 2 3600 0 086h 每次转弯的时候 搜索队员们都是走交叉的路线 速度是1 2m s 因为没有 进行搜索任务 所以在此期间 队员们可以做些适当的调整 可以吃些干粮 喝 点水 以更加充分的精力去迎接接下去的搜索工作 方案二 图4 队伍从区域 一直走到底到达区域 然后并排往区域 移动 其中所经历 的时间T 400 1 2 3600 0 092h 5 经过仔细分析研究得出 选择方案二更好 因为方案二走的路线整齐 时间 和方案一相差不大 方案二更便于管理 更符合实际情况 并且整排队伍一起并 排行进 途中可以互相交流搜索心得 可以一起唱唱歌 放松下紧张心情 吃点 干粮补充能量 在搜索过程中 每位搜索员的任务都是艰巨的 他们在工作的时 候不能有一丝放松 但是这样长时间的负荷工作 会导致队员们不能集中精神 容易产生疲倦感 所以有这么一个环节 让队员们放松一下 我们认为是非常必 要的 下文所讨论的模型 都是按照方案二这种转弯方法 于是 得到最优的搜 索路径如图5 图 5 行走路线说明 将整个搜索区域划分为11个区域 每个区域的宽为800m 20个人 并排站立 任意2个人间距为40m 的长为4800m 的长为5600m 的长为 10400m 的长为 7200m 20个人站成一排作为一个整体 先从区域的中心向右搜索 4800m 然后整体向下走 800m转到 号矩形 一直搜 索到最左边界 再整体向下走 800m转到 号矩形 向右搜索 10400m 向下转到 号矩形 一直搜索到最左边界 再整体向下走 800m 转到 号矩形 向右搜索 11200m 转到 号矩形 一直搜索到最上边界 然后整体向左走 800m转到 号 矩形 一直搜索到最左边界 再整体向下走 800m转到 号矩形 向右搜索 10400m 向下转到 号矩形 一直搜索到最左边界 再整体向下走 800m转到 号矩形 向右搜索 10400m 向下转回 号矩形 在一直向右搜索转到 号矩形 直到集 结点 所以搜完整个区域所需的时间为 搜索区域 的矩形的时间 号矩形 6 已搜索过 的时间 每次转弯所花的时间 根据以上所述建立模型 I 模型 I T a 2 c v1 8 ac v1 a 2 v1 b v1 n c v2 a 2 c v2 1 化简得 T 9 ac b v1 n c 1 2 ac v2 2 已知 a 11200m b 7200m c 800m v1 0 6m s v2 1 2m s n 10 次 把已知条件带入式子 2 得 T 9 11200 800 7200 0 6 3600 10 800 11200 2 800 1 2 3600 解得 T 49 63h 因为 49 63h 48h 说明不能在 48 小时内完成搜索任务 对于此问题我们还设计了几种线路 线路 1 如图 6 图 6 线路1完成其任务所花的时间用 maple 计算得 T 5600 800 0 6 11200 800 4 0 6 6 800 1 2 7200 0 6 6 3600 0 6 10 800 1 2 4 800 0 6 7 3600 0 6 15 800 1 2 3600 53 70370369h 7 线路2 如图7 图 7 线路2完成其任务所花的时间用 maple 计算得 T 5600 800 0 6 11200 800 6 0 6 8 800 1 2 7200 0 6 6 1600 0 6 7 2 400 0 6 25 800 1 2 3600 52 7777779h 线路3 如图8 8 图 8 线路3完成其任务所花的时间用 maple 计算得 T 5600 800 5 0 6 5 800 1 2 7200 0 6 7 800 1 2 6 4800 0 6 4 800 1 2 4 5600 0 6 11 800 1 2 3600 0 6 2400 4 0 6 1600 3 0 6 2 4800 0 6 3600 55 92592592h 综合比较四种线路的优缺点 我们可以看出模型I的线路最优 最符合我们 的要求 2 第 2 小问分析 20 个人站成一排作为一个整体搜索整个区域所花的时间为49 63h 给人的 第一感觉是只需加一个人就可以在 48 小时内完成搜索任务 其实不然 因为其 余 20 个人和组长相距的最大距离不超过 1000m 即 21 个人仍然要作为一个整体 来搜索 沿矩形长边搜索的次数不会减少 为了在 48 小时内完成搜索任务 按照上述的搜索方式 必须少搜索一次 即少搜索一个小矩形条 这样才可能节省一个多小时 7200 8 900 即每搜索一 次 至少要搜索 900m的宽度 900 40 22 5 至少需要 23 人才可能在 48 小时内 完成搜索任务 行走路线如图 9 图 9 行走路线说明 将整个搜索区域划分为10个区域 每个区域的宽为920m 与 的 宽为760m 23个人并排站立 任意2个人间距为40m 的长为4680m 的长为5600m 的长为 10280m 的长为 7200m 23个人站成 一排作为一个整体 先从区域的中心向右搜索 46800m 然后整体向下走 920m转 到 号矩形 一直搜索到最左边界 再整体向下走 920m转到 号矩形 向右搜 索 10280m 向下转到 号矩形 一直搜索到最左边界 再整体向下走 920m转到 号矩形 向右搜索 11200m 转到 号矩形 一直搜索到最上边界 然后整体 9 向左走 920m转到 号矩形 一直搜索到最左边界 再整体向下走 920m转到 号 矩形 向右搜索 10280m 向下转到 号矩形 一直搜索到最左边界 再整体向 下走 920m转到 号矩形 向右搜索 4680m 再往回 号矩形搜索 直到集结点 完成其任务所花的时间用maple计算得 5600 920 0 6 9 920 1 2 7200 0 6 7 11200 920 0 6 5600 920 1 2 5 600 0 6 760 1 2 3600 44 58333331h 因为 44 58333331h 48h 所以符合要求 因此需要增加到 3 人才可以完成 在 48 小时内完成搜索任务 第二问的分析第二问的分析第二问的分析第二问的分析 将50个人分成 3 组进行搜索 要在尽量短的时间内完成搜索任务 实际是 任务的均衡分配问题 在分配任务时尽量使这 3 组完成任务所用的时间大致相 同 三个组分配的任务多少与其任务区域位置 该组的人数有关 任务区域位置 越远 分配的任务应越少 小组人数越少 分配的任务也应越少 整个搜索区域 是对称的 组数是奇数 所以在分配任务时也尽量对称 方案一 证明 按照 草坪修剪 式搜索 分组人数为 20 20 10 用时最短 首先 在按 草坪修剪 式搜索过程中 仅采用一条沿整个搜索区域矩形宽 的方向搜索 其余均为沿矩形长的方向搜索 为了尽可能的减少重复走已经搜索 过的区域 将整个矩形区域的宽分成 9 份是最佳的 中间的小矩形条的宽度可以 灵活改变 其余 8 个小矩形的宽必须相等 大于等于 20 40 小于 23 40 在这个前提下 有以下的搜索路径 图10 注 x为每个小长矩形的宽 将50个人分为3组 上下两组对称 因为路径一样 最终到达终点的时间 10 一样 所以计算出第一组所用时间即可 第一组所行进的路程从 开始沿着箭头 标示走直到达终点 将7200分为9段 上下两边对称 设变量x 中间的小矩形 条的宽为7200 8x 图10最左边矩形的宽度也为x 完成这个区域搜索任务的时间 T为 T 7200 8 x 2 x 1 2 5600 0 6 3 11200 x 0 6 4 x 1 2 3600 0 6 x 1 2 3600 T 20 648148150 0009259259261x 3 由式 3 可知时间T是x的减函数 又因为800920 x 可以将50人分为以下几种情况 20 20 10 21 21 8 22 22 6 随着第一组人数的增多 第一组完成搜索任务的时间在不 断的减少 第二组完成搜索任务的时间在增加 为了使完成所有搜索任务的时间 最短 三个组完成各自任务的时间应该大致一样 所以第一组的人数应该减少 第二组的人数相应要增加 即在 22 6 22 21 8 21 20 10 20 这 三种队员分配方案中 20 10 20 是最佳的 完成任务的时间最短 接下来分别算出按这三种人员分配方案完成整个搜索任务的时间 以验证上 述的判断 图11 第二组所进行的区域如图11所示 情况一 将50人分为22 6 22 即x 880m 经maple计算得出第一组时间 T 7200 8 x 2 x 1 2 5600 0 6 3 11200 x 0 6 4 x 1 2 3600 0 6 x 1 2 3600 T19 83333334 第二组时间 T 5600 0 6 5600 1 2 1920 2 1 2 8 4720 0 6 7 240 1 2 560 0 1 2 1920 2 1 2 3600 T23 50000000 综上所述按情况一的分配方法 最终所需要的时间为23 50h 情况二 将50人分为21 8 21 即x 840m 经maple计算得出第一组时间 T 7200 8 x 2 x 1 2 5600 0 6 3 11200 x 0 6 4 x 1 2 11 3600 0 6 x 1 2 3600 T19 87037037 第二组时间 T 5600 2 0 6 320 1 2 2160 2 1 2 7 320 1 2 8 4760 0 6 56 00 1 2 2160 2 1 2 3600 T25 20370371 综上所述按情况二的分配方法 最终所需要的时间为25 203h 情况三 将50人分为20 10 20 即x 800m 经MAPLE计算得出第一组时间 T 7200 8 x 2 x 1 2 5600 0 6 3 11200 x 0 6 4 x 1 2 3600 0 6 x 1 2 3600 T19 90740741 第二组时间 T 5600 2 0 6 400 1 2 2400 2 1 2 6 4800 0 6 5600 1 2 240 0 2 1 2 5 400 1 2 3600 T20 92592593 综上所述按情况三的分配方法 最终所需要的时间为20 92h 方案二 分区域 将整个搜索区域划分为3个 上下两个关于中间的区域对称 如图12 区域 I 区域 II 区域 III 图 12 队员分组 将 50 个人分为 3 组 第 1 第 3 两组各 20 人搜索的路线对称 区域 和区 域 第 2 组 10 人负责中间区域 区域 首先将第一组的 20 个人站成一 12 排 我们把它看成一段 800m的线段 如图 12 中 所示向左移动 800m 沿 方 向整体向上平移 800m 依次沿 至 的方向搜索 直到该组的20个人全部到达 集结点 在搜索过程中 搜索到达最左或右边界后再整体行走转弯 第三组的20个人行走 搜索的路线和方法与第一组是相同的 理论上他们 将同时到达集结点 第二组的 10 个人搜索区域 先排成一排以中心为起始点向左搜索 800m 然后整体向下行走 400m 再向右搜索直到最右边界 再向上行走 400m 向左搜 索 5600m到达中心位置 行走 800m到达最开始搜索的位置 向上行走 800m 向 左搜索 4000m 向下行走 400m 向右搜索 4000m 再向下行走 400m 将这个过程 重复 3 次 搜索完区域后 走回到集结点 第一组完成其任