《高级运筹学》非线性规划模型及基本概念.ppt

《《高级运筹学》非线性规划模型及基本概念.ppt》由会员分享，可在线阅读，更多相关《《高级运筹学》非线性规划模型及基本概念.ppt（30页珍藏版）》请在三一办公上搜索。

1、高级运筹学,北京物资学院研究生课程,信息学院 李珍萍,Operations Research,Operational Reasearch直译为“运用研究”或“作业研究”许国志等根据史记中：“运筹于帷幄之中，决胜于千里之外”将其翻译成“运筹学”,运筹学是运用科学的数量方法主要是数学模型研究对人力、物力进行合理筹划和运用，寻找管理及决策最优方案的综合性学科。,本学期教学内容,非线性规划 第一章：非线性规划模型及基本概念 第二章：无约束非线性规划 第三章：约束非线性规划 第四章：多目标规划 现代优化算法简介,非线性规划教学参考书,1 施光燕、董加礼,最优化方法 高等教育出版社，2004。2 施光燕、

2、钱伟懿，庞丽萍，最优化方法（第二版）高等 教育出版社，2007。3 郭科等 最优化方法及应用，高等教育出版社，2007。,非线性规划模型及基本概念,信息学院 李珍萍2015年9月,研究生高级运筹学课件,本章内容,一、非线性规划的数学模型 1.非线性规划问题实例 2.非线性规划问题的数学模型二、基本概念,例1 把边长为a的正方形铁板的四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？,解：设剪去的正方形边长为x（0 x a/2),做成的无盖水槽体积为：,该问题的数学模型为：求x（0 x a/2)，使 f(x)达到最大，即：,1.非线性规划问题实例,一、非线性规划的数学模型,

3、例2 已知某规划区内有m个客户，第i个客户的位置坐标为(ai,bi)，现要在该区域内选定一个位置建立配送中心为客户供应商品。问如何选定配送中心的位置，才能使配送中心到各用户的总距离最小？,解：设配送中心的位置坐标为(x1,x2),则,例3 求表面积为常数6a2(a0),体积最大的长方体体积。,解：设长方体的长、宽、高分别为x1,x2,x3.则,例4 设有400万元资金，要求4年内使用完，若在一年内使用资金x万元，则可得效益 万元（已使用的资金不能再次使用，获得的效益当年不能使用），当年不用的资金可存入银行，年利率为10%,试制定出资金使用规划，使4年的效益之和最大.,解：设xi(i=1,2,3

4、,4)分别表示第i年所使用的资金数，则,化简得,SETS:N/1.4/:X;ENDSETSmax=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 Infeasi

5、bilities: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,例5 某公司专门生产储藏用的容器，订货合同要求该公司制造一种敞口的长方体容器，容积为12 m3,该容器的底必须为正方形，容器总重量不超过68kg，已知制作容器四壁的材料为每平方米10元，重3kg；制作

6、容器底的材料每平方米20元，重2kg。试问制造该容器所需的最小费用是多少？,解：设该容器的底边长和高分别为x1 m,和x2 m.则,SETS:N/1.2/:X;ENDSETSmin=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 Va

7、lue Reduced Cost X(1)4.000000 0.000000 X(2)0.7500000 0.000000,例6 有一底面为长方形的烤箱，长为L，宽为W。某公司要为该烤箱制造一批蛋糕烤盘，要求蛋糕烤盘的底面积为A,底面形状为矩形两端加半圆（如下图所示）。问如何设计烤盘尺寸才能使烤箱一次烤出的蛋糕数量达到最多？,解：假设烤箱中的烤盘按行列整齐排放。设烤箱中可放置的烤盘数量为n行，m 列。每个烤盘所占最大矩形的长、宽分别为x,y，烤盘两端的半圆半径为r。显然2r等于x,y的最小值。,一般最优化问题的数学模型,如果目标函数和约束条件都是线性函数，则称为线性规划。否则称为非线性规划。如

8、果要求部分或全部变量为整数，则称为整数规划。,2.非线性规划问题的数学模型,无约束非线性规划问题,一般非线性规划问题的数学模型,二、基本概念,1.局部极小点：现有多元函数 f(x1,x2,xn),若点 x 0=(x10,x20,xn0)T 存在一邻域(x0),使对任意x(x0),均有 f(x0)f(x),则称 x 0是 f(x)的局部极小点。,2.方向导数 定义:设 在点x0处可微，P是固定不变的非零向量，e是方向P上的单位向量，则称极限 为函数f(x)在点x 0处沿P方向的方向导数，记作,3.下降方向,4.梯度：定义:以f(x)的n个偏导数为分量的向量称为f(x)在x处的梯度，记为,梯度也可

9、以称为函数 f(x)关于向量 x 的一阶导数.,若,则P是函数f(x)在点x0处的下降方向。,则P是函数f(x)在点x0处的上升方向。,若,5.梯度和方向导数的关系,其中e是方向P上的单位向量。,(1)梯度方向是函数值的最速上升方向；(2)函数在与其梯度正交的方向上变化率为零；(3)函数在与其梯度成锐角的方向上是上升的，而在与其梯度成钝角的方向上是下降的；(4)梯度反方向是函数值的最速下降方向,例7：求函数 f(x)=x12+x22+1在(0，3)T 处的最速下降方向，并求沿最速下降方向移动一个单位后新的目标函数值。,沿最速下降方向移动一个单位后的点为(0，2)T，新的目标函数值为 5.,解：,定义:若f(x)二阶可微，则以其二阶偏导数为元素构成的下列矩阵称为f(x)的Hesse矩阵,6.Hesse 矩阵,例8 求下列函数的梯度及hesse矩阵,7.泰勒展开式设f(x)具有二阶连续偏导数，则,其中,8.凸函数若f(x)是定义在n维欧氏空间Rn中某个凸集S上的函数，若对任何实数（0 1）以及S中任意两点 x(1),x(2)(x(1)x(2),恒有,则称f(x)为定义在凸集S上的凸函数。,若,则称f(x)为定义在凸集S上的严格凸函数。,x,y,x(1),x(2),y=f(x),凸函数的几何意义：当x为单变量时，凸函数的任意两点间的曲线段总在弦的下方。,