资源描述：
《高级运筹学-第9章：非线性规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第九章：非线性规划模型9.1基本概念和基本原理一、什么是非线性规划：目标函数和约束条件中有非线性函数的规划问题。例9-1某企业生产一种产品y需要生产资料x1和x2，用经济计量学方法根据统计资料可写出生产函数为:但是投入的资源有限，能源总共1O个单位，而每单位生产资料x1要消耗1单位能源，每单位生产资料x2要消耗2单位能源。问:应如何安排生产资料使产出最大？解:Max、生产资料1(x1)生产资料2(x2)能源限量能源1210产量y1例9-2某厂生产两种产品，第一种产品每件售价30元，第二种产品每件售价450元。设x1与x2分别
2、为第一、二种产品的数量，据统计，生产第一种产品所需工作时间平均为0.5小时，生产第二种产品所需工作时间平均为(2+0.25x2)小时。已知该工厂在这段时间内允许的总工作时间为800小时，试确定使总收入最大的生产计划？解:Max二、非线性规划问题的特点局部最优点不是全局最优点。三、极值问题1、一元函数y=f(x)：①极值点存在的必要条件：f’(x)=0，此时求出的x0为驻点。②极值点存在的充分条件：a.若在驻点x0附近f’’(x0)<0，则该点x0为极大值点。b.若在驻点x0附近f’’(x0)>0，则该点x0为极小值点。产品1
3、(x1)产品2(x2)工作时间限量工作时间0.52+0.25x2800售价3045022、多元函数y=f(X)=f(x1,x2,…,xn)：在X0附近作泰勒展开，得3①极值点存在的必要条件：f(x)=0，此时求出的x0为驻点。②极值点存在的充分条件：4四、凸函数与凹函数：1、定义：y=f(x)是En中某凸集R上的函数①对[0,1]及X1、X2R，且X1≠X2若f[X1+(1-)X2]≤f(X1)+(1-)f(X2)，则f(x)为R上的凸函数。若f[X1+(1-)X2]＜f(X1)+(1-)f(X2
4、)，则f(x)为R上的严格凸函数。②对[0,1]及X1、X2R，且X1≠X2若f[X1+(1-)X2]≥f(X1)+(1-)f(X2)，则f(x)为R上的凹函数。若f[X1+(1-)X2]＞f(X1)+(1-)f(X2)，则f(x)为R上的严格凹函数。yxoX1X2X1+(1-)X2y=f(x)凸函数yxoX1X2X1+(1-)X2y=f(x)凹函数yxoX1X2y=f(x)非凸、非凹函数52、性质：fi(X)为凸集R上的凸函数，则对ki≥0，i=1,2,…,m，有k1f1(X)+
5、k2f2(X)+…+kmfm(X)仍为凸函数。3、凸函数的判定：f(X)定义在凸集R上，若f(X)有连续的二阶导数，则f(X)为凸函数H为半正定。f(X)为严格凸函数H为正定。4、凸函数的局部极值与全局极值的关系若目标函数在可行域中为凸函数，则其极值点为最优值点；若目标函数在可行域中为严格凸函数，则其极值点为唯一最优值点。6五、凸规划：1、定义：非线性规划(p)Minf(X)gi(X)≥0，i=1,2,…,m若f(X)，-gi(X)为凸函数，则(p)称为凸规划。2、性质：①(p)的可行解集R是凸集；最优解集R*也是凸集。
6、②(p)的任何局部最优解均是全局最优解。③若f(X)为严格凸函数时，其最优解必唯一。特例:线性函数既是凸函数又是凹函数，故L.P.为凸规划。六、寻优方法概述：1、N.L.P.问题分类①无约束条件的NLP问题。②有约束条件的NLP问题。2、寻优方法①间接法(解析法)：适应于目标函数有简单明确的数学表达式。②直接法(搜索法)：目标函数复杂或无明确的数学表达式。a.消去法(对单变量函数有效)：不断消去部分搜索区间，逐步缩小极值点存在的范围。b.爬山法(对多变量函数有效)：根据已求得的目标值，判断前进方向，逐步改善目标值。79.2无
7、约束条件下单变量函数寻优一、消去法原理：逐步缩小搜索区间，直至极值点存在的区间达到允许的误差范围为止。设要寻求f(X)的极小值点为X*，起始搜索区间为[a0,b0]。x1、x2[a0,b0]，且x2＜x1，计算f(x1)和f(x2)，并且比较结果：f(x)xoa0b0X*x1,x2在x*的右侧x1x2f(x)xoa0b0X*x1,x2在x*的左侧x1x2f(x)xoa0b0X*x1,x2在x*的两侧x1x2①x1,x2均在x*的右侧，f(x2)＜f(x1)，去掉[x1,b0]，此时x*[a0,x1]②x1,x2均在x*
8、的左侧，f(x2)＞f(x1)，去掉[a0,x2]，此时x*[x2,b0]③x1,x2均在x*的两侧，f(x2)＝f(x1)：a.去掉[x1,b0]，此时x*[a0,x1]b.去掉[a0,x2]，此时x*[x2,b0]8二、黄金分割法(0.618法)：是一种常用的消去法与对分法、Fi
