16 数学的实践与认识 毋庯置疑的故我们可用模型二求岀满足精度要求的解来检验模型3的结果 我们对3组数据分别用模型二和模型三进行求解,结果如下 (X,Y。,an) △a( Model2) △a( Model3) 飞机1(60,100,270) 6.53 6.55 飞机2(70,100,270) 飞机3(80,100,270) 飞机4(50,100,270) 4.16 飞机5(40,100,270) 飞机6(0,40,0 第一组:为避免侧面碰撞,6架飞机都需转动较大的角度,这是较为极端的情况,偏差的平 方和较大,但没有一架飞机需调整的角度在10度以上。 △a( Model2) △a( Model3) 飞机1(60,80,180) 4.91 飞机2(60,70,180) 2.54 飞机3(60,60,180) 飞机4(60,90,180 飞机5(60,100,180) 飞机6(0,80,0) 4.17 第二组:与第一组类似:但可能发生的碰撞是正面的。 (X,Y6,a) a( Model 2) △a( Model3) 飞机 飞机2(55,5,90) 飞机3(90,60,180) 飞机4(40,130,270) 飞机5(80,5,180) 0.00 0.00 飞机6(0,60,0) 第三组:四架飞机十字交错而过,另有两架飞机水平飞行,两个模型都给出了较令人满意 的调度 各组数据吻合程度很好,且给出的调整方案也颇为符合逻辑,与一般常识相符,这说 明模型三的算法是可靠的。值得指出的是以模型二的较粗略的可行解作为模型三的输入 是非常必要的,这不但使解能快速收敛到指定精度,使计算时间符合要求,而且可用保证 所求解的全局最优性。宾州大学教授 James.P. Ignizio曾在其所著 Goal Programming and Extensions中指出“非线性最优化…不具有用于求解问题的比较初等的通用方法,更令人 失望的是非线性最优化不能保证对一个一般的问题找出整体最优解除非这个问题具有 非常特殊的形式。这意味着研究人员必须经常满足于只找出局部的最优解。事实上,即使 所采用的方法能偶然找出整体最优解,但往往也很难判别这个最优解是整体的还是局部 的。”这就指明了求一般的非线性规划问题的全局最优解目前尚无良策。如果没有模型 的输出作为模型3的输入,要找到全局最优解至少是相当困难的,时间上当然难以满足要 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Ltd. All rights reserved
© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved
第26卷(1996)第期 17 (二)误差分析 1.建模中的误差 考察模型假设可知假设9带来一定误差,简单分析后可知考虑转弯半径使飞行轨迹 在垂直飞行方向上产生一个偏差X X=(1-cos)R,其中R为转弯半径,θ为转角 对最小转弯半径小于10公里的中小型飞机,转角小于15度时偏差 X≤(1-cos15°)共10=0.34公里 对最小转弯半径约为40公里的大型飞机,转角小于8度时偏差 X≤(1-cos8°)*40=0.39公里 i种情况下偏差均小于相撞条件8公里的5%,可以忽略不计。由于飞行管理中让- 架飞机做大于8度的转向是较少发生的事(由模型1知两架距离为60公里的飞机在一条 直线上相对飞行时,也只需一架转7.66度,一架转7.67度即可避免相撞。)故该处假设可 以认为是合理的。下面给出发生极端情形时的一个对策:设一架大型飞机做30度的转弯 此时偏差ⅹ=(1-cos30°)*40=5.36公里不可忽略。在飞机开始转弯后(转弯过程约需 1.6分钟)地面控制站的计算机可算出一条曲率处处大于1/40的偏转线,以此曲线引导 飞机飞回偏转线。这种局部调整法的优点在于计算简单,不对全局的调整角度方案产生影 响,持别适用于这种小概率事件。 计算误差 模型一、二计算过程中的误差仅来源于机器的截断误差,对于最后结果没有重大影 模型三计算中的误差来源于 a、建模过程中对目标函数进行替换时。 b、用SUMT算法进行计算时 对于a我们对△a从0度到10度计算了c+s以1度为基准的相对误差,如下表所 小 偏差(度) 拟偏差 相对拟 拟偏差相 平方 偏差 对误差 3.046E-43.046E-4 12345678 1.218E-41.218E-40 2.74lE-32.741E-30 4.872E-34.874E-34.1E-4 7.61lE-37.615E-35.2E-4 1.095E-21.097E-21.8E-3 1.491E-21.493E-21.3E 1.946E 1.949E-21 2.462E-22.467E 10 3.038E-23.046E-22.6E-3 2 o1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved
© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved
18 数学的实践与认 相对误差在0.3%以下,这些表明替换函数对最后结果没有显著髟唧 对于b我们认为文献[12]3]4]中提供的算法已考虑了误差问题。在程序中实际 给出了两个误差控制是:相对精度界ε;和绝对精度界ε,当满足 x(k,j)一x11(k-1,-1)<E1x,(k,)+E 时程序结束。这保证了解的误差在精度要求以内。 3.输入误差对结果影响 通过对输入数据给以小的扰动,经大量计算可得如下定性结果 a.飞机位置有小的扰动对结果影响甚微,扰动增大时影响明显 b.飞机方向角的扰动对结果影响显著,扰动大小与结果变化幅度基本是在一个数量 以上结果说明为保证结果的准确性应尽量减小对飞机方向角测量的误差,同时对飞 机位置测量的误差也应控制在一定范围以内。 七、模型的评价及推广 (一)模型的评价 模型三是我们得到的主要结果,该模型可对区域内任意位置、方向的6架以内的飞机 给出调整对策,如果飞杋管理的计算机计算速度比486DX66快10倍左右,则可实现实时 控制。具有计算时间短、精度高的特点,实用性强,较为完满地解决了原始问题。建模过程 中用到的非线性规划方法具有一般性,容易作出推广。缺点是当飞机数目增多时,非线性 规划的规模増大了,计算时间增长较快,幸好对假设的分析表明这种情况是很少发生的。 (二)模型的推广(略) 参考文献 1.实用非线性规划,D.M. Himmelblau 2.非线性边值问题的一些解法,L.ions 线性与非线性规划引论,D.G. L,uenberger .最优设计的数学方法,程极泰 5.无约束最优化计算方法,邓乃扬 6.国际航空运输管理,顾其行 7. Goal Programming and Extensions, James. P. Ignizio 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Lid. All rights reserved
© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved
第26卷(1996)第1期 空中防撞系统的设计 黄春峰饶红玲刘伟 (中国科学技术大学,合肥230026) 指导教师:于清娟 编者按:本文用相对运动的观点建立飞机两两不桕撞的约来条件,将问題归结为一个非 线性规划问题,用惩罚函数方法化为无约柬极值问題求得最优解。罚函数选取合理,表达清 关键词:非线性规划,惩罚函数,最优解 一、符号约定 P为第i架飞机坐标;0,为第i架飞机方向角;r,为P和P间距;6为P,与 轴的夹角;ν为飞机飞行速度 二、问题的分析与求解 1.设计目标 要设计的防撞系统中,为确保飞机不相撞,应淸足如下条件 (1)安全距离要求P,|≥8 (2)飞机偏离航向不应太远,要求|0|≤30 根据上述条件及题目的要求,防撞系统的目标是达到总航向的改变最小。即 in(∑△.|)上述的条件和目标是我们建模的依据。 2.飞机相撞的判据 根据相对运动原理P相对P,的速度方向为((cos0,-cos),v(sin0.-sin0,)) t时刻P,相对P,的位置为(a,+(cos0,-cos0,),b,+t(stn0,-sin0,)) 令堆=l,则有 PP,|2=f(1)=(a+b,)+Aw、,一0 6,+ +0 a,5n2 cos +6 0<l<l 由上可知.P与P1若相撞仅有三种可能 1f(0)<64 但这与初始条件不符,故无须考虑 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Lid. All rights reserved
© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved
20· 数学的实践与认识 04--m-+m=20< 所以当f()满足(2)或(3)时,P与P相撞,否则不相撞 通过上述问题分析,可以看出这个模型的总目标就是确定每个可调的方向角,使它在 不违反判据ro(+2)28所规定的限制下,实现前述子目标因此从本质上这是 个非线性规划问题 3.非线性规划法解决问题 根据前面的分析,我们已把问题转化为求如下极值 f(0)=∑|△a 用惩罚函数法可将其作为无约束极值问题求解,也即求minh(0)=f(0)+Mc(0) M是一个很大的常数因子,c(0)在θ满足约束条件时为0,否则为正值,这样,h(0)的 极值通常只能在满足约束条件处取得,并且是f(0)的极值 取c()=cb()+cr() o,)={8-1a-2+a a-+ △0,<x/6 Cb(0,)= △0.|△1|>x/6 我们用步长加速法求极值(详见文献) 由于步长加速法求出的是局部最优解,为尽量求出全局最优解,为尽量求出全局最优 解,我们选用几组不同的初值代入,求出极小值,再从中选出最优者 取刚进入的飞机左偏1度为初始值,得出一个解为第三架飞机左偏约2.68度,第六 架飞机左偏约0.94度,总改变角为约3.629693度。即各机新方向角为243,236,223.18 159,230,52.94 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Ltd. All rights reserved
© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved