《非线性规划》PPT课件.ppt

《《非线性规划》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《非线性规划》PPT课件.ppt（56页珍藏版）》请在三一办公上搜索。

1、1,数学建模与数学实验,经济数学系数学建模研究室,非线性规划,2,实验目的,实验内容,2、掌握用数学软件求解优化问题。,1、直观了解非线性规划的基本内容。,1、非线性规划的基本理论。,4、实验作业。,2、用数学软件求解非线性规划。,3、钢管订购及运输优化模型,3,*非线性规划的基本解法,非线性规划的基本概念,非线性规划,返回,4,定义 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题,非现性规划的基本概念,一般形式:（1）其中，是定义在 En 上的实值函数，简记:,其它情况:求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式,5,

2、定义1 把满足问题（1）中条件的解 称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）记为D即 问题(1)可简记为,定义2 对于问题(1)，设，若存在,使得对一切，且，都有，则称X*是f(X)在D上的局部极小值点（局部最优解）特别地当 时，若，则称X*是f(X)在D上的严格局部极小值点（严格局部最优解）,定义3 对于问题(1),设,对任意的,都有 则称X*是f(X)在D上的全局极小值点（全局最优解）特别地当 时，若，则称X*是f(X)在D上的严格全局极小值点（严格全局最优解）,返回,6,非线性规划的最优性条件,1.等式约束问题的最优性条件：,7,2.不等式约束问题的最优性条件,8,

3、9,3、等式和不等约束问题的最优性条件,10,11,非线性规划的基本解法,SUTM外点法,SUTM内点法（障碍罚函数法）,1、罚函数法,2、近似规划法,返回,12,罚函数法,罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为序列无约束最小化方法简称为SUMT法其一为SUMT外点法，其二为SUMT内点法,13,其中T(X,M)称为罚函数，M称为罚因子，带M的项称为罚项，这里的罚函数只对不满足约束条件的点实行惩罚：当 时，满足各，故罚项=0，不受惩罚当 时，必有 的约束条件，故罚项0，要受惩罚,SUTM外点法,(3)的最优解若可行即为(

4、1)的最优解,(3)的最优解若不可行取MM使得，(3)的最优解逼近可行域。,14,罚函数法的缺点是：每个近似最优解Xk往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着Mk的增大，可能导致错误,1、任意给定初始点X0，取M11，给定允许误差，令k=1；2、求无约束极值问题 的最优解，设为Xk=X(Mk)，即；3、若存在，使，则取MkM()令k=k+1返回（2），否则，停止迭代得最优解.计算时也可将收敛性判别准则 改为.,SUTM外点法(罚函数法)的迭代步骤,15,SUTM内点法（障碍函数法）,16,内点法的迭代步骤,17,近似规

5、划法的基本思想：将问题(3)中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为(3)的解的近似,近似规划法,每得到一个近似解后，都从这点出发，重复以上步骤,这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解。,18,近似规划法的算法步骤如下,19,返回,20,用MATLAB软件求解,其输入格式如下:1.x=quadprog(H,C,A,b);2.x=quadprog(H,C,A,b,Aeq,beq);3.x=quadprog(H,

6、C,A,b,Aeq,beq,VLB,VUB);4.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0);5.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options);6.x,fval=quaprog(.);7.x,fval,exitflag=quaprog(.);8.x,fval,exitflag,output=quaprog(.);,1、二次规划,21,例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t.x1+x22-x1+2x22 x10,x20,MATLAB（youh1）,1、写成标准形式：,

7、2、输入命令：H=1-1;-1 2;c=-2;-6;A=1 1;-1 2;b=2;2;Aeq=;beq=;VLB=0;0;VUB=;x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB),3、运算结果为：x=0.6667 1.3333 z=-8.2222,s.t.,22,1.首先建立M文件fun.m,定义目标函数F（X）:function f=fun(X);f=F(X);,2、一般非线性规划,其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，基本步骤分三步：,23,3.建立主程序.非线

8、性规划求解的函数是fmincon,命令的基本格式如下：(1)x=fmincon(fun,X0,A,b)(2)x=fmincon(fun,X0,A,b,Aeq,beq)(3)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB)(4)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon)(5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options)(6)x,fval=fmincon(.)(7)x,fval,exitflag=fmincon(.)(8)x,fval,exitflag,outpu

9、t=fmincon(.),输出极值点,M文件,迭代的初值,参数说明,变量上下限,24,注意：1 fmincon函数提供了大型优化算法和中型优化算法。默认时，若在fun函数中提供了梯度（options参数的GradObj设置为on），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。2 fmincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hessian矩阵。3 fmincon函数可能会给出局部最优解，这与初值X0的选取有关。,25,1、写成标准形式：s.t.,2x1+3x2

10、6 s.t x1+4x2 5 x1,x2 0,例2,26,2、先建立M-文件 fun3.m:function f=fun3(x);f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2,MATLAB(youh2),3、再建立主程序youh2.m：x0=1;1;A=2 3;1 4;b=6;5;Aeq=;beq=;VLB=0;0;VUB=;x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB),4、运算结果为：x=0.7647 1.0588 fval=-2.0294,27,1先建立M文件 fun4.m,定义目标函数:function f=fun

11、4(x);f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,x1+x2=0 s.t.1.5+x1x2-x1-x2 0-x1x2 10 0,例3,2再建立M文件mycon.m定义非线性约束：function g,ceq=mycon(x)g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;,28,3主程序youh3.m为:x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon),MA

