2008年全国大学生数学建模竞赛C题获奖论文.pdf

《2008年全国大学生数学建模竞赛C题获奖论文.pdf》由会员分享，可在线阅读，更多相关《2008年全国大学生数学建模竞赛C题获奖论文.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 题目地面搜索问题摘要 我们经过认真读题，抓住了本题中的几个要点，分别是：每个人搜索时的可探测半径为 20 米；步话机通讯半径 为 1000 米；每个人搜索到目标，需要用步话机及时向组长报告；且搜索时 不能留一点死角。就这些约束条件进行分析，我们得到了“一个20 人每人隔 20 米排成一排一同沿一个路线前进”的方案。然后，我们根据总 时间最短 的原则，设计了一个不搜索只行进的距离最短的部队行进方案（如图一）。再是根据“不留一点死角”和“总时间最短”的原则，对180 度拐角处和 90 度拐角处，进行了认真地分析分别制定其通过方案（如图二、图三）。之后，便计算总路程（包括边行进边搜索的路程和不搜

2、索只行进的路程），分别除以其速度求 20 人搜索该区域时所用的时间。其时间大于48 小时，因此，要增加一人帮助其搜索。我们本着总时间 小于 48 小时的条件，分析了以上我们所建立的模型，认为：搜索时间是不能节省的，只行走的时间又过短，只能节省在过第一个180度弯时等待的时间（过第一个 180 度弯之后，最快与最慢的之间相差3040米，与步话机 1000米的通讯半径不符，所以，期间需等待0.48 小时）。故增加一人使他在过第一个180度弯时和之前帮助较慢的人员前进，以节省其等待时间。经计算最终时间小于48 小时。做第二问时我们用到第一问的数据，将50 人分成 20 人、20人和 10 人，再根据

3、人数按比例划分面积。之后，根据条件“搜索完成后需要进行集结”，对该区域进行了划分，并设计了各个小组的行进路线（如图四）。最终，搜索总时间为21.39 小时。关键词：步话机通讯半径、不能留一点死角、时间最短、小于 48 小时2 1 问题的重述5.12 汶川大地震使震区地面交通和通讯系统严重瘫痪。救灾指挥部紧急派出多支小分队，到各个指定区域执行搜索任务，以确定需要救助的人员的准确位置。在其它场合也常有类似的搜索任务。在这种紧急情况下需要解决的重要问题之一是：制定搜索队伍的行进路线，对预定区域进行快速的全面搜索。通常，每个搜索人员都带有GPS 定位仪、步话机以及食物和生活用品等装备。队伍中还有一定数

4、量的卫星电话。GPS可以让搜索人员知道自己的方位。步话机可以相互进行通讯。卫星电话用来向指挥部报告搜索情况。下面是一个简化的搜索问题。有一个平地矩形目标区域，大小为 11200米 7200米，需要进行全境搜索。假设：出发点在区域中心；搜索完成后需要进行集结，集结点（结束点）在左侧短边中点；每个人搜索时的可探测半径为20 米，搜索时平均行进速度为0.6 米/秒；不需搜索而只是行进时,平均速度为 1.2 米/秒。每个人带有GPS 定位仪、步话机，步话机通讯半径为1000 米。搜索队伍若干人为一组,有一个组长，组长还拥有卫星电话。每个人搜索到目标，需要用步话机及时向组长报告，组长用卫星电话向指挥部报

5、告搜索的最新结果。现在有如下问题需要解决：1假定有一支 20人一组的搜索队伍,拥有 1 台卫星电话。请设计一种你认为耗时最短的搜索方式。按照你的方式，搜索完整个区域的时间是多少?能否在 48 小时内完成搜索任务?如果不能完成，需要增加到多少人才可以完成。2为了加快速度，搜索队伍有50 人，拥有 3 台卫星电话，分成3 组进行搜索。每组可独立将搜索情况报告给指挥部门。请设计一种你认为耗时最短的搜索方式。按照你的搜索方式,搜索完整个区域的时间是多少?2 问题的分析与假设1.人员完全听从组长的安排，组长在队伍中间。2.假设搜索区域的地面规则平整，搜索任务不受天气地形等影响能不间断进行。3.假设记录通

6、讯时间为零。4.假设搜索过程完全按照题中路线图进行，无突发事件发生。3 模型的建立与求解3 3.1 关于模型 1（问题一）的建立与分析3.1.1 宏观路线的制定终点起点图一我们进过分析之后，打算采用20 人排成一排，一同前进，并根据一定的路线对该区域进行搜索。如图一为队伍行进路线图。要是总时间最少，则队伍行进过程中重复扫描时间最少，即，使徒步行进距离最短。经分析得，图一中，反复扫描时间较少。则我们认为此行进路线为最佳行进路线（图中每个方格为 800*800 的正方形）。3.1.2 180度与 90 度的拐弯方式2 号1 号4 图二图三在此行进路线中，有180 度和 90 度的拐角，为使其搜索没

