地面搜索大学生数学建模论文

1、高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从a/b/c/d中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）

2、： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：地面搜索摘要本文针对震后搜救问题，运用最优化数学模型，找到了较理想的搜索路线。模型一运用最优化线形法找到了线形搜寻方式；模型二利用多元函数区域方程，计算出搜寻时间为51.834小时

3、，之后运用哈密顿回路，找到了多种闭合回路。计算出最理想的路线，即所用时间最短的路径，得出其时间为47 .90小时，所用时间能在48小时内完成，第一个问题解决。对哈密顿理论推广，找到了派出50 人的最佳路线（图2-）所用时间为22.59小时。关键词最优化、哈密顿问题、线性规划、多元函数、搜索、模型、 c语言程序1、 问题重述5.12汶川大地震使震区地面交通和通讯系统严重瘫痪。救灾指挥部紧急派出多支小分队，到各个指定区域执行搜索任务，以确定需要救助的人员的准确位置。在其它场合也常有类似的搜索任务。在这种紧急情况下需要解决的重要问题之一是：制定搜索队伍的行进路线，对预定区域进行快速的全面搜索。通常，

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

5、搜索到目标，需要用步话机及时向组长报告，组长用卫星电话向指挥部报告搜索的最新结果。现在有如下问题需要解决：1假定有一支20人一组的搜索队伍, 拥有1台卫星电话。请设计一种你认为耗时最短的搜索方式。按照你的方式，搜索完整个区域的时间是多少? 能否在48小时内完成搜索任务? 如果不能完成，需要增加到多少人才可以完成。2为了加快速度，搜索队伍有50人，拥有3台卫星电话，分成3组进行搜索。每组可独立将搜索情况报告给指挥部门。请设计一种你认为耗时最短的搜索方式。按照你的搜索方式, 搜索完整个区域的时间是多少?二、符号说明 时间 搜索路线 时间 集结点 时间 出发点三、问题分析第一问题分析：令人寒心的伤亡

6、统计：四川省民政厅昨日发布消息，截至（5.31）日下午2时统计，全省1030.29万人不同程度受灾，因灾死亡1人、伤病6.31万人，直接经济损失21.31亿元，其中农业直接经济损失14.98亿元。截至31日14时，全省已紧急下拨应急资金4070万元。热血的救援安排：让我们共同祈祷受灾人数不要再增加，我们已派出一小分队救援，就让人员伤亡不要再增加，下面是我们应就得具体安排。我们的设备如表（一）：人 员物 资12345678910组长11副组长121314151617181920步话机1111111111卫星电话1111111111gps定位仪11111111111111111111食物若干若干若

7、干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干其他工具若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干若干5.12汶川大地震是让全世界都震惊的一个消息，而在这时我们的同胞还在废墟中等待着营救，这场大地震使震区地面交通和通讯系统严重瘫痪。我们必须前去营救，而在这时我们所面对的是大小为11200米7200米的废墟，我们只有二十人，我们只有两天的时间，只能比我们所拥有的时间短，要不会有更多的人员伤亡，所以当我们完成不了时，我们可以求助，所以我们要想一个最优的办法来完成这次搜索，我们用的的是gps定位仪、步话机以及食物和生活用品等装备下面是我们想的几

8、种办法来证明：首先我要收悉我们的地形图，如图（一）第一问题：二十人能否在48小时完成搜索。答：通过以下计算得出，可以在规定时间完成。模型一：最优化线性法我们的出发点在图中间也就是坐标点为（5600，3600），我们的二十个人用直升机直接送到坐标点，以进行下一步搜查行动，由于我们二十个人为一队，而且我们有1台卫星电话，所以我们必须同步而行，以为我们联系半径为1000米，所以我们之间距离不得超过2000米，而不至于丢失队友，造成更大的人员丢失，只有这样我们才可以更好的搜索救援，下面是人员安排：我们把二十人按一定顺序编号1到20号，每个人的搜索范围为20米的半球从地面到地下，以保证被埋群众也得救，每

