规划模型专题二 非线性规划课件.ppt

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

1、规划模型专题二,非线性规划、动态规划与多目标规划,第一部分 非线性规划,前面有老师介绍了线性规划问题，典型的问题“下料问题”、“运输问题”等，这些问题都比较简单。但实际中的问题不仅仅是简单的线性规划问题，可能是比较繁杂的非线性规划问题。,下面我们从一个竞赛题目出发，以理解非线性规划的定义、建模过程及其求解过程。,在约1万米的高空的某边长为160km的正方形区域内，经常有若干架飞机作水平飞行，区域内每架飞机的位置和速度向量均由计算机记录其数据，以便进行飞行管理。当一架欲进入该区域的飞机到达区域边缘时，计算机记录其数据后，要立即计算并判断是否会发生碰撞。若会发生碰撞，则应计算如何调整各架飞机（包括

2、新进入的飞机）飞行的方向角，以避免碰撞，且使飞机的调整的幅度尽量小，,例1 1995年全国数学建模A题：飞行管理问题,一、例题讲解,该题比较有意思的一句话是：,“使调整弧度最小”,开放性的一句话，没有限制得很死，较灵活，,给参赛者的创新空间比较大一些，使得构建模型的目标函数表现形式很多，再加上模型求解方法（算法）的多样性，从而可以呈现出五花八门的论文。,不碰撞的标准为任意两架飞机的距离大于8km;,假设条件：,飞机飞行的方向角调整幅度不应超过 ；,（因飞机飞行的速度变化不大）所有飞机的飞行 速度 v 均为800km/h;,有时需要通过查阅文献、资料给出合理假设,注：,进入该区域的飞机在到达区域

3、边缘时，与区域内 飞机的距离应在60km以上；,最多需考虑六架飞机；,不必考虑飞机离开此区域后的状况。,根据当年竞赛题目给出的数据，可以验证新进入的飞机与区域内的飞机的距离超过60公里。,根据当年竞赛题目给出的数据，可以验证区域内的飞机不超过架(包括新进入的)。,个人的想法不同，队友之间争执不下的情况下，若时间允许，都可一一写到论文中去，建立的模型一、模型二；或者经讨论后，选择一个认为更合理的。费时较多的是计算（那时侯是自己编程解NLP）,现在看来，无论是构建模型，还是计算，都不太难。,本例题未给出数据，将重点放在如何构建模型上,解：,(1)不考虑飞机的尺寸，用点代表飞机；,(2)已在区域内的

4、5架飞机按给定的方向角作 直线飞行，则必不会碰撞，也不会发生 意外；(应该根据题目中所给出的数据简 单的 验证一下),(3)飞机调整方向角的过程可在瞬间完成,(不 计调整方向所花费的时间)。,为解决该问题，补充假设：,变量、参数的符号假设（为了建模）,时间（可以根据数据算出来）,四种情况：,四个象限，易用4个表达式表示,说明：用初等数学的知识即可完成，,思考：在哪个时间段某两架飞机可能相撞？,In fact, 我们只需考虑两架飞机同时在区域内飞行时的情况，也就是说，,才是同在区域内的状况。,记为,根据题目条件，需计算第 架飞机之间的最短距离,为此，我们可以给出原问题的模型如下：,思考：是否还有

5、其他的表达形式？,非线性规划模型,分别从目标函数和约束条件角度思考,首先思考一下目标函数是否有其它的表达？,同学们首先想到的可能是,Oh, Sorry!有正有负抵消,最小一乘 法,最小二乘 法,因最小一乘法带绝对值，不好计算，以上两式，比较而言，后者较好。,为了避免抵消,or,有的队员这样考虑：,令为 ,转化为二次规划,用到经验模型中确定参数的近似准则:,就所有飞机而言，,让调整弧度最大的,即,尽可能小，,Chebshavf 准则,全国数学建模竞赛开展之初, 竞赛题大多是优化类型的题目, 那时的计算机性能没有现在好, 速度也没有现在快, 因此在模型的计算方面花的培训时间比较多。,虽然目前可供选

6、择的软件比较多，但是必要的优化知识是必须掌握的。,其次讨论一下约束条件是否有其它表达？,若考虑区域内不发生碰撞（若时间允许，也可以考虑出了区域的情况，另外建模）、错层飞行（飞高或者飞低避免碰撞），进行模型的进一步改进，重点应放在解决问题的方法上。,如,无论选择哪一种表达，怎样考虑约束条件，目标函数都不可能是线性的。,现在看来，那年的题目建模不难，只是在条件的考虑上和建模中目标函数的表达方面较难一点。但在当时不然。,是一个带不等式约束的非线性规划问题。,而且不可能转化成线性的形式。,若目标函数或约束条件中含有非线性函数，则称这种模型问题为非线性规划（Non-Linear Prog-ramming

