生产运筹--非线性规划的基本概念(PPT 78页)(2)

上传人:ahu****ng1 文档编号:146109605 上传时间:2020-09-26 格式:PPTX 页数:79 大小:1.43MB
返回 下载 相关 举报
生产运筹--非线性规划的基本概念(PPT 78页)(2)_第1页
第1页 / 共79页
生产运筹--非线性规划的基本概念(PPT 78页)(2)_第2页
第2页 / 共79页
生产运筹--非线性规划的基本概念(PPT 78页)(2)_第3页
第3页 / 共79页
生产运筹--非线性规划的基本概念(PPT 78页)(2)_第4页
第4页 / 共79页
生产运筹--非线性规划的基本概念(PPT 78页)(2)_第5页
第5页 / 共79页
点击查看更多>>
资源描述

《生产运筹--非线性规划的基本概念(PPT 78页)(2)》由会员分享,可在线阅读,更多相关《生产运筹--非线性规划的基本概念(PPT 78页)(2)(79页珍藏版)》请在金锄头文库上搜索。

1、第五讲 非线性规划的基本概念,非线性规划问题 非线性规划数学模型 非线性规划的图解法 梯度、Hesse矩阵、Jacobi阵 凸函数和凸规划 解非线性规划方法概述 一维最优化,在科学管理和其他领域中,大量应用问题可以归结为线性规划问题,但是,也有另外许多问题,其目标函数和(或)约束条件很难用线性函数表达。如果目标函数和(或)约束条件中包含有自变量的非线性函数,则这样的规划问题就属于非线性规划。 非线性规划是运筹学的重要分支之一。最近30多年来发展很快,不断提出各种算法,而其应用范围也越来越广泛。比如在各种预报、管理科学、最优设计、质量控制、系统控制等领域得到广泛且不短深入的应用。 一般来说,求解

2、非线性规划问题比线性规划问题困难得多。而且,也不象线性规划那样有单纯形法这一通用的方法。非线性规划的各种算法大都有自己特定的使用范围,都有一定的局限性。到目前为止还没有适合于各种问题的一般算法,这是需要深入研究的一个领域。我们只是对一些模型及应用作简单介绍。,非线性规划问题举例 例一:选址问题 设有 个市场,第 个市场位置为 ,它对某种货物的需要 量为 。现计划建立 个仓库,第 个仓库的存储 容量为 试确定仓库的位置,使各仓库对各市场的 运输量与路程乘积之和为最小。 设第 个仓库的位置为 第 个仓库到第 个市场的货物供应量为 则第 个 仓库到第 个市场的距离为,目标函数为,约束条件为 (1)每

3、个仓库向各市场提供的货物量之和不能超过它的存储容量。,(2)每个市场从各仓库得到的货物量之和应等于它的需要量。,(3)运输量不能为负数,例2. 木梁设计问题 把圆形木材加工成矩形横截面的木梁,要求木梁高度 不超过 ,横截面的惯性矩(高度的平方 宽度)不小 于 ,而且高度介于宽度与4倍宽度之间。问如何确定木 梁尺寸可使木梁成本最小.,设矩形横截面的高度为 , 宽度为 ,则圆形木材的半径,而木梁长度无法改变,因此成本只与圆形 木材的横截面积有关。,目标函数为,约束条件为,(1)数学规划模型的一般形式:,其中,简记为MP(Mathematical Programming),2 非线性规划问题的数学模

4、型,(2)简记形式:,引入向量函数符号:,(3)数学规划问题的分类:,若 为线性函数,即为线性规划(LP);,若 至少一个为非线性, 即为非线性规划(NLP);,对于非线性规划,若没有 ,即X=Rn,称为 无约束非线性规划或无约束最优化问题; 否则称为约束非线性规划或约束最优化问题。,(4)可行域和可行解:,称,为MP问题的约束集或可行域。,若x在X内,称x为MP的可行解或者可行点。,(5)最优解和极小点,对于非线性规划(MP),若 ,并且有,如果有,定义:,如果有,定义,则称 x* 是(MP)的局部最优解或局部极小解,例1: 用图解法求解 min f(x)=(x12)2 +(x22)2 s.