9、个人行程如下面三维立体图：如图（二）我们通过知道队员探测范围半径20米，搜索速度为0.6米/秒，不需搜索而只是行进时,平均速度为1.2米/秒，在通过地震是由于地裂，所以底下也有人，通过matlab设计出照底下的三维立体视图。1.我们每个人的搜索范围如图所示，图2表示我们每个队员所能搜查的范围，我们停留在abcd地面上，中心e是我们队员，我们在图一的中心为20人，当我们落地时，二十个人散开为一个长为800米矩形：如图（三）2.我们队员就三成如图所示的形状，其长为800米，每个人站在圆中点，每个人相差40米，散开规则是最短的时间最快的展开队形，其中十九个人不搜索前进，依次按距地形图20，60，10

10、0760终止散开，最后一个人以0.6米/秒搜查速度前进，每个人到达自己的散开位置时，就已搜查速度前进向前推步前行，第二十号人人以搜查速度前进的原因是：图三中阴影部分都是不搜查部分，我们不能丢下任何一部分已造成人员伤亡，所以我们要求第二十号人以搜索速度前进，我们可以减小未搜查部分，就如趋近于相切，如图（四）我们可以把未搜查范围花最小：3.我们的忠旨就是在最短的时间救最多的人，所以我们采用上述的疏散方法，散开时我们每个队员都配发指令，一号到十九号行走一定路程就开始进行搜查行动，而二十号队员始终以搜查速度前进，而这样就导致20号队员落后，通过下列分析运算可知：分析：由题意给内容得知搜索时平均行进速度

11、为0.6米/秒；不需搜索而只是行进时,平均速度为1.2米/秒，所以跟就搜查散开方法得知分析如下：已知：一号到十九号都已1.2米/秒散开，而20号以0.6米/秒而不致使队员走过的地方未进行营救搜查。但又因为每个人散开后并不停止，而是进行疏散后的队形向前推步搜查，所以二十号队员就落后，但我们的器械只能在2000米的范围内不丢失队友，所以我们要让队友始终保持在2000米范围内，这样我们就要找个地方让他们的距离不要拉太长，所以我们考虑当20人在转折点时做个先后顺序，有一位我们去营救每分每秒都有生命在呼唤，这是我们不能做无谓的等待，所以每个人在自己的路线上都不要停留去等待队友，所以我们一直保持着前进的营

12、救路程，有一位我们的出发点是中心所以我们选择沿线两头散开，疏散到预计的800米范围，让二十号不落后的时间段就是在每一次拐弯时，这样我们就把距离变化为远近近远的行程。模型二：多元函数区域优化地面搜索是一个复杂的行程路线，为了节省时间我们采用离散的优化方法，即区域优化和多元函数。计算过程如下：最优化设计问题可以把20人分成几个小分队 每个小分队负责某一个区域 最短时间即为所有小分队同时完成任务所需时间 执行任务离中心点近的分队，区域可以安排大点 离中心点远的分队，区域小一点（因为还有步行时间） 具体几人一分队，区域面积多大，如下： 1 线性规划问题的模型线性规划问题的标准形式是：minc1x1+c

13、2x2+cnxn (1)s.t. 11 1 12 2 1n n 1 a x+a x+a x=b21 1 22 2 2n n 2ax +a x +a x=b (2)m1 1 m2 2 mn n ma x +a x +a x=b1 2 n x,x ,x 0其中(1)为目标函数，(2)为约束条件， 0( 1t1,t 2,t3 ) j x j= n为非负约束。线性规划也常用矩阵 向量的形式表示。若记1 ( t1,t 2,t3 )tn c= c c ， 1 (t1,t 2,t3 )tn x = x x ， 1 ( t1,t 2,t3 )tm b= b b ，a 为mn矩阵，把非负约束0( 1, , )

