全国数学建模竞赛C题ppt课件.ppt

2008全国赛C题 地面搜索 解法浅谈 1 各位专家 教练下午好 2 一 2008全国赛C题题目 5 12汶川大地震使震区地面交通和通讯系统严重瘫痪 救灾指挥部紧急派出多支小分队 到各个指定区域执行搜索任务 以确定需要救助的人员的准确位置 在其它场合也常有类似的搜索任务 在这种紧急情况下需要解决的重要问题之一是 制定搜索队伍的行进路线 对预定区域进行快速的全面搜索 通常 每个搜索人员都带有GPS定位仪 步话机以及食物和生活用品等装备 队伍中还有一定数量的卫星电话 GPS可以让搜索人员知道自己的方位 步话机可以相互进行通讯 卫星电话用来向指挥部报告搜索情况 3 下面是一个简化的搜索问题 有一个平地矩形目标区域 大小为11200米 7200米 需要进行全境搜索 假设 出发点在区域中心 搜索完成后需要进行集结 集结点 结束点 在左侧短边中点 每个人搜索时的可探测半径为20米 搜索时平均行进速度为0 6米 秒 不需搜索而只是行进时 平均速度为1 2米 秒 每个人带有GPS定位仪 步话机 步话机通讯半径为1000米 搜索队伍若干人为一组 有一个组长 组长还拥有卫星电话 每个人搜索到目标 需要用步话机及时向组长报告 组长用卫星电话向指挥部报告搜索的最新结果 现在有如下问题需要解决 4 问题1 假定有一支20人一组的搜索队伍 拥有1台卫星电话 请设计一种你认为耗时最短的搜索方式 按照你的方式 搜索完整个区域的时间是多少 能否在48小时内完成搜索任务 如果不能完成 需要增加到多少人才可以完成 问题2 为了加快速度 搜索队伍有50人 拥有3台卫星电话 分成3组进行搜索 每组可独立将搜索情况报告给指挥部门 请设计一种你认为耗时最短的搜索方式 按照你的搜索方式 搜索完整个区域的时间是多少 5 二 问题1的分析 1 对题意的理解 1 搜索完整个区域的时间 是指最后一名队员从出发点到达集结点所用的时间 2 能否在48小时内完成搜索任务 是指 纯工作 时间能否控制在48小时内 不包括进餐或休息时间 3 题目仅给出了搜索时的平均行进速度 并未给出队员停顿下来搜索一个半径为20米的圆形区域需要花费多少时间 因此对于搜索方式理解为在行进中连续或分段连续进行搜索 6 2 问题的分析 1 搜索时间下限的估计 需要搜索的面积为11200米 7200米 8064 104平方米 一个队员的搜索半径为20米 若将上述矩形区域划分成40 40的小正方形 共有50400个小正方形 20个队员 平均每个队员要搜索2520个小正方形 一个队员搜索一个小正方形的最短用时 直穿 40 0 6 66 67秒 转向 66 67秒 扫角 扫角 7 直穿 2520个小正方形需用时 下限 2 小组搜索方式的确定 队员之间要相互联络 不能分得太开 20个队员一字排开能搜索的宽度为800米 将待搜索的矩形区域分成126个800 800的正方形 依次完成这126个正方形的搜索 直穿 一个方块 每个队员需要搜索800米 8 转向 1号40米 2号40 3 120米 20号40 39 1560米 以上不包括 扫角 而每个队员需 扫角 一次 9 称1号为 内拐 20号为 外拐 三 模型的建立与求解 如果不包括 扫角 与重复搜索 小组搜索一个方块的距离为一定 1600米 因此优化的目标是转向最少 10 11 12 13 确定搜索线路的原则 A尽量避免 空走 B尽量避免 转向 一种近似解法 C尽量避免重复搜索 1 搜索线路的确定 14 红线代表1号 蓝线代表20号的搜索线路 15 2 搜索时间的确定 转向 32次 直穿 94次 具体1号内拐17次 外拐15次 20号内拐15次 外拐17次 20号最后到达集结点 20号搜索用时 20号出发及集结 空走 用时 20号总用时 47 73小时 16 3 解的可行性验证 组长放在什么位置 假设队员的信息在1000米的范围内可以相互交流 20号队员的信息可传达给19号队员 如此通过数次传递 最终到达组长处 为减少传递次数 将组长放在11号位 在搜索过程中 只要保持相邻两个队员的距离在1000米 就可以保证信息的传达 每 外拐 一次 相邻两个队员中靠外的那个落后80米 若其后有一次 内拐 则追回这80米 因此 只有连续 外拐 12次以上相邻两个队员间的距离才超过1000米 上述的搜索线路最多连续 外拐 5次 因此是可行的 综合上面的讨论 48小时内可完成搜索任务 17 四 问题2简解 分析 为了尽量利用第一问的解法 将50人分为20 20 10三组 对20人的组可直接利用前面的网格划分 对10人的组 可将前面的800 800的网格细分为400 400的网格 在分配各组任务时 尽量做到均衡 两个20人的组分配的搜索区域最好是对称的 18 19 20人组 转向8次 直穿 42格 20号外拐5次 内拐3次 20号搜索用时 20号 空走 用时 20号总用时 19 453小时 1号总用时 18 222小时 20 10人组 转向31次 直穿 69格 1号外拐17次 内拐14次 10号外拐14 内拐17次 1号搜索用时 1号 空走 用时 1号总用时 19 475小时 综上讨论 全部50名队员中10人组的1号最后到达 总用时 19 475小时 21 五 学生答卷中存在的问题 1 对题意缺乏理解 跳跃式瞬间搜索 进餐 休息问题 2 文章表述不清 许多无搜索线路图 6 对搜索线路未作可行性验证