非线性规划

管理工程学院《运筹学》1第2章：非线性规划模型2.1基本概念和基本原理一、什么是非线性规划：目标函数和约束条件中有非线性函数的规划问题。例2-1某企业生产一种产品y需要生产资料x1和x2，用经济计量学方法根据统计资料可写出生产函数为:3/223/112xxy但是投入的资源有限，能源总共1O个单位，而每单位生产资料x1要消耗1单位能源，每单位生产资料x2要消耗2单位能源。问:应如何安排生产资料使产出最大？解:Max3/223/112xxy、10221xx0,21xx生产资料1(x1)生产资料2(x2)能源限量能源1210产量y管理工程学院《运筹学》2例2-2某厂生产两种产品，第一种产品每件售价30元，第二种产品每件售价450元。设x1与x2分别为第一、二种产品的数量，据统计，生产第一种产品所需工作时间平均为0.5小时，生产第二种产品所需工作时间平均为(2+0.25x2)小时。已知该工厂在这段时间内允许的总工作时间为800小时，试确定使总收入最大的生产计划？解:Max21x450x30y800x2x25.0x5.022210xx21、二、非线性规划问题的特点局部最优点不是全局最优点。三、极值问题1、一元函数y=f(x)：①极值点存在的必要条件：f'(x)=0，此时求出的x0为驻点。②极值点存在的充分条件：a.若在驻点x0附近f''(x0)0，则该点x0为极大值点。b.若在驻点x0附近f''(x0)0，则该点x0为极小值点。产品1(x1)产品2(x2)工作时间限量工作时间0.52+0.25x2800售价30450管理工程学院《运筹学》32、多元函数y=f(X)=f(x1,x2,…,xn)：在X0附近作泰勒展开，得)xxx(),X(xxxx)X(f21xx)X(f)X(f)X(f0ii3jin1j,iji02in1ii00)XXX(,XHX21X)X(f)X(f)X(f0TT00,x)X(fx)X(f)X(f:n0100其中.X)X(f0梯度处的一阶导数向量在为nn1nn1112n021n02n1022102hhhhx)X(fxx)X(fxx)X(fx)X(fH.HessienX)X(f0矩阵处的二阶导数矩阵在为管理工程学院《运筹学》4①极值点存在的必要条件：f(x)=0，此时求出的x0为驻点。②极值点存在的充分条件：XHXXfXfT21)()(0为极小值点。则正定若0X,H.a)0hhhh,,0hhhh,0hH(nn1nn1112221121111正定为极大值点。则负定若0X,H.b)0hhhh)1(,,0hhhh,0hH(nn1nn111n2221121111负定只为驻点。则不定若0X,H.c的极值和极值点。求例20x4x2x8x2)x,x(f:22212121,04484)()()(:2121xxxXfxXfXf令解,12X0得驻点4004x)X(fxx)X(fxx)X(fx)X(fH222122212212,H正定显然,X0为极小值点故10)1,2(f*管理工程学院《运筹学》5四、凸函数与凹函数：1、定义：y=f(x)是En中某凸集R上的函数①对[0,1]及X1、X2R，且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上的严格凸函数。②对[0,1]及X1、X2R，且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上的严格凹函数。yxoX1X2X1+(1-)X2y=f(x)凸函数yxoX1X2X1+(1-)X2y=f(x)凹函数yxoX1X2y=f(x)非凸、非凹函数管理工程学院《运筹学》62、性质：fi(X)为凸集R上的凸函数，则对ki≥0，i=1,2,…,m，有k1f1(X)+k2f2(X)+…+kmfm(X)仍为凸函数。3、凸函数的判定：f(X)定义在凸集R上，a.若f(X)有连续的一阶导数，则f(X)为凸函数对X1、X2R，有f(X2)≥f(X1)+(X2-X1)f(X1)Tf(X)为严格凸函数对X1、X2R，有f(X2)＞f(X1)+(X2-X1)f(X1)Tb.若f(X)有连续的二阶导数，则f(X)为凸函数H为半正定。f(X)为严格凸函数H为正定。4、凸函数的局部极值与全局极值的关系若目标函数在可行域中为凸函数，则其极值点为最优值点；若目标函数在可行域中为严格凸函数，则其极值点为唯一最优值点。10xx2x2x3)X(f::212221判断函数凹凸性例正定解4006)()()()(222122212212xXfxxXfxxXfxXfH为严格凸函数。)X(f管理工程学院《运筹学》77五、凸规划：1、定义：非线性规划(p)Minf(X)gi(X)≥0，i=1,2,…,m若f(X)，-gi(X)为凸函数，则(p)称为凸规划。2、性质：①(p)的可行解集R是凸集；最优解集R*也是凸集。②(p)的任何局部最优解均是全局最优解。③若f(X)为严格凸函数时，其最优解必唯一。特例:线性函数既是凸函数又是凹函数，故L.P.为凸规划。管理工程学院《运筹学》88六、寻优方法概述：1、N.L.P.问题分类①无约束条件的NLP问题。②有约束条件的NLP问题。2、寻优方法①间接法(解析法)：适应于目标函数有简单明确的数学表达式。②直接法(搜索法)：目标函数复杂或无明确的数学表达式。a.消去法(对单变量函数有效)：不断消去部分搜索区间，逐步缩小极值点存在的范围。b.爬山法(对多变量函数有效)：根据已求得的目标值，判断前进方向，逐步改善目标值。管理工程学院《运筹学》92.2无约束条件下单变量函数寻优一、消去法原理：逐步缩小搜索区间，直至极值点存在的区间达到允许的误差范围为止。设要寻求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*的左侧，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]管理工程学院《运筹学》10二、黄金分割法(0.618法)：是一种常用的消去法与对分法、Fibonacci法比较，具有计算次数少，过程简单的特点。1、原理：LxL-x,xxLLx满足0LLxx22解得,012即有618.0618034.0251处。的为黄金分割点，位于618.0L,L618.0Lx1的对称点。为112x,L382.0L)1(LLxLxLx1x2管理工程学院《运筹学》112、取点法则：Lx1x2a0b0L)ab(aLx:0001取点)ab(bxLx00012①f(x2)≤f(x1)，取[a1=a0,b1=x1]x’1=x2x’2=b1-(b1-a1)a1b1x’1x’2②f(x2)＞f(x1)，取[a1=x2,b1=b0]x'1=a1+(b1-a1)x2=x1a1b1x’1x’2计算n个点后，总缩短率为En=n-1＜，可得试点数n。管理工程学院《运筹学》12123、计算步骤：求函数f(x)的极值点第一步：取初始区间[a0,b0]x1x2a0b0)ab(ax:0001取点)ab(bx0002)x(f)x(f21和计算⑴若求f(x)的极小值点，则①f(x2)≤f(x1)，取[a1=a0,b1=x1]x′1=x2x′2=b1-(b1-a1)②f(x2)＞f(x1)，取[a1=x2,b1=b0]x′1=a1+(b1-a1)x′2=x1a1b1x’1x’2管理工程学院《运筹学》13⑵若求f(x)的极大值点，则①f(x2)≥f(x1)，取[a1=a0,b1=x1]x′1=x2x′2=b1-(b1-a1)②f(x2)＜f(x1)，取[a1=x2,b1=b0]x′1=a1+(b1-a1)x′2=x1第二步：求区间的缩短率|abab|00kk若.则停止，得近似极值点否则，继续缩短区间，止。直至满足给定的精度为管理工程学院《运筹学》14例求解f(x)=-18x2+72x+28的极大值点，≤0.1，起始搜索区间为[0,3]解：①用间接法：令f’(x)=-36x+72=0，得驻点x=2又因为f’’(x)=-36＜0，故x=2为f(x)的极大值点，fmax=100②用直接法中的黄金分割法：令n-1=，得n=1+(lg)/(lg)≈5.78442约6步即可，计算结果见下表：kakbkf(ak)f(bk)pk=bk-akpk/p0x1k=ak+·pkx2k=bk-·pkf(x2k)△f(x1k)0032882311.8541.14686.9＜99.62f(x)xo3x1x2100f,2x*max*11.146386.9821.8540.6182.2921.85499.62＞98.4621.1462.29286.998.461.1460.3821.8541.58496.89＜99.6231.5842.29296.8998.460.7080.2362.0221.85499.62＜99.9941.8542.29299.6298.460.4380.1462.1252.02299.99＞98.7251.8542.12599.6299.720.2710.0903管理工程学院《运筹学》152.3无约束条件下多变量函数寻优一、爬山法原理：通过点的直接移动，逐步改善目标函数取值，直至达到极值点为止。由以下二部分组成：①选定搜索方向；②在选定的方向上爬山搜索。二、变量轮换法(或降维法):选择与坐标轴平行的方向为搜索方向设S=f(X)=f(x1,x2,…,xn)，极值点存在的区间为x1*[a1,b1]，x2*[a2,b2]，…，xn*[an,bn]1、原理：①从起点X(0)出发，沿平行于x1轴的方向P(1)进行一维搜索，求得f(X)在该方向P(1)上近似极值点X(1)；②从点X(1)出发，沿平行于x2轴的方向P(2)进行一维搜索，求得f(X)在该方向P(2)上近似极值点X(2)；③从点X(2)出发，照此交替进行下去，直至满足给定的精度为止|f(X(k))-f(X(k-1))|＜或|S(k)-S(k-1)|＜管理工程学院《运筹学》162、算法步骤：设S=f(X)=f(x1,x2)，极值点存在的区间为x1*[a1,b1]，x2*[a2,b2]第一步：从X(0)=(x1(0),x2(0))T出发①先固定x1=x1(0):求以x2为单变量的目标函数的极值点，得X(1)=(x1(0),x2(1))T，S(1)=f(X(1))