14、j x j= n简记为x 0 ，则线性规划可表示为：minctxs.t. ax=bx 0 计算得到时间为176878秒约为49.133小时2 函数解析问题f（q r）=qn/rn n=(.5.6.)得到186630秒约为51.834小时，超时得到177893秒约为49.41473小时如图（六）途中分不同的四个大区，两个圆中心的是起始点，短边上的是集结点，我们队员以每一小区进行搜查，以其中的n个小区搜查，通过计算，队员不但分离而且很有可能造成丢失，从而使这次搜查行动失败，而且理论时间超长，预算不够用。通过分析得到，模型一为合理方法，而二把组分开并且时间过长，还有区域分析法中的函数和

15、线性规划并没有解释出最短时间，而是按每个人走的路程之和取得平均值，最后得到模型一运用哈密顿定理，和哈密顿图分析得到，例：下列展示哈密顿定理我们拿出一个做例来解释哈密顿并且对模型一分析。哈密顿图主要定义：如果图g中存在一条通过图g中各个顶点一次且仅一次的回路，则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图。如果图g中存在一条通过图g中各个顶点一次且仅一次的回路，则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图。主要定理：设图g是哈密顿图，如果从g中删去个p顶点得到图g，则图g的连通分支数小于等于p。设图g是具有n(n=3)个顶点的无向简单图，如果g中任意两个不同顶点的度数之

16、和大于等于n-1，则具有哈密顿通路，即g是半哈密顿图。设图g是具有n n(n=3)个顶点的无向简单图，如果g中任意两个不同顶点的度数之和大于等于n，则g具有哈密顿回路，即g是哈密顿图。例： 指出图（七）是否哈密顿图，有无哈密顿通路，回路？ 解 ：(1) 有哈密顿回路，故是哈密顿图。(2) 只有哈密顿通路，无哈密顿回路，故不是哈密顿图。(3) 既无哈密顿通路，又无哈密顿回路，当然不是哈密顿图。 下面我们对模型以进行统计，即图示搜查路线，我们的出发点是矩形中心而集结点是短边的中心，目的是搜查所有地形，所以我们可以搜索到每个角落，所以我们的路线满足哈密顿图，如果图g中存在一条通过图g中各个顶点一次且

17、仅一次的回路，则称此回路为图的哈密顿回路。下面我们画出不同哈密顿图来展示我们搜索路线，下面是初始动作和第一次转弯时的动作： 如图（五）写出了搜查得出不开始，我们通过搜查开始和第一次转弯，进行计算，我们得出了搜索路线，我们先把20人行走的路线看为一条直线，但是我们所进行的不是地毯式搜索，原因在于地毯式搜索要求同时出发，而如果同时出发就会浪费更多的时间，如：由计算得知队员按一定的程序前进，而不是地毯式勘察，上图中各线的意义： 点划线 一号的开始路线和到达第一个转折点的路线，还有行程。虚线 二十号开始路线和到达第一个转折点的路线，还有行程。实线 组长的行程，由于队员都按一定程序前进，所以最后定为主线

18、，也是中分线。双点划线 是队员到达转折点所形成的函数图像，以为我们是一次行走的所以出现三角形图。因为我们的队员是按一定程序前进的，而我们所采取的是从中心散开，沿邻近的边散开，所以中心前进的人在开始就没有不搜索时间，直接前行，也就是我们的组长十号依次副组长十一号沿边不搜索前进40米到达搜索位置，而后不停留继续前进，两边自动分开到自己的搜索点后以搜索速度向图八中表示的路线推步前进，从而达到运算效果，然后我们分别计算出t.t.q的值，让后取其中最大的，就为搜索的最短时间，然后通过优化路径求解，详细分析运算在图八下得出：下面是对图五的详细分析： t 一号在全过程中的时间 t 二十号在全过程中的时间 q

