单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,高级运筹学,北京物资学院研究生课程,信息学院 李珍萍,高级运筹学北京物资学院研究生课程信息学院 李珍萍,Operations Research,O,p,erational Reasearch,直译为,“,运用研究,”,或,“,作业研究,”,许国志等根据史记中：,“,运筹于帷幄之中，决胜于千里之外,”,将其翻译成,“,运筹学,”,运筹学是运用科学的数量方法,主要是数学模型,研究对人力、物力进行合理筹划和运用，寻找管理及决策最优方案的综合性学科。,Operations Research,Operation,本学期教学内容,非线性规划,第一章：非线性规划模型及基本概念,第二章：无约束非线性规划,第三章：约束非线性规划,第四章：多目标规划,现代优化算法简介,本学期教学内容 非线性规划,非线性规划,教学参考书,1,施光燕、董加礼,最优化方法 高等教育出版社，,2004,。,2,施光燕、钱伟懿，庞丽萍，最优化方法（第二版）高等 教育出版社，,2007,。,3,郭科等 最优化方法及应用，高等教育出版社，,2007,。,非线性规划教学参考书,非线性规划模型及基本概念,信息学院 李珍萍,2015,年,9,月,研究生,高级运筹学,课件,非线性规划模型及基本概念信息学院 李珍萍研究生高级运筹学,本章内容,一、非线性规划的数学模型,1.,非线性规划问题实例,2.,非线性规划问题的数学模型,二、基本概念,本章内容一、非线性规划的数学模型,例,1,把边长为,a,的正方形铁板的四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？,解：设剪去的正方形边长为,x,（,0,x,a/2),做成的无盖水槽体积为：,该问题的数学模型为：求,x,（,0 x a/2),，,使,f(x),达到最大，即：,1.,非线性规划问题实例,一、非线性规划的数学模型,例1 把边长为a的正方形铁板的四个角处剪去相等的正方形以制,例,2,已知某规划区内有,m,个客户，第,i,个客户的位置坐标为,(,a,i,b,i,),，现要在该区域内选定一个位置建立配送中心为客户供应商品。问如何选定配送中心的位置，才能使配送中心到各用户的总距离最小？,解：设配送中心的位置坐标为,(,x,1,x,2,),则,例2 已知某规划区内有m个客户，第i个客户的位置坐标为(a,例,3,求表面积为常数,6a,2,(a0),体积最大的长方体体积。,解：设长方体的长、宽、高分别为,x,1,x,2,x,3,.,则,例3 求表面积为常数6a2(a0),体积最大的长方体,例,4,设有,400,万元资金，要求,4,年内使用完，若在一年内使用资金,x,万元，则可得效益 万元（已使用的资金不能再次使用，获得的效益当年不能使用），当年不用的资金可存入银行，年利率为,10%,试制定出资金使用规划，使,4,年的效益之和最大,.,解：设,x,i,(i=1,2,3,4),分别表示第,i,年所使用的资金数，则,例4 设有400万元资金，要求4年内使用完，若在一年内使用,化简得,化简得,SETS:,N/1.4/:X;,ENDSETS,max=sum(N(i):X(i)0.5);,X(1)400;,1.1*X(1)-(X(1)(1/2)+X(2)440;,1.21*X(1)-1.1*(X(1)(1/2)+1.1*X(2)-(X(2)(1/2)+X(3)484;,1.331*X(1)-1.21*(X(1)(1/2)+1.21*X(2)-1.1*(X(2)(1/2)+1.1*X(3)-(X(3)(1/2)+X(4)532.4;,Local optimal solution found.,Objective value:44.48003,Infeasibilities:0.1136868E-12,Extended solver steps:5,Total solver iterations:86,Variable Value Reduced Cost,X(1)94.96247 0.1572583E-08,X(2)113.9322 0.1183437E-08,X(3)136.7926 0.000000,X(4)152.9036 0.000000,SETS:Local optimal solution f,例,5,某公司专门生产储藏用的容器，订货合同要求该公司制造一种敞口的长方体容器，容积为,12 m,3,该容器的底必须为正方形，容器总重量不超过,68kg,，已知制作容器四壁的材料为每平方米,10,元，重,3kg,；制作容器底的材料每平方米,20,元，重,2kg,。试问制造该容器所需的最小费用是多少？,解：设该容器的底边长和高分别为,x,1,m,和,x,2,m,.,则,例5 某公司专门生产储藏用的容器，订货合同要求该公司制造一种,SETS:,N/1.2/:X;,ENDSETS,min=40*X(1)*X(2)+20*(X(2)2;,(X(1)2*X(2)=12;,2*(X(1)2+12*X(1)*X(2)68;,Local optimal solution found.,Objective value:131.2500,Infeasibilities:0.1399592E-10,Extended solver steps:5,Total solver iterations:78,Variable Value Reduced Cost,X(1)4.000000 0.000000,X(2)0.7500000 0.000000,SETS:Local optimal solution f,例,6,有一底面为长方形的烤箱，长为,L,，宽为,W,。某公司要为该烤箱制造一批蛋糕烤盘，要求蛋糕烤盘的底面积为,A,底面形状为矩形两端加半圆（如下图所示）。问如何设计烤盘尺寸才能使烤箱一次烤出的蛋糕数量达到最多？,例6 有一底面为长方形的烤箱，长为L，宽为W。某公司要为该烤,解：假设烤箱中的烤盘按行列整齐排放。,设烤箱中可放置的烤盘数量为,n,行，,m,列。每个烤盘所占最大矩形的长、宽分别为,x,y,，烤盘两端的半圆半径为,r,。,显然,2r,等于,x,y,的最小值。,解：假设烤箱中的烤盘按行列整齐排放。,一般最优化问题的数学模型,如果目标函数和约束条件都是线性函数，则称为,线性规划,。,否则称为,非线性规划,。,如果要求部分或全部变量为整数，则称为,整数规划,。,2.,非线性规划问题的数学模型,一般最优化问题的数学模型如果目标函数和约束条件都是线性函数，,无约束非线性规划问题,一般非线性规划问题的数学模型,无约束非线性规划问题一般非线性规划问题的数学模型,二、基本概念,1.,局部极小点,：,现有多元函数,f(x,1,x,2,x,n,),若点,x,0,=(x,1,0,x,2,0,x,n,0,),T,存在一邻域,(x,0,),使对任意,x,(x,0,),均有,f(x,0,)f(x),则称,x,0,是,f(x),的局部极小点。,二、基本概念1.局部极小点：,2.,方向导数,定义,:,设 在点,x,0,处可微，,P,是固定不变的非零向量，,e,是方向,P,上的单位向量，则称极限,为函数,f(x),在点,x,0,处沿,P,方向的方向导数，,记作,2.方向导数,3.,下降方向,3.下降方向,4.,梯度：,定义,:,以,f(x),的,n,个偏导数为分量的向量称为,f(x),在,x,处的梯度，记为,梯度也可以称为函数,f(x),关于向量,x,的一阶导数,.,4.梯度：梯度也可以称为函数 f(x)关于向量 x 的一,若,则,P,是函数,f(x),在点,x,0,处的下降方向。,则,P,是函数,f(x),在点,x,0,处的上升方向。,若,5.,梯度和方向导数的关系,其中,e,是方向,P,上的单位向量。,若则P是函数f(x)在点x0处的下降方向。则P是函数f(x),(1),梯度方向是函数值的最速上升方向；,(2),函数在与其梯度正交的方向上变化率为零；,(3),函数在与其梯度成锐角的方向上是上升的，而在与其梯度成钝角的方向上是下降的；,(4),梯度反方向是函数值的最速下降方向,(1)梯度方向是函数值的最速上升方向；,例,7,：求函数,f(x)=x,1,2,+x,2,2,+1,在,(0,，,3),T,处的最速下降方向，并求沿最速下降方向移动一个单位后新的目标函数值。,沿最速下降方向移动一个单位后的点为,(0,，,2),T,，新的目标函数值为,5,.,解：,例7：求函数 f(x)=x12+x22+1在(0，3)T,定义,:,若,f(x),二阶可微，则以其二阶偏导数为元素构成的下列矩阵称为,f(x),的,Hesse,矩阵,6.Hesse,矩阵,定义:若f(x)二阶可微，则以其二阶偏导数为元素构成的下,例,8,求下列函数的梯度及,hesse,矩阵,例8 求下列函数的梯度及hesse矩阵,7.,泰勒展开式,设,f(x),具有二阶连续偏导数，则,其中,7.泰勒展开式其中,8.,凸函数,若,f(x),是定义在,n,维欧氏空间,R,n,中某个凸集,S,上的函数，若对任何实数,（,0,1,）以及,S,中任意两点,x,(1),x,(2),(,x,(1),x,(2),),恒有,则称,f(x),为定义在凸集,S,上的凸函数。,若,则称,f(x),为定义在凸集,S,上的严格凸函数。,8.凸函数则称f(x)为定义在凸集S上的凸函数。若则称f(,x,y,x,(1,),x,(2,),y=f(x),凸函数的几何意义：当,x,为单变量时，凸函数的任意两点间的曲线段总在弦的下方。,xyx(1)x(2)y=f(x)凸函数的几何意义：当x为单变,