第七章运筹学.ppt

《第七章运筹学.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章非线性数规划NonlinearProgramming§1问题的提出[eg.1]某单位拟建一排厂房，厂房建筑平面如图所示。由于资金及材料的限制，围墙及隔墙的总长度不能超过80米。为使建筑面积最大，应如何选择长宽尺寸？分析：设长为米，宽为米，则有f(x)为非线性函数1例2设某物理过程具有如下规律用试验法。现要确定参数使所得试验点构成的曲线与理论曲线误差平方和为最小，且满足2非线性规划：目标函数或（和）约束条件为非线性函数的规划。分析：f(x)为非线性函数，求最小。3§2基本概念2.1非线性规划的数学模型数学模型的

2、一般描述4或52.2非线性规划的图示例1求解如下非线性规划问题o22666分析：非线性规划的最优解可能在可行域的任一点达到。72.3极值问题极值存在的条件89101112132.4凸函数与凸规划1、凸函数与凹函数14函数f(x)图示152、凸性的判别16例3173.凸函数的极值对于定义在凸集上的凸函数，其极小点就是最小点，极小值就是最小值。4.凸规划下述问题为凸规划.18凸规划的局部最优解为全局最优解，当凸规划的目标函数为严格凸函数时，若存在最优解，则最优解必定唯一。凸规划是一类比较简单而又具有重要理论意义的非线性

3、规划。19例如下非线性规划是否为凸规划：20的海赛矩阵：所以，该问题为凸规划。21如图所示，该问题最优解（最小点）在C点取得。225.下降迭代算法下降迭代算法23几种终止迭代的准则：24§3无约束非线性规划的解法无约束非线性规划的数学描述解法分类：解析法：用函数的解析性（一阶、二阶导数）。梯度法、共扼梯度法、变尺度法等。直接法：用问题的函数值。步长加速法。25梯度法1.基本原理26对于充分小的272、求解步骤(1)28其中重复迭代，直至满足精度为止。29例30找下一点31于是32几何分析D(1,1)对于等值线为圆的

4、无约束极小化问题，不管初始点选在哪里，只要一次迭代即可求得最优解。33§4有约束的非线性规划有约束非线性规划数学描述344.1库恩-塔克(Kuha-Tucker)条件1.几何说明35对于362.库恩-塔克(Kuha-Tucker)条件设37式中38例用K-T条件求解如下非线性规划。39引入乘子40讨论：练习P1917.77.17(b)414.2二次规划二次规划的数学描述421.二次规划的K-T条件求相应问题梯度43引拉格朗日乘子442.线性规划描述引入松弛变量及人工变量45取46于是得到相应的线性规划问题。47以4

5、8例题149解505152535455小结一、数学描述数学模型的一般描述56二、极值问题57三、凸函数与凸规划582.凸规划下述问题为凸规划.59四、无约束非线性规划(1)60其中：61五、有约束非线性规划有约束非线性规划数学描述621.K-T条件632.二次规划(1)二次规划的数学描述64(2)线性规划描述以65例题2设非线性规划为试将非线性规划问题化为线性规划。66解67686970000001-657x30106100-601z210150-100-22z11z2z1y3y2y1x3x2x1bXBCB1100

6、000071