基于图论和非线性规划求最佳搜救路线问题数学模型

1、 2014年河南科技大学模拟训练一承 诺 书我们仔细阅读了数学建模选拔赛的规则.我们完全明白，在做题期间不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人研究、讨论与选拔题有关的问题。我们知道，抄袭别人的成果是违反选拔规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守选拔规则，以保证选拔的公正、公平性。如有违反选拔规则的行为，我们将受到严肃处理。我们选择的题号是（从A/B/C中选择一项填写）： C 队员签名 ：1. 王瑞 2. 徐水帅 3. 石赛赛 日期： 2014 年 8 月

2、 20 日2014年河南科技大学数学建模竞赛选拔编 号 专 用 页评阅编号（评阅前进行编号）：评阅记录（评阅时使用）：评阅人评分备注基于图论和非线性规划求最佳搜救路线问题摘要马来西亚航空公司mh370航班意外失事引发了全球的关注，如何在最短的时间内找到失事飞机残骸以及黑匣子成为了关注焦点。本文将搜集的数据信息进行处理，对已有的问题作了合理的假设优化，并应用动态规划、图论、网络搜索、最优化等理论，最终建立了最短路模型、最小时间模型从而得到最佳搜索路线。针对问题一，通过查找资料得知搜救船的搜救半径为6km，区域平均海洋深度为4.5km，运用勾股定理得到实际搜寻半径为4km。我们将着重搜救区域650

3、*93简化为一块矩形区域648*96，为使在最短时间内找到黑匣子，我们对常见的“平行线扫视搜寻法”做出改进，通过将三艘船排开，相邻间隔为8km，横向搜索，形成一条搜索宽度为24km的搜索带。再根据实际搜寻半径，我们将搜救区域划分为108个24*24的小正方形，并绘制出相应的网格图，建立了以所行Hamilton路最短为目标函数的图论模型。另外我们考虑到拐角所用时间较长，因此在所行最短的路线的基础上使船队经过的拐角最少以达到最优化结果，最终得到最佳线路图，然后通过计算直线行驶和拐角所用时间，得到最短搜救时间为81.3h.对于问题二，简化假设该题，计算飞机和轮船的平均搜索能力，以成本当成目标函数，以

4、黑匣子的寿命、搜救工具的数量、搜救面积当做约束条件，构建非线规划模型，运用lingo软件求得动用飞机2架，轮船0艘 ，最小成本为2762088元。关键字 平行扫视搜寻 哈密尔顿圈 非线性规划 1、问题重述 马来西亚航空370号班机空难，是指2014年龄月8日一班从马来西亚吉隆坡前往中国北京的波音777-200ER航机失踪事件，被认为是有史以来“最离奇”的飞机失联案例。1空难的谜团不能解开，很大程度上取决于能不能打捞到“黑匣子”。MH370的失联，各国为此出动了25架飞机，40艘舰艇，甚至包括若干卫星。（1） 请你以MH370为基本背景，基于互联网报导的这次事件的一些数据（如不同搜索设备的搜索能

5、力，速度，续航时间，代价等）基础上，做出合理假设、简化，针对（2） 某一种搜索工具（如卫星、飞船、船只）讨论其搜索的范围和优缺点，制定相应的最优搜索方案；（3）若假设所有的飞机船舰及卫星都有一个国家统一调度，再讨论如何才是最优飞机残骸和黑匣子的方案？2、问题分析问题一的分析，由于搜救区域一定，故问题就转化为了如何利用现有的搜集力量在最短时间内完成搜救任务。由于具备搜救能力的船只有限，要缩短时间，就要扩大搜索半径，减少搜救路程。所以可将可用船只一字排开，横向扫过区域。接着，根据横向搜索宽度，可将搜索区域划分为多个小方块，每个方块中心看作点，这样便可以用图论知识将最短搜索路径转化为求最短的哈密尔顿

6、圈问题。紧接着，再考虑使路径拐角最少，我们得出了最终的最短搜索路径，进而可求出最短搜救时间。问题二的分析，问题二受到了黑匣子的寿命、搜救工具的数量、搜救面积等因素的制约，且搜寻工作不得不考虑到成本的问题，故此问题可化为求在上述约束条件下，以总成本为目标函数建立非线规划模型，最后根据相关数据求得最小成本。 3、问题假设1. 假设该海域为黑匣子最终落水区域，且可近似看作标准矩形区域2. 假设搜寻工作不受天气影响，搜寻设备能持续工作3. 假设海床是一块平面，深度一定4. 假设相同的搜救工具搜救能力相同4、符号说明符号说明S问题一总路程问题一直线路程问题一拐弯路程t问题一搜寻时间x问题二派出船的数量y

