非线性规划模型

1、1 非线性规划2CONTENTS目录12343第一节 非线性规划的定义1、非线性规划引例线性规划和整数规划它们的目标函数和约束条件都是自变量的线性函数，在实际中还有大量的问题，其目标函数或约束条件很难用线性函数来表示。先看两个实例。问题1 容器设计问题问题提出 某公司生产贮藏用容器，订货合同要求该公司制造一种敞口的长方体容器，容积为12立方米，该容器的底为正方形，容器总重量不超过68公斤。已知用作容器四壁的材料为每平方米10元，重3公斤；用作容器底的材料每平方米20元，重2公斤。试问制造该容器所需的最小费用是多少？ 421,xx21212040)(minxxxXf0,6821212212121

2、221xxxxxxx模型建立 设该容器的底边长和高分别为则问题的数学模型为则问题的数学模型为 5问题 2营业计划的制定问题提出某公司经营两种设备，第一种设备每件售价 30 元，第二种设备每件售价 450 元。据统计，售出一件第一种设备所需要的营业时间平均是0.5小时，第二种设备是)25. 02(2x小时，其中2x是第二种设备的售出数量。已知该公司在这段时间内的总营业时间为 800 小时。 试决定使其营业额最大的营业计划。模型建立设该公司计划经营第一种设备1x件，第二种设备2x件。其数学模型为2145030)(maxxxXfst0,800)25. 02(5 . 021221xxxxx6 定义定义

3、 如果目标函数或约束条件中至少有一个是非线性函数如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题时的最优化问题就叫做非线性规划问题2 非现性规划的基本概念非现性规划的基本概念 一般形式一般形式: （1） 其中 ， 是定义在 En 上的实值函数，简记: Xfmin .,.,2 , 1 0 m;1,2,., 0. . ljXhiXgtsjinTnExxxX,21jihgf,1nj1ni1nE :h ,E :g ,E :EEEf 其它情况其它情况: : 求目标函数的最大值或约束条件为小于等于零求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一

4、般形式的情况，都可通过取其相反数化为上述一般形式7 对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点： （i）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。 （ii）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。 （iii）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它。 （iv）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效

5、果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。 83 线性规划与非线性规划的区别 如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。94 求解非线性规划的基本迭代格式求解非线性规划的基本迭代格式10 01 01 0-1 .)( min2121222121xxxxtsxxxxf，线线性性规规划划问问题题：用用图图解解法法求求解解下下面面的的非非引例引例11三角形表示的是可行域。三角形表示的是可行域。同心圆表示的是目标函数的等值同心圆表示的是目标函

6、数的等值线。线。最优解为（最优解为（1/2，1/2） 最优值为最优值为1/21/21/212 对于非线性规划模型(NP)，可以采用迭代方法求它的最优解。迭代方法的基本思想是：从一个选定的初始点出发，按照某一特定的迭代规则产生一个点列 使得当 是有穷点列时，其最后一个点是(NP)的最优解；当 是无穷点列时，它有极限点，并且其极限点是(NP)的最优解。迭代13数值方法的基本思路：迭代数值方法的基本思路：迭代给定初始点给定初始点x0根据根据x0,依次迭代产生点列依次迭代产生点列xkxk的最后一点为最优解的最后一点为最优解xk有限有限xk无限无限xk收敛于最优解收敛于最优解14迭代格式 通常，我们把基

7、本迭代格式（1）中的 称为第k 轮搜索方向， 为沿 方向的步长，使用迭代方法求解(NP)的关键在于，如何构造每一轮的搜索方向和确定适当的步长。kpkpkt15迭代格式迭代格式xkxk+1kx kkkxxx 1pkkkkptx kkkxxx 1称称pk为第为第k轮轮搜索方向搜索方向，tk为第为第k轮沿轮沿pk方向的方向的步长步长。产生产生tk和和pk的不同方法，形成了不同的算法。的不同方法，形成了不同的算法。16一般步骤17第二节 无约束优化问题 当用迭代法求函数的极小点时，常常用到一维搜索，即沿已知某一已知 方向求目标函数的极小点。一维搜索方法有很多，常用的有：试探法，斐波那契法，0.618法

8、等；插值法（抛物线插值法，三次插值法等）；微积分中的求根法（切线法，二分法等） 考虑一维极小问题 若f(t)是a,b区间上的下单峰函数，这里介绍不断通过缩短a,b的长度，来搜索得近似最优解的方法。180.618法（近似黄金分割法）法（近似黄金分割法） , ,( ) , , ,( ) , ta bta ttbta b如果使得函数在上严格递减且在上严格递增 称为上的下单峰函数 , ( )a bt称为的单峰区间。下下单单峰峰函数函数上唯一的极小点。上唯一的极小点。在在为为显然此时显然此时,)(batt 19搜索法求解：搜索法求解：(t)min0 t(t)minmax0 tt 或或基本过程：基本过程：

9、给出给出a,b,使得使得t*在在a,b中。中。a,b称为称为搜索区间搜索区间。迭代缩短迭代缩短a,b的长度。的长度。当当a,b的长度小于某个预设的值，或者导数的绝的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。对值小于某个预设的正数，则迭代终止。20假定：已经确定了单假定：已经确定了单峰峰区间区间a,b(t)min0 t(t)minmax0 tt (t)min bta )(1t )(2t t)(1t )(2t tt1t2ababt1t2新搜索区间为新搜索区间为a,t2新搜索区间为新搜索区间为t1,b21区间缩小比例的确定：区间缩小比例的确定：区间缩短比例为区间缩短比例为

10、(t2-a)/(b-a)缩短比例为缩短比例为(b-t1)/(b-a)缩短比例缩短比例 满足：满足：每次插入搜索点使得两个区间每次插入搜索点使得两个区间a,t2和和t1,b相等；相等；每次迭代都以相等的比例缩小区间。每次迭代都以相等的比例缩小区间。618. 0215 缩短比例缩短比例0.618法法)(1t )(2t )(1t )(2t t1t2ababt1t222确定确定a,b,计算探索点计算探索点t1=a+0.382(b-a)t2=a+0.618(b-a)0.618法解题步骤：法解题步骤：)()(21tt 是是否否 at2是是停止，输出停止，输出t1否否以以a,t2为新的搜索区间为新的搜索区间

11、 1tb是是停止，输出停止，输出t2否否以以t1,b为新的搜索区间为新的搜索区间23例：例：5 . 0,3 , 0 12)(min 30精精度度其其中中单单谷谷区区间间求求解解 tttt 解：解：t1t2)(1t )(2t 30t 1、第一轮：、第一轮：t1=1.146, t2=1.8546648. 3)(,2131. 0)(21 tt t200.5242、第二轮：、第二轮：t2=1.146, t1=0.7082131. 0)(0611. 0)(21 tt t20=1.1460.53、第三轮：、第三轮：t1=0.438, t2=0.7082082. 0)(0611. 0)(12 tt b-t1

12、=1.146-0.4380.51.8540t t2t11.4160 tt2t1254、第四轮：、第四轮：t2=0.876, t1=0.7080798. 0)(0611. 0)(21 tt b-t1=1.146-0.7080.5输出：输出：t*=t2=0.876为最优解，最优值为为最优解，最优值为-0.07980 1.416tt1t226第三节 无约束极值问题的解法无约束极值问题可表述为 求解该问题的迭代法大体上分为两点：一用到函数的一阶导数或二阶导数，称为解析法。另一是仅用到函数值，称为直接发。 27梯度法（最速下降法） 对基本迭代格式 我们总是考虑从点 出发沿哪一个方向 ，使目标函数下降的最

13、快。微积分的只是告诉我们，点 的负梯度方向 是从点 出发使 f 下降最快的方向。为此，称负梯度方向 为 f 在点 处的最速下降方向。kxkpkxkxkx28 给定初始点nEX 0，允许误差0,令 k=0； 计算kXf； 检验是否满足收敛性的判别准则： kXf， 若满足，则停止迭代，得点kXX*，否则进行； 令kkXfS，从kX出发，沿kS进行一维搜索， 即求k使得： kkkkkSXfSXf0min； 令kkkkSXX1，k=k+1 返回. 最速下降法是一种最基本的算法，它在最优化方法中占有重要地位最速下降法是一种最基本的算法，它在最优化方法中占有重要地位. .最最速下降法的优点是工作量小，存储

14、变量较少速下降法的优点是工作量小，存储变量较少, ,初始点要求不高；缺点是收初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法值点时，宜选用别种收敛快的算法. . 最速下降法最速下降法具体具体步骤：步骤：29例30Newton法法0)()(),(min ttt 二次可微，二次可微，其中其中考虑考虑Newton法基本思想：法基本思想：用探索点用探索点tk处的二阶处的二阶Taylor展开式近似代替目标展开式近似代替目标函数，以展开式的最小点为新的探索点。函数，以展开式

15、的最小点为新的探索点。2)(21)()()(kkkkkttttttttg 展展开开式式：)()(:,0)(1kkkktttttg 求求导导得得的的点点的的最最小小点点即即导导数数为为31牛顿法算法步骤：牛顿法算法步骤： 如果如果f f是对称正定矩阵是对称正定矩阵A A的二次函数，则用牛顿法经过一次迭代的二次函数，则用牛顿法经过一次迭代就可达到最优点就可达到最优点, ,如不是二次函数，则牛顿法不能一步达到极值点，如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似但由于这种函数在极值点附近和二次函数很近似, ,因此牛顿法的收因此牛顿法的收敛速度还是很快的敛速度还

16、是很快的. .32例解33用用MatlabMatlab解无约束优化问题解无约束优化问题 1. 一一元元函函数数无无约约束束优优化化问问题题: : min f（x） 21xxx 其中（3）、（4）、（5）的等式右边可选用（1）或（2）的等式右边。 函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。常用格式如下：常用格式如下：（1）x= fminbnd (x= fminbnd (fun,xfun,x1 1,x,x2 2) )（2）x= fminbnd (x= fminbnd (fun,xfun,x1 1,x,x2 2 ，options)opt

17、ions)（3）xx，fval= fminbndfval= fminbnd（.）（4）xx，fvalfval，exitflag= fminbndexitflag= fminbnd（.）（5）xx，fvalfval，exitflagexitflag，output= fminbndoutput= fminbnd（.）34运行结果： xmin = 3.9270 ymin = -0.0279 xmax = 0.7854 ymax = 0.6448 例例1 1 求 f = 2xexsin在 0 x8 中的最小值与最大值 主程序为主程序为: f=2*exp(-x).*sin(x); fplot(f,0,8

18、); %作图语句作图语句 xmin,ymin=fminbnd (f, 0,8) f1=-2*exp(-x).*sin(x); xmax,ymax=fminbnd (f1, 0,8)35例例2 2 对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？解解先编写先编写M M文件文件fminbndtest.mfminbndtest.m如下如下: : function f=myfun(x) f=-(3-2*x).2*x;主程序调用主程序调用fminbnd:fminbnd: x,fval=fminbnd(fminbndtest,0,1.5); xmax=x

19、fmax=-fval运算结果为运算结果为: : xmax = 0.5000,fmax =2.0000.即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米.36 命令格式为命令格式为: :（1 1）x= fminuncx= fminunc（fun,Xfun,X0 0 ）；或）；或x=fminsearchx=fminsearch（fun,Xfun,X0 0 ）（2 2）x= fminuncx= fminunc（fun,Xfun,X0 0 ，optionsoptions）；）； 或或x=fminsearchx=fminsearch（fun,Xfun,X0 0 ，optionsopti

20、ons）（3 3）xx，fval= fminuncfval= fminunc（.）；）； 或或xx，fval= fminsearchfval= fminsearch（.）（4 4）xx，fvalfval，exitflag= fminuncexitflag= fminunc（.）；）； 或或xx，fvalfval，exitflag= fminsearchexitflag= fminsearch（5 5）xx，fvalfval，exitflagexitflag，output= fminuncoutput= fminunc（.）；）； 或或xx，fvalfval，exitflagexitflag，o

21、utput= fminsearchoutput= fminsearch（.） 多元函数无约束优化问题多元函数无约束优化问题标准型为标准型为：min F(X)37例例3 3 min f(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1) 1 1、编写、编写M-M-文件文件 fun1.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 2、输入、输入M M文件文件myprg3.mmyprg3.m如下如下: : x0 = -1, 1; x=fminunc(fun

22、1,x0) y=fun1(x) 3 3、运行结果、运行结果: : x= 0.5000 -1.0000 y = 1.3029e-1038第四节 约束极值问题 带有约束条件的极值问题称为约束极值问题，也叫规划问题。 求解约束极值问题要比求解无约束极值问题困难得多。为了简化其优化工作，可采用以下方法：将约束问题化为无约束问题；将非线性规划问题化为线性规划问题，以及能将复杂问题变换为较简单问题的其它方法。 库恩塔克条件是非线性规划领域中最重要的理论成果之一，是确定某点为最优点的必要条件，但一般说它并不是充分条件（对于凸规划，它既是最优点存在的必要条件，同时也是充分条件）。391、二次规划、二次规划 若某非线性规划的目标函数为自变量 x 的二次函数，约束条件