5、t. h(x)= x1 + x2 - 6 = 0,x1,x2,0,6,6,2,2,3,3,最优解 x* = ( 3,3 )T,可行解 x = ( 1.5,4.5 )T,最优级解即为最小圆的半径: f(x)=(x12)2 +(x22)2 = 2,3 非线性规划问题的图解法,对二维最优化问题,总可以用图解法求解,而对三维或高维问题,已不便在平面上作图,此法失效。,x1,x2,0,6,6,2,2,D可行域,最优解 x* = ( 2,2 )T,例2: 用图解法求解 min f(x)=(x1 - 2)2 +(x2 - 2)2 s.t. h(x)= x1 + x2 - 6 0,3 非线性规划问题的图解法,

6、最优级解即为最小圆的半径: f(x)=(x1 - 2)2 +(x2 - 2)2 = 0,解:先画出等式约束曲线 的图形抛物线,,例3:用图解法求解,再画出不等式约束区域,,最后画出目标函数等值线,,所以 最优解 x*=(4,1), 最优值 min f(x)=4.,4 梯度、Hesse矩阵、Jacobi阵,(1) 二次函数,一般形式:,矩阵形式:,二次型:,矩阵A的正定性: 正定、半正定、负定、不定。,其中AAT。,二次型的正定性: 正定、半正定、负定、不定。,(2) 梯度,定义:f(x) 是定义在En上的可微函数。f(x) 的n个偏导数为分量的向量称为f(x) 的梯度.,性质:设f(x) 在定

7、义域内有连续偏导数,即有连续梯度,则梯度有以下两个重要性质: 性质一 函数在某点的梯度不为零,则该梯度方向必与过该点的等值面垂直; 性质二 梯度方向是函数具有最大变化率的方向(负梯度方向也叫最速下降方向)。,解: 由于,例:试求目标函数 在点 x =0,1T 处的最速下降方向,并求沿这个方向移动一个单位长度后新点的目标函数值。,则函数在 x =0,1T 处的最速下降方向是,这个方向上的单位向量是:,解: 由于,例:试求目标函数 在点x =0,1T 处的最速下降方向,并求沿这个方向移动一个单位长度后新点的目标函数值。,新点是:,函数值:,几个常用的梯度公式:,(3)Hesse矩阵,多元函数 f(

8、x) 关于x的二阶导数,称为 f(x)的Hesse矩阵.,当f(x)的所有二阶偏导数连续时,即,Hesse矩阵是对称的.,时,,几个常用Hessian公式:,(4)Jacobi矩阵,向量变量值函数:,向量值函数g(x)在点 x0处的Jacobi矩阵,向量变量值函数的导数:,(1)凸函数:,定义,5 凸函数和凸规划,例:正定二次函数,其中A是正定矩阵,,f(x)是凸函数。,参见P104例。,性质1:,(2)凸函数的性质,性质2:,是凸集。,证明:略.,定理1:(一阶条件),n=1时几何意义:可微函数是凸的等价于切线不在函数图像上方。,(3) 凸函数的判定,定理2:(二阶条件),(4)凸规划的定义

9、及其性质:,凸规划定义:,凸规划性质:,凸规划的任一局部最优解都是它的整体最优解。,凸规划是以后重点讨论的一类非线性规划,凸函数,线性函数,(1)微分学方法的局限性:,实际的问题中,函数可能是不连续或者不可微的。 需要解复杂的方程组,而方程组到目前仍没有有效的算法。 实际的问题可能含有不等式约束,微分学方法不易处理。,6 非线性规划方法概述,(2)数值方法的基本思路:迭代,给定初始点x0,根据x0,依次迭代产生点列xk,xk的最后一点为最优解,xk有限,xk无限,xk收敛于最优解,迭代格式,xk,xk+1,pk,称pk为第k轮搜索方向,tk为第k轮沿pk方向的步长。,产生tk和pk的不同方法,

10、形成了不同的算法。,定义:特殊搜索方向下降方向,定义:特殊搜索方向可行下降方向,解非线性规划问题,关键在于找到某个方向,使得在此方向上,目标函数得到下降,同时还是可行方向。 这样的方向称为可行下降方向。,定义:算法收敛、下降迭代算法,集合S上的迭代算法:,(1)初始点,;,(2)按照某种搜索方向pk产生下一个迭代点,(i)如果点列,收敛于最优解,,则称此算法收敛。,(ii)如果,,则称此算法为,下降迭代算法。,.,.,.,(3)下降迭代算法步骤,(1)给出初始点,,令,;,(2)按照某种规则确定下降搜索方向,;,(3)按照某种规则确定搜索步长,,使得,;,(4)令,,,;,(5)判断,是否满足