7、问题二派出飞机的数量m船的搜索能力n飞机的搜索能力K问题二的搜救区域面积T问题二黑匣子的寿命5、模型的建立与求解51问题一的建立与求解5.1.1数据分析由于各国派出的搜救船各不相同，为简化问题，我们将“永兴岛号远洋打捞救生船”作为标准，通过上网得出其性能参数表如下：排水量1.023万吨（正常），排水量1.305万吨（最大）主机6615千瓦（9000马力）低速柴油机2台，630千瓦柴油发电机组5台主尺寸长156.2米，设计水线长140米，型宽（最大）20.6米，型深11.50米航速巡航速度18节，最大航速20节续航力18000海里自持力90昼夜编制298人直升机2架直-8直升机或超黄蜂大型直升机

8、黑匣子搜索仪搜寻半径6km（注：1海里=1.852公里，1节=1.852km/h）根据表格，我们可知，船的航速为V=18*1.85233km/h，黑匣子搜索仪的搜寻半径为6km，自持力为90昼夜，所以，搜索船一次性补给满，可连续执行搜救任务90天。通过上网查阅资料，我们得知只有少数搜救船装备有黑匣子搜索仪，故我们假设有三艘船有。进一步上网查询，我们得到了失事飞机重点搜索区域面积为60,000 km（下图黄色条状），弧长为650km，宽度为93km.如下图：（注：黄色条带为重要区域，蓝色次之）为使问题方便解决，我们近似地将此区域处理为一块长为648km，宽为96km的矩形区域如下图：96km64

9、8km黑匣子在失事后沉入海底，海底地形凹凸不平，处理起来极为不便，故将其近似地看为是一块平面。通过上网查找资料，我们将官方公布的黑匣子信号源深度4500m作为海床离海平面的距离。据分析，实际的搜索区域应该为海面的搜索区域垂直投影到海床上的区域，也是一块648km*96km的矩形，根据勾股定理可得，黑匣子搜索仪的实际搜索半径约为4km，如下图1所示：4km6km4.5km图15.1.2模型的建立与求解为了使搜救方案更科学合理，通过查找相关搜救资料，我们得到了常见的海上搜救方法及其适用范围表：搜救方法适用范围扇形搜寻搜寻目标位置准确或搜寻区域较小时扩展方形搜寻适用于当搜寻目标位置处于相对较近的区域

10、时航迹线搜寻适用于失事船舶在计划航线上或附近遇险雕而对事发位置小不确定平行扫视搜寻搜寻目标位置很不确定并要求均匀覆盖一广阔区域横移线搜寻较多应用于航空器与船舶的协调进行的搜救行动岸线搜索船舶在熟知自身航行性能和航行水域状况采取此方法移动矩形搜索风浪大、能见度低、夜间搜寻有效距离近、被搜寻目标小不易发现、目标漂移的速度较快由于失事飞机具体坠落地点不确定且范围广，与上述“平行扫视搜寻法”较吻合，其方法具体如下：当执行平行线扫视搜寻时，先设定一搜寻区域，并根据现场情况确定搜寻线间距，搜寻设施把搜寻区域的一角作为搜寻起始点，搜寻起始点通常在搜寻矩形内距两直角边12搜寻线间距的位置，然后沿矩形长边来回保

11、持间距搜寻。图：平行扫视搜寻图解经仔细分析，我们发现“平行扫视搜寻法”并不能直接解决问题，故对其进行改进，具体过程如下：我们知道搜索区域一定，船速一定，故要使搜救时间最短，就要扩大搜索半径，减少搜救路程。关于扩大搜索半径，我们想到了将三艘搜救船一字排开，相互间间隔为8km，这样就形成了一个宽为24km的横向扫面带，则其在单位时间内扫过的面积最大。接下来考虑减少路程，根据三艘船的排列方式，我们可以将矩形搜救区域划分为108个24*24的小正方形，这样，问题就转化为怎么在最短的时间内把所有的小方格跑完。由于速度是确定的，所以只要使搜救路线最短即可。运用图论的知识，我们将每个小正方形的中心看作一个点