12、TLAB(youh3),3.运算结果为：x=-1.2250 1.2250 fval=1.8951,29,例4,1先建立M-文件fun.m定义目标函数:function f=fun(x);f=-2*x(1)-x(2);,2再建立M文件mycon2.m定义非线性约束：function g,ceq=mycon2(x)g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;,30,3.主程序fxx.m为:x0=3;2.5;VLB=0 0;VUB=5 10;x,fval,exitflag,output=fmincon(fun,x0,VLB,VUB,mycon2),MATLAB(fxx(fun),3

13、1,4.运算结果为:x=4.0000 3.0000fval=-11.0000exitflag=1output=iterations:4 funcCount:17 stepsize:1 algorithm:1x44 char firstorderopt:cgiterations:,返回,应用实例：供应与选址,某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥

14、，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？,（一）、建立模型,记工地的位置为(ai，bi)，水泥日用量为di，i=1,6;料场位置为(xj，yj)，日储量为ej，j=1,2；从料场j向工地i的运送量为Xij。,当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj。,（二）使用临时料场的情形,使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题.线性规

15、划模型为：,设X11=X1,X21=X 2,X31=X 3,X41=X 4,X51=X 5,X61=X 6X12=X 7,X22=X 8,X32=X 9,X42=X 10,X52=X 11,X62=X 12 编写程序gying1.m,MATLAB（gying1）,35,计算结果为：,x=3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000fval=136.2275,36,（三）改建两个新料场的情形,改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总

16、吨千米数最小。这是非线性规划问题。非线性规划模型为：,37,设 X11=X1,X21=X 2,X31=X 3,X41=X 4,X51=X 5,X61=X 6 X12=X 7,X22=X 8,X32=X 9,X42=X 10,X52=X 11,X62=X 12 x1=X13,y1=X14,x2=X15,y2=X16,（1）先编写M文件liaoch.m定义目标函数。,MATLAB（liaoch）,(2)取初值为线性规划的计算结果及临时料场的坐标:x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;编写主程序gying2.m.,MATLAB（gying2）,38,(3)计算结果为

17、：,x=3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867fval=105.4626exitflag=1,39,(4)若修改主程序gying2.m,取初值为上面的计算结果:x0=3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867,得结果为:x=3.0000 5.0000 0.3094 7.0000 0.0108 0.6798 0

18、0 3.6906 0 5.9892 10.3202 5.5369 4.9194 5.8291 7.2852fval=103.4760exitflag=1,总的吨千米数比上面结果略优.,(5)若再取刚得出的结果为初值,却计算不出最优解.,MATLAB（gying2）,MATLAB（gying2）,40,(6)若取初值为:x0=3 5 4 7 1 0 0 0 0 0 5 11 5.6348 4.8687 7.2479 7.7499,则计算结果为:x=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6959 4.9285 7

19、.2500 7.7500fval=89.8835exitflag=1总的吨千米数89.8835比上面结果更好.,通过此例可看出fmincon函数在选取初值上的重要性.,MATLAB（gying2）,返回,41,钢管订购及运输优化模型,2000年“网易杯”全国大学生数学建模竞赛B题,42,符号说明：,43,1、铺设总费用：,2、成本及运输总费用：,总费用=铺设总费用+成本及运输总费用=C+W,模型的分析与建立,44,建立模型,45,模型求解,利用MATLAB软件包求解得：,46,订购和运输方案表,返回,47,一个飞行管理问题 在约10,000米高空的某边长160公里的正方形区域内，经常有若干架飞

20、机作水平飞行。区域内每架飞机的位置和速度向量均由计算机记录其数据，以便进行飞行管理。当一架欲进入该区域的飞机到达区域边缘时，记录其数据后，要立即计算并判断是否会与区域内的飞机发生碰撞。如果会碰撞，则应计算如何调整各架（包括新进入的）飞机飞行的方向角。以避免碰撞。现假定条件如下：不碰撞的标准为任意两架飞机的距离大于8公里;飞机飞行方向角调整的幅度不应超过30度;所有飞机飞行速度均为每小时800公里;进入该区域的飞机在到达区域边缘时，与区域内飞机的距离应在60公里以上;最多需考虑6架飞机;不必考虑飞机离开此区域后的状况。,48,设该区域4个顶点的座标为（0,0）,(160,0),(160,160)

21、,(0,160)记录数据为：飞机编号 横座标X 纵座标Y 方向角（度）1 150 140 243 2 85 85 236 3 150 155 220.5 4 145 50 159 5 130 50 230 新进入 0 0 52注：方向角指飞行方向与X轴正向的夹角。试根据实际应用背景对你的模型进行评价与推广。,请你对这个避免碰撞的飞行管理问题建立数学模型。列出计算步骤，对以下数据进行计算（方向角误差不超过0.01度）。要求飞机飞行方向角调整的幅度尽量小。,49,符号说明：,50,51,求极小得导数为0,消去t得,52,直接搜索法求解即给出一定步长穷举，若在-10,10内以0.01为步长，计算时间为(20/0.01)6/(2.7*10(-5)s不可能。必须采用优化方法。,53,具体编程序求解有一定难度,模型的检验,模型的误差分析,54,某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货40台、60台、80台每季度的生产费用为（元），其中x是该季生产的台数若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度c元已知工厂每季度最大生产能力为100台，第一季度开始时无存货，设a=50、b=0.2、c=4，问工厂应如何安排生产计划，才能既满足合同又使总费用最低讨论a、b、c变化对计划的影响，并作出合理的解释,练习 1,55,练习 2,返回,56,谢 谢！,