数学规划导论和预备知识精.ppt

《数学规划导论和预备知识精.ppt》由会员分享，可在线阅读，更多相关《数学规划导论和预备知识精.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学规划导论和预备数学规划导论和预备知识知识第1页，本讲稿共29页教材：教材：黄红选，韩继业编著，数学规划，清华大学出版社黄红选，韩继业编著，数学规划，清华大学出版社参考书目：参考书目：1.陈宝林，最优化理论与算法（第陈宝林，最优化理论与算法（第2版），清华大版），清华大学出版社学出版社2.袁亚湘，最优化理论与方法，科学出版社袁亚湘，最优化理论与方法，科学出版社3.何坚勇，最优化方法，清华大学出版社何坚勇，最优化方法，清华大学出版社4.Operations Research(Mathematical Programming)(Third Edition),WAYNE L.WINSTON,清华大

2、学出版社清华大学出版社2第2页，本讲稿共29页平时成绩（30%）+期末成绩（70%）考试形式：开卷开卷3第3页，本讲稿共29页主要内容绪论和预备知识绪论和预备知识（第（第1章、第章、第2章）章）线性规划线性规划（第（第3章、第章、第7章）章）一般线性规划一般线性规划整数规划整数规划非线性规划非线性规划（第（第4章、第章、第5章）章）无约束非线性规划无约束非线性规划约束非线性规划约束非线性规划4第4页，本讲稿共29页绪论和预备知识绪论和预备知识l最优化的发展史最优化的发展史l最优化例子最优化例子l相关数学概念和理论相关数学概念和理论第5页，本讲稿共29页什么是最优化？什么是最优化？生产计划安排中

3、选择怎样的方案才能获得最高的利润生产计划安排中选择怎样的方案才能获得最高的利润有限的资源如何分配使得既能满足各方面要求并获得有限的资源如何分配使得既能满足各方面要求并获得最好的经济效益最好的经济效益工程设计中如何选择参数使得既能满足要求又能降工程设计中如何选择参数使得既能满足要求又能降低成本低成本对抗赛时实施更有效的策略，田忌赛马对抗赛时实施更有效的策略，田忌赛马等等等等第6页，本讲稿共29页需解决两方面的问题：需解决两方面的问题：l什么样的方案最优？l如何找出最优方案？数学规划（最优化）数学规划（最优化）数学规划（最优化）数学规划（最优化）正是为解决这些问题提供理论基础正是为解决这些问题提供

4、理论基础和求解方法。它是应用广泛、实用性很强的学科。和求解方法。它是应用广泛、实用性很强的学科。第7页，本讲稿共29页数学规划的发展史数学规划的发展史二战之前，自然科学中的最优化二战之前，自然科学中的最优化lFermat,1637;Newton,1670 lEuler,1755 lLagrange,1797lCauchy，1847最速下降法最速下降法lFermat,1637;Newton,1670lEuler,1755lLagrange,1797lCauchy，1847最速下降法最速下降法第8页，本讲稿共29页二战以后二战以后原苏联数学家原苏联数学家康托洛维奇下料问题和运输问题康托洛维奇下料问

5、题和运输问题1939 生产组织与管理中的数学方法生产组织与管理中的数学方法1960 最佳资源利用的经济计算最佳资源利用的经济计算1975 诺贝尔经济学奖诺贝尔经济学奖美国美国Dantzig线性规划线性规划 1947 单纯型算法单纯型算法Kuhn和和Tucker非线性规划非线性规划 1950 Kuhn-Tucker条件条件第9页，本讲稿共29页例1运输问题第10页，本讲稿共29页目目标标变量变量subject to,受限制受限制于，约束于，约束条件是条件是第11页，本讲稿共29页例例2生产问题生产问题l某厂生产两种产品，需要三种资源，已知各产品的某厂生产两种产品，需要三种资源，已知各产品的利润、

6、各资源的限量和各产品的资源消耗系数如下利润、各资源的限量和各产品的资源消耗系数如下表：表：产品产品A产品产品B资源限量资源限量劳动力劳动力设设 备备原材料原材料9434510360200300利润利润元元/kg70120问题：如何安排生产计划，使得获利最多？问题：如何安排生产计划，使得获利最多？第12页，本讲稿共29页Model：第13页，本讲稿共29页例例3（方程组的求解）（方程组的求解）l解非线性方程组是相当困难的一类问题，由于最优化方法的发展，对解非线性方程组提供了一种有力的手段解非线性方程组解非线性方程组在方程组有解的情况下，等价于求下列函数的极小在方程组有解的情况下，等价于求下列函数

7、的极小值点：值点：非线非线性最性最小二小二乘问乘问题题第14页，本讲稿共29页类似地，对于线性方程组类似地，对于线性方程组Ax=b的求解也的求解也可转化为一个最优问题，即求解可转化为一个最优问题，即求解线性最小二线性最小二线性最小二线性最小二乘问题乘问题乘问题乘问题第15页，本讲稿共29页一些成功的事例一些成功的事例 l最优化人员安排使美国航空公司每年节约最优化人员安排使美国航空公司每年节约2000万美元万美元；l优化货运路线让优化货运路线让Yellow Freight每年的节约超过每年的节约超过1730万美元万美元；lReynolds Metal公司通过改进卡车调度，提高了即时交付率，每年节