19、 组长在全过程中的时间 t1 所走搜索直线路程的时间 t2 转折点转折时所用的时间t3 不搜索对各段时间 t1 所走搜索直线路程的时间 t2 转折点转折时所用的时间t3 不搜索对各段时间 q1 所走搜索直线路程的时间 q2 转折点转折时所用的时间q3 不搜索对各段时间从这里可以看出我们行走的路线从开始就以把时间节省，我们采用程序散开，到达后不等人的路线前行，所以时间就在这被节省，下一步我们通过行走路线来采取最优化方法，下面是我们制定的两幅图，具体是两种不同的行走路线：下面是整个运算过程： 分析：行走路线，从开始到最后不停留（在没有就营的情况下），考虑完整转弯，在转折点不浪费时间，采用中间散开方

20、法，保证营救速度和节省时间。函数式和图（八）如下：如图（八）同理函数求：对队员行程进行c语言编程：c /* note:your choice is c ide */#define n 15#include stdio.hoid main() int i,j,k,b,a,t,f,an; int c=n-1; k=0; printf(please input %d numbers:n,n); for(i=0;in;i+) scanf(%d,&a); printf(n); for(i=1;ik;j-) if(ajaj-1) t=aj;aj=aj-1;aj-1=t; f=1;b=j; k=b;j=c;

21、 if(!f) break; else f=0; for(a=k;aaa+1) t=aa;aa=aa+1;aa+1=t; f=1;c=a; if(!f) break; printf(the sorted number:n); for(i=0;igetdc(); int v; for(v=0;vm_pointnum;v+) visiv=false; for(v=0;vgetdc(); visiv=true; pathk=v; /记录当前路径 int w,i,j,c,d,e; arcnode *p; for(p=g.verticesv.firstarc;p;p=p-nextarc) w=p-adj

22、vex; if(!visiw) dfs(g,w,k+1); else /发现了一条回路 for(i=0;pathi!=w;i+); /找到回路的起点 for(j=0;pathi+j;j+) thiscyclej=pathi+j;/把回路复制下来 if(!exist_cycle() for(c=0;c=j;c+) cyclescycountc=thiscyclec;/如果该回路尚未被记录过,就添加到记录中 cycount+; if(j=m_pointnum-1) for(e=0;etextout(150+e*10,500+cycount*20,g.verticescyclescycounte.d

23、ata); for(d=0;dm_pointnum;d+) thiscycled=0; /清空目前回路数组 /else /for pathk=0; visik=false;/注意只有当前路径上的结点visited为真.因此一旦遍历中发现当前结点visited为真,即表示发现了一条回路 int circle:exist_cycle() int i,j,k,m,n,c,ab; int tempmax_vertex_num; for(i=0;icycount;i+) /判断已有的回路与thiscycle是否相同 /也就是,所有结点和它们的顺序都相同 j=0;c=thiscycle 0 ; /例如,1

24、42857和857142是相同的回路 for(k=0;cyclesik!=c&cyclesik!=0;k+);/在cycles的一个行向量中寻找等于thiscycle第一个结点的元素 if(cyclesik) /有与之相同的一个元素 for(m=0;cyclesik+m;m+) tempm=cyclesik+m; for(n=0;nk;n+,m+) tempm=cyclesin; /调整cycles中的当前记录的循环相位并放入temp数组中 for(ab=0;ab=m;ab+) if(tempab=thiscycleab) /if(!temp.compare(thiscycle) /与this

25、cycle比较 return true; /完全相等 for(m=0;mm_pointnum;m+) tempm=0; /清空这个数组 /for return false; /所有现存回路都不与thiscycle完全相等 我输入四个点1,2,3,4,边是1-2,2-3,3-4,4-1 可是出来的结果是: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 从事中我们可以看出我们还用到了哈密顿图及原理，和上道题一样我们分析的问题都是路径行走，这次同样还是走完每边角，试图借得到回应，多以这正是哈密顿原理图解。通过哈密顿函数，哈密顿算子，哈密顿量，把原题解释的很清楚，加上c语言编程，最后得到最短时间的路径编程。主要定义：如果图中存在一条通过图中个边一次且仅一次的回路，则称此回路为欧拉回路，具有欧拉回路的图称为欧拉图。如果图中存在一条通过图中各边一次且仅一次的通路，则称此回路为欧拉通路，具有欧拉通路的