2008年全国数学建模竞赛C题资料

1、各位专家、教练下午好！各位专家、教练下午好！第一页，编辑于星期一：八点 三十七分。一、一、2008全国赛全国赛C题题目：题题目： 5.12汶川大地震使震区地面交通和通讯系统严重瘫汶川大地震使震区地面交通和通讯系统严重瘫痪。救灾指挥部紧急派出多支小分队，到各个指定区域痪。救灾指挥部紧急派出多支小分队，到各个指定区域执行搜索任务，以确定需要救助的人员的准确位置。在执行搜索任务，以确定需要救助的人员的准确位置。在其它场合也常有类似的搜索任务其它场合也常有类似的搜索任务。在这种紧急情况下需在这种紧急情况下需要解决的重要问题之一是：制定搜索队伍的行进路线，要解决的重要问题之一是：制定搜索队伍的行进路线，

2、对预定区域进行快速的全面搜索。通常，每个搜索人对预定区域进行快速的全面搜索。通常，每个搜索人员都带有员都带有GPS定位仪、步话机以及食物和生活用品等定位仪、步话机以及食物和生活用品等装备。队伍中还有一定数量的卫星电话。装备。队伍中还有一定数量的卫星电话。GPS可以让可以让搜索人员知道自己的方位。步话机可以相互进行通讯。搜索人员知道自己的方位。步话机可以相互进行通讯。卫星电话用来向指挥部报告搜索情况。卫星电话用来向指挥部报告搜索情况。第二页，编辑于星期一：八点 三十七分。 下面是一个简化的搜索问题。有一个平地矩形目下面是一个简化的搜索问题。有一个平地矩形目标区域，大小为标区域，大小为11200米

3、米7200米，需要进行全境搜米，需要进行全境搜索。假设：出发点在区域中心；搜索完成后需要进索。假设：出发点在区域中心；搜索完成后需要进行集结，集结点（结束点）在左侧短边中点；每个行集结，集结点（结束点）在左侧短边中点；每个人搜索时的可探测半径为人搜索时的可探测半径为20米，搜索时平均行进速米，搜索时平均行进速度为度为0.6米米/秒；不需搜索而只是行进时秒；不需搜索而只是行进时,平均速度为平均速度为1.2米米/秒。每个人带有秒。每个人带有GPS定位仪、步话机，步话机定位仪、步话机，步话机通讯半径为通讯半径为1000米。搜索队伍若干人为一组米。搜索队伍若干人为一组,有一个有一个组长，组长还拥有卫星

4、电话。每个人搜索到目标，组长，组长还拥有卫星电话。每个人搜索到目标，需要用步话机及时向组长报告，组长用卫星电话向需要用步话机及时向组长报告，组长用卫星电话向指挥部报告搜索的最新结果。指挥部报告搜索的最新结果。现在有如下问题需要解决：现在有如下问题需要解决：第三页，编辑于星期一：八点 三十七分。问题问题1： 假定有一支假定有一支20人一组的搜索队伍人一组的搜索队伍, 拥有拥有1台卫星电话。台卫星电话。请设计一种你认为耗时最短的搜索方式。按照你的方式，请设计一种你认为耗时最短的搜索方式。按照你的方式，搜索完整个区域的时间是多少搜索完整个区域的时间是多少? 能否在能否在48小时内完成搜小时内完成搜索

5、任务索任务? 如果不能完成，需要增加到多少人才可以完成。如果不能完成，需要增加到多少人才可以完成。 问题问题2： 为了加快速度，搜索队伍有为了加快速度，搜索队伍有50人，拥有人，拥有3台卫星台卫星电话，分成电话，分成3组进行搜索。每组可独立将搜索情况报组进行搜索。每组可独立将搜索情况报告给指挥部门。请设计一种你认为耗时最短的搜索告给指挥部门。请设计一种你认为耗时最短的搜索方式。按照你的搜索方式方式。按照你的搜索方式, 搜索完整个区域的时间是搜索完整个区域的时间是多少多少? 第四页，编辑于星期一：八点 三十七分。二、问题二、问题1的分析的分析1、对题意的理解、对题意的理解（1）搜索完整个区域的时

6、间）搜索完整个区域的时间,是指最后一名队员从出是指最后一名队员从出发点到达集结点所用的时间发点到达集结点所用的时间.（2）能否在）能否在48小时内完成搜索任务小时内完成搜索任务,是指是指“纯工作纯工作”时时间能否控制在间能否控制在48小时内，不包括进餐或休息时间小时内，不包括进餐或休息时间.（3）题目仅给出了搜索时的平均行进速度，并未给）题目仅给出了搜索时的平均行进速度，并未给出队员停顿下来搜索一个半径为出队员停顿下来搜索一个半径为20米的圆形区域需要米的圆形区域需要花费多少时间，因此对于搜索方式理解为在行进中连花费多少时间，因此对于搜索方式理解为在行进中连续或分段连续进行搜索续或分段连续进行

7、搜索.第五页，编辑于星期一：八点 三十七分。2、问题的分析、问题的分析（1）搜索时间下限的估计）搜索时间下限的估计需要搜索的面积为需要搜索的面积为11200米米7200米米=806410104 4平方米，平方米，一个队员的搜索半径为一个队员的搜索半径为20米，若将上述矩形区域划分成米，若将上述矩形区域划分成4040的小正方形，共有的小正方形，共有50400个小正方形，个小正方形，20个队员，平均每个队员个队员，平均每个队员要搜索要搜索2520个小正方形个小正方形.一个队员搜索一个小正方形的最短用时一个队员搜索一个小正方形的最短用时“直穿直穿”40/0.6=66.67秒秒“转向转向”66.67秒