7、），简记为NLP。,NLP的一般形式,其中，,中至少有一个是,非线性函数。,无约束极值问题是NLP的一种特殊形式,如数据拟合的最小二乘问题就是一个无约束极值问题。,其思想是：观察点（实验数据点）到曲线的距离的平方之和最小,二、无约束极值问题,理论上无约束极值问题可化成求解,即解一个 n 元方程组，且往往是非线性方程组。,而一般说来，非线性方程组的求解并不比求无约束极值容易。,求解无约束极值问题的基本方法：迭代法,从一个给定的初始可行点 出发，依次,产生一个可行点列,基本思路：,称具有这种性质的算法,是收敛的.,记,即,确定以后,迭代的方法很多,各种迭代法的区别在于选取,的方式不同,一般要求,递

8、减,具有这种性质的算法叫做下降,算法.,下面介绍的迭代法均为下降算法,若已得,下降得最多,使,且使,即求,1. 下降算法,于是一维搜索归结为求解一维无约束极值问题:,其算法有Newton法、平分法、黄金分割法（0.618法）、分数法（Fibonacci法）、抛物线法（二次插值法）等，,前两种算法需计算,的导数，,后三种算法只需计算,的函数值。,下面仅介绍Newton法，对其他方法的了解可参考有关书籍。,按,给定初始可行点 和控制误差 ，,迭代格式,迭代，,停止计算。,Newton 法介绍,一个好的算法必须以较快的速度收敛到最优解。,若存在,及,使,则称,为 p 阶收敛的。,该算法也是 p 阶收

9、敛的。,称为线性收敛；,当,称为超线性收敛；,称为平方收敛；,一个算法是否收敛，,由算法产生的点列,才收敛于,则称该算法为具有局部收敛,性的算法；, 若对,则称该算法为具有全局收敛性的算法。,Newton法是平方收敛的，具有局部收敛性；抛物线法是超线性收敛的，具有全局收敛性；平分法、黄金分割法、分数法是线性收敛的，具有全局收敛性。,常见一维搜索算法的收敛性,则算法求得,此时可,若求得多个极小值点，则从中选择一个较满意的结果。,说明：,在多数情况下，一维搜索的一个基本工具，,而此时一维搜索的精度并不要求很高，故一维,搜索实现的方便性更重要些。,1847年Cauchy提出了第一个无约束极值问题的算

10、法梯度法或最速下降法：,其中,求,即得,停止计算。,2. 梯度法,该算法具有全局收敛性，是线性收敛的，但有时是很慢的线性收敛，这似乎与“最速下降”矛盾。其实不然，最速下降方向函数在某点处的局部性质，对局部来说是最速下降方向，对全局来说却不一定是最速下降方向，故梯度法不是有效的实用算法。,通过对它改进或利用它与其他收敛快的算法相结合可得Newton法、Fletcher-Reeves共轭梯度法、变尺度法和Powell法等有效算法。,下面仅介绍前两者，对后两者的了解可参阅有关书籍。,则 。,其中,Newton法,该算法是平方收敛的，具有局部收敛性。,对Newton法进行改进，可得具有超线性收敛的且具

11、有全局收敛性的阻尼Newton法或修正Newton法：,有 。, Fletcher-Reeves共轭梯度法,有 。,该算法的收敛速度介于梯度法和Newton法,其中,之间，既克服了前者的慢收敛性，又避免了,后者计算量大和仅具有局部收敛性的缺陷。,求解无约束极值问题的算法非常多，不同算法的效果和实际效率也可能与所求解的问题有关，软件包中往往提供了多种算法。,后面将有教练专讲如何使用软件包求解非线性规划问题。,求解一般的 NLP 比求解的无约束极值问题和 LP 都要复杂，虽然目前已发展了许多 NLP 的算法，但不象 LP 那样有通用的单纯形法，而是各种算法都有特定的使用范围。即便如此， NLP 的

12、实际应用还是相当广泛的。,三、有约束极值问题,首先回顾 “NLP的一般形式”,其中，,中至少有一个是,非线性函数。,由于无约束极值问题的求解目前已有许多有效的算法，因此很自然想到把它们推广到有约束的 NLP ，但存在不少困难，特别是对于非线性约束，困难更大。,（一）罚函数法,一种可行的方法是根据约束问题的求解，构造某种“惩罚”函数，把它加到目标函数中去，将约束问题的求解转化为一系列无约束问题的求解。在无约束问题处， “惩罚”项必须趋于0，而约束条件要近似地满足。,外罚函数法,令,通常取,称之为罚函数，,则约束问题转化为无约束问题,其中 M 0 为罚因子.,显然, 符合上述,惩罚策略,即,当 为

