2024 MCM 问题 B: 搜寻潜水艇
题目翻译:
Maritime Cruises Mini-Submarines (MCMS)是一家总部位于希腊的公司,专门制造能够携带人类到达海洋最深处的潜水艇。潜水艇是由一艘主船运输和支持的,可以在水下自由活动。MCMS现在希望利用他们的潜水艇带游客探索爱奥尼亚海底的沉船。然而,在此之前,他们需要通过制定安全程序来赢得监管机构的批准,以应对与主船失去通讯和可能发生的机械故障(包括潜水艇推进力丧失)的情况。特别地,他们希望你开发一个模型来预测潜水艇随时间的位置。与陆地或海面上的典型搜救不同,故障的潜水艇可能会位于海底或水下某个中性浮力的位置。它的位置还可能受到海流、海水密度差异和/或海底地形的影响。
你的任务是:
- 定位 - 开发一个或多个模型来预测潜水艇随时间的位置。
- 这些预测有哪些不确定性?
- 潜水艇在发生事故之前可以定期向主船发送哪些信息来减少这些不确定性?潜水艇需要哪些设备才能做到这一点?
- 准备 - 你建议公司在主船上携带哪些额外的搜救设备以备必要时使用?
- 你可以考虑不同类型的设备,但也必须考虑这些设备的可用性、维护、准备和使用成本。如果需要,救援船需要带来哪些额外的设备来协助?
- 搜寻 - 开发一个模型,利用你的位置模型的信息,来推荐初始部署点和搜寻模式,以便最小化找到失踪潜水艇的时间。确定随时间和累积搜寻结果而变化的找到潜水艇的概率。
- 推广 - 你的模型如何扩展到其他旅游目的地,如加勒比海?当有多艘潜水艇在同一区域活动时,你的模型如何改变?
术语表
- 潜水艇:潜水艇是一种水下车辆,需要由更大的水上船只或平台运输和支持。这区别于潜艇,潜艇是自我支持的,能够在海上进行长时间的独立操作。
- 中性浮力:是指一个物体的平均密度等于它所浸没的流体的密度,导致浮力平衡了重力(如果物体的密度大于它所浸没的流体的密度,物体就会下沉;如果小于,物体就会上升)。具有中性浮力的物体既不会下沉也不会上升。
问题重述:
题目背景:一家希腊公司想要利用他们的潜水艇带游客探索爱奥尼亚海底的沉船,但是需要通过监管机构的审批,制定安全程序,应对潜水艇失去通讯或动力的情况。
题目要求:建立一个模型,预测潜水艇在水中的位置随时间的变化,考虑到潜水艇可能在海底或中层,受到海流、海水密度和海底地形的影响。同时,提出以下建议:
-
- 潜水艇应该定期向主船发送什么信息,以减少预测的不确定性,需要什么设备?
- 公司应该在主船上携带什么额外的搜索设备,以备不时之需?考虑到设备的成本、维护、准备和使用。
- 建立一个模型,利用位置模型的信息,推荐初始部署点和搜索模式,以最小化定位失去的潜水艇的时间。确定随时间和搜索结果累积而变化的找到潜水艇的概率。
- 说明如何将模型扩展到其他旅游目的地,如加勒比海。说明如何修改模型,以适应同一区域内多艘潜水艇的移动。
问题分析:
这个题目的重点难点有以下几个方面:
- 如何建立一个能够准确预测潜水艇在水中位置的模型,考虑到潜水艇可能在海底或中层,受到海流、海水密度和海底地形的影响。
- 如何评估模型的不确定性,以及潜水艇应该定期向主船发送什么信息,以减少不确定性,需要什么设备。
- 如何在主船上准备合适的搜索设备,以应对潜水艇失去通讯或动力的情况,考虑到设备的成本、维护、准备和使用等因素。
- 如何利用位置模型的信息,推荐最佳的初始部署点和搜索模式,以最小化搜索和定位潜水艇所需的时间,以及计算找到潜水艇的概率。
- 如何将模型扩展到其他海域,如加勒比海,以及如何调整模型,以适应同一海域内有多艘潜水艇同时运行的情况。
为了解决这些问题,我认为可能需要应用以下几种数学模型:
- 位置预测模型:可以考虑使用微分方程模型,将潜水艇的位置、速度、方向、深度等作为状态变量,将海流、海水密度、海底地形等作为影响因素,建立一个动态系统,描述潜水艇的运动规律。也可以考虑使用机器学习模型,如神经网络、支持向量机等,利用历史数据或模拟数据,训练一个能够根据潜水艇的初始状态和环境条件,预测其未来位置的模型。
- 不确定性评估模型:可以考虑使用概率统计模型,如置信区间、假设检验、蒙特卡罗模拟等,分析位置预测模型的误差、稳定性、灵敏度等,评估模型的可靠性和有效性。也可以考虑使用信息论模型,如熵、互信息、信息增益等,分析潜水艇向主船发送的信息的质量和量化,确定最优的通讯和定位设备和策略。
- 搜索设备选择模型:可以考虑使用多目标规划模型,将搜索设备的成本、维护、准备、使用等作为目标函数,将搜索设备的类型、数量、性能等作为决策变量,将搜索设备的可用性、安全性、兼容性等作为约束条件,建立一个优化问题,求解最优的搜索设备组合和配置方案。
- 搜索模式推荐模型:可以考虑使用图论模型,将海域划分为若干个网格,将每个网格作为一个节点,将节点之间的距离作为边的权重,建立一个加权图,描述海域的空间结构。然后可以考虑使用最短路径算法、最小生成树算法、最小费用最大流算法等,根据位置预测模型的信息,推荐最佳的初始部署点和搜索模式,以最小化搜索和定位潜水艇所需的时间。也可以考虑使用概率模型,如马尔可夫链、贝叶斯网络等,根据位置预测模型的信息,计算每个网格中找到潜水艇的概率,以及随时间和搜索结果累积而变化的找到潜水艇的概率。
- 模型扩展和调整模型:可以考虑使用灵敏度分析模型,分析模型对不同海域的海流、海水密度、海底地形等参数的敏感性,确定模型的适用范围和可推广性。也可以考虑使用博弈论模型,分析多艘潜水艇在同一海域内的相互影响和协作策略,确定模型的修改和优化方案。
B题整体模型构建
- 潜水器动力系统失效:模型需要考虑潜水器在无推进力情况下的行为。
- 失去与主船通信:考虑无法从主船接收指令或发送位置信息的情况。
- 中性浮力和海底定位:潜水器可能位于海底或达到水下某个中性浮力点。
- 水流和海水密度变化:影响潜水器位置的环境因素。
- 海底地理:海底的地形可能会影响潜水器的最终位置或移动路径。
数学模型和公式
为预测潜水器的位置,我们可以建立基于物理学原理的动态模型,考虑力学和流体动力学的因素。以下是潜水器运动的基本方程:
动力学方程
设潜水器的质量为 m ,受到的浮力为 Fb ,重力为 Fg ,水流对潜水器施加的力为 Fc ,潜水器在水中的阻力为 F_d,则潜水器的运动方程可表示为:
md2r→dt2=Fb→+Fg→+Fc→−Fd→
其中, r→ 是潜水器的位置向量, t 是时间。
m :潜水器的质量
Fb→ :浮力,方向向上
Fg→=m⋅g :重力,方向向下, g 是重力加速度
Fc→ :水流对潜水器的作用力,方向依赖于水流方向
Fd→ :阻力,方向与潜水器运动方向相反,大小可以用 Fd=12ρv2CdA 来估计,其中 ρ 是水的密度, v 是潜水器相对于水的速度, Cd 是阻力系数,$A$ 是潜水器迎水面积
潜水器浮力和阻力的计算
浮力 Fb 可以通过潜水器排水量和水的密度来计算,阻力 Fd 可以根据潜水器的形状、表面粗糙度和运动速度来估算。
数值解法
由于潜水器的运动方程是一个二阶微分方程,我们可以采用数值方法(如欧拉方法或龙格-库塔方法)对其进行求解,得到潜水器随时间变化的位置和速度。
模型假设
- 潜水器被视为质点,忽略其尺寸和形状的影响。
- 假设水流速度和方向是已知的,可以从海洋流动模型获得。
- 海底地形对潜水器运动的影响通过调整浮力和阻力参数来模拟。
通过上述模型和方法,我们可以预测在不同情况下潜水器的位置,为MCMS制定安全程序提供科学依据。
为了解决上述复杂的数学建模问题,我们将问题分解为四个主要部分:定位、准备、搜索和外推。下面是针对每个部分的详细分析和数学模型。
定位
模型构建
- 基于多传感器融合的动态预测模型:利用卡尔曼滤波(Kalman Filter)或扩展卡尔曼滤波(Extended Kalman Filter, EKF)来整合来自潜水器内部(如IMU传感器)和外部(如声纳、GPS浮标)的多源信息,预测潜水器随时间变化的位置。
数学公式
假设潜水器的状态为 x→t=[xt,yt,zt,x˙t,y˙t,z˙t]T ,
其中 xt,yt,zt 表示潜水器在三维空间中的位置,
x˙t,y˙t,z˙t 表示对应的速度。
卡尔曼滤波的预测和更新步骤如下:
- 预测步骤: x→t|t−1=F→tx→t−1|t−1+B→tu→tP→t|t−1=F→tP→t−1|t−1F→tT+Q→t
- 更新步骤: K→t=P→t|t−1H→tT(H→tP→t|t−1H→tT+R→t)−1x→t|t=x→t|t−1+K→t(z→t−H→tx→t|t−1)P→t|t=(I−K→tH→t)P→t|t−1
其中, F→t 是状态转移矩阵, B→t 是控制输入矩阵, u→t 是外部控制输入, P→t 是估计误差协方差, Q→t 是过程噪声协方差, H→t 是观测模型矩阵, R→t 是观测噪声协方差, K→t 是卡尔曼增益, z→t 是实际观测值。
不确定性分析
- 主要的不确定性来源包括传感器噪声、模型误差、外部环境(如水流变化和海底地形)的未知性。蒙特卡洛模拟(Monte Carlo Simulation)可用于评估这些不确定性对预测准确性的影响。
准备
- 附加搜索设备推荐:基于成本-效益分析,推荐搭载多波束声纳(用于精确地图制作)和侧扫声纳(用于宽范围搜索)。
- 设备需求和成本分析:使用线性规划模型来平衡设备的可用性、维护成本、准备状态和使用成本。
搜索
搜索模式和初始部署点的确定
- 基于概率地图的搜索模型:结合潜水器位置预测模型和海域环境信息(如水流、海底地形),使用贝叶斯搜索理论(Bayesian Search Theory)来确定最佳搜索区域和搜索路径,最小化找到失联潜水器的时间。
数学公式
搜索区域被划分为多个网格,每个网格 i 的概率 Pi 表示潜水器存在于该网格的概率。搜索效率 ηi 取决于搜索设备的类型和搜索环境。总搜索概率可通过以下公式计算:
总P总=∑iPiηi
外推-模型扩展
- 适用于其他海域:考虑不同海域的特定条件(如水流、密度分层、地形),调整模型参数以适应新环境。
- 多潜水器运动:引入多体动力学和相互作用模型,考虑多潜水器在同一区域内的协同和避障策略。
通过上述分析和模型构建,我们可以对MCMS公司的潜水器进行有效的位置预测和搜索计划制定,为确保游客安全提供坚实的数学支持。
第一题:开发一个模型,预测潜水器随时间的位置(定位模型构建)。
目标:开发一个模型预测潜水器随时间变化的位置。
方法:采用基于物理模型和数据融合技术的动态预测方法,结合卡尔曼滤波器(Kalman Filter)进行实时位置估计和预测。
数学模型:
状态向量: x→t=[x,y,z,x˙,y˙,z˙]T ,表示潜水器在时间 t 的位置和速度。
动态方程:描述潜水器的运动状态,考虑到水流影响和自身动力系统失效情况。
x→t+1=F→x→t+B→u→t+w→t
其中, F→ 是状态转移矩阵,
B→ 是控制输入矩阵,
u→t 是控制向量(在这个案例中可能为零,因为考虑到动力系统失效),
w→t 是过程噪声。
观测方程:描述如何从状态向量中得到观测量(比如声纳定位)。
z→t=H→x→t+v→t
其中, z→t 是观测向量, H→ 是观测矩阵, v→t 是观测噪声。
不确定性分析
主要来源:过程噪声 w→t (如水流不确定性),观测噪声 v→t (如声纳定位误差)。
减少不确定性:通过多传感器数据融合和频繁更新状态估计。
所需信息和设备
- 信息:深度、速度、加速度、周围水流速度和方向、海底地形。
- 设备:惯性测量单元(IMU)、Doppler速度计、声纳、水下GPS浮标、压力传感器。
Python代码实现及可视化例程
假设我们已经有了潜水器的初始位置和一系列通过声纳和IMU获得的观测数据,以下是使用Python实现简化版的卡尔曼滤波器进行位置预测的代码示例。
潜水器预测位置不确定性预测图
此代码示例演示了如何使用卡尔曼滤波器对潜水器的位置进行预测和更新,考虑到过程噪声和观测噪声。通过可视化,我们可以看到卡尔曼滤波器如何有效地根据观测数据估计潜水器的真实位置。
第二题:准备 - 推荐附加搜索设备(携带额外设施的必要性)
目标:确定主船携带的附加搜索设备以及可能需要的救援设备,同时考虑成本因素。
方法:
- 成本-效益分析:分析不同搜索设备的成本(购买、维护、准备和使用)与其搜索效率之间的关系。
- 设备选择标准:基于设备的覆盖范围、探测深度、精确度和可靠性等指标,结合成本效益分析结果,进行设备选择。
数学模型:
设备效用函数 U(e) 可以定义为设备搜索效率和成本的函数:
U(e)=α⋅E(e)−β⋅C(e)
其中, e 表示不同的搜索设备,
E(e) 表示设备的搜索效率(如探测范围、深度等),
C(e) 表示设备的总成本(包括购买、维护和使用成本),
和α和β 是权重参数,用于调整搜索效率和成本在效用函数中的相对重要性。
总成本 C(e) 可以进一步细化为:
C(e)=Cpurchase(e)+Cmaintenance(e)+Creadiness(e)+Cusage(e)
分别对应购买成本、维护成本、准备状态成本和使用成本。
推荐设备
- 多波束声纳:用于海底地形精确绘图,有助于识别潜在障碍物和沉船位置。
- 侧扫声纳:宽范围搜索,适用于初步定位潜水器可能的位置区域。
- 自主水下无人机(AUV):携带声纳和摄像头,用于详细搜索和视觉识别。
- 水下定位系统:提高救援效率,精确定位潜水器位置。
Python代码实现及可视化例程
假设我们有不同设备的成本和搜索效率数据,以下是一个简化版的成本-效率分析,以及如何选择最优设备的Python示例代码。
此代码示例演示了如何使用成本-效益分析来选择最优的搜索设备。通过将每种设备的搜索效率与成本结合起来计算一个综合效用分数,可以确定最有价值的设备。可视化结果进一步揭示了每种设备的综合得分,帮助决策者做出更明智的选择。
此外,还以对搜索设备的搜索路径进行预测,代码如下:
路径预测可视化分析图
第三题:搜索 - 开发用于推荐设备部署点和搜索模式的模型以最大限度地减少找到失踪潜水器的时间。
目标:利用定位模型提供的信息,设计一种搜索策略,以最小化找到失联潜水器所需的时间。
方法:
- 基于贝叶斯搜索理论的模型:考虑海域环境特性(如水流、海底地形)和预测的潜水器可能位置,利用贝叶斯搜索理论来更新搜索区域的概率分布,优化搜索路径和初始部署点。
- 搜索模式:......
数学模型:
概率分布更新:设搜索区域被划分为 n 个网格,每个网格 i 中潜水器存在的先验概率为 P_i。根据新的观测信息,使用贝叶斯定理更新概率分布:
P(Ai|B)=P(B|Ai)P(Ai)P(B)
其中, Ai 表示潜水器位于网格 i , B 表示观测信息, P(Ai|B) 是给定观测信息 B 后潜水器位于网格 i 的后验概率。
搜索效率:设定搜索设备在不同搜索模式下的效率 ηm ,
其中 m 表示搜索模式(如螺旋搜索、平行线搜索等),考虑搜索设备的性能和搜索环境,确定每种模式的搜索效率。
推荐搜索策略
- 选择最初部署点:选择具有最高后验概率 P(A_i|B) 的网格作为初始搜索点。
- 确定搜索模式:基于环境特性和潜水器可能的位置分布,选择最高效的搜索模式。
Python代码实现及可视化例程
假设我们已经根据定位模型得到了潜水器可能的位置分布,以下是如何实现贝叶斯搜索理论以优化搜索策略,并可视化搜索区域和推荐的初始部署点的代码示例。
此代码示例首先模拟了潜水器可能位置的概率分布,然后确定了具有最高概率的网格作为最初的搜索部署点,并通过热图可视化了整个搜索区域的概率分布以及推荐的初始部署点。
通过贝叶斯更新和搜索策略的优化,结合具体的海域环境特性和潜水器的预测位置信息,可以有效地指导搜索救援行动,提高找到失联潜水器的效率。
以下是潜水器搜索效率随时间变化的动态图,此可视化通过动态图展示了搜索效率随时间的变化情况,突出显示效率的提升或下降。
第四题:外推 - 模型扩展
不考虑其他旅游目的地,比如加勒比海,那么这条航线可能会更加便捷。你的模型将如何改变,以考虑在相同的一般速度移动的公式多个潜水器?
目标:扩展模型以适应其他旅游目的地(如加勒比海)和处理同一区域内多潜水器的移动。
方法:
- 适应不同水域特性:根据不同目的地的海域特性(如水流、水温、海底地形和盐度等),调整模型参数以适应这些环境差异。
- 多潜水器动态模型:引入多目标跟踪算法(如多目标卡尔曼滤波器或粒子滤波器),处理同一区域内多潜水器的位置预测和追踪。
数学模型:
环境参数调整:
......
......
多潜水器状态模型:对于每个潜水器 i ,其状态向量为 x→t,i ,包括位置和速度等信息。多潜水器系统的状态向量 X→t 是所有潜水器状态向量的集合。
多潜水器位置预测和追踪
- 状态更新:使用多目标卡尔曼滤波器或粒子滤波器对每个时间步 t 的潜水器位置进行更新和预测。
- 相互作用处理:在模型中引入潜水器之间的相互作用项,如避免碰撞的控制逻辑。
Python代码实现及可视化例程
下面的代码示例展示了如何模拟加勒比海区域内两个潜水器的运动,并使用简化的方法进行位置预测。
两个潜水器三维运动的轨迹模拟图
此代码模拟了两个潜水器在加勒比海区域内的简化运动,并通过动画展示了它们的移动轨迹。在实际应用中,每个潜水器的运动会更加复杂,包括受到水流影响、相互作用以及尝试保持一定距离以避免碰撞。
多潜水器位置分布热力图
此可视化展示了在特定时间点,多潜水器在搜索区域内的分布情况。
多潜水器位置关联热力图
通过调整模型以适应不同的海域特性和引入多潜水器动态追踪算法,此方法可以被扩展应用于更复杂的情况,如导航、搜索和救援任务。
以下为赛前回答:
美国大学生数学建模(MCM/ICM)是一项由美国自然科学基金协会和美国数学与数学应用协会共同主办的国际性建模竞赛。2024年美赛将于北京时间2024年2月2日早上6点开始。
不知道大家是否正在为美赛的建模问题感到困惑,不妨参考一下作为本科和研究生期间经历的数十场数学建模比赛的老手以及2022年美国大学生数学建模比赛的F奖得主的我的经验。
我们将为24美赛的每个赛题提供深入完整的解题思路和建模过程,帮助您轻松应对各种难题。请您敬请期待,我们会在美赛正式开始后第一时间进行更新哦。
下文包含24年美赛的人员分工推荐,以及介绍一个美赛中常用的算法模型
24美赛的推荐人员分工:
组队和分工对于在美赛中斩获佳绩至关重要。以下是一些建议:
数学建模美赛要求一个由三人组成的团队在四天内完成模型构建、编程实现和论文撰写的挑战。对于初次参加或经验较少的团队而言,时间紧张且任务繁重。那么,如何应对呢?
当然,首要任务是认真学习优秀的论文,加强算法应用和编程技能。此外,根据团队实际情况找到合适的分工模式,也是提高效率的有效方法。
以下是四种分工方式的详细介绍:
分工方式一:建模+编程+论文写作
- 适用团队:两位擅长建模、一位建模基础较弱的成员。
- 团队组成:小A(模型建立)、小B(编程实现)、小C(论文排版及数据收集)。
- 评价:这是一种经典且广泛应用的分工,适用性强。但也可能因沟通不畅导致效率降低。负责论文的成员在模型建立初期可协助其他工作。
分工方式二:每人独立负责一个模型的建立、编程和论文写作
- 适用团队:每个成员都具备一定的建模基础。
- 团队组成:小A、小B、小C均独立完成模型。
- 评价:适用于确定算法选择较快的题型。每个成员应掌握经典及几种高级算法。
分工方式三:两人实现模型建立,一人完成论文写作
- 适用团队:同分工方式二。
- 团队组成:同分工方式二。
- 评价:要求成员都有良好的建模基础。可根据参赛规则和题目特点选择此方式或方式二。
分工方式四:一人负责建模和编程,两人负责数据处理与论文写作
- 适用团队:一名经验丰富的成员和两名建模基础较弱的成员。
- 团队组成:小A(建模与编程)、小B和小C(数据与论文)。
- 评价:适用于争取获奖的团队,一人主导模型工作,其他成员协助。
美赛中常用的算法模型:模拟退火算法
模拟退火算法是一种基于概率和随机性的算法,用于解决组合优化问题。它通过生成大量随机样本来模拟复杂系统的行为或计算数值解。模拟退火算法最早的思想是由N. Metropolis等人于1953年提出。1983年,S. Kirkpatrick等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发,伴随温度参数的不断下降,结合一定的概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法可用于求解组合问题,如TSP和Knapsack问题等。模拟退火算法的核心思想是通过赋予搜索过程一种时变且最终趋于零的概率突跳性,从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。
模拟退火算法的流程分为以下几步:
- 令T=T0,表示开始退火的初始温度,随机产生一个初始解x0,并计算对应的目标函数值E(x0);
- 令T=kT,其中k取值0到1之间,为温度下降速率;
- 对当前解xt施加随机扰动,在其邻域内产生一个新解xt+1,并计算对应的目标函数值E(xt+1),计算ΔE=E(xt+1)-E(xt);
- 若ΔE<0,接受新解作为当前解,否则按照概率e^(-ΔE/kT)判断是否接受新解;
- 在温度T下,重复L次扰动和接受过程,即执行步骤3和4;
- 判断温度是否达到终止温度水平,若是则终止算法,否则返回步骤2。
其中,接受概率为: P = { 1, E_t+1 < E_t e^(-ΔE/kT), E_t+1 >= E_t }
模拟退火算法的应用如下:
- 模拟退火算法在VLSI设计中的应用:用模拟退火算法几乎可以很好地完成所有优化的VLSI设计工作,如全局布线、布板、布局和逻辑最小化等等。
- 模拟退火算法在图像处理中的应用:模拟退火算法可用来进行图像恢复等工作,即把一幅被污染的图像重新恢复成清晰的原图,滤掉其中被畸变的部分。
- 模拟退火算法在神经网计算机中的应用:模拟退火算法具有跳出局部最优陷阱的能力。在Boltzmann机中,即使系统落入了局部最优的陷阱,经过一段时间后,它还能再跳出来,系统最终将往全局最优值的方向收敛。
- 模拟退火算法的其他应用:除了上述应用外,模拟退火算法还用于其他各种组合优化问题,
下面是一个使用模拟退火算法解决三维空间中的优化问题的Python程序。该程序使用模拟退火算法来优化一个三维函数,并使用Matplotlib库进行三维可视化。
这个程序使用模拟退火算法来优化一个三维函数,并使用Matplotlib库进行三维可视化。程序首先定义了一个名为的函数,该函数使用模拟退火算法来优化三维函数。然后,程序使用函数来优化三维函数,并将结果显示在Matplotlib窗口中。程序使用函数生成一组坐标,并使用函数生成一个三维函数的表面。最后,程序使用Matplotlib库创建一个3D散点图和一个3D曲面图,该图显示了三维函数的随机采样点,并根据每个点的z坐标值进行颜色渐变: