海上静态目标最佳搜索方案模型数学建模竞赛论文

同济大学数学建模竞赛论文1海上静态目标最佳搜索方案模型摘要针对MH370搜索，本文根据MH370的相关参数，确定了可能坠落的区域，并通过分析最可能航线，对该区域进行网格划分，通过求解沿各条基线两边呈正态分布的概率密度函数在划定的特定区域的积分来确定各子区域的坠落可能性。首先以伊尔-76运输机为基础，综合考虑了续航、最大燃油航程等飞机离散搜寻特征，简化建立其搜索范围与搜索半径。通过拉格朗日逐点乘数法和渐进搜寻方法，建立了离散搜索能力对静止目标的最优搜索模型，并结合MH370可能航向所建立的各个子区域坠落几率模型，求解出各子域的重要度指数，并按照其重要度指数依次排序进行搜索。对于多搜索工具的统一调度问题，则是首先根据第一题所解出各个区域的重要性指数划分出几个区域，确定这几个区域的搜索顺序，以提高搜索效率。之后根据不同搜索工具的各项特征，包括位置特征、自身性能指标等，建立海上立体联合最优搜寻模型，并给出了求解算法。关键字：离散搜索联合最优搜索2一、问题重述1.1背景资料马来西亚航空370号班机空难，是指2014年3月8日一班从马来西亚吉隆坡前往中国北京的波音777-200ER航机失踪的事件，被认为是有史以来“最离奇”的飞机失联案列。空难的谜团能不能解开，很大程度上取决于能不能打捞到“黑匣子”。MH370的失联，各国为此出动了25架飞机，40艘舰艇，甚至包括若干卫星。1.2需要解决的问题（1）以MH370为基本背景，基于互联网报导的这次事件的一些基本数据(如不同搜救设备的搜索能力，速度，续航时间，代价等)的基础上，做出合理的假设、简化，针对某一种搜索工具（如卫星、飞机、船只）讨论其搜索的范围和优缺点，制定相应的最优搜索方案；（2）若假设所有的飞机舰船及卫星都由一个国家统一调度，讨论最优的搜索飞机残骸和黑匣子的方案。二、模型假设2.1问题一模型假设1.飞机在搜寻的过程中不考虑待搜寻海域的环境状况（风、浪、流、气温、水温等）；2.搜寻过程中使用的飞机型号均相同，为伊尔－76运输机；3.假定飞机在搜寻过程中保持300米的飞行高度不变，则搜寻范围为以飞机为顶点的圆锥形放射状，投影在水面上则为圆形的搜寻区域，如图2.1图2.1根据伊尔－76运输机飞行660公里，搜索面积约7000平方公里考虑，可近似假设该圆形搜索区域的半径为4公里，则搜索宽度为8公里；34.5.6.假定黑匣子与飞机的主体残骸为非漂流物，即在失事地点沉入海底，不在洋流与风压影响下运动；伊尔－76运输机的最大燃油航程为7800公里，而本模型划定的黑匣子和飞机主体残骸的可能沉入目标总区域为520公里×520公里的矩形范围（具体见下文），因此可以忽略飞机的续航问题；黑匣子只能持续自主供电发出信号30天。2.2问题二模型假设1.不同搜索工具的代价与行驶的距离成正比；2.在待搜索区域附近有多艘可用专业搜寻舰船、多架可用专业搜寻飞机、多艘可用过路船舶及多颗可用卫星，以此构成了立体搜索力量全体。其中专业搜索舰船和过路船舶距待搜索区域的初始距离、最大航速、搜寻能力不一定相同。专业搜寻飞机的距待搜索区域的初始距离、最大航速、搜寻能力、最大续航时间也不一定相同；3.所有可用卫星的搜索能力、运行速度、运行高度完全相同。三、符号说明3.1问题一符号说明——黑匣子或飞机主体残骸位于子域的概率；——黑匣子或飞机主体残骸位于子域且对该子域实施了次搜索的发现概率；——对子域实行次搜索的费用；——黑匣子或飞机主体残骸位于子域且施加于该子域的最初搜索没有发现目标而在第次发现目标的概率；——对子域第次搜索的费用；——执行搜索计划时在最初的次搜索中施加于子域的搜索次数；——采用搜索计划时施加于子域的搜索次数。3.2问题二符号说明：——待搜索海域面积；——可调用的舰船数；——可调用的飞机数；——调用参与搜索行动的卫星数；——每艘舰船距待搜海域的初始距离（——每架飞机距待搜海域的初始距离（——每艘舰船的搜寻能力（——每架飞机的搜寻能力（，，，，，）；，）；，）；，）；4——每艘舰船的最大航速（——每架飞机的最大航速（——每架飞机的最大续航时间（，，，）；，）；，，）；，，）；——第j架飞机在整个行动中出动的次数（——第i艘舰船以最大航速驶至待搜寻海域所需要的时间；——第j架飞机以最大航速往返待搜寻海域所需要的时间；——第i艘舰船在待搜海域中进行搜索作业的时间；——第j架飞机在待搜海域上空进行搜索作业的时间；——待搜寻海域可容纳的搜索舰船的数量上限；——待搜寻海域可容纳的搜索飞机的数量上限；T——整个搜索行动的总耗时。四、模型的建立与求解4.1问题一的模型的建立与求解在MH370的搜救背景下，本模型针对飞机这类搜索工具，讨论其搜索范围和优缺点，并制定最优的搜索方案。新华网报导在3月26日，中国空、海搜救力量在南印度洋回合，密切协同，全力对疑似马航客机失去联系附近海域展开立体搜寻。而中国派出了伊尔－76机组，实时云底高500米左右，风速12米每秒，浪高3－3.5米。获知任务海域气象和海况信息后，伊尔－76机组立即从9100米高空从容下降，在500米高度钻云而出，并保持300米高度对任务海域展开搜寻。8时许，伊尔－76机组到达任务海域，10时许，离开任务海域返回珀斯，总计在疑似海域飞行660公里，搜寻面积约7000平方公里。伊尔－76运输机具体参数如表4.1：表4.1中文名机长机高翼展机翼面积空重伊尔－76运输机46.59米14.76米50.50米300平方米70吨引擎起飞重量燃油重量平飞速度巡航速度最大燃油航程AviadvigatelD-30170吨70吨850公里/小时750-800公里/小时7800公里5为简化该模型，做出如下假定条件：针对第一题，本模型所要研究的问题可以描述为：在派出参与搜寻的飞机总数为40即总资源一定的前提下，如何分配飞机资源，才能使搜索到黑匣子或飞机主体残骸的概率最大或者使搜索成功所耗费的飞机资源期望值最小，而这个问题的基础是概率论，主要包含三个要素：[2]（1）目标位置和移动路径的初始概率分布。这是所有的搜索问题都需要涉及到的，并且需要首先解决的问题，比如在MH370的搜寻问题中，搜寻失踪飞机的初始位置信息、所在南印度洋的海域环境信息等。（2）探测函数。假定黑匣子和飞机主体残骸确实位于某个区域，将投入到这个区域的飞机搜索资源或者搜索时间与成功搜索概率之间的函数关系称为探测函数关系（DetectionFunction）。（3）对可用搜索资源的约束条件。对MH370的搜索不可能无休止地进行下去，搜索资源是有限的，都会受到诸如时间和人力资源的限制。给定探测函数和目标的概率分布后，本模型要解决的核心问题就是在飞机总数即总搜索资源一定的情况下，如何分配搜索资源使得成功搜索到目标的可能性最大或花费的搜索代价最小。针对这个问题，本模型初步构想到，一种方法是使每个瞬间搜索成功的概率达到最大，另一种方法是在搜索过程中每次都挑选搜索成功概率最高的区域进行搜索，渐进迭代。根据文献[1]，可以知道，离散搜索力是相对于连续搜索力而言的，连续搜索力顾名思义，是指搜索力可以连续不断地施加于搜索区，舰载声呐、拖曳声呐的搜索力都是连续的。而目前伊尔－76运输机等飞机的搜索力呈间断方式一次次施加于搜索区，因此是离散搜索力。下面就根据离散搜索力，具体从上述提到的三个要素进行模型的搭建。4.1.1初始概率密度函数初始概率分布函数及黑匣子和飞机主体残骸的位置的初始概率分布函数。在MH370的海上搜救行动中，黑匣子和飞机主体残骸的初始位置的确定，在不同的情况下有不同的遇险初始位置信息的来源，具体包括：我们引入概率分布函数，具体定义如下：其中，当，，且根据前述假定，黑匣子和飞机主体残骸为非漂流物，因此。本模型假设了10条可能航向，可能航向在搜索区域的可以视作搜寻的基线。在基线区域内，遇险目标分布概率在搜寻基线附近最高，并且离开基线越远，概率越低，基线两边均为正态分布。6图4.1基线区域内概率密度分布图以通过搜索资料得到马来西亚航空370号班机的失联地点（北纬06°55’15”,东经103°34’43”）为原点。搜索区域根据资料做出一定简化假设为以失联地点为中心520km×520km的方形区域。以失联地点为中心建立直角坐标系，如下图4.2所示图4.2直角坐标系的建立可能的航向在该坐标系中都可表示为通过原点的直线，分别记作，，，，，，，，，，下面给出各条直线的具体方程：：：：；：；：；：；：；：；；：；：；；失联客机向各个航向飞行的可能性相同，并且根据客机燃油、雷达信息等因素本模型认为其飞行的最大半径为的性质可以确定基线区域内概率密度分布函数的参数坐标系下的概率分布函数为（。根据正态分布函数，因此得出在整个）式中为直线的斜率为了便于调配将520km×520km的搜索区域分为40km×40km的小区域，总数为个。失联客机在每个小区域的概率为对于整个方形搜索区域来说7各个小区域在540km×540km的范围内子域的条件概率为4.1.2探测函数本模型对探测函数的定义为：在中找到目标，其中是搜索飞机在时刻的位置。一般情况下，探测函数用来表示即可[2]。而在本模型中，采取了一个便于测量的形势，定搜寻飞机的搜寻范围宽度的8公里为，即为距离，在这个距离内飞机搜索不到目标的概率与在这个距离内飞机搜索到目标的概率相等。4.1.3探测资源模型假定在搜索路径已经给出的条件下，可以定义搜索资源分配函数如下：函数意义为在时间区间中，能分配到点处的搜索资源。4.1.4离散搜索能力对静止目标的最优搜索模型在前述计算初始概率密度函数时，本模型将目标分布区域划分为13×13共计169个子域，其中，根据前述初始概率密度函数的计算结果，可以得到黑匣子或飞机主体残骸位于子域的概率为。并假定搜索的时间有一定的限定，上限值为，并根据黑匣子从失事开始能持续供电发出信号时间为30天的特征，记天。本模型构建一种搜索策略，将总搜索时间分为相等的等分，使每一等分至少可以搜索一个子域。先给出一个定义：离散搜索力的搜索计划定义为一个有序的数组：，其中为搜索力量的总量，即投放飞机的总次数，搜索每个区域的时间。其中，的含义是采用搜索计划时，将第一次搜索施加于第子域，若第一次搜索没有发现目标，则把第二次搜索施加于第子域，以此类推，直到成功搜索到黑匣子或飞机主体残骸，或者搜索的时间耗尽，这时，的全排列可达到，而其中允许出现重复数字。这又是因为在有限的单位子域搜索时间内，即使目标在所在子域里，也存在不能发现的概率。在这排列中，每一个排列都对应一个搜索计划，并且对应相应的成本开销，搜索计划不同，搜索效率也差别很大，本模型的目的就是要寻求最优的搜索计划，使得发现黑匣子或飞机主体残骸的概率最大。关于发现黑匣子或飞机的主体残骸的概率和相应的总搜索费用的定义和二者的约束条件定义如下：用表示第次查找第子域，并查找成功的概率，由此可知：8当且仅当搜索计划中存在对子域的第次查找，才存在，由此可见，搜索成功的概率与子域的查找次序无关，只与搜索计划中对每个子域的查找次数有关。为总搜索费用的上限，用表示对子域的第次查找的费用，因此，为使得搜索次数最大化，总搜索费用应满足：同样，当且仅当搜索计划中存在对子域的第次查找，才有意义。因此，对于黑匣子或飞机的主体残骸的概率和相应的总搜索费用来说：同时还需要满足约束条件：其中为飞机或者时间资源的约束上限。根据资料[1]，采用拉格朗日乘数法可以将目标函数和约束条件放在一个公式中，将带有约束条件的极值问题求解转化为普通的求解极值问题。构造拉格朗日函数如下：其中叫做拉格朗日乘子，该函数称为逐点拉格朗日函数，且，，对于一个带有参数（数量或者时间）的资源配置是最优配置的充分条件是函数满足：对求导：求解，可得最优搜索方案如下：其中必须满足成本开销约束条件：令则可以求出对应的的值。上述介绍的拉格朗日乘数法得到的是具体的资源分配方案，但是不能给出具9体的搜索顺序，即所求解的搜索方案。因为飞机的离散搜索是一次次进行的，并且每个任务子域都为40公里×40公里的范围，且在范围内的搜索模式相同，具体见下文论述，因此每次出任务搜索子域的搜索费用是只与距离相关的函数，因此对子域的单次搜索费用均相同。若=递减，可按下述方法寻求搜索计划，令满足：在确定了前次搜索之后，令满足：这种方法用了渐进的搜索方法，在搜索过程中每次都挑选搜索成功概率最高的区域进行搜索，并且考虑目标确实在子域，但是却被忽略掉的概率，这样得到的搜索计划就是最优的搜索计划。4.1.5求解离散搜索能力对静止目标的最优搜索模型因为前述假定黑匣子和飞机的主体残骸都不随洋流或风压运动，为静止目标，因此初始概率密度函数结果即为黑匣子或飞机主体残骸位于子域的概率。表4.21234567891011121310.00070.00100.00140.00200.00270.00340.00400.00460.00500.00530.00530.00540.005320.00110.00140.00200.00270.00340.00430.00500.00570.00620.00630.00630.00630.006230.00170.00210.00290.00370.00460.00540.00630.00690.00720.00730.00720.00700.006740.00260.00320.00400.00490.00590.00670.00760.00800.00830.00820.00790.00760.007050.00360.00430.00520.00620.00720.00800.00870.00900.00900.00870.00830.00760.007060.00470.00560.00640.00740.00830.00920.00960.00960.00950.00890.00820.00730.0066的值70.00570.00660.00740.00830.00920.00970.00990.00970.00920.00830.00740.00660.005780.00660.00730.00820.00890.00950.00960.00960.00920.00830.00740.00640.00560.004790.00700.00760.00830.00870.00900.00900.00870.00800.00720.00620.00520.00430.0036100.00700.00760.00790.00820.00830.00800.00760.00670.00590.00490.00400.00320.0026110.00670.00700.00720.00730.00720.00690.00630.00540.00460.00370.00290.00210.0017120.00620.00630.00630.00630.00620.00570.00500.00430.00340.00270.00200.00140.0011130.00530.00540.00530.00530.00500.00460.00400.00340.00270.00200.00140.00100.0007而为对子域搜索第一次发现黑匣子或飞机主体残骸的概率，这对同一机组来说，概率相同，即都相等。为对子域第次搜索的费用，飞机在子域的搜索方式相同，故可认为搜索费用相同，因此从出发点到子域距离的函数，满足：表4.3123456789101112131897.38869.71843.38818.56795.45774.26755.22738.56724.52713.33705.18700.22698.562869.71840.81813.20787.07762.62740.10719.76701.88686.75674.63665.77660.37658.563843.38813.20784.25756.70730.81706.82685.04665.77649.37636.17626.48620.56618.564818.56787.07756.70727.68700.22674.63651.23630.39612.51598.03587.34580.78578.565795.45762.62730.81700.22671.11643.77618.56595.92576.33560.32548.41541.05538.566774.26740.10706.82674.63643.77614.54587.34562.65541.05523.19509.76501.40498.56的值7755.22719.76685.04651.23618.56587.34557.97530.97507.00486.89471.54461.87458.568738.56701.88665.77630.39595.92562.65530.97501.40474.68451.80433.97422.52418.569724.52686.75649.37612.51576.33541.05507.00474.68444.83418.56397.45383.48378.5610713.33674.63636.17598.03560.32523.19486.89451.80418.56388.27362.78345.05338.5611705.18665.77626.48587.34548.41509.76471.54433.97397.45362.78331.70308.00298.5612700.22660.37620.56580.78541.05501.40461.87422.52383.48345.05308.00275.13258.5613698.56658.56618.56578.56538.56498.56458.56418.56378.56338.56298.56258.56218.5610因此可以计算出下式的值：如下表所示。表4.41234567891011121310.751.121.662.453.424.445.316.216.927.437.527.777.5921.251.702.473.464.515.816.978.168.979.349.479.549.3532.042.643.654.926.277.709.2010.3311.0311.4811.4311.3110.8843.154.005.306.698.399.9811.6612.7313.5613.6513.4113.0712.1354.505.647.068.8010.6712.4614.1315.1415.6615.6015.1514.0313.03的值（单位66.117.559.1211.0412.9114.9216.3417.0617.4716.9816.0214.5713.2277.599.1610.8712.7614.8216.5817.7118.3518.0817.0615.8014.2712.5088.9210.4112.2614.0915.8717.0618.0818.2817.5016.4914.8513.2211.29）99.6911.0612.7914.2715.6616.6817.2416.9016.1014.7212.9811.219.46109.8411.2512.3813.6514.8315.3315.5914.9014.0312.5411.069.137.62119.5510.5411.4312.4413.0613.4913.3712.5411.5310.278.646.985.76128.809.5410.1610.8511.3811.4310.8610.178.977.896.515.214.21137.598.278.579.169.319.198.758.217.195.924.703.773.08根据计算结果，将子域递减排序，则根据模型得出了走遍待搜索区域的最佳方案。图4.3区域重要性11重要性程度从左至右递减如下所示：这里补充对于每一个分割区域的大小都为40km×40km的方形具体搜索方法。飞机的搜索范围是半径为4km的圆，其搜索宽度为8km。因此可以将40km×40km的区域分成8km×8km的小区域，则有5×5个小区域。无论如何搜索，在指定区域内最短的搜索时间等于总的搜索面积与飞机单位时间搜索面积的比值。把每个8km×8km的小区域中心看作图中的点，要寻找到其搜索的最佳线路就是需要寻找经过每一点一次且仅一次的路径，即其路径是“一笔画”，图4.4给出的就是一种拐角最少的“一笔画”路径。图4.4一笔画路径但是上述“一笔画”路径并不能完全覆盖整个搜索区域。显然在拐角处搜索覆盖的范围是一个半径为4km的圆，它是边长为8km的正方形的内切圆，因此不能覆盖拐角的阴影部分（见图4.5）图4.5拐角实际上，“一笔画”搜索路径未能覆盖的搜索面积为阴影面积，占总面积的。由于仅有的面积未被“一笔画”路径搜索到，而且该路径的全部时间都用于搜索，因此决定在该路径的基础上进行完善以达到要求。沿对角线方向搜索，即往返为可覆盖拐角处“一笔画”未搜索到的区域。综合上述结论可以计算得到飞机搜索一个40km×40km的方形区域所要飞12行的距离为。4.2问题二的模型的建立与求解通过搜索资料，得马来西亚航空370号班机的失联地点为北纬06°55’15”,东经103°34’43”，利用GOOGLEEARTH搜索并确定失联地点周围最近的10座机场。将失联地点与10座机场的坐标连线，得到十条可能性最大的失联后的航线即最可能飞行区域，如图4.6所示。图4.6失联飞行区域海上立体联合最优搜寻模型4.2.1模型的建立根据前文对飞机残骸及黑匣子存在的520km×520km=270400km²区域建立的网格，及对13×13个大小为40km×40km的小格的重要性分析，已得到每个网格的重要性参数。出于对搜索工作的高效性的考虑，采用集中搜索，即将所有能参与搜索的搜索工具同时投入对某一大小适当的搜索区域开展搜索工作。一次搜索的区域不宜过大也不宜过小，出于经济性、高效性及各搜索工具的搜索能力综合考量，将整个520km×520km=270400km²的待搜索区域通过小网格的合并，合并时考虑重要性参数为主要依据，分为九大待搜索区域，如图4.7所示。13图4.7九大待搜索区域划分图对于每块区域，将其包含的所有小格的重要性参数106.51226.95212.6196.37339.6185.55175.23126.1414求和，得113.29则确定该九大区域的搜索顺序为→→→→→→→→。对每个区域的搜索方式相同，现以对区域的搜索为例，给出海上立体联合最优搜寻模型。不同的搜索工具具有不同的搜索能力、速度、续航时间及代价，其中，认为不同搜索工具的代价与行驶的距离成正比。假设在待搜索区域附近有多艘可用专业搜寻舰船、多架可用专业搜寻飞机、多艘可用过路船舶及多颗可用卫星，以此构成了立体搜索力量全体。其中专业搜索舰船和过路船舶距待搜索区域的初始距离、最大航速、搜寻能力不一定相同。专业搜寻飞机的距待搜索区域的初始距离、最大航速、搜寻能力、最大续航时间也不一定相同。而所有可用卫星的搜索能力、运行速度、运行高度完全相同。模型的目标是选择最佳的搜索舰船、搜寻飞机及卫星，并使其协同工作，使完成对整个待搜索海域的搜索消耗的行动总时间T最小，以舰船与飞机联合完成对搜索海域全覆盖为行动结束的标志，舰船与飞机有一者搜索过即认为该区域已被搜索。而使用卫星数量则根据其运行速度、覆盖宽度及舰机联合作业的时间确定。通过资料搜索得，一颗卫星的覆盖区域约等同于宽度30km的条带状区域，一颗卫星的运行速度为，故一颗完成对区域的全覆盖搜索需t=，R颗卫星同时参与完成对Px区域的全覆盖搜索需t/R=，因此调用以参与工作的卫星数R取为[t/T]+1颗。下面对舰机联合完成对搜索海域全覆盖的最优方案进行决策。引入以下决策变量：（i=1,2，…，M），舰船不参与搜徐行动，飞机参与搜索行动，飞机不参与搜徐行动（j=1,2，…，N），舰船参与搜索行动为了以最短的时间对待搜索海域完成高效的搜索覆盖，需对舰船与飞机在整个搜索行动中各自所需时间进行分析。将可供调度的舰船与飞机力量的情况绘制在如图4.8所示的图中，设整个搜索行动的开始时刻为，结束时刻为，则整个搜索行动的总耗时。15图4.8对舰船在整个行动中所需时间的分析：由于每艘舰船的最大航速、距待搜索区域的初始距离不同，故它们到达待搜索区域的时刻（i=1,2，…，M）不同，在图中舰船、可在搜寻行动结束前到达待搜海域，舰船在搜寻行动开始时刻就位于待搜索海域内，舰船在搜寻行动结束前无法到达待搜索海域。因此，、、有参与此次搜索行动的资,对于搜索行动。就如图5.3所示的舰船力量而言，只有舰船格。对于有资格参与搜索行动的舰船而言，均有开始时刻已经位于待搜索海域内的舰船而言，对飞机在整个行动中所需时间的分析：与舰船情况类似，并非所有可调度飞机都有资格参与搜索行动，只有在搜索行动结束前可以飞至搜索区域的飞机可以参与行动。如图5.3所示，飞机可以参与行动，而飞机则不能。对于每一架16有资格参与搜索行动的飞机而言，由于其续航时间的限制，需要来回进行多架次飞行。每架次飞行时间等于其最大续航时间大航速往返待搜寻海域所需要的时间的时间，有两部分构成：飞机以最；飞机在待搜海域上空进行搜索作业。认为飞机飞往待搜索海域与返回基地的时间相等，并不考虑飞机在基地补充燃料的时间。通过以上分析可知，要实现对待搜索海域的舰机完全覆盖需满足：即（）（）由上式接触T，则模型M-1可表示如下：（（）（））（）该模型的目标函数（式5.1）是求整个搜索行动总耗时T的全局最小值，