飞行管理问题-数学建模

1、1995全国大学生数学建模竞赛A题 赛 题 在约在约10000M10000M高空的某边长高空的某边长160km160km的正方形区域的正方形区域 内内, ,经常有若干架飞机作水平飞行经常有若干架飞机作水平飞行, ,区域内每区域内每 架飞机的位置和速度向量均由计算机记录其架飞机的位置和速度向量均由计算机记录其 数据数据, ,以便进行飞行管理以便进行飞行管理. .当一架欲进入该区当一架欲进入该区 域的飞机到达区域边缘时域的飞机到达区域边缘时, ,记录其数据后记录其数据后, ,要要 立即计算并判断是否会与区域内的飞机发生立即计算并判断是否会与区域内的飞机发生 碰撞碰撞. .如果会碰撞如果会碰撞, ,

2、则应计算如何调整各架则应计算如何调整各架( (包包 括新进入的括新进入的) )飞机飞行的方向角飞机飞行的方向角, ,以避免碰撞以避免碰撞. . 通过通过给定的假设条件给定的假设条件建立数学模型建立数学模型, ,并对所给并对所给 数据进行计算数据进行计算, ,要求飞机飞行方向角调整的幅要求飞机飞行方向角调整的幅 度尽量小度尽量小. . 假定条件 （1）不碰撞的标准为任意两架飞机的距离大于）不碰撞的标准为任意两架飞机的距离大于 8km。 （2）飞行方向角调整的幅度不应超过）飞行方向角调整的幅度不应超过30度。度。 （3）所有飞机飞行速度为）所有飞机飞行速度为800km/h。 （4）新飞机进入该区域

3、边缘时，与区域内飞机）新飞机进入该区域边缘时，与区域内飞机 的距离应在的距离应在60km以上。以上。 （5）最多考虑）最多考虑6架飞机。架飞机。 （6）不必考虑飞机离开此区域后的状况。）不必考虑飞机离开此区域后的状况。 给定数据 设该区域设该区域4 4个顶点的坐标为个顶点的坐标为 (0,0),(160,0),(160,160),(0,160).(0,0),(160,0),(160,160),(0,160). 飞机位置、飞机方向记录数据：飞机位置、飞机方向记录数据： 飞机编号横坐标X纵坐标Y方向角(度) 1150140243 28585236 3150155220.5 414550159 513

4、0150230 新进入0052 摘要摘要 从形式上看，该问题属于最优控制问题，若考虑从形式上看，该问题属于最优控制问题，若考虑6架架 飞机，该问题便有六个可控制对象，相当复杂。基于飞机，该问题便有六个可控制对象，相当复杂。基于 此，首先对问题进行一些必要的简化，然后从不同的此，首先对问题进行一些必要的简化，然后从不同的 侧重角度，讨论并确定了目标函数和约束条件，建立侧重角度，讨论并确定了目标函数和约束条件，建立 了非线性模型；在具体计算中，根据计算的需要，将了非线性模型；在具体计算中，根据计算的需要，将 非线性模型化为了线性模型，再选用合适的初始解，非线性模型化为了线性模型，再选用合适的初始解

5、， 利用利用分枝定界法的思想最终得到解。在问题的最后，分枝定界法的思想最终得到解。在问题的最后， 还考虑了利用逐步逼近搜索方法、能量梯度求解法及还考虑了利用逐步逼近搜索方法、能量梯度求解法及 球状模型求解法等其它方法对该问题的解决进行了讨球状模型求解法等其它方法对该问题的解决进行了讨 论。论。 符号说明符号说明 是代表第是代表第i架飞机，刚进入的飞机记为第架飞机，刚进入的飞机记为第6架架; 表示第表示第i架飞机在时刻架飞机在时刻T时位置的坐标时位置的坐标; 为第为第6架飞机刚进入正方形区域边界的时架飞机刚进入正方形区域边界的时 刻刻; 代表第代表第i 架飞机在时刻架飞机在时刻T的速度，速率为的

