搜索
暑期建模培训评阅栏评阅号评阅情况学员评语教员评语暑期建模培训评阅栏评阅号评阅情况学员评语教员评语2013高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》(以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载)。我们完全明白，在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料(包括网上查到的资料)，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示(包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等)。我们参赛选择的题号是(从A/B/C/D中选择一项填写)：B我们的参赛报名号为(如果赛区设置报名号的话)：所属学校(请填写完整的全名)：中国人民解放军理工大学参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：(论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。)日期：年月日赛区评阅编号(由赛区组委会评阅前进行编号)：2013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号(由赛区组委会评阅前进行编号)：赛区评阅记录(可供赛区评阅时使用)：评阅人评分备注全国统一编号(由赛区组委会送交全国前编号)：全国评阅编号(由全国组委会评阅前进行编号)：运动目标快速搜索辨识摘要护航是我军的经常性任务，具有重要意义。运用舰载直升机快速完成一定区域内可疑运动目标的搜索辨识是护航最重要的任务之一。本文讨论的问题可归结为对可疑运动目标搜索辨识的路线优化问题。针对各个问题给出的不同条件，建立了相应的模型，并进行求解。问题一中，运用余弦定量得出直升机对单一可疑目标的最优搜索路线。考虑多可疑目标时，采用聚类分析的方法，将目标进行分类，得到若干聚集小区域。针对小区域内的搜索，本文建立了基于聚类分析和贪婪算法的优化模型以及基于聚类分析和模拟退火算法的优化模型两个模型。利用MATLAB求解模型并比较得到，最快搜索时间为721秒。问题二中，用两架直升机对22个运动的可疑目标进行搜索辨识。考虑到飞机的整体搜索效能由最后搜索完毕的直升机决定，则需给两架直升机合理分配任务量，使差值最小。分配方法为，先进行聚类分析，得到若干偶数个小区域。再以这些小区域的几何中心的位置分布为主要因素，将小区域进行聚类分析，得到几块位置相对集中的小区域群。分类时，将这些小区域群均分成两部分，若两部分的任务量不同，需合理修正至相同。在小区域群及小区域内部的搜索，仍可以构建问题一中的模型。利用MATLAB求解得，在最优路线下，一架直升机的搜索时间为1256秒，另一架的搜索时间为1568秒。问题三中，要实现保护重要货船及搜索时间最短的双目标。先定义危险性系数，利用层次分析法得到距离和时间的影响权重。为保证安全性，先派遣一架直升机搜索辨识危险性最大的可疑船只，并且由于该机在开始的一段时间没有进行搜索辨识，应分配更少的任务量，使得搜索完毕时间差值最小。在小区域内的搜索辨识仍采用问题一的搜索算法。从而保证在确保货船安全的前提下，最快搜索辨识完所有目标。利用MATLAB求解得，直升机搜索最危险目标的搜索时间为420秒，总搜索时间为1865秒，另一架的搜索时间为1920秒。关键词：余弦定量，聚类分析，层次分析，危险性系数，贪婪算法，模拟退火1问题重述亚丁湾护航，是中国海军在亚丁湾索马里海盗频发海域护航的一项军事行动。自2008年12月26日起，我海军已派遣10批护航编队担负护航任务。在护航期间，舰载直升机主要完成搜索目标和营救任务，特别是对于水面上可疑运动目标的搜索辨识是最重要的任务之一。军舰在护航过程中，通常可以通过舰载雷达扫描发现50km以内的可疑目标，一旦发现可疑船只，舰载直升机就会紧急起飞，执行搜索辨识这些可疑船只的任务。当直升机进入以待辨识目标为中心，半径为2km的圆型区域内即可识别可疑目标是否为海盗船。在同一时间、同一区域内会有多个运动的可疑目标，问题是如何才能够最有效地搜索辨识所有的可疑目标。军舰通常跟随需要护航的船队航行，船队的航速一般为15节，航向为正北方向。如果军舰载有两架直升机，直升机的飞行速度为250km/h，最大续航能力为2.5小时。请你们结合军舰护航的实际问题，通过建模研究下面问题：（1）现通过舰载雷达发现有10个运动的可疑目标正在接近护航船队，并即时测得这些可疑目标的相对位置、航向和航速数据如表1所示。请你们给出一架直升机最优的飞行搜索辨识策略和路线。（2）如果在50km的范围内舰载雷达发现22个运动的可疑目标，并测得的相对位置、航向和航速如表2所示。为了快速搜索辨识这些可疑目标，可以同时起飞两架舰载直升机执行这个任务。请你们给出这两架直升机最优的飞行搜索辨识策略和路线。（3）现在有相对位于（20，25）（km）处的重要货船请求护航保护，该货船的航速15节，航向310度。可疑目标船只如表2所示。请你们给出两架直升机最优的飞行搜索辨识策略和路线，使得所用时间尽量短，而且使对货船的潜在威胁程度最低。2问题分析本文研究的是运动目标搜索路线优化问题。首先需要定义最优。由于可疑船只对舰队有一定危险性，越快搜索完毕越安全。因此本文主要考虑搜索时间最短为优化目标，根据运动的几何关系，主要运用余弦定量，得到直升机搜索单个可疑目标时的最优搜索路线。其次，采用合适算法优化直升机对各个可疑目标的搜索辨识顺序。问题一是求一架直升机搜索十个目标的最优策略和路线。题中十个可疑目标的相对位置、航向和航速各不相同，但分析发现在一定范围内有趋同性。而直升机在搜索时，一次性搜索完临近的几个可疑目标比跳跃式的搜索要更省时间。因此，先对该十个目标进行聚类分析，得到几个小区域。由于可疑船只的速；度要比直升机小得多，直升机搜索时可疑船航行距离相对于直升机搜索的距离可以忽略不计。则聚类时可以主要考虑相对位置，忽略可疑船只的航向和航速，从而简化了问题，减小了计算的复杂度。小区域内的可疑目标的位置相对集中，直升机可以依次进行搜索辨识。本文分别运用贪婪算法、遗传算法进行搜索。搜索过程中，直升机每搜索完一个小区域之后，可疑船只的相对位置会发生改变，则不能采用之前的分类。因此重新进行聚类分析，确定新的小区域分布。再根据小区域的分布情况，确定下一个搜索的区域。如此反复，直至搜索完毕，这样就能保证在每一次小区域搜索过程中，都使搜索时间最小。本题的难点在于搜索期间，可疑船只的位置时刻变化。本文采用两种解决方法。一是直升机每搜索完一个小区域之后，重新进行聚类分析，确定新的小区域分布。一是将区域分的足够细，使得在每个小区域中搜索时，可疑船只的相对位置改变可以忽略不计。这样就能使得在每一次小区域搜索过程中，都使搜索时间最小。从而以局部最优逼近全局最优。问题二是在舰载雷达发现22个运动的可疑目标，并测得的相对位置、航向和航速的情况下，同时起飞两架舰载直升机进行搜索。求这两架直升机最优的飞行搜索辨识策略和路线。同样可以先进行聚类分析，得到若干偶数个小区域。再以这些小区域的几何中心的位置分布为主要因素，将小区域进行聚类分析，得到几块位置相对集中的小区域群。分类时，将这些小区域群均分成两部分，若两部分的任务量不同，需合理修正至相同。用两架直升机分别对这两部分进行搜索。在区域群及小区域内部的搜索，可以采用问题一中的搜索算法。从而使得两架直升机的搜索效能同时达到最大化。同等时间内，直升机的搜索效能相同，整体搜索效能由最后搜索完毕的直升机决定。则保证两架直升机的搜索效能的差值最小就保证全局搜索效能最大，则其相应的搜索路线即为最优搜索路线。问题三是在要尽量保护重要货船的情况下，同时求出搜索时间最短的最优飞行搜索辨识策略和路线。首先确定对货船危险性最大的可疑目标。影响危险性大小的因素主要有可疑船只与货船的距离以及可疑船只追上货船的时间长短。利用层次分析法得到距离和时间的影响权重，从而定义危险性系数。用MATLAB得到各个可疑船只的危险性系数，然后选出危险性最大的可疑船只。为保证安全性，需先派遣一架直升机搜索辨识危险性最大的可疑船只。再以该可疑船只所在位置及原点连线为分界，将小区域分成两部分，并合理修正尽量使两架直升机搜索完所有目标的时间大致相等。由于先去搜索辨识危险性最大的可疑船只的直升机在开始的一段时间没有进行搜索辨识，则应分配其更少的任务量。在小区域内的搜索辨识仍采用问题一的搜索算法。这样用一架直升机保证货船的安全，并合理分配两架直升机的搜索任务量使得搜索时间差最小，从而保证在确保货船安全的前提下，最快搜索辨识完所有目标。3符号说明直升机t时刻的坐标(,)ttxy可疑船只i在t时刻的坐标(,)iittxy可疑船只i的速度iv直升机的速度v直升机搜索的路线长度l直升机的可辨识半径R军舰护航的货船在t时刻的位置(',')ttxy船队速度'v4模型假设（1）护航船队的航速为15节，舰载直升机飞行速度为250km/h，最大续航能力为2.5h，其在半径为2km的圆型区域内可识别可疑目标；（2）直升机忽略起动时间；（3）舰艇、可疑目标、护航船队的航向和航速不变；（4）直升机的辨识距离为二维空间；（5）直升机对可疑目标的截相遇采用直线方式；（6）直升机可以同时辨识进入其探测区域的所有可疑船只；（7）可疑船只对船队中的货船没有危险；5问题一的求解5.1问题一的模型准备5.1.1搜索线路准备图1是利用excel画出的可疑船只的初始位置分布图，军舰在原点位置，直升机从原点处起飞开始搜索。当直升机进入以待辨识目标为中心，半径为2km的圆型区域内即可识别可疑目标是否为海盗船。图1可疑船只的初始位置分布图根据相对运动概念可知，即可疑船只进入直升机半径为2km的圆型探测区域，就会被辨识。由于已知可疑船只的运行速度、方向、位置，则直升机在一点辨识完之后，能够预知到达下一个搜索目标的位置，从而使得可疑船只刚好在圆形探测区域的边界上。这样就将动态的可疑船只变为静态的。直升机飞行的最短距离由直升机的初始位置与目标在时间t时所处的位置确定。图2最短识别时间的几何关系图2表示了最短识别时间的几何关系在时间t内，直升机从A运动到B，可疑船只从1A运动到1B。则直升机至少要沿着直线AB飞行cR的距离。因此A𝐵𝐴1𝐵10min{:}ttvtcR在图2中，利用余弦定理，上面的式子可表示为2220min{:2cos}iittvtRavtvta图3最短时间识别中的几何关系根据图3中最短时间识别中的几何关系，且1v、iv、r、a和cos都是已知常量，化简关系式就变成22220min{:()(22cos)0}iittvvtvRvatRa所以，0t可由如下二次方程的根求得22222()(22cos)0iivvtvRvatRa如果220Ra，则上述方程有两个符号相反的根，易知100,[,],.taRtaR其中1t为方程的正根，1[]t表示超过1t的最小整数。如果01tt，那么只有一条最短的识别路线；如果01tt，那么就有无数多条可行的识别路线。5.1.2最优系数确定（1）搜索效能分析搜索效能即为在最短的时间内，尽可能快得辨识出更多的可疑船只。（2）层次分析法确定最优系数A𝐴1𝐵1𝑎𝛽𝑣𝑡+𝑅𝑣𝑖𝑡（5.1）（5.2）（5.3）（5.4）（5.5）5.1.3聚类分析（1）综合考虑可疑目标的相对位置、航向和航速，利用spss软件进行聚类分析，得到图4。此时有两种分法，一是船只分为4、5、6、8和1、2、3、7、9、10两