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

问题二：将目标区域按短边分成三组，并与问题一同理在各自区域搜索。模型如下：
其中，
0 Z8 r0 t. y& G

$ M+ _" L3 S0 I

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

三、符号说明

符号, A6 R1 }2 d* w: {" y	含义	单位	备注
6 f- n+ Q, ]3 ~) `0 d( ~3 q	搜索完所用的时间 " h x+ H% A4 x0 \4 x( O! I& w	小时7 }0 N' [* c) W1 e( x	# ~7 f5 {0 O/ y4 ~
! g/ C3 G& E, D8 I; O4 H3 i# u	第一种转角的次数* w1 u2 P8 H8 i/ A3 A	次 # g% n5 W$ W6 m. h; \|8 E	见转角说明B图6 M9 S& s& q, D& D
5 z2 f5 c2 q% p- z T, _: k	第二种转角的次数1 `6 x) S' d! t% u) b, [	次 ( C& [9 n/ _- Z% z	见转角说明A图* B& [( A5 f C3 K& c
- K, G& l7 l7 ~% j0 Z/ A H	搜索时的平均速度 , G) E7 w2 [8 u2 K	* W1 c% ?, v2 u6 o/ q9 u/ B	- j, \|. F4 \|7 F& P2 c% ?0 E7 U
' E" Q s* l2 Z" R) ^' a	不搜索只行进的平均速度 ) _5 z ?4 R5 I; o+ p( S	1 p1 s, q2 e5 C+ k$ Q	( K2 ?- ~0 B1 B( @$ `+ E; e, b/ K0 F
4 K/ W, [1 \' I3 I8 w	每个人搜索时可探测的半径 " N- J9 q5 q, }) S1 _	- k% `3 C V6 `) t3 i+ q0 y	6 C5 I, g6 A9 n) K/ z/ k
1 u* ?/ G" _' K- v F0 A	搜索宽度. ^, Q8 O! y/ X `$ @$ m P' R! V. C	9 S5 E* h; m9 ?1 {/ O; c z9 p, [8 j	! A* z$ c- E1 U3 h: N- Y
7 K. H+ W$ s# H8 ?$ c0 Y$ J	横向格数 ( e }6 X* S- h4 [	次 5 W0 {4 k' \4 k	* F# T% C) w% I$ U2 ?7 X
* F+ V/ g9 A' C6 V	纵向格数3 w! k/ ?" q0 S5 T6 S# ^	次! j' s# q+ \, P. h. W1 a+ V# R	. I4 v) X3 i3 T S, u2 [
+ g* s. R' o s. C' [' a* u; o$ ~	以返回集结点的时间 5 h& O) P6 R6 { n* f9 a7 P	小时) b+ q. k$ y" ~	! k% V; b! K2 X6 o
0 w q: P* D- s	起点到开始“拖”的时间/ u/ f" ?* t' J4 v" d	小时 ( O7 L- Z& r; G# j2 M	1 k2 H! d& R% d9 ?( j- i
+ c% l4 w$ W' R	增加的人数- r8 S0 x6 `4 i6 x' h1 \	人 # Z. D/ l1 E4 }. w* A) V+ H	) {* i4 P( j: }) u$ Y
& p0 G7 A9 P- ^	人数 $ m) p i5 P. S, p	人. \|/ r1 u- _" \|# G- q	4 d) W+ h# `( j, \, g4 ~! L+ p
- ^3 ]' ~3 T! T; ?( \	区域短边长度 9 p t2 n2 f7 k. N! Y- v; k	! N" P1 t2 p+ p$ N* h	$ M% e9 H3 E3 Q. Q( m9 \|7 t9 c; n2 }
0 ]% o. o% K/ N0 [; S7 r0 b1 d	区域长边长度: A/ B- [0 }1 t8 [# ^	5 t& O4 S' v/ U* U# {5 L- i	* Z% O4 m: {/ K0 U- G; z
) B9 R- L0 S8 G% I6 J! I2 _	第一、二分区 3 \8 W7 \6 {) p	3 G6 c4 h5 \$ N1 A" ?2 S0 E! ^	1为第一分区2为二分区 , n) V. F. Z+ I8 j% g$ \|- T) ^
8 c# L8 M' K+ C( a5 _/ o	第一、第二分区人数2 }) ~- V/ x2 P7 O! b. p2 Y	人 $ H, y( o. r2 e0 h	1为第一分区人数2为二分区人数 3 W3 P( ]; r' z( Y: ]

四、模型假设

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

附录

- N+ \: |9 g8 d& j# 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. [4 g$ r5 a  D5 \% ^# g
82250.85: B) l" }/ W6 P
1( E% f+ Y& D( c: F. k
0.0000009 h, S! |3 G$ e* \0 i1 ]! x+ ~

T
" U! y1 Y9 g) E, G) B' \! @22.84746
7 v9 X6 Q, g0 j% ~& |4 d  L2
$ G9 e7 i2 i; h: p. o
0.000000
; F+ O& R! c3 l* U  Q

zan