查看: 6239|回复: 8

2008c地面搜索数学模型2

[复制链接]

字体大小: 正常放大

E304731541

5 主题	5 听众	270 积分

升级 85%

该用户从未签到

电梯直达

1^#

发表于 2009-8-24 22:14 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

地面搜索数学模型

摘要

建模目的：保证不出现盲点的情况下尽可能在最短时间内搜索完整个目标区域。模型能用在CCD探测器搜索和数字电视地面广播系统网络规划等。

问题一：鉴于目标区域为矩形，故采用20人并排搜索的 “拖地式法”，保证不超出通讯范围且无盲区，具体模型为：

通过搜索路径分析得图模型（1）所示，求得搜索时间为49.78727小时。基于此模型易发现搜索路径转角数一定大于9，而包含9个转角的搜索路径用时为48.29 ，故20个人不可能完成任务。下面考虑增加队员，路线在图模型（1）改进得到，模型如下：计经计算得到只需增加一人，即可使时间为47.5876 ，

问题二：将目标区域按短边分成三组，并与问题一同理在各自区域搜索。模型如下：
其中， 5 l6 k! S5 [; y3 Y

$ Z: C) L3 J$ {5 \) C! H% y9 P' z
经LINGO算得：把50人分成20、10、20人3组，搜索时间为22.84746小时。

模型特点：①无盲区 ②转角少 ③完成搜索返回集结点的距离短 ④重复搜索区域尽可能小。模型的创新之处在于充分考虑到搜索路径转角对搜索时间的影响。画一个图分析多个不同的问题。

关键词：拖地式法转角盲区模型 LINGO

一、问题重述

问题背景：5.12汶川大地震使震区地面交通和通讯系统严重瘫痪。救灾指挥部紧急派出多支小分队，到各个指定区域执行搜索任务，以确定需要救助的人员的准确位置。在其它场合也常有类似的搜索任务。在这种紧急情况下需要解决的重要问题之一是：制定搜索队伍的行进路线，对预定区域进行快速的全面搜索。通常，每个搜索人员都带有GPS定位仪、步话机以及食物和生活用品等装备。队伍中还有一定数量的卫星电话。GPS可以让搜索人员知道自己的方位。步话机可以相互进行通讯。卫星电话用来向指挥部报告搜索情况。
问题条件：一个平地矩形目标区域，大小为11200米×7200米，需要进行全境搜索。假设：出发点在区域中心；搜索完成后需要进行集结，集结点（结束点）在左侧短边中点；每个人搜索时的可探测半径为20米，搜索时平均行进速度为0.6米/秒；不需搜索而只是行进时,平均速度为1.2米/秒。每个人带有GPS定位仪、步话机，步话机通讯半径为1000米。搜索队伍若干人为一组,有一个组长，组长还拥有卫星电话。每个人搜索到目标，需要用步话机及时向组长报告，组长用卫星电话向指挥部报告搜索的最新结果。
求解问题：
1．假定有一支20人一组的搜索队伍, 拥有1台卫星电话。请设计一种你认为耗时最短的搜索方式。按照你的方式，搜索完整个区域的时间是多少? 能否在48小时内完成搜索任务? 如果不能完成，需要增加到多少人才可以完成。
2．为了加快速度，搜索队伍有50人，拥有3台卫星电话，分成3组进行搜索。每组可独立将搜索情况报告给指挥部门。请设计一种你认为耗时最短的搜索方式。按照你的搜索方式, 搜索完整个区域的时间是多少?

二、问题分析

针对题意，对地面静态的目标搜索，由于指定区域为矩形，所以采用搜索路径为矩形会比较优化，在搜索过程中转角是不可避免的，搜索路径的过程中需要的时间来至四个方面①搜索目标的时，②从起点到开始搜索的时间③转角所用的时间④停止搜索到返回的时间。每个探测搜索组拖地式法进行搜索（即一个组排成一行向同一个方向平行前进进行探测），拖地式法的搜索避免了重复探测、盲点和由于组员之间距离过大而超出通讯范围，同时减少转移的路线。拖地式法需要把探测区域分成以组视距宽为宽的矩形区，矩形区之间连接的探测，需要整组的转移，那么整个搜索行动所用的时间，就至少包含探测时间和转移的时间。
问题一，
按照拖地式法，我们的最短搜索方式的原则是①尽可能走长边探测一直测到界线。②最长路程转移者，沿界线为转移住。③开始的方向选择要尽量使它结束测量时回到集结点的路程最短。起点正好在所分格的一条边上，所以起步选择水平向上为最优。
按上述的原则计算出我们的最短搜索时间，与48小时比较，即可知能否在48小时内完成搜索任务，如果不能完成，便逐步加人数，再计算出至少加多少人才能在48小时之内完成。
问题二，
把搜索区域按短边分成三个任务区域。然后按问题一的拖地式法的原则在各自的任务区内搜索。

