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

问题二：将目标区域按短边分成三组，并与问题一同理在各自区域搜索。模型如下：
其中， 1 u" s. O9 }: J' W @ K, w

4 |7 f4 ^- @9 E

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

三、符号说明

符号! I2 L* W# B5 ?% t( [% G	含义	单位	备注
! I1 E6 ] X7 E8 y6 A' e# [2 V d	搜索完所用的时间 ' n) F; j% @- ]8 \ M' x1 r	小时" Z1 \|8 g6 W5 G3 @	5 h; {! j R2 S& h! U
( j. G; e/ L. i; [	第一种转角的次数/ _, E8 Q1 w; A2 ~	次( j7 c" g2 I# d" S- F0 V5 \|8 T	见转角说明B图 9 L6 ~& ]" k+ y
$ ?% R/ t' S# n0 K- [3 ~	第二种转角的次数8 G" \|% N4 n1 b* `	次4 O5 y6 z0 o+ ?0 E+ f7 p" p	见转角说明A图; M$ }- j9 v9 {, ^; \; {
* W8 \|0 ]0 v" Q# H5 [3 J	搜索时的平均速度. X" g Z: Q! _' Q' z	. v1 m; i9 f, X	* q4 @3 [+ M2 a1 o' S7 F$ U# s
# O# ?6 ?% B1 M& m% b7 H1 d! u	不搜索只行进的平均速度- F7 t% u5 a! ?	) o* b7 a! `; Z3 h5 s( i8 V9 A	) e. {/ V9 J8 r+ F, Q3 ?6 a
+ ~) F! l K" F/ e% G, N" ^% }4 N	每个人搜索时可探测的半径 # V( O7 @2 k! Z) e0 e# x	( p" G x X2 F' i; G	9 r( y0 `& i; o, J( e8 r
8 v+ j& `8 L1 w! R* r2 g9 ~- ~% ^	搜索宽度 ( b% T* f8 S) B! o5 _8 b& O0 m	* W f+ b/ H/ Q! n+ O# q	* }: W. ]+ L# W
! }0 H0 J! b: @	横向格数 / A) S2 X8 _% A' X8 o, _2 b* K	次2 g8 T1 ]7 g- ~) L	& }" B8 G4 S1 K4 ~3 U
) O( R7 C9 @5 z( u+ C8 \|* Q	纵向格数/ k6 S8 e, z+ u% D) \	次 \|* R( c* K m& v6 K0 G	1 T7 z4 m9 v; l- f
: Z" w! F* [8 d" Y6 E, x	以返回集结点的时间4 U# C4 e( r% Y0 ]& Q4 B	小时! s& {9 C h* F6 U* t	* F1 \6 g. D" v/ O3 H. U
9 j2 x U/ B6 @1 ?1 \|/ q, O	起点到开始“拖”的时间 4 Q g) Y* f3 e$ G) S	小时 p9 U' p- x* \|6 `	/ z" ]; s. e* ]
* j8 M3 W) T/ D3 \	增加的人数 7 Q! `8 \|( Q$ C9 ?4 d; b; y	人 ; B0 J- W$ R) h2 g, M, r8 \|	3 s: V8 e2 o$ l8 Y* }; Y0 a9 \
, W' f: s- `: w Q2 l# f	人数; L* W. q/ k) I- ` H	人1 Q3 l+ z. H5 t% ~# [- j	9 n/ Y, Q; B$ l" m. c
1 c$ u: ?' V) w: B% v. f	区域短边长度 2 N* F2 z% I( r	! k% i: ^! ^# p" S6 O- {/ _	\|: Z! b) d3 S/ V; f
# s6 `7 A. `& h6 V. p. O( M	区域长边长度- m$ r0 Q3 Z n3 N0 _	J2 \: b$ w0 R& f+ f' N- ~	( S3 B) G2 \|1 _7 c5 A
. F- `; G+ S, a$ \|/ p1 T+ C0 W+ v	第一、二分区% I s; v6 e9 j	& H9 [- z- P+ O4 t* _	1为第一分区2为二分区 & K7 g S6 c$ O' M1 S
( C6 N* S# a% }, j) {2 F, M# B	第一、第二分区人数- K5 f& {2 }( m$ }) z: u	人$ c0 s4 f6 M) @# y6 t) y3 D+ D0 S) c	1为第一分区人数2为二分区人数 , S' L+ V3 J: b; Y3 b

四、模型假设

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

附录

9 ~ D/ M" b. d% Q7 ^

附件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
) Z' q- v( q( G, y, ]! T3 P* C; K82250.853 @/ i7 Y3 q1 J2 T. d
1
/ G3 t, ^0 I9 K9 o' C! B* z0.000000' a( U6 o a: d+ R8 [# A

T0 a, U( S2 J5 R0 ?# T6 k0 b. X# D
22.847465 ~0 p; V& P4 `# Z1 e- q
2
) u) W/ i( h- I5 I. A5 k
0.000000' l: }9 a0 R/ R. o; P

zan