数学建模竞赛中的优化问题

1、汇报人：鲁胜强 数学建模培训讲座 - 温州医学院数学建模竞赛中优化问题-95A:飞行管理问题数学建模竞赛中的优化问题第1页一个飞行管理问题1.1 问题描述1995年全国大学生数学建模竞赛中A题（“一个飞行管理问题”）。在约10000米高空某边长为160km正方形区域内，经常有若干架飞机做水平飞行，区域内每架飞机位置和速度向量均由计算机统计其数据，方便进行飞行管理，当一架欲进入该区域飞机抵达区域边缘时，统计其数据后，要马上计算并判断是否会与区域内飞机发生碰撞。 数学建模竞赛中的优化问题第2页现假定条件以下：不碰撞标准为任意两架飞机距离大于8km；飞机飞行方向角调整幅度不应超出30；全部飞机飞行速

2、度均为800kmh；进入该区域飞机在抵达该区域边缘时，与区域内飞机距离应在60km以上；最多需考虑6架飞机；无须考虑飞机离开此区域后情况。数学建模竞赛中的优化问题第3页请你对这个防止碰撞飞行管理问题建立数学模型，列出计算步骤，对以下数据进行计算（方向角误差不超出0.01），要求飞机飞行方向角调整幅度尽可能小。该区域四个定点坐标为（0，0）、（160，0）、（160，160）、（0，160）。统计数据见表21。 数学建模竞赛中的优化问题第4页表21 飞机位置和方向角统计数据飞机编号横坐标纵坐标方向角（）飞机编号横坐标x纵坐标y方向角（）飞机编号横坐标纵坐标方向角（）飞机编号横坐标x纵坐标y方向角

3、（）115014024341455015928585236513015023031551552205新进入0052说明：方向角指飞行方向与x轴正向夹角。试依据实际应用背景对你模型进行评价和推广 数学建模竞赛中的优化问题第5页 * 对问题仔细阅读, 首先抓住题目中关键词“管理”进行联想. 抓住诸如“碰撞”、“调整”、“防止碰撞”、“马上”、“判断”等等词语. * 联络处理问题方案,不加约束继续联想，再将关键词搭配起来. 1. 问题前期分析数学建模竞赛中的优化问题第6页160km160km飞行位置示意图数学建模竞赛中的优化问题第7页马上 判断 碰撞 条件 实时 算法 防止 碰撞 调整 方向角 实时

4、 幅度尽可能小 相对距离优化问题优化算法优化调整方案数学建模竞赛中的优化问题第8页问题初步了解和想法 飞行管理问题是优化问题,在调整方向角幅度尽可能小同时，还必须注意调整方案及算法实时性.数学建模竞赛中的优化问题第9页2. 问题探究（1）优化问题目标函数为何？方向角调整尽可能小方向角怎样表示方向角概念是什么方向角平方和目标函数数学建模竞赛中的优化问题第10页任意两架飞机距离大于8 公里；飞机飞行方向角调整幅度不应超出 30 ；（2）优化问题约束条件为何？两点间距离表示方法判断防止碰撞依据把飞机视为点总结：目标函数和约束条件中都含有方向角。数学建模竞赛中的优化问题第11页（3）分析6架飞机当前碰

5、撞情况描点作图；分析飞机在飞行区域时间；判断5架飞机此刻情况；判断新进入飞机与其它5架飞机碰撞情况。数学建模竞赛中的优化问题第12页（4）求解方法特殊到普通：先考虑2架，然考虑3架优化问题为非线性规划问题，编程求解。总结：初等算法和高等算法都可。创新之处：算法。数学建模竞赛中的优化问题第13页模型一及求解模型建立这个问题显然是一个优化问题。设第i 架飞机在调整时方向角为 （题目中已给出），调整后方向为 ，题目中就是要求飞机飞行方向角调整幅度尽可能小，所以有化目标函数能够是： （1）数学建模竞赛中的优化问题第14页为了建立这个问题优化模型，只需要明确约束条件就能够了。一个简单约束是飞机飞行方向角