8、秒“扫角扫角”秒秒7120216011220.).)(+“扫角扫角”秒秒转转向向用用时时3887.第六页，编辑于星期一：八点 三十七分。“直穿直穿”2520个小正方形需用时个小正方形需用时小时小时秒秒66946416800867662520.（下限）（下限）（2）小组搜索方式的确定）小组搜索方式的确定队员之间要相互联络，不能分得太开，队员之间要相互联络，不能分得太开，20个队员一字个队员一字排开能搜索的宽度为排开能搜索的宽度为800米，将待搜索的矩形区域分米，将待搜索的矩形区域分成成126个个800 800的正方形，依次完成这的正方形，依次完成这126个正方形个正方形的搜索的搜索.“直穿直穿”

9、一个方块，一个方块，每个队员需要搜每个队员需要搜索索800米米第七页，编辑于星期一：八点 三十七分。号号1号号2号号20“转向转向”1号号40米米2号号403 =120米米20号号4 4039=1560米米以上不包括以上不包括“扫角扫角”，而每个队员而每个队员需需“扫角扫角”一次一次第八页，编辑于星期一：八点 三十七分。称称1号为号为“内拐内拐”，20号为号为“外拐外拐”秒秒内拐一次用时内拐一次用时3887.秒秒外拐一次用时外拐一次用时712620.三、模型的建立与求解三、模型的建立与求解如果不包括如果不包括“扫角扫角”与重复搜索，小组搜与重复搜索，小组搜索一个方块的距离为一定（索一个方块的距

10、离为一定（1600米），因米），因此优化的目标是转向最少。此优化的目标是转向最少。第九页，编辑于星期一：八点 三十七分。第十页，编辑于星期一：八点 三十七分。( )0(1,2,.,9;1,.,14;1,2,3,4)1kijxijk 4( )12kijkx (3)(1)(3)(1)11(1)(1)1(113)ijijijijxxxxj (2)(4)(2)(4)1,1,(1)(1)1(18)ijijijijxxxxi 第十一页，编辑于星期一：八点 三十七分。914(1)(2)(2)(3)(3)(4)(4)(1)11()ijijijijijijijijijxxxxxxxx min( )0(1,2,.

11、,9;1,.,14;1,2,3,4)1kijxijk 4( )12,(1,2,.,9;1,.,14)kijkxij (3)(1)(3)(1)11(1)(1)1(113)ijijijijxxxxj (2)(4)(2)(4)1,1,(1)(1)1(18)ijijijijxxxxi . .s t第十二页，编辑于星期一：八点 三十七分。确定搜索线路的原则确定搜索线路的原则A 尽量避免尽量避免“空走空走”B 尽量避免尽量避免“转向转向”一种近似解法一种近似解法C 尽量避免重复搜索尽量避免重复搜索1、搜索线路的确定、搜索线路的确定第十三页，编辑于星期一：八点 三十七分。红线代表红线代表1号、蓝线代表号、蓝

12、线代表20号的搜索线路号的搜索线路第十四页，编辑于星期一：八点 三十七分。2、搜索时间的确定、搜索时间的确定“转向转向”32次次, “直穿直穿”94次次具体具体1号内拐号内拐17次，外拐次，外拐15次；次；20号内拐号内拐15次，外拐次，外拐17次，次，20号最后到达集结点号最后到达集结点.20号搜索用时：号搜索用时：秒秒1171196712620173887156080094.小时小时5547.20号出发及集结号出发及集结“空走空走”用时：用时：小小时时秒秒176033633213802.20号总用时：号总用时：47.73小时小时第十五页，编辑于星期一：八点 三十七分。3、解的可行性验证、解

13、的可行性验证组长放在什么位置？组长放在什么位置？ 假设队员的信息在假设队员的信息在1000米的范围内可以相互交流，米的范围内可以相互交流，20号号队员的信息可传达给队员的信息可传达给19号队员，如此通过数次传递，最终号队员，如此通过数次传递，最终到达组长处，为减少传递次数，将组长放在到达组长处，为减少传递次数，将组长放在11号位号位.在搜索在搜索过程中，只要保持相邻两个队员的距离在过程中，只要保持相邻两个队员的距离在1000米，就可以米，就可以保证信息的传达保证信息的传达. 每每“外拐外拐”一次，相邻两个队员中靠外的那个落后一次，相邻两个队员中靠外的那个落后80米，米，若其后有一次若其后有一次

14、“内拐内拐”，则追回这，则追回这80米，因此，只有连续米，因此，只有连续“外拐外拐”12次以上相邻两个队员间的距离才超过次以上相邻两个队员间的距离才超过1000米，上米，上述的搜索线路最多连续述的搜索线路最多连续“外拐外拐”5次，因此是可行的次，因此是可行的.综合上面的讨论，综合上面的讨论，48小时内可完成搜索任务小时内可完成搜索任务第十六页，编辑于星期一：八点 三十七分。四、问题四、问题2简解简解分析：分析： 为了尽量利用第一问的解法，将为了尽量利用第一问的解法，将50人分为人分为20；20；10三组；对三组；对20人的组可直接利用前人的组可直接利用前面的网格划分；对面的网格划分；对10人的

15、组，可将前面的人的组，可将前面的800800800的网格细分为的网格细分为400400的网格的网格. 在分配各组任务时，尽量做到均衡，两个在分配各组任务时，尽量做到均衡，两个20人的组分配的搜索区域最好是对称的人的组分配的搜索区域最好是对称的.第十七页，编辑于星期一：八点 三十七分。第十八页，编辑于星期一：八点 三十七分。20人组人组转向转向8次，次，“直穿直穿”42格格20号外拐号外拐5次，内拐次，内拐3次次20号搜索用时：号搜索用时：秒秒95693657126205388736080042.小小时时26819.20号号“空走空走”用时：用时：小小时时秒秒18506766621380420.

16、20号总用时：号总用时：19.453小时小时1号总用时：号总用时：18.222小时小时第十九页，编辑于星期一：八点 三十七分。10人组人组转向转向31次，次，“直穿直穿”69格格1号外拐号外拐17次，内拐次，内拐14次；次；10号外拐号外拐14，内拐，内拐17次次1号搜索用时：号搜索用时：秒秒7269108388714381287176040069.小时小时19719.1号号“空走空走”用时：用时：小时小时秒秒278010002120800380.1号总用时：号总用时：19.475小时小时综上讨论，全部综上讨论，全部50名队员中名队员中10人组的人组的1号最号最后到达，总用时：后到达，总用时：19.475小时小时第二十页，编辑于星期一：八点 三十七分。五、学生答卷中存在的问题五、学生答卷中存在的问题1.对题意缺乏理解对题意缺乏理解“跳跃式瞬间搜索跳跃式瞬间搜索”“进餐、休息问题进餐、休息问题”2.文章表述不清文章表述不清许多无搜索线路图许多无搜索线路图6.对搜索线路未作可行性验证对搜索线路未作可行性验证3.遗漏部