《清华大学《运筹学》第四章.ppt》由会员分享，可在线阅读，更多相关《清华大学《运筹学》第四章.ppt（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章 非线性数规划非线性数规划 Nonlinear Programming1 1 问题的提出问题的提出 eg.1 某单位拟建一排厂房，厂房建筑平面如图所示。由于资金及材料的限制，围墙及隔墙的总长度不能超过80米。为使建筑面积最大，应如何选择长宽尺寸？分析：设长为 米，宽为 米，则有 f(x)为非线性函数1例2 设某物理过程具有如下规律 用试验法 。现要确定参数 使所得试验点构成的曲线与理论曲线误差平方和为最小，且满足 2非线性规划：目标函数或（和）约束条件为非线性函数的规划。分析：f(x)为非线性函数，求最小。32 2 基本概念2.1非线性规划的数学模型数学模型的一般描述4或52.2非
2、线性规划的图示例1 求解如下非线性规划问题o2 22 26 66 66分析：非线性规划的最优解可能在可行域的任一点达到。72.3极值问题极值存在的条件89101112132.4凸函熟与凸规划1、凸函熟与凹函熟14 函数f(x)图示152、凸性的判别16例3173.凸函数的极值 对于定义在凸集上的凸函数，其极小点就是最小点，极小值就是最小值。4.凸规划 下述问题为凸规划.18 凸规划的局部最优解为全局最优解，当凸规 划的目标函数为严格凸函数时，若存在最优解，则最优解必定唯一。凸规划是一类比较简单而又具有重要理论意义的非线性规划。19例 如下非线性规划是否为凸规划：20 的海赛矩阵：所以，该问题为
3、凸规划。21 如图所示，该问题最优解（最小点）在C点取得。225.下降迭代算法 下降迭代算法23几种终止迭代的准则：243无约束非线性规划的解法无约束非线性规划的数学描述解法分类：解析法：用函数的解析性（一阶、二阶导数）。梯度法、共扼梯度法、变尺度法等。直接法：用问题的函数值。步长加速法。25梯度法1.基本原理26对于充分小的272、求解步骤(1)28其中重复迭代，直至满足精度为止。29例30找下一点31于是32几何分析D D(1,1)(1,1)对于等值线为圆的无约束极小化问题，不管初始点选在哪里，只要一次迭代即可求得最优解。334 有约束的非线性规划有约束非线性规划数学描述344.1 库恩-塔克(Kuha-Tucker)条件1.几何说明35对于362.库恩-塔克(Kuha-Tucker)条件 设37式中38例 用K-T条件求解如下非线性规划。39引入乘子40讨论：414.2 二次规划二次规划的数学描述421.二次规划的K-T条件求相应问题梯度43引拉格朗日乘子442.线性规划描述引入松弛变量及人工变量45取46于是得到相应的线性规划问题。47 以4849