6、调整幅度不应超出30，即 （2） 数学建模竞赛中的优化问题第15页题目中要求进入该区域飞机在抵达该区域边缘时，与区域内飞机距离应在60km以上。这个条件是个初始条件，很轻易验证当前所给数据是满足，所以本模型中能够不予考虑。剩下关键是 要满足题目中描述任意两架位于该区域内飞机距离应该大于8km。但这个问题难点在于飞机是动态，这个约束不好直接描述，为此我们首先需要描述每架飞机飞行轨迹。数学建模竞赛中的优化问题第16页记飞机飞行速率为（800kmh），以当前时刻为0时刻。设第 架飞机在调整时位置坐标为 （已知条件），时刻位置坐标为 ，则 （3）数学建模竞赛中的优化问题第17页假如要严格表示两架位于该

7、区域内飞机距离应大于8km，则需要考虑每架飞机在区域内飞行时间长度。记Ti 为第 架飞机飞出区域时间，即 （4） 数学建模竞赛中的优化问题第18页记 时刻第 架飞机与第 架飞机距离为 ，并记 ，这时在区域内飞机不相撞约束条件就变成了 （5） 其中 （6）另外，经过计算能够得到数学建模竞赛中的优化问题第19页 （7） （8） （9） （10） 数学建模竞赛中的优化问题第20页所以 是一个关于 t 二次函数，表示是一条开口向上抛物线。当 即 （记为 ）时， 函数取最小值 。注意到 （初始时刻不相撞），假如 （即 ）则此时约束条件（5）一定成立，所以假如 且 ，只要在右端点函数值非负即可，即数学建模

8、竞赛中的优化问题第21页 （11）假如 且 ，只需要 求最小值 即可，即 （12）实际上，约束（11）表示是 在右端点函数值非负，这个约束在（12）条件下也是自然成立，所以能够是对约束（11）不再附加且条件。 数学建模竞赛中的优化问题第22页于是我们模型就是 （13） （14） （15） （16） 数学建模竞赛中的优化问题第23页模型求解上面这是一个非线性规划模型，即使是严格满足题目要求模型，但得到模型逻辑关系比较复杂，约束（16）是在一定条件下才成立约束，而且其中计算式（4）也含有相当复杂关系式，使用LINGO软件不太轻易将模型很方便输入，因为逻辑处理不是LINGO优势所在。即使想方法把这个

9、模型输入到LINGO，也不一定能求出好解（笔者尝试过，不过LINGO运行时有时会出现系统内部错误，可能是系统有问题，无法继续求解）。而且，在实时飞行调度中显然需要快速求解，所以下面我们想方法简化模型。数学建模竞赛中的优化问题第24页这个模型麻烦之处就在于，要求严格表示两架飞机飞行距离应大于8km，所以需要考虑每架飞机在区域内飞行时间长度，比较繁琐。注意到区域对角线长度只有 ，任何一架飞机在所考虑区域内停留时间不会超出 。所以这里我们简化一下问题； 数学建模竞赛中的优化问题第25页不再单独考虑每架飞机在区域内停留时间，而是以最大时间 （这是已经是一个常数）代替之，此时全部 ，这实际上强化了问题要

10、求，即考虑了有些飞机可能已经飞出区域，但仍不允许两架飞机距离小于8km。 数学建模竞赛中的优化问题第26页程序：MODEL:TITLE 飞行管理问题非线性规划模型;SETS:Plane/1.6/: x0, y0, cita0, cita1, d_cita;! cita0表示初始角度，cita1为调整后角度,d_cita为调整角度;link(plane, plane)|&1 #LT# &2: b,c;ENDSETSDATA:数学建模竞赛中的优化问题第27页1501402438585236150155220.5145501591301502300052x0 y0 cita0 =数学建模竞赛中的优化