13、可行解时,不受“惩罚”;,当 为非可行解时,M 越大,“惩罚”越重.,因此,当 M 充分大时,要使,极小,则 应充分小,从而,的极小值点充分逼近可行域,的最优解,逼近 的最优解.,给定 (可为非可行解点),可以取小一些,初始惩罚因子,(如取 ),迭代过程,中 M 不断增加,放大系数 c 1(可取 c =10).,令k=0,以 为初始点求,若,则 ;,否则, 令,以 为初始点求,该算法所得 是从可行域外部,故 又称为外罚函数法或外点法.,趋于,说明,外罚函数的构造形式有多种,迭代格式也有 多种,目前有不少专家在做这方面的工作;,对于最优解 靠近边界的情况不太好;,对保证在可行域内迭代很有效.,而

14、只是近似满足约束，,这是某些实际问题不能,“挡”在可行域内了.,这种方法称为罚函数法或,外点法的每个迭代点 往往不是可行解,接受的.,为使迭代点总是可行解,在可行域的,边界筑起一道“墙”，,当迭代点靠近边界时，目标,函数值陡然增大，以示惩罚，于是迭代点就被,外点法.,只适用于不等式约束问题,2. 内罚函数法,当 从可行域内部趋于边界时, 至少有某个,外罚函数：,趋于0, 无限增大.,于是所求解的有,约束问题转化为求解无约束问题,其中 r 0 为罚因子.,可实现上述“惩罚”,而 r 很小,几乎不受惩罚;,策略，即,无限增大，,当 为可行域的内点时， 为有限正数，,施以重罚,迫使迭代点落在可行域内

15、，,的最优解.,当 接近可行域的边界时，,最终逼近,给定初始可行点 ,初始惩罚因子,(可取 ),缩小系数 0 c 1,令 k = 0,以 为初始点求,得最优解 .,若,则 ;,否则, 令,以 为初始点求,(可取 c = 0.1 ).,缩小到原来的1/10,控制在误差范围之内，从而使得之间的误差也在控制范围内,困难的。,因此可将内点法和外点法结合起来使用，,外点法，,内点法，即令,内点法要求 为可行域的内点,有时这是很,得到所谓的混合罚函数法。,那些不等式约束用,3. 混合罚函数法,当给定 后，对,等式约束和不被 满足的,而对被 满足的那些不等式约束用,为简便起见，取平方,其中,r 充分小，1/

16、r 充分大，这样少用一个参数,罚函数法中的罚因子的选取对方法的收敛快慢有较大影响，尤其是当M不断增大和r不断减少时， 越来越“病态”，使得求解无约束问题很困难。为此，人们提出了许多改进的方法，其中最有效的是“乘子法”。需要详细了解时参阅相关书籍。,4. 其他方法,罚函数法要用到目标函数和约束函数的偏导数，而某些实际问题中出现的函数很复杂，甚至难以解析表达，无法求得函数的偏导数，此时常用直接法(主要跟函数的函数值打交道)。,这一类方法一般算法简单，直观性强，对函数无特殊要求，但计算量随维数和约束条件数的增加而成指数增大，故对维数低、函数复杂、要求精度不高的问题较适用。,（二）网格法,对有约束问题

17、，假定已知变量的取值范围，,若无上、下界约束，则可根据问题的性质估计一下最优解所在范围。,最简单的一种直接方法就是网格法，它是在区域,上打网格，网格等间距与否皆可，求网格点的约束函数和目标函数值，比较满足约束条件的点的目标函数值的大小，从中选择小的。,网格的间距是要求的解的误差上限，若网格的间距超过控制误差，则在求出的点附近加密网格再求。否则，便求得了近似最优解。,网格法遍历全部网格点才能得出极小值点的大体位置。如果考虑不是这样有规律地取试验点，而是随机地选取试验点，即使只计算预定点数的一部分，只要这部分点在区域E中是均匀分布，则对 f (x) 在E 中的大致形态能有所了解。在E中投入一定量的试验点后，往往发现较好的点集中在E的某一部分，因此，可将,（三）随机试点法,E 缩小后再重复上述过程。通过不断收缩E来求极小值点。这就是随机试验法的基本思路。,此外，求解一般非线性规划还有序列线性规划法、可行方向法以及最有效的算法之一的广义简约梯度法（GRP法）。Goldfarb投影梯度法是求解线性约束的NLP的最有效的算法之一，Wolf算法是求解目标函数为二次函数而约束条件为线性函数的二次规划的最有效的算法。可参阅有关书籍。,NLP也可用 Lingo 或 Matlab（优化工具箱）软件求解，但其结果往往依赖于初值的选择。,