数模系列:历年优秀论文+入门+进阶+国赛+美赛+其他(待更新中)
数模成绩为国二\省一\o奖\H奖,在博客做一个总结。先放国赛美赛的历年优秀论文,资料来源微信公众号数学模型。(目前完成部分:入门+进阶+美赛,接下来随缘更新国赛篇)
国赛历年优秀论文(提取码: nae6)
美赛历年优秀论文(提取码: vuyq)
文章目录
数模系列:历年优秀论文+入门+进阶+国赛+美赛+其他(待更新中)一、数模入门1.数模是什么2.入门级知识储备二、进阶1.分析2.通用建模方法3.例子三、国赛1.团队赛前准备2.题目分析解读3.优秀模型分析四、美赛1.团队赛前准备2.题目分析解读第一问:第二问:第三问:3.优秀模型分析五、其他总结一、数模入门
本章以下内容主要面向零基础和有一定基础的数模同学
1.数模是什么
数学建模:数模是用对实际问题做适当简化抽象,用数学方法模拟、求解、分析。
求解一道数模题时,一般的,我们需要提炼题目的关键词和隐含信息,查阅资料加深对于题目背景和题目问题的认识,量化条件,抽象问题,求解分析,验证讨论。在这个过程中,建模人的分析、抽象、推导、创新等多种能力都发挥各自的作用。而对于入门者,抽象量化能力的强化是最迫切的需求。
抽象量化,狭义上指的是:
1.方程、不等式、图、向量机、决策树、自动机等有解空间或者多个离散解的数学方式表达问题的求解和条件;
2.用变量、向量、含有信息的矩阵、状态、节点、集合、元胞、坐标、进过函数映射的y等方法抽象欲求解和欲表达的量;
3.用数学化或者符合数学思想的方法剥离题目来构建模型。
抽象量化的一般方法是结合理解让需要被抽象的对象和已知的数学对象“对号入座”。首先去捕捉对象的特点、条件、约束,尽量概括成具有数学性的话或者符号公式,接着列举符合的数学对象,根据提炼的东西来筛选和修改已选数学对象。
举个不恰当的例子,如何用抽象量化的方法描述“栈”?首先分析栈的特点:1.有存储元素的能力2.读出时优先读出后写入的元素。
根据第一点,我们想到图、向量、树、矩阵、集合是符合的。接着我们提炼信息:读出元素优先最新写入的元素。从这一点我们抓到关键变量“写入时间的先后”,令元素在数据结构中排列是遵循写入时间的先后的正序,并且在写操作时我们优先修改最后一位元素,这种特征下我们可以排除集合和矩阵,考虑用图的节点抽象元素,让单向图中的节点按照写入顺序生成子节点来写入新元素;当然按照写入顺序排序的向量也是同理。
概括的说:
一、变量设置方面:决策(是否xxx)往往可以抽象为布尔型的变量,数量和价格、距离等可以计算对象往往可以抽象为方程或者不等式中的未知量x,而时间、总价格、效率、总距离、统计量(均值方差协方差)往往作为min或者max的修饰对象,需要用其他参数和变量写成函数格式。
二、模型搭建方面:选址、传播、设置站点或岗哨、建设xx服务类设施的题目优先考虑网络图,需要方案的问题可以在目标规划求解的基础上构建自己的评价指标,涉及服务和被服务关系时排队论往往不可或缺、预测方法固定的有回归、灰度、马尔科夫、时间序列。在有数据、需要探究其关系或者做出决策时,回归和决策树、贝叶斯概率、聚类是主要手段。在传统的模型不适用的情况下,可以查询相关文章寻找特殊的量化公式或者模型,我们只需要抓住一些关键信息量化新的指标来优化和完善模型,就能起到事半功倍的效果。
2.入门级知识储备
常用的资源:
走近数学——数学建模篇(全国大学生数学建模竞赛组织委员会)
《数学建模》(姜启源)(提取码:cxar )
MathorCup高校数学建模挑战赛
深圳杯数模挑战赛
常用的模型:
规划类:线性规划、非线性规划、动态规划、多目标优化模型模拟类:线性回归、多元线性回归、BOX-COX变换、残差分析预测类:时间序列、灰度、logistics、SEIR、微分差分方程、马尔科夫链权重确定类:AHP、主成分分析、因子分析法、熵权法、模糊评价法其他常用类:图、排队论、社会力模型、决策树、博弈论
常用的方法:
蒙特卡洛法、Dijkstra、Floyd、穷举法、元胞自动机
常用的学习思路:
先学习模型的公式,再了解模型的使用情境、可应用的问题类型,最后将公式推导和原理推导手动完成一遍。
常见的子问题:
在各类数模题中往往有与如下问题有相似的类型的子问题,如果能对下列问题有一套甚至几套建模方法,个人认为已经可以解决70%+的数模问题。
1.已知x1,x2,x3,...,单位盈利为w1,w2,w3,...,多个目的地与起点的距离是d1,d2,d3,...,对应的单位距离的运费为z1,z2,z3,...,试求一个盈利最大运费最小的方案。2.已知路口的车流流入量lamdba,红绿灯n秒且忽略黄灯,在车流量稳定的情况下试分析车辆在路口的平均等待时间。3.结合第a学期b门课程的成绩,评估某年级某院某班级的每个学生的学习能力。4.结合历年来五一长假期间西安机场的航班情况,试预测今年五一期间机场在何时达到客流量的高峰,客流量大致为多少。5.TSP问题。6.试画出各种数据已知的气球在穿越n层风速为vi(i=1,2,3,...,n)的气流层时的轨迹。7.试给出方案确定学校应该新增座椅的数量和位置,学校地形、椅子成本已知。8.商场拟定根据历年来顾客的购买数据进行分析,调整促销商品的种类和价格,试给出方案。9.请根据雪崩的物理原理建立模型模拟雪崩随时间的变化。10.根据每日治愈人数、感染人数以及其他数据建立传染病模型。
二、进阶
注:由于本人是一个建模水平一般但是想法很多的人,因此以下经验可能更适合同类型的同学作参考。
许多建模同学的问题可能并不是对上述问题没有解决手段,而是模型拿出来千篇一律、没有亮点,或者对自己好的思路不知道怎么构建、实现。我认为这是处于一个厚积薄发的瓶颈期,如果能找到克服问题的方法,建模能力就会更上层楼、登堂入室(自己深有体会)。那么进阶中需要的能力是什么呢?如何强化呢?
1.分析
结合不同情况,可以分为三类。
一类同学是做题总是拿老一套模型;或者做题的时候脑子就想不到其他模型也适用。对于这类同学,我认为主要问题是储备的模型并不牢靠,对模型比较生疏,不太会使用也不清楚它适用于哪些问题。建议是加强论文阅读或者博客阅读,可以查阅模型相关的文章,引申到模型适用于哪些情景和问题。同时不要吝惜练习,在训练中大胆地使用这些要学习的模型,与其他同学交流该模型的优劣、用途。
二类同学是模型拿得出,但是缺乏亮点,看上去食之无味弃之可惜。对于这类同学,他\她可能已经在模型的运用和练习上打下了一定的底子,不过欠缺一些创造力和想象力。而我认为,想象力和创造力抽象后是相似+随机+推导,相似是指创新的想法来源于已知的知识体系但是又不完全等同于已知的知识,在思考的过程中大脑有意识或者无意识地捕捉到了解决该问题或者构建该模型的过程与曾经的xxx有相似之处,可以类比或者在此之上发散;随机是指在整顿思路得到创新点和梁点的时候,优化创新的方向是随机的、未知的,这种随机与做题的经验和感觉有很大的关系;推导是指把成型的思路量化成公式、根据思路优化改造模型的能力。对于相似和推导能力,我们可以通过对各种模型的理论推导来强化,对于随机能力,积累做题经验,阅读有想法的文章,及时总结,都不失为优化的方法。
三类同学的特征是状态不稳定,有时候自己思路泉涌,模型有自己的东西;有时候觉得自己脑子空空,面对问题只能挤出来一两个老模型应付应付;有的时候自己有了一些想法,但是落到模型上不知道从何下手。这种情况比较复杂,也许你是想法很多但是基础薄弱的小白,也许你是积累颇丰无处发力的建模人。首先应该认真的审视自己的真实水平,确定自己是积累不足还是想法不足,审视的方法因人而异,不过多赘述。积累不足去补基础,认真学习;想法不足或者实现想法的能力不强的同学,你不稳定的发挥说明你的理论基础和储备基础是在线的,可能是缺乏系统的训练总结限制了你的稳定性。这种情况下优秀的榜样可以起到很好的引领作用,推荐阅读优秀国一论文和o奖论文,在那些比较有新意的模型或者量化点上多推敲琢磨一下,总结心得即可
(在国赛和美赛篇我会列举一些个人的推荐,同时展示个人总结和心得)。
2.通用建模方法
整理思路(总理)➡剥茧抽丝(挖掘)➡师夷长技(吸收)➡优化改造(优化)
首先快速浏览问题梗概,分析问题需求(把问题具体化),抓取关键词或者关键信息,有时候题目动则在一个很大的范围内要求你规划什么什么方案,这种情况下结合信息简化问题就显得很重要。
接着整理一个大致的建模思路(类似于 我估计要用几个微分方程表示xx的变化然后用一些分析方法理一下xx和xx的关系再做打算 \ 估计要围绕这几个变量和xx的关系做文章,我想提炼几个指标做一个目标规划评价一下 这种程度的思路就行)
然后结合生活经验和做题经验,对思路中的变量和条件展开合理的分析和量化,从模糊的思路中按照:是什么—为什么—怎么做 的本质原则展开成更具体的逻辑线(此处比较抽象,下文例子可见)
接下来,查阅资料学习思路中的逻辑线如何数学化或者对题目背景的理解。一方面参考其他文献可以快速地帮助我们了解哪些模型是适用于我们的思路的,另一方面可以收集一些同类型问题背景下的信息,辅助我们修正思路中不当之处或增加一些关键点。切记此处不是拿来主义,我们可以觉得一篇论文的模型是比较完美的,但是一定不是我们可以直接拿来用的,可以参考但是不能让别人的模型完全主导你的建模逻辑线。完成这一步后,我们已经有了一个比较成熟的建模逻辑线和一个基于一些可参考样例的模型雏形了。
最后,我们的工作将决定这个模型能否成功的展示我们逻辑线中自己的思想。好的模型需要让自己建模逻辑中比较有新意或者比较科学严谨或者贴近题目背景符合实际的一点在模型里体现出来,这里不仅指代上文逻辑线中自己关于模型的创意,也涵盖建模者从题目立意、题目需求、生活实际、整篇论文的逻辑出发考虑到的小tips。实际上就是把好东西抽象量化出来,自然地融入到模型框架甚至论文表述的逻辑顺序里去。
找好东西有几个常见的思路:
引入新的定义或者变量,考虑生活实际或者政策或者人之常情。让结果更加清晰,多角度解读或综合解读结果。合适的检验,鲁棒性、残差分析等。浑然一体的建模思路,让建模看起来像建设高楼一样逐步推进,层层相连的同时更上一层楼。注意类比、近似的使用,在电路、物理、信号、网络通信等学科的知识原理可以运用于模型。
关于抽象量化上文有介绍。而“自然”是说我们量化出来的小模型、约束方程或者不等式组在模型的这个地方运用是有道理的,要么从生活常识上它符合我们一般人的认知,要么逻辑推理上有足够的推导证明它根正苗红,要么事后诸葛亮来个验证分析讨论其合理性。
3.例子
如何规划电动汽车充电站在全国的建设方案
一、总理:
电动汽车充电站、全国、建设方案,围绕题目和背景做一个简单的思维发散:
1.问题就是规划电动汽车充电站建设方案。肯定要查一下电动汽车充电站的相关的信息和它的用户相关的信息,后面应该有参数用得上,具体查啥等思路进一步理清楚。
2.全国这么大这么复杂,且不说有没有办法一个模型求出全国怎么规划,搜索相关信息的时间成本就很棘手。所以我们先解决一个小地方(省、市、区)的推广方案,提出一个输入参数就能求出方案的模型,再推广到全国(具体、简化)。
3.并且车用户的个人信息本来就查不到几个,能用的信息肯定是那种一个区域统计的总量。所以我们的模型如果想考虑一个个的客户是不太实际的 ,可以用车辆大量聚集的地方如小区、超市、公司停车场、加油站等地点模拟车所在的位置(简化)。
4.再想的细致一点,在一个小地方上的建设东西,图模型八九不离十了,那么图怎么建立呢?我们把该地的地图简化成背景图,标出车在的点(需求点),标出主干道作为图的边,问题就成为了在图上找服务点来满足需求点的问题(抽象),现在就是欠缺量化指标和规划的条件了
二、挖掘
结合生活,汽车-充电站的关系就好比于客户-服务方的关系,在哪建多少个充电站就好比服务站点应该在哪建多少个(这只是一个说法,这个地方是为了找一个你更熟悉的情景关系,有助于你接下来的分析)。我们不妨从客户-服务方的出发点分别思考他们对于如何建立服务站有这什么样的考量。
服务方:想挣钱-------需要-------客户多、建设成本低、运营维修成本低-------需要-------离的近、服务质量好(吸引顾客来)、每个点潜在客户多、少建点、每次建的成本低一点、减少维修次数
客户:省钱/方便-------需要------- /距离近/服务好-------需要-------离的近、排队时间少-------需要-------每个点的人数不太多
逻辑线形成,提炼因素:距离、成本、需求量、服务质量(排队时间)、(政策限制)、其他(维修运营成本)
接下来需要考虑这些因素加入到我们的模型中,使用合理的方法对上述因素进行组合,让它把我们的问题具体到 某变量/方程组/不等式组,例如:我们想找出建设的可能的地点,有什么方法呢。简单的如直接取所有路段的中点或者交叉点,复杂的用一些指标约束我们的选址条件,我们的因素组合量化起来。
三、吸收
这里我找一篇相关论文,模拟不太有思路时去找相关论文阅读的步骤。
引用论文:[1]张国亮. 城市内和城市间电动汽车充电站的选址布局研究[D]. 天津:天津大学,.
DOI:10.7666/d.Y2241610.
摘取关键的模型和信息:
可以在上述模型中看到,作者用引力模型量化需求量,建立三个布尔变量表示一个节点是否在组合中、组合是否满足路的需求、线路能否被满足需求。因此模型建成了一个单目标零一规划模型,将建设问题分拆成了三个子问题:怎么建设、建设好不好、建设的约束条件。
一、怎么建设:候选点是否建立充电站、充电站是否属于某个充电组合/方案、路的需求是否能被某个组合/方案满足。
二、建设好不好:被满足服务的路径需求总量最大时最好。
三、建设的约束条件:建设充电站总数目等于一个定值,被启用的充电站组合/方案内所有充电站都开放服务/被启用、每个能被满足需求的路径都至少有一个充电组合/方案,方案内有充电站是服务于该路径的。
我们大致理解了作者的思路后,发现它设计的布尔型变量来待定图上的节点是否建充电站这个思路不仅方便我们求解,而且与参数相乘和求和都能方便地表达新的含义,这是一个值得学习保留的点。此外,约束条件也可以适当参考,不等式的表达和量化比较简洁清晰。顺便一提的是,他用引力模型计算需求量是个不错的点子,我们可以也引用一些合理的模型把成本、需求量、距离的量化进行优化。
结合我们的题目经过一定量的修改,我们得到如下模型。模型舍弃了充电站方案的集合的概念,直接求解方案。对于原本路径只能考虑该路径上的候选点,修改为考虑任意候选点。对于原本求解需求点的需求量,模型改写为需要充电站的个数。
接下来我们肯定要优化这个粗糙的模型。在本模型中,首先目标上,从服务质量角度看用于服务的充电站尽量多,从成本角度充电站总数量尽量少。约束条件上,充电站总量小于建设阈值,每个需求点有至少有刚好符合需求的充电站来服务。回顾一下提出的逻辑链和因素:距离、成本、需求量、服务质量(排队时间)、(政策限制)、其他(维修运营成本),不难发现模型只在数量上作为优化方向,没有足够的优化约束和优化理由对需求点和充电站间的对应关系S_k,q求解,而且求解出的结果应该是不能满足所有需求点的需求的(由于约束条件二)。
为此我们可以做扩展,考虑到服务质量和距离,让目标兼顾充电站数量尽量少,充电站与需求点的距离尽量小,每个充电站服务的需求点数量尽量均衡,于此同时,我们希望求解出的结果至少能刚好满足所有需求。如下:
四、优化
一般来说,如果是针对一个问题中的一部分,建模到上面这个程度已经是不错的水平了,进一步的优化出于两种动机:1.仍然感觉有些因素/关键信息/关系没有反映在模型上;2.模型针对求解的问题来说体量太少了,显然是有缺的(比如国赛第二题你就这么个规划模型解决了,那肯定不正常)。
针对2,我的建议是放缩,尝试在这个已建成的模型和题意间查漏补缺,看看是否存在未知变量/关系/方案。因为我们上面的挖掘和吸收部分都是从大到小,从整体到局部,从目标到细节,所以把模型当做求解问题的一小部分,思考求解问题还缺少什么样的信息和什么样的关系是合适的,这是所谓的缩(比如本题中,电动车进入充电站之后的充电、排队的模型,不同类型的充电站选址、建设规划等等),建模思路和我相反的同学就可以把模型放大为求解模型的总架构,思考其中缺失的细节部分和连接框架的逻辑关系,是所谓的放。
针对1,我的建议是参考上面通用建模方法里所讲的提炼好东西的方法,有两个基本的思路,一是考虑模型的情形和现实背景间是否存在某些区别或信息缺失,想办法补足;二是考虑从各种角度解读模型的适用性、合理性。
1.例如电动站是不是有相关新闻或者政策,里面是不是提到了一些有趣的信息:只能建设在某些区域?充电站是小体积易迁移?
2.例如,上述模型是细化到局部地区的,如果扩展到全国是不是要考虑不同的城市经济、交通情况?整体规划上是不是要考虑地形、公路铁路以及政策限制?
3.例如,模型中的超参数:S_0和r_0是怎么确定的,有没有相关材料或者自己设计的仿真说明其合理性?
4.例如,模型的建立没有客观指标说明其好坏,有没有办法做鲁棒性检验、或者代入某地区真实数据来检验?
5.例如,能不能针对该模型的一部分,建立新的模型,在条件符合某一条件时替换到新模型来求解,以增加模型对不同情况的适应能力?
6.例如,针对现实中的不同情况,是否能设置不同组仿真来对比方案的好坏?
三、国赛
1.团队赛前准备
2.题目分析解读
3.优秀模型分析
四、美赛
1.团队赛前准备
对于美赛啊,众所周知美赛全程是美国大学生美术绘图大赛(狗头),于国赛、校赛都有较大的区别,所以赛前去了解这些区别,针对美赛做一些特殊的准备是很重要的。在赛前准备这一块,我想先简单谈谈我们团队的经验,再在下面以一道题为例解剖我在处理B真题的时候整个建模的思路和心理历程。
分享经验讲座的录播链接
建模方面,往年题训练是必要的,我的建议是队伍做五年以内的两种类型的题目(数量上2:4都可以1:4),保证自己队伍对六道题起码有选两种的余地,而且灵感来了可以冲(例如我们队一般就是做D题的,B纯粹是因为我们感觉思路很清晰想冲一把)。
编程和论文方面,如果你们有啥问题可以私聊我或者评论区,我代你们问问我队友吧。
团队方面,我浓缩为一个核心两个基本点:以多读优秀论文为核心,坚决学习优秀论文的优点,坚决把握团队做题的节奏。
其中,阅读优秀论文是最最最最最最最最最最最最最最最最最最最最最最重要的。俗话说,一流的师傅,二流的徒弟;想考九十分就要在考试前用一百分的目标约束自己。从最优秀的论文入手绝对是适应美赛风格、提升自己能力最快的途径。像我们在赛前,把近五年的美赛题(不看E\F)的优秀论文基本都一起阅读整理了。我们的阅读方法是早上起来开腾讯会议,先把题目看了,划关键词和重要信息。一起解读题意后,各自去看该题的所有优秀论文(O\F),整理文章的解题思路和从各个职位上解读的亮点作为阅读笔记,到下午三点/四点,再一起分享阅读笔记,共同学习。如果时间有余,我们就花一到两小时梳理如果我们做题的话解题的思路。
分享一个D编号为1900007的优秀论文阅读笔记,提取码1234
建模的学习重点:优秀论文中建模的思路是怎么推导的,建模的框架是什么样的,模型在哪一部分的修改和题目背景符合的很好,哪一部分是创新点、特点,常用的模型有哪些。编程可能偏重学习论文中的算法设计、可视化展示的方法,论文可能偏向于学习文章中常用的句子、段落、结构,同时也会注意论文中的图表(偷一张队友的图为例)。
当然了,读论文虽好,也不能光纸上谈兵,做题也是必要的。什么叫把握做题的节奏呢?就是说做题的时候严格的控制大致的时间安排,做到对做题时间的大致把握、队员分工的大致熟悉以及超出预期时间时的风险方案预备。在做题训练中把这些工作做到位,正式比赛就能游刃有余,对进度心里有数,也不会因此而焦虑或者浪费团队效率,是非常有用的。毕竟比赛是三个人的合作,把合作的细节和节奏把握住了,肯定能起到事半功倍的效果,多是一件美事。
我们队读论文的时间表:
我们队根据训练时间的经验预估的时间表:
2.题目分析解读
题目如下:
美赛B题目,提取码1234
美赛B题目中文翻译+划重点,提取码1234
美赛BO奖论文,提取码1234
那么题目浏览一下,我们大致来进行一个问题的梳理分析:
第一问显然是一个有多种因素影响方案好坏的求解方案问题,考虑因素包括:性能、安全、经济、任务需求、地形、火灾大小、频率,目标时给出方案最优时无人机的数量和组合。第二问是模型要适应未来十年火灾的变化,并计算增加的成本。那有未来的时间尺度应该是要做预测分析,模型对xx变化的适应应该考查的是模型计算的无人机数量和组合的方案是否仍然较优,模型对变化的鲁棒性等等,成本计算只要合理的考虑系统内的成本就行。第三问是考虑无人机放置问题,结合题意应该要注意到保护中继器远离火场、保证中继器在射程内最大化利用。整体来说,B题想要我们针对澳洲维多利亚地区火灾设置合理的无人机采购和部署的方案,目的是方便EOC(后方)通过无人机指挥地面靴小队(现场)解决“快速丛林火灾”/极端火灾(下面并称为极端火灾)。
第一问:
第一部分: 地区危险等级评价模型
小tips,对于方案求解问题,我们的出发点一般是摸清楚方案实施的动机和背景系统的运作方式与各种因素的关系。针对澳洲这个地方,无人机方案并不是想要解决全部的火灾,而是“快速丛林火灾响应”,也就是快速突发的、危险性、传播性较大的火灾,这是一个很重要的解读点。而澳洲地区,地理环境复杂、面积广袤、不同地形地区的火灾频率和危害差异很大,无人机布置肯定不能一视同仁、一概而论,我就想到说结合考虑因素,我们把澳洲地图进行划分,用各种因素来评价某一地点对“快速丛林火灾响应”的需要程度,这样对因素量化的同时也解决了无人机方案如何适应广大面积下不同地区的不同需求。
因此建立地区危险评估模型。网格化地图1km,考虑经纬度(x,y)地区的火灾频率f(x,y),火灾规模size(x,y)、近期有无火灾situation(x,y),地貌g(x,y)得到安全系数S(x,y),根据网格和临接网格的安全系数打分得到安全等级。
上面用AHP把三种指标揉在一起评价后,其实完全可以把地形也放进去,不过我想做一些优化。一是我感觉AHP弄太多指标不太好,而且地形听起来和那三种火灾相关的指标不是一种类型,应分开;二是网格化地图上相邻地区仅1km距离,如果一处地方的邻近处有火灾隐患,势必会牵连该地的安危,这种相关性应加以考虑。因此优化如下:针对不同地形,对安全系数进一步分级,同等安全系数时易燃地区的危险程度更高,不易燃地形更低;用3*3的卷积核来挖掘每个地区邻接地的相关性。
其实事后诸葛亮的角度来说,这个评价方法依然有一些主观,篇幅充足的情况下,应该一个可信性检验。我们上述权重都是用澳大利亚信息公开里的各地火灾数据计算的,作为检验我们可以筛选出其中属于极端火灾的火灾,代入它们的数据观察它们计算的危险等级分类是最高的比例,比例越高则模型越合理。当然按照美赛惯例,对AHP指标进行鲁棒性分析也是很好的,图附在了文章末尾。
第二部分:无人机组合和数量方案-基于组合率最大和成本最小
关于无人机的方案,其实属于常见的资源调度类优化问题,就是不同地区有不同的需求,怎么安排最好这样子,我们抓住方案的优化方向耐心的梳理出目标和约束条件就可以了。
回顾一下考虑因素:性能、安全、经济、任务需求、地形、火灾大小、频率,目标时给出方案最优时无人机的数量和组合。性能是反映无人机方案的能力,根据我对题意的解读,是极端火灾发生时无人机能否快速到达现场的反应时间越小,能力越大。安全这个指标有点难办,是无人机安全吗?结合第三问我想应该不是的,而前方的消防员已经身处火海了,所以是考虑EOC(后方)的安全,这好办啊,把EOC统统移到危险等级为一般或者安全的地方就完事了。经济就是少花钱多办事,让无人机工作效率上去,效率可能和无人机组合有莫大的关系,先放一放。任务需求想说的是无人机得干点他们想干的事儿嘛,包括但不限于及时响应极端火灾、对现场持续提供通信和观察。我想买这么贵的机器应该不是平时吃灰然后几年一遇的极端火灾才出来溜溜的,他们平时就在澳洲上空巡逻,预备火灾更合理。
于是进行抽象量化:保持无人机性能最大只需让响应时间最小,时间取决于火灾现场和EOC的距离,无人机的速度。因此约束EOC设置在离火场最近的安全地区,无人机取能保证往返时的最大速度即可。(性能、安全、)
接着,考虑任务需求,我们EOC都流动在离火场最近的安全区域了,那肯定要SSA监控火灾现场或者检查有无火情,然后中继器无人机保证EOC和SSA通信往来。这种需求下,我分为两个情境来思考:一、已知火情,需要无人机动态的维持观测任务。二、未知火情,需要无人机动态的观察是否出现火情。
情境一,首先我们得在短时间(30s)内扫描火场,并且有无人机持续交接班来保持火场始终有电量适当的无人机提供观测和通信服务。
关于交接班的轮班示意图:
情境二:只需对所有危险等级为最高的地区都保持一架无人机监控,就可以在最坏的情况下也保持对极端火灾的及时响应能力。当然适当的准备一些备用无人机也是必要的,引入损耗比φ。
到目前为止,SSA的安排已经很清楚了,但是中继器无人机(下面称USA)始终不明朗。考虑到EOC就固定在火场最近的安全区域点了,而SSA的数量也跟USA没关系,看起来中继器无人机好像很难搞。我们打开思路,尝试找到系统内所有元素与USA的关系:SSA→支援→某高危/防范地区→信号传送→USA→信号转发→EOC,在信号传输这块上,我们结合计网的知识,想到了允许多种不同主机的信号并行的通过路由器、中继器转接收发,那USA是不是也有类似的功能呢?大致确定了可行性后,我决定把USA的求解重点放在多个SSA复用同一个USA来达到“组合”和“工作效率”的指标要求。(任务需求,组合)我设计了一个简单的贪心算法来优化USA的数量,使得每个USA都尽可能的服务更多SSA:
举个例子,如图,绿色为EOC和USA可以停留的低风险地区,黄色小点是EOC,半透明圈是EOC+中继器扩大的无线电射程,红色为火灾现场,半透明圈是便携式无线电的射程。因此,紫色区域为USA候选位置1,绿色区域为USA候选位置2,黄色区域是两个候选区域的相交区域,如果在黄色区域派去USA而不是紫色和绿色区域各派遣一个USA,则可以节省一个USA,且USA的使用对象提升至2。
计算出USA的数量n0后,用同上的交接班方法计算出总USA的数量,至此确定了不计损耗的前提下USA的总数量。最后定义复用率=USA的数量/SSA的数量,得出规划模型,使得复用率最小、成本最小,约束条件为n>n0(隐含条件)、速度和最大航程在合理范围:
(emmm这个书写错误可以说很蠢了,请大家引以为戒)
第二问:
第一部分:未来十年的极端火灾可能性和严重程度预测
根据上面的分析,我们首先要解决未来十年火灾的预测问题,预测可能出现的火灾的危险程度和可能性。我们常用的预测包括时间序列模型、马尔科夫链、灰度预测模型、微分方程模型等等。首先排除马尔科夫链,因为未来的状况不一定属于已知状况的一种。其次考虑模型的输入和计算问题,如果是对每个地区逐个计算,则网格化地图有长*宽个地区待计算,采用时间序列或者灰度预测模型的话输入向量的维度则过大,平滑手段显然不再有效。如果做整体的数量预测,就给不出可能性估计的方法,而且有极端火灾的年份方差很大,数据过于稀疏。而微分方程难内手调的权重以精确的把握火灾的生灭、大小情况,也不符合,至此传统模型全排除。
为了解决这个困难,我们队阅读大量预测极端事件、小概率时间的文献,终于找到了一种很棒的方法:
可公度模型。这种方法是以系统内各元素的普遍规律为基础,根据特殊事件来预报特殊事件。
参考文献,提取码1234
只要理解为I_j∈{+1,-1, 0},就不难得出该式子就是说在Xi+1之前的元素可以通过加减关系推导出X_i+1,当这个式子在某个系统中对多组X_i+1和X_j成立且拒绝均匀分布假设,就有较充分的置信度拿来作为预测手段。
拒绝均匀分布方法:计算每个元素对应频数后计算卡方分布即可。
学习完该模型后我们就可以开始做预测了,只需要把有极端火灾的年份代入三元可公度模型计算即可。
由于我的失误,导致文章内第15页中计算概率的计算方法与蝴蝶图并不对照,误导大家非常抱歉,在此更正。
一、如果根据蝴蝶图的计算概率方法,计算步骤如下:
1.先找出除了自身外所有参与预测的点:
2.根据蝴蝶图的对称性检查是否需要增加节点,例如假如上图中的2是不计数的,但是它的对称点6是计数的,那么2就也是计数的。上图中没有遗漏的对称点,故m还是13个。而n为所有在蝴蝶图里有连线的不包括自身的点,也就是13。
3.计算P = m / n = 13 / 13 = 100%
二、如果根据频数计算概率方法,计算步骤如下:
1.遍历所有的间隔(在本图中为17(18)、3(2、3)、9(8)三种),找到对应的除自身外的(计算自身也行)、不重复的用于预测年份的总数:m = 14 + 1 + 1 = 16
2 n为所有参与预测的包括自身的年份,即为 17, 所以P = m / n =16 / 17 = 94.12%。
由此得到未来会发生极端火灾的具体年份,接着对火灾的严重程度也进行预测,结果做成饼状图分析:
第二部分:额外成本计算-消防员处理极端火灾事件的成功概率模型
在预测火灾后,为了适应未来十年极端火灾事件可能性的变化,只针对极端火灾事件增加EOC和"地面靴"消防员的设备配置,得到增加的设备成本。设备包括“地面靴”小队的手持式无线电台、可穿戴设备和EOC的双向无线电。从安全性角度,我们假设每个地面靴”小队的消防员人手一个手持无线电台和一套可穿戴设备,每个EOC有一个双向无线电用于监视和通信、一个双向无线电备用。当然上面这些没有权威资料,我们是根据网上的一些新闻和杂志推测的。
假设各个火灾间相互独立,用十年内极端火灾的概率之和作为会发生的极端火灾的期望值,然后计算EOC和消防员的增加成本。由于消防员和火灾间的关系尚不明朗,我们大胆假设小心求解,建立了消防员处理极端火灾事件的成功概率模型:
这样就找到了消防员数量和极端火灾严重程度的量化关系。接下里的计算就顺理成章了,略。
需要指出的是,第一部分求复用率最小和成本最小的规划模型是个伪规划模型,因为在此之前已经确定了SSA和USA的需求数量,后续模型是通过调节磨损率控制磨损成本,并且把复用率压低在合适区间。没有这个规划模型,就能达到理论上的复用率最小,只是没有备用的无人机,也不失为简洁的方案。在第二部分的消防员处理极端火灾事件的成功概率模型,其实主观成分较大,不够严谨,可惜相关的资料实在是有点太少了,没有足量的数据拟合两者的关系,合理性上多少有点不好。
第三问:
在开始之前,我们分析一下题目,优化USA在不同海拔不同地形的位置,适应火场和地形。结合题目背景内信号在不同地形有不同的射程,我给出的思路是先建立不同地形/海拔下的射程模型,然后根据射程限制和保护USA远离火场的需要再规划其位置。
第一部分:信号损耗方程
可以看到我们的模型显然是大量引用找来的信号损耗方程。这个是我考虑的,本身这个数据也不好收集,我们主观意志下建模就不太好,就采用专业点的方程更好。
感兴趣的话可以看一下这里面大量的参数估计,有点实用性。
第二部分:火灾蔓延模型-USA位置优化
如图,我们结合火场的地形和海拔,思考火灾的蔓延对USA的潜在风险。为了简化,我们约束USA与火场即将蔓延的边界处至少保持50m距离,火灾蔓延考虑东南、西北、东北、西南、东、西、南、北八个方向。(图是用PPT画的)
结合常识,我们建立火灾蔓延距离和风速、地形、火灾规模的 模型:
风速的数据用地形和海拔来大致评估:
因此,综合射程和安全,给出优化条件:信号信噪比大于20db,USA与火场即将蔓延的边界处至少保持50m距离。
(像这样的地图题美赛确实爱考察,如果有好的结果,不要吝啬图表和可视化结果。受限模型不能做全局图,也可以选取有代表性的几个地点单独作图分析)
3.优秀模型分析
算了我懒得看新论文,大家自行分析整体吧。
五、其他
总结
提示:这里对文章进行总结: