数学规划导论和预备知识

数学规划导论和预备知识第1页，共29页，2023年，2月20日，星期六教材：黄红选，韩继业编著，数学规划，清华大学出版社参考书目：1.陈宝林，最优化理论与算法（第2版），清华大学出版社2.袁亚湘，最优化理论与方法，科学出版社3.何坚勇，最优化方法，清华大学出版社4.OperationsResearch(MathematicalProgramming)(ThirdEdition),WAYNEL.WINSTON,清华大学出版社2第2页，共29页，2023年，2月20日，星期六平时成绩（30%）+期末成绩（70%）考试形式：开卷3第3页，共29页，2023年，2月20日，星期六主要内容绪论和预备知识（第1章、第2章）线性规划（第3章、第7章）一般线性规划整数规划非线性规划（第4章、第5章）无约束非线性规划约束非线性规划4第4页，共29页，2023年，2月20日，星期六绪论和预备知识最优化的发展史最优化例子相关数学概念和理论第5页，共29页，2023年，2月20日，星期六什么是最优化？–生产计划安排中选择怎样的方案才能获得最高的利润–有限的资源如何分配使得既能满足各方面要求并获得最好的经济效益–工程设计中如何选择参数使得既能满足要求又能降低成本–对抗赛时实施更有效的策略，田忌赛马–等等第6页，共29页，2023年，2月20日，星期六需解决两方面的问题：什么样的方案最优？如何找出最优方案？数学规划（最优化）正是为解决这些问题提供理论基础和求解方法。它是应用广泛、实用性很强的学科。第7页，共29页，2023年，2月20日，星期六数学规划的发展史二战之前，自然科学中的最优化Fermat,1637;Newton,1670Euler,1755Lagrange,1797Cauchy，1847最速下降法Fermat,1637;

Newton,1670Euler,1755Lagrange,1797Cauchy，1847最速下降法第8页，共29页，2023年，2月20日，星期六二战以后原苏联数学家康托洛维奇－下料问题和运输问题1939《生产组织与管理中的数学方法》1960《最佳资源利用的经济计算》1975诺贝尔经济学奖美国Dantzig－线性规划

1947单纯型算法Kuhn和Tucker－非线性规划

1950Kuhn-Tucker条件第9页，共29页，2023年，2月20日，星期六例1—运输问题第10页，共29页，2023年，2月20日，星期六目标变量subjectto,受限制于，约束条件是第11页，共29页，2023年，2月20日，星期六例2—生产问题某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg70120问题：如何安排生产计划，使得获利最多？第12页，共29页，2023年，2月20日，星期六Model：第13页，共29页，2023年，2月20日，星期六例3（方程组的求解）解非线性方程组是相当困难的一类问题，由于最优化方法的发展，对解非线性方程组提供了一种有力的手段解非线性方程组在方程组有解的情况下，等价于求下列函数的极小值点：非线性最小二乘问题第14页，共29页，2023年，2月20日，星期六类似地，对于线性方程组Ax=b的求解也可转化为一个最优问题，即求解线性最小二乘问题第15页，共29页，2023年，2月20日，星期六一些成功的事例最优化人员安排使美国航空公司每年节约2000万美元；优化货运路线让YellowFreight每年的节约超过1730万美元；ReynoldsMetal公司通过改进卡车调度，提高了即时交付率，每年节约货运成本700万美元；GTE本地能力扩张每年节约3000万美元。Proctor&Gamble(保洁公司)通过北美运营重构，削减了20%的厂房，每年节约2亿美元；DigitalEquipment通过优化全球供应链节约了3亿美元；优化水热生成器安排让南部公司每年节约1.4亿美元；

第16页，共29页，2023年，2月20日，星期六数学规划的分类根据问题的不同特点分类无约束极小化问题等式约束极小化问题不等式约束极小化问题一般约束极小化问题根据函数类型的分类线性规划非线性规划二次规划整数规划根据解法的分类解析方法直接方法约束最优化问题

无约束最优化问题第17页，共29页，2023年，2月20日，星期六最优化术语：可行点（可行解）：在数学规划中，满足所有约束条件的点。可行域（可行集）：所有可行点组成的集合。最优解（全局极小点）:使得目标函数取得最小值的可行解局部最优解（局部极小点）任意全局极小点必为局部极小点，但反过来不成立。然而，对于凸规划而言，局部极小点就是全局极小点。第18页，共29页，2023年，2月20日，星期六预备知识（多元函数分析）梯度Hesse矩阵Taylor公式极值的判别条件（必要条件、充分条件）方向导数第19页，共29页，2023年，2月20日，星期六梯度几种特殊类型函数的梯度公式第20页，共29页，2023年，2月20日，星期六Hesse矩阵第21页，共29页，2023年，2月20日，星期六Taylor公式第22页，共29页，2023年，2月20日，星期六极值的判别条件一元函数：

设f(x)的定义域为区间D,x0为內点，f(x)在点x0可微，若x0为极值点，则

必要条件：二元函数：

设f(x,y)的定义域为区域D,(x0,y0)为內点，f(x,y)在点(x0,y0)可微，若(x0,y0)为极值点，则多元函数：第23页，共29页，2023年，2月20日，星期六充分条件一元函数：

设f(x)的定义域为区间D,x0为內点，f(x)在点x0二次可微，

(1)若,则x0为极小点(2)若,则x0为极大点第24页，共29页，2023年，2月20日，星期六若

,则(x0,y0)是极值点。当时，(x0,y0)是极小点。当时，(x0,y0)是极大点。二元函数：

设f(x,y)的定义域为区域D,(x0,y0)为內点，f(x,y)在点(x0,y0)二次可微，第25页，共29页，2023年，2月20日，星期六多元函数：(1)x0为D的一个內点(2)f(x)在点x0二次可微(3)(4)

H(x0)>0（

H(x0)<0

）则x0是极小点(极大点)。第26页，共29页，2023年，2月20日，星期六方向导数（偏导数导数）设有单位向量h=(h1,h2,...,hn)T,表示n维空间中的一个方向，则可微函数f(x)在点x沿h的方向导数为：1.函数沿各个方向的变化率2.从各个方向中求出f(x)变化最快的方向，亦即变化率最大的方向。第27页，共29页，2023年，2月20日，星期六对于方向导数，有以下结论：若，则h为f(x)在点x的上升方向；若，则h为f(x)在点x的下降方向；若，则对任何方向h，有若