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

问题二：将目标区域按短边分成三组，并与问题一同理在各自区域搜索。模型如下：
其中， 3 z! X9 N' Q7 C. w6 ^& T- f9 V

: [# H4 V$ {' X2 s
经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小时之内完成。
问题二，
把搜索区域按短边分成三个任务区域。然后按问题一的拖地式法的原则在各自的任务区内搜索。

三、符号说明

符号# ?& E" R4 ^1 ?- y- q	含义	单位	备注
' j% e$ m* u* c) I/ y0 v+ s2 i	搜索完所用的时间% S1 Y1 v& S! W' G% }: [# c	小时8 C: v# D3 t: _+ z	. u2 {* ~# H1 d5 y% c' Y% x3 K9 t: ^
6 v- A/ R/ C, c- k \' R/ `	第一种转角的次数5 s6 k- \5 \. W	次7 B- K$ e* F0 O6 o# @	见转角说明B图 % x2 \|+ t* R" o% v) ^% c& Z$ ^( }
- Y- E) u0 u& y; D	第二种转角的次数 ( a @- p- D* `) ^- b# G	次 & Y5 z( n8 ^% F, r	见转角说明A图 , Q& z* l% u" [$ ~* G
+ b) d. d- \, Y9 f6 w* W	搜索时的平均速度 * C( \|# U ~( E# s% v& d8 h	% O* S3 T: Z2 F. I. K, J' C( \	) I# S0 ~4 }, D. Z+ d$ V4 {
0 m0 P1 V1 w! q3 n+ L/ Z	不搜索只行进的平均速度2 Y$ u, L& }6 O9 I	1 l/ x O1 Y% n' O, m	^. B L- r' g9 Z0 E
& v2 C# u' u# O2 U	每个人搜索时可探测的半径. g$ l/ z2 ]' }4 K8 [) {6 f# s	. ^- V) E( i) A, j; R# H* N	/ ]) y# E* ? ]- [
* r/ `0 ]$ b5 R0 l r, L9 C	搜索宽度* Y/ t, _( a2 N) r5 R& R( O	' o& @2 h3 t. I9 d5 t	- f9 a0 {* H) a x
) b: R+ I5 l/ l' b	横向格数 3 D& c! c8 Z& H: M	次7 J" d1 u/ q% g$ Y$ m% \|, y	' C& T: U' N8 K4 P) q3 \3 ]
9 Z. r0 O9 z3 j# S6 T" a	纵向格数 9 D p" w7 ?7 E; u* {	次 0 X P: s# J" n- H; \|" y# y+ u	3 ~( C( R! d) Z9 c
; I h- S, J9 ]& D. m Y2 h+ f! }: }. O	以返回集结点的时间1 j- Z$ G" Z- s	小时3 S2 r; Z, e! k! z2 m8 m: d	+ R% i5 X8 C7 G _, v3 t
, A4 g& T; G6 i	起点到开始“拖”的时间 ( U, a0 F& Y% v' Q5 A! S	小时 : B% ]! L0 U/ ~) j. }3 A	7 @. D" Z' w$ I7 ~; r G
" }) T& Z! A" C& J! d u) j# e	增加的人数 # O- \; t' n- `5 Q	人 \9 t6 n7 c" Z$ g( Q2 t1 D0 d5 j4 D	2 H) k( U( \|+ t2 G; @
# @$ s3 v1 t) S/ N1 _* S	人数$ Y2 N- R4 { Z1 g% n% \* S	人 - J2 H1 L' O3 S0 `, N* C9 H	0 ]& n2 d) z5 L
- e1 L& N% u% d; Q! F	区域短边长度 ' N% ]8 i& m( a5 w- a9 l	2 _' Y+ Z. Q* P2 c8 C: w	# U# [9 I6 o- Q- Q
6 ?& t" c/ c* }8 I7 U( p! A	区域长边长度 , f: ^5 F& ^ b V! T! [	7 d' c4 F; k' l' N) q	% B# b: B) v3 C, `! u
3 k8 @* Q7 A1 @	第一、二分区; \$ {1 g: S4 N- D	$ `7 l, n3 ?; {" \|2 f" o	1为第一分区2为二分区 2 Y/ e- a/ K- L; g* ]( v
n# W6 G+ m2 Q" S& @7 O	第一、第二分区人数& m% f/ X' {0 n8 C0 u6 d	人 7 _+ w" ~! a" Y8 B) ?- j	1为第一分区人数2为二分区人数0 X0 u3 o2 I/ q% f

四、模型假设

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

附录

$ ]- L) C! |+ }( V4 S

附件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
& {: s. ]' W; I7 t4 G& r, ?82250.85( G1 ^7 G, Z+ T3 t. B0 k. o
1( j* E5 K3 ]+ r$ m+ m. r: n4 }" p7 T
0.000000
3 ?" c) F* f& I* L2 C7 T) S
T
4 ?. d2 f# R* T5 d3 V/ V22.847462 h3 D" C5 K5 `- t; j
2/ q9 [& G1 ~7 O: n) A# |5 i

0.000000
8 T/ h! P5 s* e9 j* C# B

zan