2008年全国数学建模竞赛c题

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