查看: 6236|回复: 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 ，

问题二：将目标区域按短边分成三组，并与问题一同理在各自区域搜索。模型如下：
其中， ; Z5 _4 i; }: T& W

, C' ?, w) L2 ~" s( u# Y N& 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小时之内完成。
问题二，
把搜索区域按短边分成三个任务区域。然后按问题一的拖地式法的原则在各自的任务区内搜索。

三、符号说明

符号 5 \! a" ^# q& o8 S1 K" r9 ]; w	含义	单位	备注
: J4 F9 r0 n5 ^" ~. N8 m1 j- V! W	搜索完所用的时间) }1 j2 P( \|" {# n0 e	小时/ P3 Y3 K8 s/ O% [/ t$ Z+ A7 m	5 \|- r, `# I* N8 m8 e! X7 C6 d
! m3 B$ o K" x$ U5 \& a	第一种转角的次数 - G9 {1 ]# Q1 L3 _	次 w; A+ q& C6 P	见转角说明B图4 _" k7 @7 Z! t' H! t4 b% y3 \|. Z; t
& l7 R% o' T' \4 h	第二种转角的次数) I% D, v1 k) [/ R+ V* U6 n	次5 {, k7 u1 D) r! V) ~# k	见转角说明A图, Z ], }) }2 t( g" X( @) _
0 d) U% f3 K7 c0 P	搜索时的平均速度 2 k. h3 P8 x- t2 d	- x, P+ w \|( z* G3 G8 \|3 U	. W. V& {/ W* F' H' X& ]
$ ^) }' B3 \|9 @$ \5 x	不搜索只行进的平均速度 L" k4 V+ v: c! L! C) ?% l% }5 H	# h, Q, U% @4 W	: a9 r2 @1 s- F3 h
8 b# _# h+ Z$ g' m	每个人搜索时可探测的半径 " p, F+ D2 u0 ~' @5 ~" q	& ?2 X6 x, [% Y) }	# n/ s# d' K- L5 @: V1 o! A
; T6 y( H- e! F$ l3 p' K	搜索宽度* x7 Y6 {; z! I3 i+ F	; N& n# c* J: ]5 F3 G	) d. M0 x G, \: C! K' u
1 p" }/ c, e; o% g0 ]1 J, _	横向格数6 K# N4 {+ Q+ [; R- P, H$ u" ~: x; F% l	次 ; Z3 f7 M0 }. j. x/ c# j4 v	0 o' d7 m2 w6 S7 d
" M7 X8 s9 O; R! D0 l5 G, m	纵向格数 ! o5 n+ [8 Q1 @7 ]0 Y	次( u5 T( O. Y1 q1 v& i	) w6 P+ I- J7 s4 y+ Z) l9 w9 \|9 b
7 L7 d/ ^8 B* C$ p( m	以返回集结点的时间% u# N, E& ~' Z	小时$ {. f# n; y: g- R# v# d	F% s+ v6 g+ t$ B4 \& k
; M) ~, @0 s/ s5 @5 V# `	起点到开始“拖”的时间; O v- a0 N6 r/ n' X6 B9 n/ `	小时4 L/ W; e: S! \( U" J. ^1 Z6 \|	) `1 e& S0 s1 T/ [) }# U6 Q
, K4 \|3 ~) H; W, d' l- ]	增加的人数/ L1 u+ L/ F( \$ s: A	人2 P! T- [, T l: z" \	! I% l! i, z2 o6 m* P
( z: y# l" i6 x! v4 M	人数 . l3 c( t+ O$ \* c m8 n( e# \|	人 : y* x* Y4 e6 B( @) R	- I) Q& w7 W) n5 [
* ^9 \- G/ E: Q0 a" l	区域短边长度 / E8 @' u3 o( a9 @	- Y2 \|; ^, Q5 G C+ P	! u5 S# y3 _1 G. g0 E
( K; n- @8 a, E	区域长边长度' k, H+ d. h3 {( V1 x# c, R	2 \|% {$ ~0 U, W" a; o! g+ y	1 G2 T! y9 S* ~2 W5 E9 I
6 G& K7 I2 [" [1 D* \	第一、二分区 " I# n$ u8 Q3 m. N( i" E) j	% e3 l- U$ y0 Y/ I5 e; _2 w$ o9 C& U	1为第一分区2为二分区 ' w/ g/ q, ?) v3 A* V8 U
" p7 s* h! p4 q3 N) E) o	第一、第二分区人数$ D: P' t) M) u+ i/ r/ p	人1 l& S( p4 ~2 R5 B, q' r, G$ c9 V% D' d+ V	1为第一分区人数2为二分区人数 . r" f/ h: l! `' ]

四、模型假设

假设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

附录

0 P" t& C4 k3 t, F `# D6 C

附件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+ X  H& I* d( d8 t& O+ p
82250.859 \  b% `" F5 Z' p! o! C2 l+ ~
14 B/ p$ e9 y+ D
0.000000! c. e) U0 K4 |8 x: T

T" V, d5 S. v1 P9 W: p6 K' O
22.84746
4 \) F8 J- o; {) r2; b  Z' ]5 N9 S3 T

0.000000
  ?. e! {. a7 B3 o5 R; n) G& N7 G# X

zan