数学的实践与认识 云南大学 杜强张晶谢洪波教师指导组 云南大学 肖明海冯俊田雯教ⅷ指导组 昆明师专 李红芳郭文俊李刚教师指导组 云南师范大学 孙兴平黄鹏施宏昌教师指导组 北京航空航天大学 邝富华冉晓林霍继文李卫国 北京商学院 王建军李瑾白虹黄先开 北京邮电大学 香盈波李云立林胜丁金扣 北京大学 张霖涛罗卫东丁立吴崇试 北京大学 林涛黎德元凌海滨孙山泽 清华大学 冯汉鹰诸葛丰杨小苇包维柱 清华大学 刘军宁肖狀谢峰李栓虎 上海交通大学 周吴芦烈杨荣震张建强 华东理工大学 李希明李琦王奇许三保 桂林电子工业学院 常志泉吴岭刘召卫周孝华 东南大学 丁剑张德冯南姚瑞波 东南大学 关永涛杨杉李晟孙志忠 南京航空航天大学 荀海波王冬夏顺东顾玉娣 南京航空航天大学 刘贤军金晓虎顾正晖张毅 合肥工业大学 朱明张啸郭志军杜雪樵 中国科学技术大学 孙亮贾英东张珲周智 中国科学技术大学 许锦波贾志峰朱朝阳陈发来 福州大学 陈桂阳林霖游香明林可容 1995年全国大学生数学建模竞赛各赛区 参赛院校数及队数 序号 赛区 校数 队数 江苏安徽 浙江 123456789 江西 山东 湖南 湖北 广西 四川 171 2 O1995-2004 Tsinghua Tongfang Optical Disc Co, LId. All rights reserved
© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved
第26卷(199G6)第1期 6 23 甘肃 广东 天津 河北 山西 辽宁 10 吉林 黑龙江 上海 北京 联合 合计 联合赛区包括福建、内蒙古和青海 1995年全国大学生数学建模竞赛评阅委员会名单 (排名不分先后) A题小组负责人:王强北京应用物理与计算数学研究所 成员 王荫清四川联合大学(西区)应用数学系 李煤山东工业大学数理系 胡小东中科院应用数学所运筹室 雷功炎北京大学科学与工程计算系 谭永基上海复旦大学数学系 B题小组负责人:项可凤中国科学院系统科学所 成员 朱道元南京东南大学数力系 叶其孝北京理工大学应用数学系 尹景学吉林大学数学系 刘祥官浙江大学应用数学系 林元烈清华大学应用数学系 石坚中国科学院系统科学所 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Ltd. All rights reserved
© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved
数学的实践与认识 飞行管理问题答卷评述 谭永基 (复旦大学,上海200433) 本题是以空域飞行管理为背景,经简化和整理而成的一个赛题。该问题主要可以归结 为非线性规划模型或经一定简化,建立线性规划模型。由于实际的需要,提出的箅法应在 计算机上快速地实现 非线性规划模型及求解 设六架飞机在调整时的方向角为0,调整后的方向角为0=0,+△0(=1,2,…,6), 设任意两架飞机在区域内的最短距离为d(θ,0,、),那么问题的非线性规划模型为 使得 (+△0.,0,+△0)>81≤i,j≤6,≠ 绝大多数答卷能正确逮立模型,有的答卷在建模时,出于某些考虑加强了不碰撞的要 求,如要求在调整后的0.2√2小时內不发生碰撞或永远不允许发生碰撞,从而简化了 d的表述。 求解此模型的一种方法是枚举法,但是枚举工作量极大,必须釆取逐步求精(细分) 隐式枚举、枚举和二分法相结合等技巧,方能在较短时间内求得符合精度的最优调整方 案。参赛答卷中釆用了许多提高枚举效率的措施。有的答卷在枚举时采用了 Monte-Car lo法,随机产生大量△B}组合,从其中的可行解中选出最优解。这种方法可显著提高计 算速度,有一定新意。 另一种解法是引进惩罚函数,将问题化为无约束极值,然后将其极小化。在答卷中采 用了丰富多采的无约束化和极小化技术。有的方法,如能量梯度化有一定的特色。然而 非线性规划方法能否快速找到全局最优解,十分强烈地依赖于初值的选取:有的试卷用步 长较粗的枚举得到的解作为初值然后再用极小化的方法得到最优解,计算速度很快.可 以实时调整,达到∫实用的要求 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)第1期 有不少答卷用∑△a|2,max1△|作为优化的目标,这都是合理的。 、线性规划模型 若不考虑区域的范围,用相对运动的观点不难得出两架飞机调整方向角后不发生碰 撞,调整角度应满足的条件。为简单起见,排除某些特殊的情形,条件是: ①若<,1<(5+”+0)m360<360°-a 或 ②若,>0,<(2+支)m36360-a 其中,0,D,∈[0,360°),a1= arcsin(3),,为调整时两飞机的距离,角度均以自 架飞机位置指向第j架飞机的矢量为始边计算 若以∑|△|,max|△a|作为目标函数,以上述不碰撞条件和|△a≤30作为约束 条件,是一个可归化为多个线性规划问题的规划问题。求解这一系列线性规划,比较它们 目标函数值就能得到原问题的最优解 许多答卷用类似的方法将问题归结为线性规划求解。但有不少答卷在建立不碰撞条 件时疏忽了一些情形从而条件不够完整。对某些飞机初始位置,可能产生错误 由于变量较少,线性规划求解速度较快,这是采用这一模型的优点。然而,若必须排除 在区域外的碰撞,由于条件不是线性的,归结为线性规划问题就有一定困难。有的答卷提 出了一些克服这一困难的方法。较有成效的方法有两种。一种是在△不大时将条件展 开略去高阶项,另一种用低维枚举确定△θ+△θ,的允许范围,再用线性规划求解 2 O1995-2004 Tsinghua Tongfang Optical Disc Co, LId. All rights reserved
© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved
数学的实践与认识 飞行管理问题的实时算法 谭浩南朱正光刘剑 (复旦大学,上海200433 指导教师:蔡志杰 编者按:该文以区域内飞机谲整飞行角幅度的平方和为目标数,以自调整时刻起ω.3·小· 吋內飞机两两不发生碰撞为约束祭件,建立了一个非线性规划模型,用逐步求精的直接搜索和 引入罚函数化为无约東极值用序列无约来最小化(SUMT)两种方法进行求解。 作者在建模和求解时从实际霄要出发,精益求精,将上述两种方法桕结合,得到了精度高 基本上是实时的方法与程序,还对模型与方法作出了恰当的分析与评价,文章清腑、完鳘。 摘要本文讨论了在一定区域空间内进行飞行管理避免飞机相撞的模型,提出了直 搜索法和非线性规划(SUMT)法两种解法,并将两种方法有机结合,得出的算法在486做机上 计算时间小于10秒,误差不超过0.01度,完全符合问题的要求 本文接着给出四种不同情况分别用两种方法求解,进行比较检验,取得很好的吻合,充分 说明了模型3的可靠性。本文还对模型的误差进行分析并对模型进行推广 关键词:非线性规划,直接搜索,罚函数 问题的提出(略) 二、问题的分析 该问题是一个在一定约束条件下的最优化问题,初步分析题意后可知约束条件是非 线性的,难以化归为线性规划问题。由于题目涉及数据变量不是太多,可以考虑用逐步求 精的直接搜索法求解。由于题目要求的精度较高,而对于计算时间的要求也较高,如果求 解时间在2、3分钟以上将失去任何实际意义。我们将求解时间上限定为0.5分,以符合实 际的要求。直接搜索法求的近似解难以同时满足两方面的要求。但直接搜索法至少能在 较短的时间内得到一个较好的可行解,这就为运用非线性规划的方法提供了条件。非线性 规划的算法种类繁多,但均只适用于某些类型的问题。由于缺乏适用的计算机软件包,我 们自行编写了实现算法的程序。综合程序准备时间和收敛速度两方面因素我们选择了 sUMT算法。SUTM算法与直接搜索法相结合,使我们能够在足够短的时间内找到问题 的足够精确的解。 2 01995-2004 Tsinghua Tongfang Optical Disc Co, Ltd. All rights reserved
© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved