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

1、高级运筹学北京物资学院研究生课程北京物资学院研究生课程信息学院信息学院 李珍萍李珍萍Operations Research,Operational Reasearch直译为直译为“运用研究运用研究”或或 “作业研究作业研究”许国志等根据史记中：许国志等根据史记中：“运筹于帷幄之中，决运筹于帷幄之中，决胜于千里之外胜于千里之外”将其翻译成将其翻译成“运筹学运筹学”运筹学是运用科学的数量方法运筹学是运用科学的数量方法主要是数学模主要是数学模型型研究对人力、物力进行合理筹划和运用，研究对人力、物力进行合理筹划和运用，寻找管理及决策最优方案的综合性学科。寻找管理及决策最优方案的综合性学科。本学期教学内

2、容本学期教学内容 非线性规划非线性规划 第一章：非线性规划模型及基本概念第一章：非线性规划模型及基本概念 第二章：无约束非线性规划第二章：无约束非线性规划 第三章：约束非线性规划第三章：约束非线性规划 第四章：多目标规划第四章：多目标规划 现代优化算法简介现代优化算法简介 非线性规划非线性规划教学参考书教学参考书1 1 施光燕、董加礼施光燕、董加礼,最优化方法最优化方法 高等教育出版社，高等教育出版社，20042004。2 2 施光燕、钱伟懿，庞丽萍，最优化方法（第二版）高等施光燕、钱伟懿，庞丽萍，最优化方法（第二版）高等 教育出版社，教育出版社，20072007。3 3 郭科等郭科等 最优化

3、方法及应用，高等教育出版社，最优化方法及应用，高等教育出版社，2007 2007。非线性规划模型非线性规划模型及基本概念及基本概念信息学院信息学院 李珍萍李珍萍20152015年年9 9月月研究生研究生高级运筹学高级运筹学课件课件本章内容 一、非线性规划的数学模型一、非线性规划的数学模型 1.1.非线性规划问题实例非线性规划问题实例 2.2.非线性规划问题的数学模型非线性规划问题的数学模型 二、基本概念二、基本概念例例1 把边长为把边长为a的正方形铁板的四个角处剪去相等的正的正方形铁板的四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最方形以制成方形无盖水槽，问如何剪法使水槽

4、的容积最大？大？解：设剪去的正方形边长为解：设剪去的正方形边长为x（0 x a/2),做成的无盖水做成的无盖水槽体积为：槽体积为：2()(2)f xaxx该问题的数学模型为：求该问题的数学模型为：求x（0 x a/2)，使使 f(x)达到达到最大，即：最大，即：20/2max()(2)x af xaxx 1.1.非线性规划问题实例非线性规划问题实例一、非线性规划的数学模型一、非线性规划的数学模型例例2 已知某规划区内有已知某规划区内有m个客户，第个客户，第i个客户的位置坐标为个客户的位置坐标为(ai,bi)，现要在该区域内选定一个位置建立配送中心为客户供，现要在该区域内选定一个位置建立配送中心

5、为客户供应商品。问如何选定配送中心的位置，才能使配送中心到各应商品。问如何选定配送中心的位置，才能使配送中心到各用户的总距离最小？用户的总距离最小？解：设配送中心的位置坐标为解：设配送中心的位置坐标为(x1,x2),则则2212121min(,)()()miiif x xxaxb例例3 3 求表面积为常数求表面积为常数6a2(a0),体积最大的长方体体积。体积最大的长方体体积。解：设长方体的长、宽、高分别为解：设长方体的长、宽、高分别为x1,x2,x3.则则1231232121323123max(,).2()60,0,0f x xxx x xstx xx xx xaxxx例例4 设有设有400

6、万元资金，要求万元资金，要求4年内使用完，若在一年内使用年内使用完，若在一年内使用资金资金x万元，则可得效益万元，则可得效益 万元（已使用的资金不能再次使万元（已使用的资金不能再次使用，获得的效益当年不能使用），当年不用的资金可存入银用，获得的效益当年不能使用），当年不用的资金可存入银行，年利率为行，年利率为10%,试制定出资金使用规划，使试制定出资金使用规划，使4年的效益之年的效益之和最大和最大.x解：设解：设xi(i=1,2,3,4)分别表示第分别表示第i年所使用的资金数，则年所使用的资金数，则12341211311224112233max()04000(400)1.1.0(400)1.1

7、 1.10(400)1.1 1.1 1.1f xxxxxxxxxstxxxxxxxxxxxx123411121122311223341234max()4001.1440.1.211.11.14841.3311.211.211.11.1532.4,0f xxxxxxxxxstxxxxxxxxxxxxx x x x化简得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

8、)-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.79

9、26 0.000000 X(4)152.9036 0.000000例例5 5 某公司专门生产储藏用的容器，订货合同要求该公某公司专门生产储藏用的容器，订货合同要求该公司制造一种敞口的长方体容器，容积为司制造一种敞口的长方体容器，容积为12 m12 m3 3,该容器的该容器的底必须为正方形，容器总重量不超过底必须为正方形，容器总重量不超过68kg68kg，已知制作容，已知制作容器四壁的材料为每平方米器四壁的材料为每平方米1010元，重元，重3kg3kg；制作容器底的材；制作容器底的材料每平方米料每平方米2020元，重元，重2kg2kg。试问制造该容器所需的最小费。试问制造该容器所需的最小费用是多

10、少？用是多少？解：设该容器的底边长和高分别为解：设该容器的底边长和高分别为x1 m,和和x2 m.则则2121212211212min()4020.1221268,0f xx xxstx xxx xx xSETS: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 Tot

11、al solver iterations:78 Variable Value Reduced Cost X(1)4.000000 0.000000 X(2)0.7500000 0.000000例例6 有一底面为长方形的烤箱，长为有一底面为长方形的烤箱，长为L，宽为，宽为W。某公司要。某公司要为该烤箱制造一批蛋糕烤盘，要求蛋糕烤盘的底面积为为该烤箱制造一批蛋糕烤盘，要求蛋糕烤盘的底面积为A,底面形状为矩形两端加半圆（如下图所示）。问如何设计烤底面形状为矩形两端加半圆（如下图所示）。问如何设计烤盘尺寸才能使烤箱一次烤出的蛋糕数量达到最多？盘尺寸才能使烤箱一次烤出的蛋糕数量达到最多？解：假设烤箱中的

12、烤盘按行列整齐排放。解：假设烤箱中的烤盘按行列整齐排放。设烤箱中可放置的烤盘数量为设烤箱中可放置的烤盘数量为n行，行，m 列。每个烤盘所占最列。每个烤盘所占最大矩形的长、宽分别为大矩形的长、宽分别为x,y，烤盘两端的半圆半径为，烤盘两端的半圆半径为r。显然显然2r等于等于x,y的最小值。的最小值。22max42(1).22,0,00,1fmnmxLnyWxyrrArkxk ys trxryr x ym nk 且且为为整整数数1,20,2rxkry 一般最优化问题的数学模型一般最优化问题的数学模型min()(1).()0(1,2,.,)(2)()0(1,2,.,)(3)jinf xst h xj

13、lg ximxR如果目标函数和约束条件都是线性函数，则称为如果目标函数和约束条件都是线性函数，则称为线性规划线性规划。否则称为否则称为非线性规划非线性规划。如果要求部分或全部变量为整数，则称为如果要求部分或全部变量为整数，则称为整数规划整数规划。2.非线性规划问题的数学模型非线性规划问题的数学模型无约束非线性规划问题无约束非线性规划问题一般非线性规划问题的数学模型一般非线性规划问题的数学模型min()(1).()0(1,2,.,)(2)()0(1,2,.,)(3)jinf xst h xjlg ximxRmin()nx Rf x二、基本概念二、基本概念1.局部极小点局部极小点：现有多元函数 f

14、(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方向的方向导数，方向的方向导数，记作记作 1:RRfn0000()()()limtf xf xtef xPt0()f xP3.3.下降方向下降方向4.梯度：定义定义:以f(x)的n个偏导数为分量的向量称为f(x)

15、在x处的梯度，记为梯度也可以称为函数 f(x)关于向量 x 的一阶导数.12()()()()Tnf xf xf xf xxxx若0()0Tf xP则P是函数f(x)在点x0处的下降方向。0()0Tf xP则P是函数f(x)在点x0处的上升方向。若5.5.梯度和方向导数的关系梯度和方向导数的关系00()()Tf xf xeP 其中e是方向P上的单位向量。(1)梯度方向是函数值的最速上升方向；(2)函数在与其梯度正交的方向上变化率为零；(3)函数在与其梯度成锐角的方向上是上升的，而在与其梯度成钝角的方向上是下降的；(4)梯度反方向是函数值的最速下降方向例7：求函数 f(x)=x12+x22+1在(

16、0，3)T 处的最速下降方向，并求沿最速下降方向移动一个单位后新的目标函数值。122()2xf xx(0,3)0()|6f x沿最速下降方向移动一个单位后的点为(0，2)T，新的目标函数值为 5.解：定义:若f(x)二阶可微，则以其二阶偏导数为元素构成的下列矩阵称为f(x)的Hesse矩阵22221121222222122222212()()()()()()()()()()nnnnnf xf xf xxx xx xf xf xf xf xx xxx xf xf xf xx xx xx6.Hesse 6.Hesse 矩阵矩阵例8 求下列函数的梯度及hesse矩阵23132221233241432

17、)(xxxxxxxxxXf32112322213321342()64642xx xxf xxxxxxx x212132123112222()21242462xxxxf xxxxx7.泰勒展开式泰勒展开式设f(x)具有二阶连续偏导数，则其中21()()()()2TTf xPf xf xPPf x PxxP018.8.凸函数凸函数若f(x)是定义在n维欧氏空间Rn中某个凸集S上的函数，若对任何实数（0 1）以及S中任意两点 x(1),x(2)(x(1)x(2),恒有(1)(2)(1)(2)(1)()(1)()fxxf xf x则称f(x)为定义在凸集S上的凸函数。若(1)(2)(1)(2)(1)()(1)()fxxf xf x则称f(x)为定义在凸集S上的严格凸函数。xyx(1)x(2)y=f(x)凸函数的几何意义：当x为单变量时，凸函数的任意两点间的曲线段总在弦的下方。