12、，最短搜救路线就转化为了求经过所有点的最小哈密顿圈。但考虑的每个小正方大小一样，故得到的所有哈密顿圈大小也一样，即路程一样。通过进一步分析和查找相关资料，为使时间最短，那就要减少搜救路线的拐角数，这就要求搜救船尽可能以直线行走，根据这些原则，我们得到了最终的搜救路线图。二、模型假设三、符号约定搜救路线图当搜救船转角时，会出现部分区域扫不到情况，如下图所示：所以，最终路程S=直线路程+拐弯路程下面我们对拐弯路程作详细分析。由于是3艘船一字摆开齐头并进，因此在整个过程中最左边的船航程最大，因此我们只考虑最左边的船的航程。另外，船在拐弯时会有90度弯和180度弯两种情况。为方便描述，我们记最左边的船

13、为一号船。当船队遇到90度拐角时，经分析可知，一号船按如下图2所示路线走可满足在将区域全部扫描完整基础上航程最短条件。 图2 （注释：一号船走到区域的边界时再朝下一个既定位置直线行驶。）当船队遇到180度拐角时，经分析可知，船队按如下图3所示路线走可满足条件。 图3 （注释：当船队遇到180度角时左右船位置互换。） 经计算可得总距离S=+=4+(4.5+24*4+1.5+9)*24 由Matlab得s=2684.4km。又因为搜索船队的速度v=33km/h，我们可以得到最短搜索时间t=S/v=81.3453小时。5.2问题二的建立与求解5.2.1建模思路由于卫星涉及到的数据量多、大且不易找到，

14、故我们仅假设现有的搜救力量只有船和飞机，且飞机和船都可由同一点调度。经查阅资料，黑匣子发射信号的能力只有30天，飞机有25架，船有40艘，搜救面积为问题一中黄色搜救区域的3倍，即 18000(用K表示)所以以它们作为约束变量，建立以总成本为目标函数的线性规划模型，以求得最小成本。5.22模型建立与求解通过查找资料，我们得到了飞机和船的搜救力量信息：为便于解决问题，我们各个型号的搜救能力取平均值，将其作为标准。得到：船的搜寻能力m=(9+12+50+24+56+21+42+25+21+24+19+27+47+58+62)/15=43.2 n mile/h.=148.17.168km/h飞机的搜寻

15、能力n=(180+220+150+180+220)/5=190 n mile/h.=651.681 km/h（1 n mile=3.4299 km）另外我们查找数据得到轮船和飞机的耗油量以及考虑到人工成本等因素得出轮船每小时搜寻需要花费a=3000元，飞机需要花费b=10000元。搜索时间T=K/（mx+nb）设需要调用的船x艘，飞机y架，总成本为z，由非线性规划的相关知识可建立数学模型：min z=(3000*x+10000*y)*180000/(148.17168*x+651.681*y)s.t. 0X40 0Y25 0180000/(148.17168*x+651.681*y)30*24

16、用lingo软件进行求解，其程序如下：min=(3000*x+10000*y)*180000/(148.17168*x+651.681*y);x<=40；y<=25;180000/(148.17168*x+651.681*y)<=720;gin(x);gin(y);运行结果如下：Local optimal solution found. Objective value: 2762088. Objective bound: 2762088. Infeasibilities: 0.000000 Extended solver steps: 7 Total solver itera

17、tions: 228 Variable Value Reduced Cost X 0.000000 100307.4 Y 2.000000 0.000000 Row Slack or Surplus Dual Price 1 2762088. -1.000000 2 40.00000 0.000000 3 23.00000 0.000000 4 581.8956 0.000000根据结果，我们决定派出两架飞机执行全部搜索任务，最小成本为2762088元。6.模型的评价优点：1、问题一中我们在理论和细节方面把握的非常到位，在理论方面我们运用了哈密尔顿回路的原理，将问题简化为求哈密尔顿圈的最优解，并联合实际求出在将区域全部扫描完的基础上的最短路线。在细节方面比如在计算搜索半径时我们考虑到海床对搜索半径的影响进而得到实际的搜索半径，还有船队在遇到拐角时可能会未搜索一定区域等。另外我们还用photoshop软件做出效果图使得该模型更好理解。2、运用lingo求解问题，使结果更具说服力缺点：在考虑问题时我们并未考虑搜救中心到搜救地点的距离以及各搜救船只和飞机的搜索能力的不同等现实因素。7、参考文献1.图论，作者王树禾，科学出版社2