11、停止条件。是则停止,否则转第2步。,搜索步长确定方法:,称,为最优步长,且有对k的梯度,(4) 终止条件,(5)常用的收敛性判别准则:,取其中之一,也可同时取(1)与(2);(1)与(3);或(1),(2)和(3)等。,(6)算法的收敛速度,则称 的收敛阶为 。,设算法所得的点列为,,如果,1.线性收敛(当k充分大时):,2.超线性收敛:,3.二阶收敛: (*)式中 =2时成立。,(*),单变量(一维)最优化,一维最优化问题 进退法 黄金分割法 抛物线搜索法 三次插值法,下降迭代算法中最优步长的确定,.,.,一维最优化问题:,解析的方法(极值点的必要条件),一、一维最优化问题,1. 单峰函数,

12、定义:设,是区间,上的一元函数,,是,在,上的极小点,且对任意的,有,(a)当,时,,(b)当,.,.,.,.,.,则称 是单峰函数。,.,.,性质:通过计算区间 a, b 内两个不同点的函数值,就可以确定一个包含极小点的子区间。,.,.,.,.,.,2 搜索法求解:,或,基本过程: 给出a,b,使得x*在a,b中。a,b称为搜索区间。 迭代缩短a,b的长度。 当a,b的长度小于某个预设的值,或者导数的绝对值小于某个预设的正数,则迭代终止。,二进退法,思想,从一点出发,按一定的步长, 试图确定出函数值呈现“高 - 低 - 高”的三点。一个方向不成功,就退回来,再沿相反方向寻找。,进退法的计算步

13、骤,如何确定包含极小点的一个区间?,例:,假定:已经确定了单峰区间a,b,新搜索区间为a,x2,新搜索区间为x1,b,三. 黄金分割法(0.618法),区间缩小比例的确定:,区间缩短比例为(x2-a)/(b-a),缩短比例为(b-x1)/(b-a),缩短比例 满足: 每次插入搜索点使得两个区间a,x2和x1,b相等; 每次迭代都以相等的比例缩小区间。,黄金分割法的计算公式的推导:,通过确定 的取值,使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合,从而减少算法的计算量。,同理可得。,3. 0.618法的算法步骤:,确定a,b,计算探索点 x1=a+0.382(b-a) x2=a+0.61

14、8(b-a),是,否,是,停止,输出x1,否,以a,x2为新的搜索区间,是,停止,输出x2,否,以x1,b为新的搜索区间,3. 0.618法的算法框图:,黄金分割法的迭代效果: 第 k 次后迭代后所得区间长度为初始区间长度的,其它的试探点算法:Fibonacci算法。,例:,解:,1、第一轮: t1=1.146, t2=1.854,t200.5,2、第二轮: t2=1.146, t1=0.708,t20=1.1460.5,3、第三轮: t1=0.438, t2=0.708,b -t1=1.146-0.4380.5,4、第四轮: t2=0.876=(1.146-0.438), t1=0.708,

15、b-t1=1.146-0.7080.5,输出:t*=t2=0.876为最优解,最优值为-0.0798,四 Fibonacci法,此法类似于0.618法,也是用于单峰函数。其计算过程也与0.618类似,第1次迭代计算两个试探点,以后每次迭代只需新加一点,另一试探点取自上次的迭代点。此法与0.618法的主要差别为:区间长度的缩短比率不是常数,而是由Fibonacci 数确定;给出精度后,迭代次数可预先确定;适合于参数只能取整数值的情况。,定义 称满足条件 (i)F0 = F1 = 1; (ii) 的数列 Fn 为Fibonacci数列。,由定义推知Fibonacci数列的前10项为1,1,2,3,5,8,13,21,34,55,89。通过求解递推关系可求得该数列的通项为,在Fibonacci法中,第n次迭代的搜索区间的长度(记为 )是上一次区间长度的 倍,所以要使在第n次迭代时搜索区间的长度不超过,只需,即可。因 是已知值,所以给出精度后利用(2.4)式可求得迭代次数。,Fibonacc法在迭代中计算试探点的公式为,即有,Fibonacci法,(1) 对初始区间

展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 商业/管理/HR > 管理学资料

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号