地面搜索优化模型.doc

地面搜索优化模型摘要512汶川大地震给国家造成了重大损失，特别是震区地面交通和通讯系统严重瘫痪，给搜索与救援行动带来很大的麻烦。为了高效、有序地完成救援行动，所有救援人员必须有明确的路线。因此，我们对地面搜索路线问题进行了优化分析。问题1：由于区域大，人数少，利用分治算法把目标区域按纵向分成20块，以短边中线对称，每块由1个搜索人员利用蛇形搜索方式去完成，为使他们完成任务后回到集结点的时间尽量相同，我们引入了方差与主、次要区域的概念，建立了一个以方差为目标函数的非线性规划模型。利用软件解得具体结果如下表1：1234567891034735035335635836136436737037350.750.750.750.750.750.750.750.750.750.7注:（为区域号；为区域的宽度；为区域内耗时）搜索完目标区域所用的时间为50.68小时，所以不能在48小时内完成任务，利用模型1通过软件试探求解，可知需要增加2个人才可以在48小时内完成任务，所用时间为46.38小时。问题2：为了避免搜查重复造成资源、时间的浪费，再次利用分治算法思想将目标区域划分3个子区域，3个队都独自在区域内独立搜索，区域的面积不同所须的人也不同，通过先确定各区域的大致形状与位置，再根据面积与人数成正比的关系建立方程组，解得3个队的人数分别为：30、10、10。确定区域与人数后，各区域所需的时间在模型1的基础上进行分析求解，耗时最多的那组所需的时间即为总耗时，得到完成目标区域搜索任务的时间为：21.5小时。本文的模型计算均用软件求解，模型具有通用性好、实用性强的特点。关键词 ：分治算法 蛇形搜索 主要区域 次要区域 软件 非线性规划一、问题重述5.12汶川大地震使震区地面交通和通讯系统严重瘫痪。救灾指挥部紧急派出多支小分队，到各个指定区域执行搜索任务，以确定需要救助的人员的准确位置。在其它场合也常有类似的搜索任务。在这种紧急情况下需要解决的重要问题之一是：制定搜索队伍的行进路线，对预定区域进行快速的全面搜索。有一个平地矩形目标区域，大小为米米，需要进行全境搜索。假设：出发点在区域中心；搜索完成后需要进行集结，集结点（结束点）在左侧短边中点；每个人搜索时的可探测半径为米，搜索时平均行进速度为米/秒；不需搜索而只是行进时,平均速度为米/秒。每个人带有定位仪、步话机，步话机通讯半径为米。搜索队伍若干人为一组,有一个组长，组长还拥有卫星电话。每个人搜索到目标，需要用步话机及时向组长报告，组长用卫星电话向指挥部报告搜索的最新结果。问题1:用一支20人一组的搜索队伍, 拥有1台卫星电话。请设计一种为耗时最短的搜索方式。搜索完整个区域的时间是多少? 如果不能在48小时内完成搜索任务，需要增加到多少人才可以完成。问题2:为了加快速度，搜索队伍有50人，拥有3台卫星电话，分成3组进行搜索。每组可独立将搜索情况报告给指挥部门。请设计1种耗时最短的搜索方式。二、模型假设1. 在整个救援过程中探测仪器不会失效或功能减弱；2. 定位仪、步话机、卫星电话在搜索过程中随时可以用。2、忽略搜索人员向组长报告及组长用卫星电话向指挥部报告的时间。3、搜索人员可以通过其他搜索人员间接与组长联系。4、第2问中，不同组之间的人员不能通过步话机联系。三、符号说明： 第个队员；：分给第个队员的区域；：第个队员在救援时分配到的主要区域的宽度；：上半区矩形短边的总宽度；：上半区矩形长边的总宽度；：每个队员搜索范围的直径；：每个队员搜索时的速度；：每个队员不搜索时的速度；：第个队员开始搜索时到达的指定点；：第个队员在没有开始搜索时所走的路经；：第个队员在开始搜索后在主要区域竖直方向上所经过的路程；：第个队员在开始搜索后在主要区域水平方向上所经过的路程；：第个队员在开始搜索后在次要区域竖直方向上所经过的路程；：第个队员在最后由中线回到集结地不搜索时所经过的路程；：第个队员完成搜索任务回到集结地所花的时间；:第个子区域的面积（第二问，=1.2.3）；：第个队员沿着通道在长边方向上走过的路程；:第个小分队结束任务时所花的时间；：全部任务结束时所花的时间；四、模型建立与求解问题1：由于矩形中心对称且人数为偶数，为简化模型我们将只讨论该矩形水平放置时上半区的情况。下半区的情况则完全相同。根据题目要求20位搜救队员要将目标区域全部搜索一遍。由于面积大、人数少，在此情况下为了尽可能减少搜索时间，我们采用分治算法将目标区域以长边的平行线为边界划分为若干个小区域。划分后对于任意一个区域相应由队员负责。对于任意一个区域其宽为，长为米。如下图1所示： 总长度米图1则有上半区所有的累加后等于上半区矩形短边的总宽度，即：接着我们开始设计每个队员的具体搜索路线。首先将队员派遣到指定地点，在到达指定地点前，其所经过的直线路径必然穿过其它队员的主要区域，在不同的主要区域内会有相应的队员在接下的时间里对所经过的地方（在其主要区域内的）进行没有死角的蛇形搜索如图2。主要区域主要区域小虎牙、主要区域图2注：由最上面的区域开始依次编号为、。为避免重复计算与不必要的讨论，在到达指定地点前不进行搜索。到达指定地点后即开始进行蛇形搜索。为保证在进入次要区域开始搜索前不走的弯路，经计算可知指定地点的不同位置有5个（即每两个人要从同一指定地点出发），分别在由第一层开始的每连续两层的交界线最右端往左米。（下文中将进行详细讨论）从出发点到指定地点沿直线行进所走过的路经由三角函数关系可知等于由始点到中线最右端往左米处所在边与该点到所在边所构成的直角三角形的斜边的长。即：开始蛇形搜索后在竖直路线上进行搜索而在水平路线上则不进行搜索，则在队员所分得的主要区域上竖直方向上所经过的路程即等于水平方向上搜索范围加一个后除以直径的值与主要区域的积，即: 水平方向所经过的路程即等于水平方向上搜索范围，即：当主要区域的搜索任务完成后则进入次要区域，在进入次要区域前要保证不走的弯路，则有：11200/40=280（为的整数倍即正好有整数个来回）考虑到如果从连续两层的交界线最右端往左20米的地方开始搜索的话，则由连续层上层的蛇形图得经过280个来回后其向下运动而相同的由连续层下层的蛇形图得经过27.5个来回后其也向下运动，并不会产生走弯路的情况如图3：连续层上层连续层下层图3由图3得只要指定地点设在连续两层的交界线最右端往左米处就能达到进入次要区域开始搜索前不走的弯路的目的。很容易就可计算出指定地点不同位置的数目为5。次要区域则是在矩形区域的最左边留下来的让每个队员在到集结点前尽量都在搜索的一个区域，如图4：次要区域上下半区分界线（中线）图4则对每个队员所对应的次要区域竖直方向上所经过的路程等于上半区矩形短边的总宽度减去自己的区域到中线的最短距离即：最后由中线到集结地不搜索时所经过的路程为：综上所述：为使各个队员完成搜索任务所消耗的时间基本相同我们引入方差作为目标函数。建立模型如下：代入具体数据，经编程（见附录程序1.1），得在方差为零时得到时间：具体结果如下表1：1234567891034735035335635836136436737037350.750.750.750.750.750.750.750.750.750.7（注：为区域号；为区域的宽度；为区域内耗时。）因为，且其总差为，所以加1人不够，经试探得总共要加2人。代入具体数据，经编程（见附录程序1.2），得在方差为零时得到时间：具体结果如下表2：123456789101131431731932232532733033333533834046.446.446.446.446.446.446.446.446.446.446.4由以上数据可知相邻两个队员之间的间距最大为743米，与1000米的步话机限制还有相当大的差距。所以以上结果可以实现。问题2：由于有3部卫星电话，3个小分队队可以独立进行搜索，为了避免搜查重复造成资源、时间的浪费，将目标区域划分3个子区域，面积为，3个队都独自在区域内独立搜索，任务完成后按指定的路径回到集结点，以最后一个队的最后一位队员回到集结点时得时间作为所有任务完成时得时间，理想状态下每位队员从开始搜救到任务结束时一直在进行搜寻，也就意味着每各小分队的队员在搜寻时走过的面积与人数、时间成正比，当两个队所花时间相同时每个队人数的多少与其所负责的区域面积大小成正比，因此在队员数与区域大小的确定是相互的，即先将50个队员分为3组再根据人数的多少确定区域的位置与大小或先将目标区域分为3个子区域再根据面积的大小确定各区域中的人数，我们选择了后者-先分区再分人，在每个子区域中的分工与模型1相似。将目标区域按下图所示的方式划分为3个子区域：（y人）（y人）（x人）第i个队员的行走路线蛇形搜索是竖直方向是直去直回，没夹角图中=，夹在中间的区域是留给中的人回集结点时的过道，目的是为了使中的人回去时不会重复走已经搜索完的区域，减少时间、资源的浪费，宽度为，每一个队员都有一条路，宽度为40。理想的情况是3个分队同时完成搜索任务，即所花的时间是相同的，根据面积与人数成正比，面积分别为区域面积的一半减、加中间通道的面积，：各区域人数和为50因此满足：得到：解得： ，； （1）面积为与的子区域内的小分队人数为10；面积为的区域内的小分队的人数为30；在面积为=5600*3000的子区域内进行搜索任务，各队员在到达指定位置前所走的路程为只是沿着中线走到预定位置：此模型与模型一形式相同，为避免浪费引入方差作为目标函数：小分队结束任务所花的时间：利用软件编程进行求解，程序见附录（程序2.1）。具体结果如下表3：1234567891027528028529129630230831432132721.521.521.521.521.521.521.521.521.521.5小分队结束任务所花的时间：（2）在面积为的子区域内进行搜索的小分队回到集结点时所花的时间：所有队员所分到的主要区域（即小区域）在矩形短边上的长度为之和为则有：从出发点到指定地点沿直线行进所走过的路程和第一问一样可表示为：则对每个队员在自己区域短边方向上所经过的路程为：在长边方向上进行蛇行搜索的长度为：在长边方向上不进行蛇行搜索，即直走的距离为：第个队员回到集结点的时间为上述四个阶段所走的路程与在此阶段的速度之比的和：引入方差作为目标函数：小分队结束任务所花的时间：利用软件编程进行求解，程序见附录（程序2.2）。具体结果如下表4：小分队结束任务所花的时间：1234567821521922222522923223623920.720.720.720.720.720.720.720.7910111213141524324725125525926326720.720.720.720.720.720.720.7整个救援搜索行动结束的时间:六、模型的推广和检验模型一中由于采用了分治算法把简化后的实际地形分成了若干个小的矩形区域，这符合实际生活中一般划分方式，同时观察该模型可知其中变量大部分在实际生活中是容易获得的，所以该模型易于推广。第二问中建立的模型，3支小分队所花的时间不同，造成了一定资源的浪费，从结果中看出人数最多的那组所花的时间比其它的两组要少，若要进行调整就只能将人多的那组分几个人到人少的组去，由于另外两组是对称的，所以要抽调人的话一定要是二的倍数，我们先进行抽调两人进行计算，通过改编程序2.1与程序2.2，得到完成任务所需的时间为21.77小时，小分队完成任务相差的时间为2小时，通过对抽调两人计算结果进行分析，不管是完成搜索的时间与时间差都不如未调整时的，由此可以看出此种分配方案在一定程度上达到了最优。七、参考文献1 唐焕文、冯恩名、孙育贤、孙丽华，数学模型引论，大连理工出版社，1990；2 陈义华，数学模型，重庆大学出版社，1991；3 欧阳亮，系统科学中数学模型，山东大学出版社，1995；4 朱道元，数学建模精品案例，东南大学出版社，1999；附录程序1.1model:sets:shijian/1.10/:t,s;endsetsfor(shijian(i):t(i)=(11200-40*i)/1.2+(11200-40*(i-1)/40)*s(i)/0.6+(3600-20-sum(shijian(k)|k#le#i:s(i)/0.6+(i-1)*40+20)/1.2+(5600)2+(3600-sum(shijian(k)|k#le#if(-1)i#gt#0,i-1,i):s(k)2)0.5)/1.2);sum(shijian(i):s(i)=3600;w=sum(shijian(i):t(i)/10;min=(sum(shijian(i):(t(i)-w)2)0.5;end程序1.2model:sets:shijian/1.11/:t,s;endsetsfor(shijian(i):t(i)=(11200-40*i)/1.2+(11200-40*(i-1)/40)*s(i)/0.6+(3600-20-sum(shijian(k)|k#le#i:s(i)/0.6+(i-1)*40+20)/1.2+(5600)2+(3600-sum(shijian(k)|k#le#if(-1)i#gt#0,i-1,i):s(k)2)0.5)/1.2);sum(shijian(i):s(i)=3600;w=sum(shijian(i):t(i)/11;min=(sum(shijian(i):(t(i)-w)2)0.5;end程序2.1model:sets:shijian