三、符号说明

符号1 M- n7 \|! A. w3 i- R! \) O	含义	单位	备注
' U. ]/ ?" H4 g' ^8 G0 l. t" ^	搜索完所用的时间( f) }" S/ ~6 z ]$ Y	小时 # T3 m1 n0 t Q9 Z" P# p& Z	" y0 K3 s0 x3 e8 P8 \5 m- a
( E N7 J9 \|% D, F+ w	第一种转角的次数" L' P- M5 V0 I5 [	次1 W/ Z! O( o& W	见转角说明B图2 C% j; G) M' z/ z
9 ~9 T/ @3 A( {; ?; h	第二种转角的次数/ o& [/ J: ~2 G0 Y# N( \|- b f	次 # f* z2 D( a# y% W% Q" A( k	见转角说明A图 - Y/ O( \|* R/ w2 M, D
* u+ E: k- Y, N2 J/ Z: u	搜索时的平均速度 M9 O- L2 I ]& q" U2 C# L	; b. R! H# y' I, T2 s& Y	. V( x. T/ L( Q0 B0 e, E% B
8 V- m- A, C6 a	不搜索只行进的平均速度 - R: q, A+ M" ~8 v" Y9 x( h	" `/ l6 P; ^* @$ e; H* Q: D	8 _4 F" g' z$ C k; l
% l0 v1 {, c% C9 W	每个人搜索时可探测的半径* x; H* x0 A* g7 W	, \& W0 L; x# H1 n; d	! M& L( D" f1 A# t/ q+ o
+ v L+ c. e; y- U# t C- ?	搜索宽度 - k. l! @0 R9 C/ F	" s1 p1 c3 j' S% }- n# O1 s% ~	! [, D: M c q1 W. u
* w8 F8 m) j3 V$ _# C	横向格数: y" K; f2 k3 G6 j3 N: o	次! S0 C, B& o# r3 W" _: i( z	$ N) r4 Z) E/ Q5 O$ f! l( C
5 E; ~& J! o8 H6 G7 c. F( e	纵向格数) z% w0 \9 x/ U, z7 ^! l; }/ O& ~ {6 }	次$ K" \; u9 W: a9 c$ `6 y8 P! O' L D0 v	. i# }# K8 t+ s" H: t8 \|
2 O' e) \8 V0 j" Q6 y	以返回集结点的时间# I0 f3 L# j( o/ x: Q8 E2 Y( ?	小时 . e& g% v0 s; D/ P+ p5 K% g' j( P	5 l2 p% ~9 ]+ U2 \
& K; i* V- ]3 q0 b	起点到开始“拖”的时间 + i. U! o' ~/ Y) ^	小时 4 t, {+ c) ^7 e, V2 U	' U- J/ ?: p5 ]' ~0 x
8 g ^1 w+ i! t: r( t$ H ]	增加的人数 7 X/ b" ]6 L- f0 P, R( M, r	人0 b$ D: e) y6 Q& j& i2 S& c" N	( I% b9 k8 U* q
& d( n9 `% A/ @8 H M. Q	人数4 P0 s9 S6 Y' A0 ]! T	人 2 P. Q, w- z# e2 V! i Z	& K: a1 {( E0 F. M! I- U2 s
6 @' t$ v3 q) M	区域短边长度 ( e9 [ `" k3 g! z	# V% T4 ^" L% G2 v: ^	0 _6 \2 I o8 Z- V
3 ]1 E/ U/ d0 E9 {	区域长边长度 & a7 {% e9 O/ q% O; B Q; J	+ p; r @# w1 q7 q6 j	/ \|- a8 X; A$ V& z$ y4 Y m
; m9 @1 t {9 ^* C	第一、二分区 . n$ c- T% `8 a	/ g+ O0 s, ^6 r; v	1为第一分区2为二分区 $ g! h% R9 U& H+ y0 W3 ~# h s
* N. O& u A$ \1 q' x4 l- v) ^	第一、第二分区人数 / b2 Z) n6 J% Z	人" k% y+ V# x, K( i' Z	1为第一分区人数2为二分区人数 ! M; F1 U" M5 N' A6 S n( e

四、模型假设

假设1：在允许范围内每个队员按各自轨道搜索，并且无盲区的情况下搜索每个角落。
假设2：搜索的整个时间段目标都是静态。
假设3：队伍在搜索时使用的通讯工具一切正常。
假设4：不考虑队伍休息的时间、通话时间。
假设5：在探测过程中不受天气、地面凹凸不平和余震因素的影响。

五、模型建立与求解

对问题一：
（1）按问题分析中的原则得20个人一组的“拖地式法”如下的模型：

得走完全部格子所用的时间为 ……….①

图模型（1）转角说明：对A图由于我们是采用每次遇到转角都要整体走完底边，然后整体平移，最后再转到另一个行道向前。这样的好处有①可以使搜索没有盲点。②每一像A图的转角比较少。③能很好的使没个人在同一个平面内，对在步话机通讯半径好控制。
对B图主要考虑的是当我们走到边时是选择AD还是BD还是CD的问题，由勾股定理我们容易知道在遇到B图转角的情况
AD是最长的BD是最短的，所以我们用的是BD的距离来算。

A

B

C

A图

B图

D

由转角说明图知道转角所用的时间模型为：

故得 ………………②

集结点

中心

第一步

11200

800

7200

图模型（1）

由图我们知道
……………③

…………..④

由①②③④得

代入数据用LINGO求解得49.78727小时，具体LINGO程式见附件1。

（2）一支20人为一组的搜索队伍，它他完成搜索至少所用的时间为探测时间加按短边至少转9个转角使用的时间

所以不能在48小时之内完成搜索。

（3）当增加一个人时所用的时间模型如下：

模型简图和模型图（1）一样，
代入LINGO求得47.3845小时，故至少增加一人。具体LINGO 程式见附件2。

对问题二：
我们把目标区域按短边分成三组区域，把50也分成三队像第一问那样在分给他们的区域内独立去完成。他们完成搜索任务所用时间模型为、、。
第一组的模型

其中：

其中：

其中：

编入LINGO优化分得人数为20、10、20，优化得搜索时间为22.84746小时。具体LINGO程式见附件3。

六、模型评价
模型优点：1）模型规律明显，问题比较充分,非常直观。
模型优点：2）搜索过程中出现重复虽然不可避免，但我们的模型已经做到重复搜索区域尽可能小
模型优点：3）在模型的求解过程中，较好地运用了相应的数学软件，如Lingo、对模型进行严格的求解，具有较高的科学性；
七、模型改进方向
我们还可以考虑加入动态目标以及搜索人员休息时间问题。并且在消除盲点的效率上进一步改进。
参考文献
[1] 谢金星，薛
毅.优化建模与LINDO NGO软件. 北京：清华大学出版社，2005.7
[2] 姜启源,谢金星.数学模型[M].北京：高等教育出版社，2003（第三版）
[3]韩中庚，数学建模方法及其应用[M].北京：高等教育出版社，2005

附录

4 W) @ l1 m; x2 G* Q& T% b* O* g

附件1：

t=800*14*9/0.6+15*((800-20)^2+20^2)^(1/2)/1.2+(800/2+800-20)/1.2 +(1200-20)/1.2;

T=t/3600;

Variable

Value

Row
Slack or Surplus

t

179053.2

1

0.000000

T

49.78727

2

0.000000

附件2：

t=11200*7200/40/21/0.6+4*((40*21-20)+20^2)^(1/2)/1.2+40*21*9/1.2+40*21/1.2+((1180+160)^+280^2)^(1/2);

a=t/3600;

Variable
Value
Row
Slack or Surplus

t
170584.2544
1
0.000000

T
47.3845
2
0.000000

附件3：
include<fstream>
　　define MaxNum 765432100
　　using namespace std;
　　ifstream fin("Dijkstra.in");
　　ofstream fout("Dijkstra.out");
　　int Map[501][501];
　　bool is_arrived[501];
　　int Dist[501],From[501],Stack[501];
　　int p,q,k,Path,Source,Vertex,Temp,SetCard;
　　int FindMin()
　　{
　　int p,Temp=0,Minm=MaxNum;
　　for(p=1;p<=Vertex;p++)
　　if ((Dist[p]<Minm)&&(!is_arrived[p]))
　　{
　　Minm=Dist[p];
　　Temp=p;
　　}
　　return Temp;
　　}
　　int main()
　　{
　　memset(is_arrived,0,sizeof(is_arrived));
　　fin >> Source >> Vertex;
　　for(p=1;p<=Vertex;p++)
　　for(q=1;q<=Vertex;q++)
　　{
　　fin >> Map[p][q];
　　if (Map[p][q]==0) Map[p][q]=MaxNum;
　　}
　　for(p=1;p<=Vertex;p++)
　　{
　　Dist[p]=Map[Source][p];
　　if (Dist[p]!=MaxNum)
　　From[p]=Source;
　　else
　　From[p]=p;
　　}
　　is_arrived[Source]=true;
　　SetCard=1;
　　do
　　{
　　Temp=FindMin();
　　if (Temp!=0)
　　{
　　SetCard=SetCard+1;
　　is_arrived[Temp]=true;
　　for(p=1;p<=Vertex;p++)
　　if ((Dist[p]>Dist[Temp]+Map[Temp][p])&&(!is_arrived[p]))
　　{
　　Dist[p]=Dist[Temp]+Map[Temp][p];
　　From[p]=Temp;
　　}
　　}
　　else
　　break;
　　}
　　while (SetCard!=Vertex);
　　for(p=1;p<=Vertex;p++)
　　if(p!=Source)
　　{
　　fout << "========================\n";
　　fout << "Source:" << Source << "\nTarget:" << p << '\n';
　　if (Dist[p]==MaxNum)
　　{
　　fout << "Distance:" << "Infinity\n";
　　fout << "Path:No Way!";
　　}
　　else
　　{
　　fout << "Distance:" << Dist[p] << '\n';
　　k=1;
　　Path=p;
　　while (From[Path]!=Path)
　　{
　　Stack[k]=Path;
　　Path=From[Path];
　　k=k+1;
　　}
　　fout << "Path:" << Source;
　　for(q=k-1;q>=1;q--)
　　fout << "-->" << Stack[q];
　　}

　　fout << "\n========================\n\n";
　　}
　　fin.close();
　　fout.close();
　　return 0;
　　}
　　Sample Input
　　2
　　7
　　00 20 50 30 00 00 00
　　20 00 25 00 00 70 00
　　50 25 00 40 25 50 00
　　30 00 40 00 55 00 00
　　00 00 25 55 00 10 00
　　00 70 50 00 10 00 00
　　00 00 00 00 00 00 00
　　Sample Output
　　========================
　　Source:2
　　Target:1
　　Distance:20
　　Path:2-->1
　　========================
　　========================
　　Source:2
　　Target:3
　　Distance:25
　　Path:2-->3
　　========================
　　========================
　　Source:2
　　Target:4
　　Distance:50
　　Path:2-->1-->4
　　========================
　　========================
　　Source:2
　　Target:5
　　Distance:50
　　Path:2-->3-->5
　　========================
　　========================
　　Source:2
　　Target:6
　　Distance:60
　　Path:2-->3-->5-->6
　　========================
　　========================
　　Source:2
　　Target:7
　　Distance:Infinity
　　Path:No Way!
　　========================
　　示例程序及相关子程序：
　　void Dijkstra(int n,int[] Distance,int[] iPath)
　　{
　　int MinDis,u;
　　int i,j;
　　//从邻接矩阵复制第n个顶点可以走出的路线，就是复制第n行到Distance[]
　　for(i=0;i<VerNum;i++)
　　{
　　Distance=Arc[n,i];
　　Visited=0;
　　}//第n个顶点被访问，因为第n个顶点是开始点
　　Visited[n]=1;
　　/ 到该顶点能到其他顶点的路线、并且不是开始的顶点n、以前也没走过。
　　//相当于寻找u点，这个点不是开始点n
　　for(i=0;i<VerNum;i++)
　　{
　　u=0;
　　MinDis=No;
　　for(j=0;j<VerNum;j++)
　　if(Visited[j] == 0&&(Distance[j]<MinDis))
　　{
　　MinDis=Distance[j];
　　u=j;
　　}
　　//如范例P1871图G6，Distance=[No,No,10,No,30,100]，第一次找就是V2，所以u=2
　　/ 完了，MinDis等于不连接，则返回。这种情况类似V5。
　　if(MinDis==No) return ;
　　//确立第u个顶点将被使用，相当于Arc[v,u]+Arc[u,w]中的第u顶点。
　　Visited=1;
　　//寻找第u个顶点到其他所有顶点的最小路，实际就是找Arc[u,j]、j取值在[0，VerNum]。
　　//如果有Arc[i,u]+Arc[u,j]<Arc[i,j]，则Arc[i,j]=Arc[i,u]+Arc[u,j]<Arc[i,j]
　　//实际中，因为Distance[]是要的结果，对于起始点确定的情况下，就是：
　　//如果(Distance + Arc[u,j]) <= Distance[j] 则：
　　//Distance[j] = Distance + Arc[u, j]；
　　//而iPath[]保存了u点的编号；
　　//同理：对新找出的路线，要设置Visited[j]=0，以后再找其他路，这个路可能别利用到。例如V3
　　for(j=0;j<VerNum;j++)
　　if(Visited[j]==0&&Arc[u,j]<No&&u!= j)
　　{
　　if ((Distance + Arc[u,j]) <= Distance[j])
　　{
　　Distance[j] = Distance + Arc[u, j];
　　Visited[j]=0;
　　iPath[j] = u;
　　}
　　}
　　}
　　}
　　//辅助函数
　　void Prim()
　　{
　　int i,m,n=0;
　　for(i=0;i<VerNum;i++)
　　{
　　Visited=0;
　　T=new TreeNode();
　　T.Text =V;
　　}
　　Visited[n]++;
　　listBox1.Items.Add (V[n]);
　　while(Visit()>0)
　　{
　　if((m=MinAdjNode(n))!=-1)
　　{
　　T[n].Nodes.Add(T[m]);
　　n=m;
　　Visited[n]++;
　　}
　　else
　　{
　　n=MinNode(0);
　　if(n>0) T[Min2].Nodes.Add(T[Min1]);
　　Visited[n]++;
　　}
　　listBox1.Items.Add (V[n]);
　　}
　　treeView1.Nodes.Add(T[0]);
　　}
　　void TopoSort()
　　{
　　int i,n;
　　listBox1.Items.Clear();
　　Stack S=new Stack();
　　for(i=0;i<VerNum;i++)
　　Visited=0;
　　for(i=VerNum-1;i>=0;i--)
　　if(InDegree(i)==0)
　　{
　　S.Push(i);
　　Visited++;
　　}
　　while(S.Count!=0)
　　{
　　n=(int )S.Pop();
　　listBox1.Items.Add (V[n]);
　　ClearLink(n);
　　for(i=VerNum-1;i>=0;i--)
　　if(Visited==0&&InDegree(i)==0)
　　{
　　S.Push(i);
　　Visited++;
　　}
　　}
　　}
　　void AOETrave(int n,TreeNode TR,int w)
　　{
　　int i,w0;
　　if(OutDegree(n)==0) return;
　　for(i=0;i<VerNum;i++)
　　if((w0=Arc[n,i])!=0)
　　{
　　listBox1.Items.Add (V+"\t"+(w+w0).ToString()+"\t"+i.ToString()+"\t"+n.ToString());
　　TreeNode T1=new TreeNode();
　　T1.Text =V+" [W="+(w+w0).ToString()+"]";
　　TR.Nodes.Add(T1);
　　AOETrave(i,T1,w+w0);
　　}
　　}
　　void AOE()
　　{
　　int i,w=0,m=1;
　　TreeNode T1=new TreeNode();
　　for(i=0;i<VerNum;i++)
　　{
　　Visited=0;
　　}
　　T1.Text =V[0];
　　listBox1.Items.Add ("双亲表示法显示这个生成树：");
　　listBox1.Items.Add ("V\tW\tID\tPID");
　　for(i=0;i<VerNum;i++)
　　{
　　if((w=Arc[0,i])!=0)
　　{
　　listBox1.Items.Add (V+"\t"+w.ToString()+"\t"+i.ToString()+"\t0");
　　TreeNode T2=new TreeNode();
　　T2.Text=V+" [W="+w.ToString()+"]";
　　AOETrave(i,T2,w);
　　T1.Nodes.Add (T2);
　　listBox1.Items.Add("\t\t树"+m.ToString());
　　m++;
　　}
　　}
　　treeView1.Nodes.Clear();
　　treeView1.Nodes.Add (T1);
　　}
　　int IsZero()
　　{
　　int i;
　　for(i=0;i<VerNum;i++)
　　if(LineIsZero(i)>=0) return i;
　　return -1;
　　}
　　int LineIsZero(int n)
　　{
　　int i;
　　for(i=0;i<VerNum;i++)
　　if (Arc[n,i]!=0) return i;
　　return -1;
　　}
　　void DepthTraverse()
　　{
　　int i,m;
　　for(i=0;i<VerNum;i++)
　　{
　　Visited=0;
　　T=new TreeNode();
　　T.Text =V;
　　R=0;
　　}
　　while((m=IsZero())>=0)
　　{
　　if(Visited[m]==0)
　　{
　　listBox1.Items.Add (V[m]);
　　R[m]=1;
　　}
　　Visited[m]++;
　　DTrave(m);
　　}
　　for(i=0;i<VerNum;i++)
　　{
　　if(R==1)
　　treeView1.Nodes.Add (T);
　　}
　　}
　　void DTrave(int n)
　　{
　　int i;
　　if (LineIsZero(n)<0) return;
　　for(i=VerNum-1;i>=0;i--)
　　if(Arc[n,i]!=0)
　　{
　　Arc[n,i]=0;
　　Arc[i,n]=0;
　　if(Visited==0)
　　{
　　listBox1.Items.Add (V);
　　T[n].Nodes.Add (T);
　　R=0;
　　}
　　Visited++;
　　DTrave(i);
　　}
　　}
　　void BreadthTraverse()
　　{
　　int i,m;
　　for(i=0;i<VerNum;i++)
　　{
　　Visited=0;
　　T=new TreeNode();
　　T.Text =V;
　　R=0;
　　}
　　while((m=IsZero())>=0)
　　{
　　if(Visited[m]==0)
　　{
　　listBox1.Items.Add (V[m]);
　　R[m]=1;
　　}
Visited[

20*(2)^1/2+((40+20)^2+20^2)^1/2+((40*2+20)^2+20^2)^1/2+((40*3+20)^2+20^2)^1/2+((40*4+20)^2+20^2)^1/2+

((40*5+20)^2+20^2)^1/2+((40*6+20)^2+20^2)^1/2++((40*7+20)^2+20^2)^1/2++((40*8+20)^2+20^2)^1/2

+((40*9+20)^2+20^2)^1/2=c;

t=14*4*800/0.6+7*800/1.2+(800/2-20)/1.2+4*((800-20)^2+20^2)^(1/2)/1.2;

T=t/3600;

a=7200
b=11200
r=20
v1=0.6
v2=1.2
x=1,2,…………50
0<L1<a/2
Variable

Value
Row
Slack or Surplus
t
' Q5 J; M2 O& e. q: t f82250.85
$ _- U3 _1 ]8 c4 M! C! x5 J1 I1' v/ K( j H+ P' C8 `/ I9 E$ ^$ S
0.000000
6 k, E+ b9 t8 C% p3 S
T
) _' W+ t/ W- m* c8 I/ k+ {2 ?6 G22.84746" e# z% |+ t/ s! c$ Q; g# p
2& M: k- L9 Q, s/ [7 R% y# H

0.000000
% [& p% g2 @& y5 y3 c

zan