数模非线性规划模型

1、数学模型电子教案,重庆邮电大学,数理学院,沈世云,1,第四章,非线性规划,一、非线性规划引例,线性规划和整数规划它们的目标函数和约束条件都是,自变量的线性函数，在实际中还有大量的问题,其目标函数或约束条件很难用线性函数来表示,如果目标函数或约束条件中含有非线性函数,则称这种规划问题为非线性规划问题。先看两个实例,问题,1,容器设计问题,问题提出,某公司生产贮藏用容器，订货合同要求该公司制造,一种敞口的长方体容器，容积为,12,立方米，该容器的底为正方形,容器总重量不超过,68,公斤。已知用作容器四壁的材料为,每平方米,10,元，重,3,公斤；用作容器底的材料每平方米,20,元,重,2,公斤。试

2、问制造该容器所需的最小费用是多少,2,模型建立,设该容器的底边长和高分别为,x,1,x,2,则问题的数学模型为,m,f,in,X,40,x,x,20,x,1,2,x,1,x,2,12,2,12,x,1,x,2,2,x,1,68,x,x,0,1,2,3,2,1,2,问题,2,营业计划的制定,问题提出,某公司经营两种设备，第一种设备每件,售价,30,元，第二种设备每件售价,450,元。据统计,售出一件第一种设备所需要的营业时间平均是,0.5,小,时，第二种设备是,2,0,25,x,2,小时，其中,x,2,是第二,种设备的售出数量,已知该公司在这段时间内的总营,业时间为,800,小时,试决定使其营业

3、额最大的营业计,划,模型建立,设该公司计划经营第一种设备,x,件，第,二种设备,x,件。其数学模型为,m,ax,f,X,30,x,1,450,x,2,1,2,0,5,x,1,2,0,25,x,2,x,2,800,s,t,x,1,x,2,0,4,二,非现性规划的基本概念,定义,如果目标函数或约束条件中至少有一个是非线性函数,时的最优化问题就叫做非线性规划问题,一般形式,mi,f,n,X,1,T,n,f,g,h,n,上的实值函,x,x,x,E,其中,X,是定义在,E,i,j,1,2,n,n,1,n,1,n,1,f,E,E,g,E,E,h,E,E,数，简记,i,j,其它情况,求目标函数的最大值或约束