7、有一点遗漏的地方，且考虑到 1000 米的步话机的通讯半径，我们对其进行了如下处理：180 度拐角，如图二（图简化成二个人在搜索，且每个小格为 40*40），搜索人员在到达应拐弯的方格时到达该格的下边缘，转个 90 度的弯贴着其边缘走到另一转弯格时再回转90 度沿着该格的中心向前走，如图二中外侧红线，在到达1 号格时转弯，到达 2 号格时再转弯；90度拐角，如图三（图三格式同图二，且蓝线为人员不搜索只行走的路程），搜索人员在到达应拐弯的方格时到达该格的下边缘，再往回退20 米到转弯格的中心，转90 度前进，并沿着方格的中心线。从图一得，180 度拐角有 14 个，90 度拐角有 2个。同时发现

8、 180度拐角为偶数个，且因为在拐弯时内测与外侧的路程不一，但在经过偶数个拐角之后，其路程有处于平齐，则为使计算简单拐180 度角的路程用其平均值。3.1.3 关于等待的考虑又经分析得，在拐第一个180 度角之后，最快与最慢的人员距离为3040 米（最慢的人员路程为 3160 米，最快的人员路程为120 米，3040120-3160），与步话机 1000米的通讯半径不服。为使其符合条件，我们使快的人员停下等慢的人员，要等1040米。经分析在过了第一个180 度的弯之后，再过其余的180 度弯时，其最快与最慢的相差的距离分别为 1040米、2000 米、1040 米、2000米 这样一直循环下去

9、，且都在步话机 1000 米的通讯半径之内，便不需考虑。3.1.4 模型计算最终，经计算得，队伍边搜索边行走的路程为102880 米，其时间约为 47.63小时；只行走的路程为 880 米，时间为 0.20小时；在第一个 180度拐角处，较快的人员要等较慢的人员 1040 米，时间为 0.48小时。最后，所需要总的时间约为48.31小时。则，不能在 48 小时内完成搜索任务。增加1 人便可完成任务。5 3.1.5 模型改进增加的这 1 人，让他分别在拐第一个弯前和拐第一个弯中去帮那些较慢的人员，以节省等待较慢人员的时间，来缩短总时间。为使总时间在 48 小时内，即，增加的人员要帮最慢的人员节约

10、至少0.31小时。当增加的人员帮助其他人员搜索1 米时，其节约的时间约为000231.036002.11-6.01小时/米。即，要帮助最慢的人员搜索1342000231.031.0米。经过以上分析得到，最慢与最快的人员相差3040 米，平均得：每人之间相差160米。即，增 加 的 人 员 要 帮 在 拐 第 一 个 弯 时 外 侧 第 二 个 人 员 节 约 至 少24.036006.0160-31.0小 时。即，要 帮 助 拐 第 一 个 弯 时 外 侧 第 二 个 人 员 搜 索1022000231.024.0米。同理得，帮外侧第三个人员701米，第四个人员 381 米，第五个人员 60

11、米，第六个人员0 米，其他的也为 0 米。则只需帮拐第一个180 度弯时外侧的五个人员向前搜索。经证明得，该模型能在48 小时内完成。3.2 关于模型 2（问题二）的建立与求解在问题一中我们把该区域分为126个 800 800 的网格，只有 20人的时候探测范围为 800米，所以我们把50 人的队伍分为 20、20、10，通过对图一的分析，我们得到图四为本题的路线（图中红线区域将800 800的正方形细分为400 400的）。终点起点6 10 人20 人（一组）20 人（二组）图四根据题一的数据，得：蓝线路与黄线路的时间为20.9小时；红线路的时间为21.39小时。最终，该模型所需时间为21.39小时。4 模型的评价与改进上诉模型的建立与求解，在假设中我们忽略了一些问题，在上述中我们假设通讯时间为零，但这在实际生活中可能会有所改变，但以上误差是可以允许的，亦是不可避免的。宏观评价一个事物的好坏应该从客观角度去分析，要使搜索时间最短，同时满足在中点出发在左端中点集结，同时要达到合理易操作，正是从客观角度去分析的，从这一角度分析也更符合实际情况。本模型具有以下优点：1、此模型是用实际数据进行检验计算，误差也是在可以允许的范围内，因此更具有实际应用价值。2、此模型具有的最大优点就是简洁实用，可以用来解决同类问题，适用范围广，推广性强。