6、速度，速率为 800km/h; 表示的是第表示的是第i 架飞机在时刻及飞行方向角架飞机在时刻及飞行方向角 后的飞行方向角（与后的飞行方向角（与x轴正向之间的的夹角）轴正向之间的的夹角）; i P )(),(tytx ii 0t )(tVi ii , 0 符号说明符号说明 表示第i架飞机飞行方向角的调整 值，逆时针为正，顺时针为负; 表示 相对于 的速度; 表示由X轴正向至 的夹角。 代表的 方向角，即 由x轴正方向至以 为起点， 为终点这一向量的夹角。 i jiij VVV i P j P ij jiij VVV ij ( (0)(0),(0)(0) ijij xxyy )0(),0( ii

7、yx (0),(0) jj xy 模型分析 如果发生碰撞，尽早调整一定优于晚调整 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点,而

8、只能到F点,要 到达AC方向,只能增大调整到E点. 关于目标函数的讨论关于目标函数的讨论 6 1 min min i i i j J sign 且 第一种目标函数 第二种目标函数 min i j J 16 maxmin i i 第四种目标函数 第三种目标函数 6 2 1 min i i 约束条件思考 非线性规划化为线性规划图示 Pi Pj 8 arcsin ij d dij 1 22 2 (0)(0)(0)(0) ijijij dxxyy Pi与Pj连线与x轴的夹角为 ij 约束条件 约束条件思考 由上图, Pi与Pj在t0时碰撞的充要条件是 vij的方向 88 arcsin,arcsin i

9、jijij ijij dd 约束条件 非线性规划化为线性规划图示 j v i v ji vv x j i 易得到： () 22 () 22 Non. () ij ij ij ijij ij ij 非线性规划化为线性规划 ）无方向（ 确定 ji ji ji ji ji ij ij ij ij ijij ij )( 22 )( 22 d 8 arcsin, d 8 arcsin 非线性规划已化为线性规划 6,.,1,.,2,1 2 )( 8 arcsin 2 6,.,2,1, 6 . min 00 6 1 ijni sign d its ji ij ij jiji i i i 上述模型未考虑区域限

10、制条件，这与实 际不符，因为两架飞机将在几千km之外发 生碰撞并不是我们本模型需要考虑的，于 是需进一步考虑正方形边界问题 改进模型改进模型 我们用空间理论加上时间因素考虑此问题， 并在考虑正方形区域限制时，可以以 为初值向 进行搜索，确定出禁飞方向角的 最大值、最小值。 ij ij d 8 arcsin ij 结论 无论什么情形，我们均可转化 该非线性规划为线性规划。由 于约束条件中存在“或者”的 情况，那么所得的线性规划问 题有多个，为了使得计算量的 减小，我们采用了分枝定界法. 进一步讨论 以上解法的关键之处是飞行方以上解法的关键之处是飞行方 向角禁区是一个区间向角禁区是一个区间, ,这

11、是由飞这是由飞 机速度完全相同造成的机速度完全相同造成的, ,若飞机若飞机 速度不相同速度不相同, ,方向角禁区不再是方向角禁区不再是 一个区间一个区间, ,考虑在一般情况下是考虑在一般情况下是 否可以对该种情况进行求解否可以对该种情况进行求解, ,如如 何求解何求解? ? 用球状模型求解法 将每架飞机视为球状模型， 整个区域视为二维平面。 ij v ij ij ij ijij 当 时 两架飞机不碰撞 重要结论 对第i，j架飞机，其飞行方向角改变量 i, j之和的一半即为其相对速度方向 的改变量 ，亦即得：ij ij 2 ij ij 另外的非线性规 划模型 00 0 i i ji ijijij

12、ij 300 30 2 . t . s Zmin 通过条件简化最终化为线性规划模型 另类非线性规 划模型 2 ij 2 ij ijijijij 2 ij 2 ij 2 ijijijij2 ijij 2 ij 2 ij ijijijij 2 ijij 2 ij 2 ij ijijijij ji 2 ji 2 2 0ii SC CxSy -t SC )CySx( )yS SC CxSy (- )xC SC CxSy (-),(inDm 0 t 0tj),i1,2,.,6,j(i, 64),(inDm . t . s )(fmin 其中 或 思考 改进后的模型 1)sinS()cosC()X(h )

13、CCC()SSS( )y)CCC(x)SSS( )S,S,C,C(Dmin )S,S,S,C,C,C(X 0)X(h ) ji ,6,.,2, 1j, i ( 064)S,S,C,C(Dmin)X(g . t . s )SC(fmin 2 0i0i , i 2 0i0i , ii 2 0j ,0i0j , j0i , i 2 0j ,0i0j , j0i , i 2 ij0j ,0i0j , j0i , iij0j ,0i0j , j0i , i 0j , j0i , i0j , j0i , i 2 60,620,210, 160,620,210, 1 i 0j , j0i , i0j , j

14、0i , i 2 ij 2 0i , i 2 0i , i 其中 思考 符号说明 -时刻t第i架飞机的坐标 -第i架飞机的方向角 -第i架飞机的方向角的调整 -时刻t第i架飞机与第j架飞机的距离 -第 i架飞机的初始位置 -飞行速度 , ii x ty t 0 i i 00 , ii xy ij r t 第一种解法的补充： v 距离的表达式: dtbta tvtv tvtv ttttt j j i i jjii ji jiij yy xx yy xxr * )sin*sin*( )cos*cos*( )()()()()( 2 2 00 2 00 22 2 2 00 2 00 00 00 2 2

15、 )()( )sin(sin*)()cos(cos*)(*2 ) 2 (*4 sin yy xx yy xx ji ji ji ji jiji ji d vb va 其中 不碰撞的条件(在区域内) t在区域内时间 满足 即为碰撞时时间 令 c=d-64 条件为: 要求仍在区域内 64)( 2 t rij 064)( 2 t rij a acbb t acb ij 2 4 04 2 2 数学模型 调整量为 使既不碰撞,调整最小 s.t. n i i 1 min 64)( 2 trij 不碰撞条件的另一种表达 )(),(),(),( , 2 4 , 04, 0)3( ; 04, 0)2( ; 0)0()