4、条件为小于等于零,的情况，都可通过取其相反数化为上述一般形式,g,X,0,i,1,2,m,i,s,t,h,X,0,j,1,2,l,j,5,定义,1,把满足问题,1,中条件的解,X,E,n,称为,可行解,或可,行,点,，所有可行点的集合称为,可行集,或,可行域,记为,n,min,f,X,D,即,D,X,g,X,0,h,X,0,X,E,i,j,X,D,问题,1,可简记,定义,1,设,X,D,若存在,0,使得对一切,为,2,对于问题,是,f(X,在,D,上的,X,X,且,都有,则称,X,X,D,f,X,f,X,局部极小值点,局部最优解,特别地当,X,X,时,f,X,f,X,若,则称,X,是,f(X,

5、在,D,上的,严格局部极小值点,严格局,部最优解,定义,3,对于问题,1,设,X,D,对任意的,X,D,都有,f,X,f,X,则称,X,是,f(X,在,D,上的,全局极小值点,全局最优解,特别地当,是,f(X,在,D,上的,严格全局极小值,时，若,则称,X,X,X,f,X,f,X,点,严格全局最优解,6,非现性规划的基本概念,定义,如果目标函数或约束条件中至少有一个是非线性函数,时的最优化问题就叫做非线性规划问题,一般形式,mi,f,n,X,1,T,n,f,g,h,n,上的实值函,x,x,x,E,其中,X,是定义在,E,i,j,1,2,n,n,1,n,1,n,1,E,E,g,E,E,h,E,E

6、,数，简记,f,i,j,其它情况,求目标函数的最大值或约束条件为小于等于零,的情况，都可通过取其相反数化为上述一般形式,g,X,0,i,1,2,m,i,s,t,h,X,0,j,1,2,l,j,7,定义,1,把满足问题,1,中条件的解,X,E,n,称为,可行解,或可,行,点,，所有可行点的集合称为,可行集,或,可行域,记为,n,min,f,X,D,即,D,X,g,X,0,h,X,0,X,E,i,j,X,D,问题,1,可简记,定义,1,设,X,D,若存在,0,使得对一切,为,2,对于问题,是,f(X,在,D,上的,X,X,且,都有,则称,X,X,D,f,X,f,X,局部极小值点（局部最优解）特别地

7、当,X,X,时,f,X,f,X,若,则称,X,是,f(X,在,D,上的严格局部极小值点（严格局,部最优解,定义,3,对于问题,1,设,X,D,对任意的,X,D,都有,f,X,f,X,则称,X,是,f(X,在,D,上的全局极小值点（全局最优解）特别地当,是,f(X,在,D,上的严格全局极小值,时，若,则称,X,X,X,f,X,f,X,点（严格全局最优解,8,三,非线性规划的图解法,用图解法求解下面的非,线性规划问题,2,2,min,f,x,1,x,2,x,1,x,2,s,t,1,x,1,x,2,0,x,1,1,0,x,1,0,2,9,三角形表示的是可行域,同心圆表示的是目标函数的等值,线,最优解

8、为,1/2,1/2,1/2,1/2,最优值为,1/2,问题,1/2,1/2,是整体的还是局部的？是严格的还是非,严格的,10,2,非线性规划方法概述,微分学方法的局限性,实际的问题中，函数可能是不连续或者不可微的,需要解复杂的方程组，而方程组到目前仍没有有,效的算法,实际的问题可能含有不等式约束，微分学方法不,易处理,11,数值方法的基本思路,迭代,给定初始点,x,0,根据,x,0,依次迭代产生点列,x,k,x,k,有限,x,k,无限,x,k,的最后一点为最优解,x,k,收敛于最优解,12,迭代格式,x,k,pk,x,k+1,x,k,x,x,x,k,1,k,k,x,t,k,p,k,1,k,k,

9、k,x,x,x,k,称,p,k,为第,k,轮,搜索方向,t,k,为第,k,轮沿,p,k,方向的,步长,产生,t,k,和,p,k,的不同方法，形成了不同的算法,13,定义：下降方向,n,1,n,n,设,f,R,R,x,R,p,R,p,0,若存在,0,使,f,x,tp,f,x,t,0,则称向量,p,是函数,f,x,在点,x,处的下降方向,若,f,x,在,x,可导，则,f,x,就是,f,x,在,x,处下降最快的方向,14,定义,设,X,R,x,X,p,R,p,0,若存在,t,0,使,x,tp,X,n,n,则称向量,p,是点,x,处,关于,X,的可行方向,解非线性规划问题，关键在于,找到某个方向，使得

10、在此方向,上，目标函数得到下降，同时,还是可行方向,这样的方向称为可行下降方向,15,第二节,凸函数和凸规划,1,凸函数及其性质,定义,n,1,设,S,R,是非空凸集,f,S,R,若对,0,1,fX,1,X,f,X,1,f,X,X,S,1,2,1,2,1,X,2,S,1,2,1,2,则称,f,是,S,上的凸函数，或,f,在,S,上是凸,若,f,x,1,xf,x,1,f,x,x,x,S,1,2,则称,f,是,S,上的严格凸函数，或,f,在,S,上是严格,若,f,是,S,上的,严格,凸函数，称,f,是,S,上的,严格,凹函数,或,f,在,S,上是,严格,凹的,16,关于凸函数的一些结论,定理,设,

11、S,R,是非空凸集,n,1,若,f,是,S,上的凸函数,0,则,f,是,S,上的凸,n,1,2,若,f,f,是,S,上的凸函数,f,f,是,S,上的凸,1,2,1,2,定理,设,S,R,是非空凸集,f,是凸函数,c,R,则集,H,f,c,x,S,f,x,c,是凸集,S,函数,f,在集合,S,上关于,c,的水平集,17,定理,设,S,R,是非空开凸集,f,S,R,可微,则,n,1,1,f,是,S,上的凸函数的充分必要,条件是,f,x,x,x,f,x,f,x,x,x,S,1,1,1,1,T,2,1,2,1,1,2,f,x,f,x,T,1,f,x,是函数在点,x,处的梯,x,x,1,n,2,f,是,

12、S,上的严格凸函数的充要,条件是,1,T,2,1,2,f,x,x,x,f,x,f,x,x,x,S,x,x,n=1,时几何意义：可微函数是凸的等价于切线不在函数图,像上方,18,1,1,2,1,2,S,R,是非空开凸集,f,S,R,二阶连续可导,定理,设,则,f,是,S,上的凸函数的充要条件,是,f,x,在,S,上是半正定的,当,f,x,在,S,上是正定矩阵时,f,是,S,上的严格,凸函数（此时,逆命题不成立,2,2,n,1,f,x,称为,Hesse,矩阵,f,x,f,x,x,x,x,1,x,n,1,1,2,f,x,2,2,f,x,f,x,x,x,x,n,x,n,n,1,19,2,2,2,2,凸

13、规划及其性质,凸规划定义,min,f,x,g,0,i,1,p,s,t,i,x,h,0,j,1,q,j,x,g,0,i,1,p,n,i,x,X,x,R,h,x,0,j,1,q,j,简称凸规划,若,X,是凸集,f,是,S,上的凸函数,称,MP,为非线性,20,凸规划性质,定理,线,性,函,数,对于非线性规划,MP,min,f,x,0,i,1,p,s,t,g,i,x,h,0,j,1,q,j,x,n,凸函数,若,g,i,x,皆为,R,上的凸函数,h,j,x,皆为线性函数,并且,f,是,X,上的凸函数，则,MP,是凸规划,定理,凸规划的任一局部最优解都是它的整体最优解,凸规划是以后重点讨论的一类非线性规

14、划,21,第三节,一维搜索方法,什么叫一维搜索问题,一维搜索问题指目标函数为单变量的非线性规划问题,又称线性搜索问题。其模型为,min,t,或,t,0,0,t,t,m,ax,min,t,t,为实数,一般一维搜索问题,有效一维搜索问题,22,一维搜索问题的算法分类,精确一维搜索（最优一维搜索,非精确一维搜索（可接受一维搜索,本节内容,两种精确一维搜索方法,0.618,法,Newton,法,两种非精确一维搜索方法,Goldstein,法,Armijo,法,23,1,0.618,法（近似黄金分割法,单谷函数,如果,t,a,b,使得函数,t,在,a,t,上严格递减,且在,t,b,上严格递增,称,t,为

15、,a,b,上的单谷,a,b,称为,t,的单谷区间,显然此时,t,为,t,在,a,b,上唯一的极,问题,凸函数是不是单谷函数？严格凸函数是不,是单谷函数？单谷函数是不是凸函数,24,搜索法求解,min,t,或,t,0,0,t,t,m,ax,min,t,基本过程,给出,a,b,使得,t,在,a,b,中,a,b,称为,搜索区间,迭代缩短,a,b,的长度,当,a,b,的长度小于某个预设的值，或者导数的绝,对值小于某个预设的正数，则迭代终止,25,假定：已经确定了单谷区间,a,b,min,t,t,0,0,t,t,m,ax,min,t,a,t,b,min,t,t,1,a,t,1,t,2,t,1,t,2,t

16、,2,b,a,t,1,t,2,b,t,t,新搜索区间为,a,t,2,新搜索区间为,t,1,b,26,区间缩小比例的确定,t,1,a,t,1,t,2,t,1,t,2,t,2,b,a,t,1,t,2,b,区间缩短比例为,t,2,a)/(b-a,缩短比例,满足,缩短比例为,b-t,1,(b-a,每次插入搜索点使得两个区间,a,t,2,和,t,1,b,相等,每次迭代都以相等的比例缩小区间,5,1,缩短比例,0,618,2,0.618,法,前一页,后一页,退,27,出,0.618,法解题步骤,确定,a,b,计算探索点,t,1,a+0.382(b-a,t,2,a+0.618(b-a,t,t,1,2,否,是

17、,否,以,t,1,b,为新的搜索区间,停止，输出,t,2,t,2,a,是,停止，输出,t,1,否,b,t,1,是,以,a,t,2,为新的搜索区间,28,求解,min,t,t,2,t,1,例,3,t,0,其中单谷区间,0,3,精度,0,5,解,1,第一轮,t,1,1.146, t,2,1.854,t,2,t,1,0,t,1,t,2,3,t,t,1,0,2131,t,2,3,6648,t,2,00.5,29,2,第二轮,t,2,1.146, t,1,0.708,t,1,0,0611,t,2,0,2131,t,2,0=1.1460.5,t,1,0,3,第三轮,t,1,0.438, t,2,0.708

18、,t,2,1.854,t,t,2,0,0611,t,1,0,2082,b-t,1,1.146-0.4380.5,0,t,1,t,2,1.416,t,30,4,第四轮,t,2,0.876, t,1,0.708,t,1,0,0611,t,2,0,0798,b-t,1,1.146-0.7080.5,t,1,t,2,0,1.416,t,输出,t,t,2,0.876,为最优解，最优值为,0.0798,31,2,Newton,法,Newton,法基本思想,用探索点,t,k,处的二阶,Taylor,展开式近似代替目标,函数，以展开式的最小点为新的探索点,考虑,min,t,其中,t,二次可微,t,0,1,2,

19、展开式,g,t,t,t,t,t,t,t,t,k,k,k,k,k,2,g,t,的最小点即导数为,0,的点,求导得,t,k,t,k,t,k,1,t,k,32,解题步骤,给定初始点,t,1,和精度,否,停止，输出,t,2,是,t,1,是,停止，输出,t,1,否,t,2,t,1,t,0,1,是,否,t,1,计算,t,2,t,1,t,1,停止，解题失败,33,例,解,求解,min,t,arctan,xdx,0,t,取,t,1,1,计算,迭代过程如下表,1,t,arctan,t,t,2,1,t,k,t,k,t,k,t,k,1,2,3,4,1,0.7854,2,0.5708,0.5178,1.3258,0.

20、1169,0.1163,1.137,0.001061,前一页,后一页,退,34,出,3,非精确一维搜索法,数值方法的关键是从一个点迭代到下一个点,确定下一个点的关键是确定搜索方向和步长,如果已经确定了搜索方向,p,k,则只要确定一个最佳,的步长即可,所谓的最佳步长即是在,p,k,方向上走一个最好的长,度使得目标函数下降的最多，即下述的最优化问题,min,f,x,tp,t,0,k,k,这样的最优化问题不需要太高的精度，只要满,足某些更宽松的精度要求即可,这样的搜索方法称之为,非精确一维搜索方法,35,Goldstein,法原理,y,y,t,Y,0),0)t,Y,0)+ m,1,0)t,0,a,b

21、,c,d,t,Y,0)+ m,2,0)t,选取,t,k,使得,t,k,在上面的直线的下方,同时保证,t,k,在下面的直线上方,t,a,b,c,d,k,36,Goldstein,算法,确定,m,1,m,2,t,0,a=0,b,t,0,0)+m,是,1,0)t,0,否,a=a, b=t,0,t,1,(a+b)/2,t,0,0)+m,2,0)t,0,否,是,停止,输出,t,0,a=t,0,b=b, t,1,(a+b)/2,若,b,则,t,1,a,前一页,后一页,退,37,出,Armijo,法原理,y,y,t,t,k,0,t,k,Mt,k,Mt,k,t,选取,t,k,使得,t,k,在直线的下方,同时保

22、证,Mt,在直线上方,k,前一页,后一页,退,38,出,第四节,无约束最优化方法,本节课讨论,n,元函数的无约束非线性规划问题,T,n,min,f,x,其中,x,x,x,x,R,1,2,n,求解此类模型,UMP,的方法称为,无约束最优化方法,无约束最优化方法通常有两类,解析法,要使用导数的方法,直接法,无须考虑函数是否可导，直接使用函数值,39,1,无约束问题的最优性条件,若存在,p,R,使,f,R,R,在点,x,R,处可微,定理,1,设,n,n,n,f,x,p,0,n,T,则向量,p,是,f,在点,x,处的下降方向,f,在点,x,R,可微,若,定理,2,设,x,是,min,f,x,的局部最优

23、,则,f,x,0,注,梯度为,0,的点称为函数的,驻点,驻点可能是极小点，也可能是极大点，也可能即不是极大,也不是极小，这时称为函数的,鞍点,定理,2,说明,UMP,问题的局部最优解必是目标函数的驻点,前一页,后一页,退,40,出,f,在点,x,R,处的,Hesse,矩阵,f,x,存在,定理,3,设,n,2,若,f,x,0,并且,f,x,正,则,x,是,min,f,x,的严格局部最,2,f,R,R,x,R,f,是,R,上的可微,定理,4,设,n,1,n,n,若,f,x,0,则,则,x,是,min,f,x,的整体最优,课下练习,画图理解定理,1,2,4,的几何意义,前一页,后一页,退,41,出,

24、无约束优化问题的基本算法,1,最速下降法（共轭梯度法）算法步骤,0,n,X,E,0,给,定,初,始,点,允,许,误,差,令,k,0,f,X,计,算,检,验,是,否,满,足,收,敛,性,的,判,别,准,则,k,f,X,k,k,X,X,若,满,足,则,停,止,迭,代,得,点,否,则,进,行,k,k,k,k,S,S,f,X,X,出,令,从,发,沿,进,行,一,维,搜,索,k,k,k,k,min,f,X,S,f,X,即,求,得,k,S,k,使,0,k,X,X,令,k,k,1,返,回,k,S,最速下降法是一种最基本的算法，它在最优化方法中占有重要地位,最,速下降法的优点是工作量小，存储变量较少,初始点要

25、求不高；缺点是收,敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极,值点时，宜选用别种收敛快的算法,42,k,1,k,2,牛顿法算法步骤,X,E,0,1,选,定,初,始,点,给,定,允,许,误,差,令,k,0,0,n,f,X,2,求,检,验,若,则,f,X,f,X,k,2,1,k,k,X,X,停,止,迭,代,否,则,转,向,3,k,2,k,1,k,S,f,X,f,X,3,令,牛,顿,方,向,k,k,k,1,X,X,S,4,转,回,2,k,1,k,k,如果,f,是对称正定矩阵,A,的二次函数，则用牛顿法经过一次迭代,就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点,但由

26、于这种函数在极值点附近和二次函数很近似,因此牛顿法的收,敛速度还是很快的,牛顿法的收敛速度虽然较快，但要求,Hessian,矩阵要可逆,要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量,43,3,拟牛顿法,为克服牛顿法的缺点，同时保持较快收敛速度的优点，利用第,k,步,和第,k+1,步得到的,X,X,k,1,2,k,k,1,k,f,X,f,X,k,1,k,k,1,构造一个正定,2,k,1,矩阵,G,近似代替,f,X,或用,H,近似代替,f,X,将,牛顿方向改为,k,1,k,1,k,1,k,1,k,1,k,1,f,X,G,S,f,X,S,H,从而得到下降方向,44,用,Matlab,解无约束

27、优化问题,1,一,元,函,数,无,约,束,优,化,问,题,x,x,x,1,2,常用格式如下,1,x= fminbnd,fun,x,1,x,2,2,x= fminbnd,fun,x,1,x,2,options,3,x,fval= fminbnd,4,x,fval,exitflag= fminbnd,5,x,fval,exitflag,output= fminbnd,m,i,n,f,x,其中,3,4,5,的等式右边可选用,1,或,2,的等式右边,函数,fminbnd,的算法基于黄金分割法和二次插值法，它,要求目标函数必须是连续函数，并可能只给出局部最优解,45,例,1,求,f,2,在,0,x,8,

28、中,的,最,小,值,与,最,大,值,e,sin,x,主程序为,f,2*exp(-x).*sin(x,fplot(f,0,8,作图语句,xmin,ymin=fminbnd (f, 0,8,f1,2*exp(-x).*sin(x,xmax,ymax=fminbnd (f1, 0,8,x,运,行,结,果,x,m,i,n,3,9,2,7,0,y,m,i,n,0,0,2,7,9,x,m,a,x,0,7,8,5,4,y,m,a,x,0,6,4,4,8,46,例,2,对边长为,3,米的正方形铁板，在四个角剪去相等的正方形以,制成方形无盖水槽，问如何剪法使水槽的容积最大,p156,例,8-1,解,设剪去的正方

29、形的边长为,x,则水槽的容积为,3,2,x,x,建立无约束优化模型为,min y,3,2,x,x,0 x1.5,2,2,先编写,M,文件,fminbndtest.m,如下,function f=myfun(x,f,3-2*x).2*x,主程序调用,fminbnd,x,fval=fminbnd,fminbndtest,0,1.5,xmax=x,fmax=-fval,运算结果为,xmax = 0.5000,fmax =2.0000,即剪掉的正方形的,边长为,0.5,米时水槽的容积最大,最大容积为,2,立方米,47,2,多元函数无约束优化问题,标准型为,min,F(X,命令格式为,1,x= fmin

30、unc,fun,X,0,；或,x=fminsearch,fun,X,0,2,x= fminunc,fun,X,0,options,或,x=fminsearch,fun,X,0,options,3,x,fval= fminunc,或,x,fval= fminsearch,4,x,fval,exitflag= fminunc,或,x,fval,exitflag= fminsearch,5,x,fval,exitflag,output= fminunc,或,x,fval,exitflag,output= fminsearch,48,说明,fminsearch,是用单纯形法寻优,fminunc,的算法

31、见以下几点说明,1 fminunc,为无约束优化提供了大型优化和中型优化算法,由,options,中的参数,LargeScale,控制,LargeScale=on(默认值,使用大型算法,LargeScale=off(默认值,使用中型算法,2 fminunc,为中型优化算法的搜索方向提供了,4,种算法，由,options,中的参数,HessUpdate,控制,HessUpdate=bfgs（默认值），拟牛顿法的,BFGS,公,式,HessUpdate=dfp，拟牛顿法的,DFP,公式,HessUpdate=steepdesc，最速下降法,3 fminunc,为中型优化算法的步长一维搜索提供了两种

32、算法,由,options,中参数,LineSearchType,控制,LineSearchType=quadcubic(缺省值,混合的二次和,三,次多项式插值,使用,fminunc,和,fminsearch,可能会得到局部最优解,LineSearchType=cubicpoly，三次多项式插,49,2,2,例,3,min f(x)=(4x,1,2x,2,4x,1,x,2,2x,2,1)*exp(x,1,1,编写,M,文件,fun1.m,function f = fun1 (x,f = exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1,2,输入,M,文

33、件,myprg3.m,如下,x,0,-1, 1,x=fminunc,fun1,x,0,y=fun1(x,3,运行结果,x= 0.5000 -1.0000,y = 1.3029e-10,50,第五节,约束最优化方法,本节课讨论约束非线性规划问题,MP,min,f,x,g,i,x,0,i,1,p,s,t,h,j,x,0,j,1,q,其中,x=(x,1,x,2,x,n,T,f(x),g,i,x),h,j,x,为,x,的实值函数,求解此类模型,MP,的方法称为,约束最优化方法,51,1,约束最优化问题的最优性条件,f,x,对于,MP,问题,min,g,i,x,0,i,1,p,s,t,h,j,x,0,j

34、,1,q,g,x,0,i,1,p,n,i,设,x,X,x,R,h,x,0,j,1,q,i,则,g,x,0,i,1,p,h,x,0,j,1,q,i,j,52,g,x,0,i,1,p,有两种,i,1,g,x,0,若,x,有变化，则约束条件可能没有破坏,i,2,g,x,0,若,x,有变化，则约束条件一定被破坏,i,使,g,x,0,的约束条件,g,x,0,称为,x,的积,i,i,令,J,表示,MP,的全部等式约束的下标集合，即,J=1,2q,I,表示,MP,的全部不等式约束的下标集合，即,I=1,2p,记,I,x,i,g,x,0,i,I,i,x,的积极约束的下标集合,53,定理,1,min,f,x,g

35、,i,x,0,i,1,p,对于,s,t,h,j,x,0,j,1,q,i,I,x,在,x,处可微,1,g,i,x,I,I,x,在,x,处连续,i,2,h,j,x,j,J,在,x,处连续可微,3,g,i,x,i,I,x,h,j,x,j,J,线性无关,若,x,是局部最优解,则,两组实数,i,I,x,j,J,使,i,j,0,i,I,x,i,f,x,g,h,0,i,i,x,j,j,x,j,J,i,I,x,54,定理,1,的说明,1,g,x,i,I,x,h,x,j,J,线性无关,称为约束,i,j,2,称下述表达式为,MP,的,Kuhn-Tucker,条件，简称,K-T,条件,0,i,I,x,i,f,x,g

36、,h,0,i,i,x,j,j,x,j,J,i,I,x,满足,K-T,条件的点称为,MP,的,K-T,点，定理,1,说明,MP,的局部最,优解一定是,MP,的,K-T,点,为了求出,MP,的最优解，可以先找出,MP,的,K-T,点，再做进一,步的判断,55,min,f,x,1,x,2,x,1,1,2,x,2,2,2,s,t,g,x,x,x,2,0,1,1,2,3,定理,1,的实例说明,g,2,x,x,1,0,g,x,x,0,3,2,h,x,x,x,1,0,1,1,2,定理,1,表明：若,x,1,x,2,T,是局部最优解,g,1,和,g,2,为积极约束，则,0,i,I,x,i,f,x,g,h,0,

37、i,i,x,j,j,x,j,J,i,I,x,2,x,1,1,1,1,1,0,1,2,1,2,x,1,1,0,1,2,0,1,2,56,4,定理,1,的特例,1,min,f,x,对于,若,x,是其局部最优,s,t,g,0,i,x,f,x,实数,i,I,x,使得,i,i,I,x,0,i,I,x,i,g,i,i,x,0,f,x,i,g,0,i,x,i,i,I,x,57,5,定理,1,的特例,2,min,f,x,对于,若,x,是局部最优,s,t,h,x,0,j,f,x,j,h,0,J,使得,j,x,j,j,j,J,h,j,j,x,f,x,j,J,若,x,局部最优解,则,f,x,落在由向量,h,x,j,

38、J,j,生成的空间中,58,min,f,x,g,i,x,0,i,1,p,6,定理,1,的改进,对于,s,t,h,j,x,0,j,1,q,1,g,i,I,在,x,处可微,i,x,2,h,j,J,在,x,处连续可微,j,x,3,g,i,I,x,h,j,J,线性无,i,x,j,x,若,x,是局部最优解,则,两组实数,i,I,j,j,J,使得,i,f,x,g,h,0,i,i,x,j,j,x,i,I,j,J,0,i,I,i,g,i,x,0,i,I,i,互补松紧条件,59,min,f,x,1,x,2,x,1,1,2,x,2,2,2,s,t,g,x,x,x,2,0,1,1,2,7,实例说明改,g,2,x,x

39、,1,0,进后的定理,1,g,x,x,0,3,2,h,x,x,x,1,0,1,1,2,定理,1,改进后表明：若,x,1,x,2,T,是局部最优解，则,f,x,i,I,0,i,I,i,g,i,x,0,i,I,i,g,i,i,x,j,J,h,j,j,x,0,60,2,x,1,1,1,1,0,1,2,x,1,1,1,2,0,3,1,1,1,0,2,1,x,1,x,2,2,0,2,x,1,0,x,0,2,3,1,2,3,0,互补松紧条件,61,min,f,x,g,i,x,0,i,1,p,定理,2,对于,s,t,h,j,x,0,j,1,q,1,f,g,h,x,处连续可,i,j,在,2,可行点在,x,处满

40、足,K,T,条件,3,f,g,i,I,x,是凸函数,h,是线性函,i,j,则,x,是,MP,问题的整体最优,注：定理,2,表明，在凸性条件下,K-T,点是整体最优解,62,例,写出,K-T,条件,求出相应的,K-T,点,判断,K-T,点是不是,问题的最优解,min,f,x,1,x,2,x,1,1,2,x,2,2,2,s,t,g,x,x,x,2,0,1,1,2,g,2,x,x,1,0,g,x,x,0,3,2,h,x,x,x,1,0,1,1,2,解,由于全部函数都是连续可微的，所以应用以下,K-T,条件,f,x,g,j,h,0,i,i,x,j,x,i,I,j,J,0,i,I,i,g,i,x,0,i

41、,I,i,63,首先写出原,MP,问题的,K-T,条件,2,x,1,1,1,2,1,0,2,x,2,0,2,1,3,1,1,x,1,x,2,2,0,x,0,2,1,互补松紧条件,3,x,2,0,1,2,3,0,根据定理,1,K-T,点还应该满足原问题的约束条件,x,1,x,2,2,0,x,1,0,x,2,0,x,x,1,0,1,2,64,利用互补松紧条件，可以求出,K-T,点,1,3,T,x,2,2,利用定理,2,由于全部函数都连续可微，并且,f,和,g,都是凸函数,h,是线性函数，所以,K-T,点就是整体最,优解,65,2,惩罚函数法,惩罚函数法的基本思想：利用原问题的中的约,束函数构造适当

42、的惩罚函数，并和原问题的目标,函数相加，得到带参数的增广目标函数，从而将,原问题题转换为一系列无约束非线性规划问题,惩罚函数法的分类：罚函数法（外部惩罚法,障碍函数法（内部惩罚法,66,1,罚函数法,罚函数法基本原理,min,f,x,考虑,s,t,g,i,x,0,i,I,h,x,0,j,J,j,x,0,i,I,i,n,g,X,x,R,h,x,0,j,J,i,构造惩罚函数,0,x,X,p,x,c,x,X,很大的正数,无约束最优化问题,min,F(x)=f(x)+p(x,的最优解必定,是原问题的最优解,前一页,后一页,退,67,出,可选的惩罚函数,c,2,p,x,c,max,g,x,0,h,x,c

43、,i,j,2,i,1,j,1,p,2,q,惩罚函数法的经济解释,f(x,为产品成本，约束条件为产品质量约束,如果违反质量约束，就给予一定的惩罚,p(x,追求的目标就是成本,f(x,和惩罚量,p(x,的总和最小,即构造的无约束最优化问题,如果惩罚条件很苛刻，最好的结果就是不违反质量,约束（无约束最优化问题的最优解为,MP,的最优解,68,2,障碍函数法,障碍函数法基本原理,构造一个新的目标函数，它在可行区域的边界筑,起一道墙,当迭代点靠近边界时，新的目标函数迅速增加,迭代点被档在可行区域的内部,迭代得到的点列就只可能在可行区域的内部,69,可选的惩罚函数,min,f,x,考虑,s,t,g,x,0

44、,i,I,i,n,X,x,R,g,x,0,i,I,i,p,1,F,x,f,x,d,d,0,构造最优化问题,min,k,k,g,x,i,i,1,min,F,x,f,x,d,ln,g,x,d,0,或,k,i,k,i,1,p,当,x,靠近边界时，至少有一个,g,i,x,趋近于零，则,F(x,将,无限增大，从而使得迭代点保持在可行区域的内部,70,四、非线性规划建模实例飞行管理问题,1,问题提出,在约,10000m,高空的某边长为,160km,的正方形区域,内，经常有若干架飞机作水平飞行。区域内每架飞机,的位置和速度均由计算机记录其数据，以便进行飞行,管理。当一架欲进入该区域的飞机到达区域边缘时,记录

45、其数据后，要立即计算并判断是否会与区域内的,飞机发生碰撞。如果会碰撞，则应计算如何调整各架,包括新进入的）飞机飞行的方向角，以避免碰撞,现假定条件如下,1,不碰撞的标准为任意两架飞机,的距离大于,8km,2,飞机飞行方向角调整的幅度不,应超过,30,3,所有飞机飞行速度均为,800km,每小时,4,进入该区域的飞机在到达区域边缘时,与区域内,飞机的距离应在,60km,以上,5,最多需考虑,6,架飞机,6,不必考虑飞机立刻此区域后的状况,71,0,试对这个避免碰撞的飞行管理问题建立数学模型，列出计算,0,0,01,步骤，对以下数据进行计算（方向角误差不超过,要求飞,机飞行方向角调整的幅度尽量小,

46、设该区域,4,个顶点的坐标为,0,0,160,0,160,160,0,160,记录的数据如表,2-8,所示,表,2-8,一个飞行管理问题的记录数据,飞机编号,横坐标,x,km,纵坐标,y,km,方向角,0,1,150,140,243,0,2,85,85,236,0,3,150,155,220,5,0,4,145,50,159,0,5,130,150,230,0,新进入,0,0,52,注：方向角指飞行方向与,x,轴正向的夹角,72,2,模型假设,1,飞机用几何上的点代表，不考虑其尺寸，位置,由坐标,x,y,给出,2,已在区域内的飞机，按给定方向角飞行，一定,不会碰撞,3,飞机调整方向角的过程可以

47、在瞬间完成，即可,在保持位置不变的情况下完成方向角的调整,73,3,模型建立,设初始时刻为新飞机到达区域边缘的时刻：记,0,0,x,i,y,i,和,为初始时刻第,i,架飞机的坐标和方向,0,i,角,i,为初始瞬间第,i,架飞机调整后的方向角,i,1,2,6,d,ij,i,j,为,i,j,两架飞机分别以方向角,i,j,飞行时在区域内的最短距离,则问题的非线性,规划模型为,6,0,i,1,m,in,z,i,i,0,i,i,i,1,2,6,6,s,t,d,ij,i,j,8,i,j,1,2,6,i,j,其中，第二个约束条件仅限于区域内,74,d,ij,i,j,的数学描述如下,T,T,v,800,km,

48、h,i,j,分别为第,i,j,架,记飞机速度为,飞,机,以,方,向,角,i,j,飞,行,在,区,域,内,的,时,间,且,T,ij,min,T,i,T,j,则,d,ij,i,j,min,x,i,x,j,vt,cos,i,cos,j,0,t,T,ij,2,0,0,2,y,0,i,y,j,vt,sin,i,sin,j,0,2,75,min,min,T,i,min,min,160,x,i,160,y,i,v,cos,v,sin,i,i,160,y,i,x,i,v,cos,v,sin,i,i,y,i,x,i,v,cos,v,sin,i,i,0,0,0,0,0,0,0,0,i,2,i,2,3,i,2,0,

49、y,i,160,x,i,v,cos,v,sin,i,i,3,i,2,2,76,0,0,0,0,b,v,x,x,cos,y,y,sin,i,j,(cos,i,j,i,j,(sin,i,j,0,0,2,0,0,2,c,x,x,y,y,i,j,i,j,a,v,cos,cos,sin,sin,i,j,i,j,2,2,2,c,b,0,2,b,2,2,d,min,at,2,bt,c,c,0,b,aT,ij,ij,0,t,T,ij,a,2,aT,2,bT,c,b,aT,ij,ij,ij,77,4,模型求解,非线性规划的算法种类繁多,但只适用于某些特定,类型的问题,本模型可以考虑用计算机编程直接搜索,求解或计

50、算碰撞方向角的上下界分析求解,1,直接搜索法,0,0,i,i,将允许调整的方向角范围,6,6,分成,2,M,k,等,分,令分点上的值,i,k,1,2,2,M,1,对允许调整方,向,的,不,同,组,合,k,1,1,2,6,k,2,k,6,k,j,1,2,2,M,1,j,1,2,6,进行搜索,在满足,2,式中第二个条件的情况下，寻求,1,式的最优解,78,5,计算结果,各架飞机碰撞方向角的上下界,飞机编号,上界,下界,0,0,1,18.581,27.519,0,0,2,26.368,41.632,0,0,3,47.127,55.629,0,0,4,53.072,65.031,0,0,5,43.55

51、2,52.791,可看出，对于初始方向角为,52,的新飞机，必,将与第,3,和第,5,架飞机相撞（至于是否在区域,内相撞，容易从图形或分析得出,0,79,1,二次规划,标,准,型,为,T,T,1,M,i,n,Z,X,H,X,c,X,2,Aeq,X,beq,s,t,A,X,b,V,L,B,X,V,U,B,用,MATLAB,软件求解,其,输入格式,如下,1,2,3,4,5,6,7,8,x=quadprog(H,C,A,b,x=quadprog(H,C,A,b,Aeq,beq,x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,x=quadprog(H,C,A,b, Aeq,beq

52、 ,VLB,VUB,X,0,x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X,0,options,x,fval=quaprog(.,x,fval,exitflag=quaprog(.,x,fval,exitflag,output=quaprog(.,80,例,1,min f(x,1,x,2,-2x,1,6x,2,x,1,2,2x,1,x,2,2x,2,2,s.t. x,1,x,2,2,x,1,2x,2,2,x,1,0, x,2,0,x,x,1,1,2,1,1,1,写成标准形式,mi,z,n,x,x,1,2,1,2,x,6,x,2,2,T,s.t,2,输入命令,1,1

53、,x,1,1,2,x,2,0,x,1,0,x,2,2,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,81,标准型为,min F(X,s.t,AX=b,Aeq,X,beq,G(X,0,Ceq(X)=0 VLB,X,VUB,2,一般非线性规划,其中,X,为,n,维变元向量,G(X,与,Ceq(X,均为非线性函数组,成的向量，其它变量的含义与线性规划、二次规划中相同,用,Matlab,求解上述问题，基本步骤分三步,1,首先建立,M,文件,fun.m,定义目标函数,F,X,