11、问题第28页max_cita = 30;T_max = 0.283;V=800;ENDDATAINIT:d_cita = 0 0 0 0 0 0;ENDINITfor(plane: cita1 - cita0 = d_cita);for(link(i,j): b(i,j) = -2*(x0(i) -x0(j)*sin (cita1(i)+cita1(j)*3.14159265/360) +2*(y0(i) -y0(j)*cos (cita1(i)+cita1(j)*3.14159265/360); c(i,j) = (x0(i) -x0(j) 2 + (y0(i) -y0(j) 2 - 64;

12、);! 防止碰撞条件;! 右端点非负;for(link(i,j): Right 数学建模竞赛中的优化问题第29页(2*V*T_max*sin(cita1(i)-cita1(j)*3.14159265/360)2 + b(i,j)*(2*V*T_max*sin(cita1(i)-cita1(j)*3.14159265/360) + c(i,j) 0);! 最小点非负;for(link(i,j): Minimum if(b(i,j)#lt#0 #and# -b(i,j)/4/V/sin(cita1(i)-cita1(j)*3.14159265/360) #gt#0 #and# -b(i,j)/4/

13、V/sin(cita1(i)-cita1(j)*3.14159265/360) #lt#T_max , b(i,j)2-4*c(i,j),-1) 0);!for(link(i,j): if(b(i,j)#lt#0, b(i,j)2-4*c(i,j), -1) ij数学建模竞赛中的优化问题第36页(2)由圆状模型导出方程讨论ij改变量与第i第j两架飞机飞行方向角改变量i, j关系由题目条件知|vi|=A=800，可用复数表示速度设第i，j飞机飞行方向改变前速度分别为改变后速度分别为改变前后相对速度分别为二者之商幅角就是ij数学建模竞赛中的优化问题第37页定理：对第i，第j两架飞机，其相对速度方向

14、ij改变量ij等于两飞机飞行方向角改变量之和二分之一，即数学建模竞赛中的优化问题第38页模型目标函数：Min其中为各飞机方向角调整量最大值或为约束条件：调整方向角时不能超出300：调整飞行方向后飞机不能碰撞：模型为数学建模竞赛中的优化问题第39页化为线性规划模型因为i可正可负，为使各变量均非负，引入新变量：模型化为数学建模竞赛中的优化问题第40页模型求解ij计算model:sets:plane/1.6/:x0,y0;link(plane,plane):alpha,sin2;endsetsfor(link(i,j)|i#ne#j:sin2(i,j)=64/(x0(i)-x0(j)2+(y0(i)

15、-y0(j)2););for(link(i,j)|i#ne#j:(sin(alpha*3.14159265/180.0)2=sin2;);data:x0=150,85,150,145,130,0;y0=140,85,155,50,150,0;enddataend数学建模竞赛中的优化问题第41页ALPHA( 1, 1) 1.234568 ALPHA( 1, 2) 5.391190 ALPHA( 1, 3) 752.2310 ALPHA( 1, 4) 5.091816 ALPHA( 1, 5) .963 ALPHA( 1, 6) 2.234507 ALPHA( 2, 1) 5.391190 ALP

16、HA( 2, 2) 1.234568 ALPHA( 2, 3) 4.804024 ALPHA( 2, 4) 6.613460 ALPHA( 2, 5) 5.807866 ALPHA( 2, 6) 3.815925 ALPHA( 3, 1) 752.2310 ALPHA( 3, 2) 4.804024 ALPHA( 3, 3) 1.234568 ALPHA( 3, 4) 4.364672 ALPHA( 3, 5) 1102.834 ALPHA( 3, 6) 2.125539 ALPHA( 4, 1) 5.091816ALPHA( 4, 2) 6.613460 ALPHA( 4, 3) 4.364

17、672 ALPHA( 4, 4) 1.234568 ALPHA( 4, 5) 4.537692 ALPHA( 4, 6) 2.989819 ALPHA( 5, 1) .963 ALPHA( 5, 2) 5.807866 ALPHA( 5, 3) 1102.834 ALPHA( 5, 4) 4.537692 ALPHA( 5, 5) 1.234568 ALPHA( 5, 6) 2.309841 ALPHA( 6, 1) 2.234507 ALPHA( 6, 2) 3.815925 ALPHA( 6, 3) 2.125539 ALPHA( 6, 4) 2.989819 ALPHA( 6, 5) 2

18、.309841 ALPHA( 6, 6) 1.234568数学建模竞赛中的优化问题第42页ijJ=123456i=10.0000005.39119032.2309535.09181620.9633612.23450725.3911900.0000004.8040246.6134605.8078663.815925332.2309534.8040240.0000004.36467222.8336542.12553945.0918166.6134604.3646720.0000004.5376922.989819520.9633615.80786622.8336544.5376920.000000

19、2.30984162.2345073.8159252.1255392.9898192.3098410.000000整理可得ij值（单位角度）也能够用MATLAB计算ij值数学建模竞赛中的优化问题第43页x=150,85,150,145,130,0;y=140,85,155,50,150,0;k=length(x);alpha=zeros(k);for i=1:k for j=1:k if i=j alpha(i,j)=0; else alpha(i,j)=(180/3.14159265)*asin(8/sqrt(x(i)-x(j)2+(y(i)-y(j)2); end endendalpha计

20、算ij值程序为计算结果为数学建模竞赛中的优化问题第44页 0 5.391190237223 5.391190237223 032.230952672331 4.804023933797 5.091816448550 6.61346048987220.963360893128 5.807866243421 2.234506736995 3.81592477539932.230952672331 5.091816448550 4.804023933798 6.613460489872 0 4.364671899111 4.364671899111 0 22.833654204009 4.53769

21、2462402 2.125538857551 2.98981913904520.963360893128 2.234506736995 5.807866243421 3.815924775399 22.833654204009 2.125538857551 4.537692462403 2.989819139045 0 2.309841365405 2.309841365405 0ij计算:a=150,85,150,145,130,0;b=140,85,155,50,150,0;x=a+b*i;c=243,236,220.5,159,230,52*pi/180;v=exp(i*c);k=len

22、gth(a);for i=1:k for j=1:k beita(i,j)=(angle(v(i)-v(j)-angle(x(j)-x(i)*180/pi; endendbeita用matlab程序编写数学建模竞赛中的优化问题第45页beita = 0 109.2636 -128.2500 24.1798 -186.9349 14.4749 109.2636 0 -88.8711 -42.2436 -92.3048 9.0000 231.7500 271.1289 0 12.4763 301.2138 0.3108 24.1798 -42.2436 12.4763 0 5.9692 -3.52

23、56 173.0651 267.6952 -58.7862 5.9692 0 1.9144 14.4749 9.0000 0.3108 -3.5256 1.9144 0运算结果最优解计算用LINGO求解程序以下数学建模竞赛中的优化问题第46页model:sets:plane/1.6/:cita;link(plane,plane):alpha,beta;endsetsmin=sum(plane:abs(cita);for(plane(i): bnd(-30,cita(i),30); );for(link(i,j)|i#ne#j: abs(beta(i,j)+0.5*cita(i)+0.5*cit

24、a(j) alpha(i,j); );数学建模竞赛中的优化问题第47页data:alpha=0.000000,5.391190,32.230953,5.091816,20.963361,2.234507, 5.391190,0.000000,4.8040024,6.813460,5.807866,3.815925,32.230953,4.804024,0.000000,4.364672,22.833654,2.125539,5.091816,6.613460,4.363673,0.000000,4.537692,2.989819, 20.963361,5.807866,22.833654,4.

25、537692,0.000000,2.309841,2.234507,3.815925,2.125539,2.989819,2.309841,0.000000; beta=0.000000 109.263642 -128.250000 24.179830 173.065051 13.474934109.263642 0.000000 -88.871096 -42.243563 -92.304847 9.000000-128.250000 -88.87096 0.000000 12.476311 -58.786243 0.31080924.179830 -42.243563 12.476311 0

26、.000000 5.969234 -3.525606174.065051 -92.304846 -58.786244 5.969234 0.000000 1.91438314.474934 9.000000 0.310809 -3.525606 1.913383 0.000000;enddataend用MATLAB计算编程以下数学建模竞赛中的优化问题第48页function f,g=plane(x)alph=0.000000,5.391190,32.230953,5.091816,20.963361,2.234507,5.391190,0.000000,4.8040024,6.813460,5

27、.807866,3.815925,32.230953,4.804024,0.000000,4.364672,22.833654,2.125539,5.091816,6.613460,4.363673,0.000000,4.537692,2.989819,20.963361,5.807866,22.833654,4.537692,0.000000,2.309841,2.234507,3.815925,2.125539,2.989819,2.309841,0.000000; bet=0.000000 109.263642 -128.250000 24.179830 173.065051 13.47

28、4934109.263642 0.000000 -88.871096 -42.243563 -92.304847 9.000000-128.250000 -88.87096 0.000000 12.476311 -58.786243 0.31080924.179830 -42.243563 12.476311 0.000000 5.969234 -3.525606174.065051 -92.304846 -58.786244 5.969234 0.000000 1.91438314.474934 9.000000 0.310809 -3.525606 1.913383 0.000000;f=

29、abs(x(1)+abs(x(2)+abs(x(3)+abs(x(4)+abs(x(5)+abs(x(6);g(1)= alpha(1,2) -abs(beta(1,2)+0.5*x(1)+0.5*x(2);g(2)= alpha(1,3) -abs(beta(1,3)+0.5*x(1)+0.5*x(3);g(3)= alpha(1,4) -abs(beta(1,4)+0.5*x(1)+0.5*x(4);g(4)= alpha(1,5) -abs(beta(1,5)+0.5*x(1)+0.5*x(5);数学建模竞赛中的优化问题第49页g(5)= alpha(1,6) -abs(beta(1,6

30、)+0.5*x(1)+0.5*x(6);g(6)= alpha(2,3) -abs(beta(2,3)+0.5*x(2)+0.5*x(3);g(7)= alpha(2,4) -abs(beta(2,4)+0.5*x(2)+0.5*x(4);g(8)= alpha(2,5) -abs(beta(2,5)+0.5*x(2)+0.5*x(5);g(9)= alpha(2,6) -abs(beta(2,6)+0.5*x(2)+0.5*x(6);g(10)= alpha(3,4) -abs(beta(3,4)+0.5*x(3)+0.5*x(4);g(11)= alpha(3,5) -abs(beta(3

31、,5)+0.5*x(3)+0.5*x(5);g(12)= alpha(3,6) -abs(beta(3,6)+0.5*x(3)+0.5*x(6);g(13)= alpha(4,5) -abs(beta(4,5)+0.5*x(4)+0.5*x(5);g(14)= alpha(4,6) -abs(beta(4,6)+0.5*x(4)+0.5*x(6);g(15)= alpha(5,6) -abs(beta(5,6)+0.5*x(5)+0.5*x(6);执行程序x0=0,0,0,0,0,0; v1=-30*ones(1,6); v2=30*ones(1,6);opt=;x= constr(plane

32、,x0,opt,v1,v2)数学建模竞赛中的优化问题第50页结果：x = -0.00000576637983 -0.00000576637983 2.58794980234726 -0.00001243487985 0.00003620473095 1.04151019765274最优解：数学建模竞赛中的优化问题第51页模型检验各飞行方向按此方案调整后，系统各架飞机均满足|ij+( I+ j)/2|ij ,结果是正确。模型评价与推广（1）此模型采取圆状模型分析碰撞问题是合理，同时采取相对速度作为判别标准，既表达了碰撞本质（相对运动），又简化了模型计算；（2）建模中用了适当简化，将一个复杂非线性

33、规划问题简化为线性规划问题，既求到合理解，又提升了运算速度，这对处理高速飞行飞机碰撞问题是十分主要。此模型对题目所提供例子计算得出结果是令人满意。（3）由对称性知模型中约束个数是 （n是飞机数），全部约束条件数是 ，计算量增加不大。数学建模竞赛中的优化问题第52页建模方案二：1.问题分析目标：不碰撞伎俩：调整飞行方向角要求：调整幅度尽可能小求解思绪：(1) 找出不碰撞条件,可用matlab画出各架飞机在t=0时刻位置和飞行方向(2)求调整幅度极小值 数学建模竞赛中的优化问题第53页题目标条件(1) 飞机在正方形区域内水平飞行。 依据 (1)可将飞机飞行空域视为二维平面xoy中一个正方形区域,顶点为(0,0),(160,0),(160,160),(0,160)。 依据 (1)可将飞机飞行空域视为二维平面xoy中一个正方形区域,顶点