8、公司通过改进卡车调度，提高了即时交付率，每年节约货运成本约货运成本700万美元万美元；lGTE本地能力扩张每年节约本地能力扩张每年节约3000万美元万美元。lProctor&Gamble(保洁公司保洁公司)通过北美运营重构，削减了通过北美运营重构，削减了20%的厂房，的厂房，每年节约每年节约2亿美元亿美元；lDigital Equipment 通过优化全球供应链节约了通过优化全球供应链节约了3亿美元亿美元；l优化水热生成器安排让南部公司每年节约优化水热生成器安排让南部公司每年节约1.4亿美元亿美元；第16页，本讲稿共29页数学规划的分类数学规划的分类l l根据问题的不同特点分类根据问题的不同特

9、点分类l无约束极小化问题无约束极小化问题l等式约束极小化问题等式约束极小化问题l不等式约束极小化问题不等式约束极小化问题l一般约束极小化问题一般约束极小化问题l l根据函数类型的分类根据函数类型的分类l线性规划线性规划l非线性规划非线性规划l二次规划二次规划l整数规划整数规划l l根据解法的分类根据解法的分类l解析方法解析方法l直接方法直接方法约束最优化问题约束最优化问题 无约束最优化问题无约束最优化问题第17页，本讲稿共29页最优化术语：最优化术语：l可行点（可行解）：可行点（可行解）：在数学规划中，满足所有约束条件的点。l可行域（可行集）可行域（可行集）：所有可行点组成的集合。l最优解（全

10、局极小点）最优解（全局极小点）:使得目标函数取得最小值的可行解l局部局部最优解（最优解（局部局部极小点）极小点）任意全局极小点必为局部极小点，但反过来不成立。任意全局极小点必为局部极小点，但反过来不成立。然而，对于然而，对于凸规划凸规划而言，局部极小点就是全局极小点。而言，局部极小点就是全局极小点。第18页，本讲稿共29页预备知识预备知识（多元函数分析）（多元函数分析）l梯度梯度lHesse矩阵矩阵lTaylor公式公式l极值的判别条件极值的判别条件（必要条件、充分条件）（必要条件、充分条件）l方向导数方向导数第19页，本讲稿共29页梯度梯度几种特殊类型函数的梯度公式几种特殊类型函数的梯度公式

11、第20页，本讲稿共29页Hesse矩阵矩阵第21页，本讲稿共29页Taylor公式公式第22页，本讲稿共29页极值的判别条件极值的判别条件一元函数：一元函数：设设f(x)的定义域为区间的定义域为区间D,x0为內点为內点，f(x)在点在点x0可可微，若微，若x0为极值点，则为极值点，则 必要条件必要条件：二元函数：二元函数：设设f(x,y)的定义域为区域的定义域为区域D,(x0,y0)为內点为內点，f(x,y)在点在点(x0,y0)可微，若可微，若(x0,y0)为极值点，则为极值点，则多元函数：多元函数：第23页，本讲稿共29页充分条件充分条件一元函数一元函数：设设f(x)的定义域为区间的定义域

12、为区间D,x0为內点为內点，f(x)在点在点x0二二次可微，次可微，(1)若若 ,则则x0为极小点为极小点(2)若若 ,则则x0为极大点为极大点第24页，本讲稿共29页若若 ,则则(x0,y0)是极值点。是极值点。当当 时，时，(x0,y0)是极小点。是极小点。当当 时，时，(x0,y0)是极大点。是极大点。二元函数：设设f(x,y)的定义域为区域的定义域为区域D,(x0,y0)为內点为內点，f(x,y)在点在点(x0,y0)二次可微，二次可微，第25页，本讲稿共29页多元函数：多元函数：l(1)x0为D的一个內点l(2)f(x)在点x0二次可微二次可微l(3)l(4)H(x0)0（H(x0)

13、0）则则x0是极小点是极小点(极大点极大点)。第26页，本讲稿共29页方向导数方向导数（偏导数偏导数 导数）导数）设有单位向量设有单位向量h=(h1,h2,.,hn)T,表示表示n维空间中的维空间中的一个方向，则可微函数一个方向，则可微函数f(x)在点在点x沿沿h的方向导数的方向导数为：为：1.函数沿各个方向的变化率函数沿各个方向的变化率2.从各个方向中求出从各个方向中求出f(x)变化最快的方向，亦即变变化最快的方向，亦即变化率最大的方向。化率最大的方向。第27页，本讲稿共29页对于方向导数，有以下结论：对于方向导数，有以下结论：l若 ，则h为f(x)在点x的上升方向；l若 ，则h为f(x)在点x的下降方向；l若 ，则对任何方向h，有l若 ，则当 时，取最大最小最小第28页，本讲稿共29页是这样一个向量：在点是这样一个向量：在点x，它指向，它指向f(x)增增加最快的方向，即加最快的方向，即f(x)的最速上升方向；的最速上升方向；是这样一个向量：在点是这样一个向量：在点x，它指向，它指向f(x)减少减少最快的方向，即最快的方向，即f(x)的最速下降方向；的最速下降方向；负梯度方向即为最速下降方向。负梯度方向即为最速下降方向。第29页，本讲稿共29页