飞行管理问题-数学建模.ppt
飞机飞行管理问题,重庆大学数理学院 段正敏,如何建立数学模型?,题 目,在约10000M高空的某边长160km的正方形区域内,经常有若干架飞机作水平飞行,区域内每架飞机的位置和速度向量均由计算机记录其数据,以便进行飞行管理.当一架欲进入该区域的飞机到达区域边缘时,记录其数据后,要立即计算并判断是否会与区域内的飞机发生碰撞.如果会碰撞,则应计算如何调整各架(包括新进入的)飞机飞行的方向角,以避免碰撞.通过给定的假设条件建立数学模型,并对所给数据进行计算,要求飞机飞行方向角调整的幅度尽量小.,假定条件,(1)不碰撞的标准为任意两架飞机的距离大于8km（2）飞行方向角调整的幅度不应超过30度（3）所有飞机飞行速度为800km/h（4）新飞机进入该区域边缘时，与区域内飞机的距离应在 60km以上。（5）最多考虑6架飞机（6）不必考虑飞机离开此区域后的状况,给定数据,设该区域4个顶点的坐标为(0,0),(160,0),(160,160),(0,160).飞机位置、飞机方向记录数据：,摘要,从形式上看，该问题属于最优控制问题，若考虑6架飞机，该问题便有六个可控制对象，相当复杂。基于此，首先对问题进行一些必要的简化，然后从不同的侧重角度，讨论并确定了目标函数和约束条件，建立了非线性模型；在具体计算中，根据计算的需要，将非线性模型化为了线性模型，再选用合适的初始解，利用分枝定界法的思想最终得到解。在问题的最后，还考虑了利用逐步逼近搜索方法、能量梯度求解法及球状模型求解法等其它方法对该问题的解决进行了讨论。,涉及知识,1.线性规划2.整数规划-关于分枝定界法3.非线性规划（有约束）-制约函数法 A 外点法 B 内点法4.非线性规划（无约束）-最速下降法5.MONTE-CARLO法,主要内容,1.详细分析模型；建立非线性规划模型；转化非线性到线性问题求解;进一步思考.2.简略讨论逐步逼近搜索方法.3.简略讨论能量梯度求解法.4.简略讨论球状模型求解法.简略讨论其它方法.6.课后练习.,符号说明,是代表第I架飞机，刚进入的飞机记为第6架 表示第I架飞机在时刻T时位置的坐标，为第6架飞机刚进入正方形区域边界的时刻；代表第I架飞机在时刻T的速度，速率为800KM/H 表示的是第I架飞机在时刻及飞行方向角后的飞行方向角（与X轴正向之间的的夹角）,符号说明,表示第I架飞机飞行方向角的调整值，逆时针为正，顺时针为负。表示 相对于 的速度。表示由X轴正向至 的夹角。代表的 方向角，即由X轴正方向至以 为起点，为终点这一向量的夹角。,模型分析,如果发生碰撞，尽早调整一定优于晚调整,A(甲飞机),F(较后调整方向),E,C(较早调整后方向),D,B(原来方向),飞行AD段再较后调整,分析图形:CDBA,且甲飞机不能通过二次调整到C点,要保证不碰撞,必调整到E点,但EDBCDB A,更糟糕的结果!,模型分析,可根据数学归纳法证明:如果发生碰撞，多次调整不如在第一次调整时调整到位好,H(角度调整太大,不是最佳),A(甲飞机),D,F,C(不会碰撞方向),E,B(飞机原飞行方向),G,O(第一次调整方向),ODC+BAOBAO+DAC=BAC,同时,经过两次调整飞机仍不能达到C点,而只能到F点,要到达AC方向,只能增大调整到E点.,思考,关于目标函数的讨论,约束条件,该模型可以直接用matlab求解,约束条件思考,非线性规划化为线性规划图示,Pi,Pj,dij,Pi与Pj连线与x轴的夹角为,约束条件思考,由上图,Pi与,Pj,在t0时碰撞的充要条件是,Vij的方向,属于(,-,+,),约束条件,非线性规划化为线性规划图示,X轴,易得到：,非线性规划化为线性规划,非线性规划已化为线性规划,上述模型未考虑区域限制条件，这与实际不符，因为两架飞机将在几千km之外发生碰撞并不是我们本模型需要考虑的，于是需进一步考虑正方形边界问题,改进模型,我们用空间理论加上时间因素考虑此问题，并在考虑正方形区域限制时，可以以 为初值向 进行搜索，确定出禁飞方向角的最大值、最小值。,结论,无论什么情形，我们均可转化该非线性规划为线性规划。由于约束条件中存在“或者”的情况，那么所得的线性规划问题有多个，为了使得计算量的减小，我们采用了分枝定界法.,进一步讨论,以上解法的关键之处是飞行方向角禁区是一个区间,这是由飞机速度完全相同造成的,若飞机速度不相同,方向角禁区不再是一个区间,考虑在一般情况下是否可以对该种情况进行求解,如何求解?,另类解法一,逐步逼近搜索方法,另类解法一,此法类似于MONTE-CARLO法,另类解法一,方法1,在内以较大跨度均匀地取N个点，通过遍历计算找到其中使 取最小值的点，然后以该点为中心，找一个较小区域，在其中再取N个点，在N个点中在找使 取最小值的点，如此迭代下去。,另类解法一,方法2,在内以较大跨度均匀地取N个点，通过遍历计算找到其中使 取最小值的M个点，然后以这M个点为中心作M个小区域，在每一个小区域中均匀地取N个点，计算出这MN个点中使 取最小值的点，如此迭代下去。,2、能量梯度求解法,另类解法二,另类解法二,定义能量函数,我们只要在空间1,2,，n上找到E的零点，便可符合题目的要求,用球状模型求解法,另类解法三,将每架飞机视为球状模型，整个区域视为二维平面。,当 时两架飞机不碰撞,重要结论,对第I，j架飞机，其飞行方向角改变量i,j之和的一半即为其相对速度方向 的改变量，亦即得：,另外的非线性规划模型,通过条件简化最终化为线性规划模型,另类非线性规划模型,思考,改进后的模型,思考,1995年全国大学生数学建模竞赛A题,飞行管理问题,第一种解法的补充：,一个飞行管理问题,在约10000m高空的某边长160km的正方形区域内,经常有若干架飞机作水平飞行,区域内每架飞机的位置和速度向量均由计算机记录其数据,以便进行飞行管理.当一架欲进入该区域的飞机到达边界区域边缘时,记录其数据后,要立即 计算并判断是否会与其区域内的飞机发生碰撞.如果会碰撞,则应计算如何调整各架(包括新进入的)飞机飞行的方向角,以避免碰撞.现假设条件如下:1)不碰撞的标准为任意两架飞机的距离大于8km;2)飞机飞行方向角调整的幅度不应超过30度;3)所有飞机飞行速度均为每小时为800km;4)进入该区域的飞机在到达区域边缘时,与区域内飞机的距离应在 60km以上;5)最多考虑6架飞机;6)不必考虑飞机离开此区域后的状况;请你对这个避免碰撞的飞行管理问题建立数学模型.列出计算步骤,对以下数据进行计算(方向角误差不超过0.01度),要求飞机飞行方向角调整的幅度尽量小.设该区域4个顶点坐标为(0,0),(160,0),(160,160),(0,160).记录数据为:,飞机编号 横坐标x 纵坐标y 方向角(度)1 150 140 243 2 85 85 236 3 150 155 220.5 4 145 50 159 5 130 150 230 新进入 0 0 52注:方向角指飞行方向与x轴正向的夹角试根据实际应用背景对你的模型进行评价与推广.,建模 关键量-时刻t第i架飞机的坐标-第i架飞机的方向角-第i架飞机的方向角的调整-时刻t第i架飞机与第j架飞机的距离-第 i架飞机的初始位置 v-飞行速度,距离的表达式:,其中,不碰撞的条件(在区域内)t在区域内时间 满足 即为碰撞时时间 令 c=d-64 条件为:要求仍在区域内,数学模型 调整量为 使既不碰撞,调整最小s.t.,不碰撞条件的另一种表达,之一超出区域,线性规划模型:相对速度方向约束条件改为:,约束条件线性化,课后练习,对第一种方法中的求解过程进行实际操作.2.选择三种另类解法中的一种,利用所给数据,求解最优解.3.每一小组同学讨论后形成报告.,学习数学,热爱数学,E-mail,
