最优化计算方法(工程优化) 第1章

1、工工 程程 优优 化化 方方 法法任课教师：杨国平任课教师：杨国平 数学与统计学院数学与统计学院联系方式：联系方式： 最优化技术与数学模型是工程类研究生应掌握的数学基础最优化技术与数学模型是工程类研究生应掌握的数学基础课，是从事相应学科理论研究的前提。课，是从事相应学科理论研究的前提。 工程中许多实际问题都可以抽象为数学建模问题，数学模工程中许多实际问题都可以抽象为数学建模问题，数学模型包括最优化模型。型包括最优化模型。 了解最优化技术的基本原理、相关算法是分析问题、解了解最优化技术的基本原理、相关算法是分析问题、解决问题的一种技能，同时也是写出高水平学术论文的关键决问题的一种技能，同时也是写

2、出高水平学术论文的关键素材。素材。 最优化技术与数学模型所包括的知识点很多，选取了一些最优化技术与数学模型所包括的知识点很多，选取了一些实用的方法。实用的方法。 从工程应用的角度出发，注重工程优化的基本思想和从工程应用的角度出发，注重工程优化的基本思想和方法的阐述。方法的阐述。 内容主要包括内容主要包括: : 线性规划、非线性规划、约束优化、无约束优化等，线性规划、非线性规划、约束优化、无约束优化等， 并对如何建立数学模型、如何选择优化方法和提高优并对如何建立数学模型、如何选择优化方法和提高优化效率作了适当的介绍。化效率作了适当的介绍。 讲授工程优化的基本理论和方法，要求通过本课程的学习，讲授

3、工程优化的基本理论和方法，要求通过本课程的学习，具有应用工程优化方法解决实际问题的技能，并为以后的学具有应用工程优化方法解决实际问题的技能，并为以后的学习和工作打好基础。习和工作打好基础。 第一章第一章 绪论绪论 第二章第二章 基本概念和理论基础基本概念和理论基础 第三章第三章 线性规划线性规划 第四章第四章 最优化搜索算法结构与一维搜索最优化搜索算法结构与一维搜索 第五章第五章 无约束最优化方法无约束最优化方法 第六章第六章 约束最优化方法约束最优化方法最优化计算方法最优化计算方法陈开周编，西电出版社陈开周编，西电出版社最优化理论与方法最优化理论与方法袁亚湘等编，科学出版社袁亚湘等编，科学出

4、版社最优化理论与算法最优化理论与算法陈宝林编，清华大学出版社陈宝林编，清华大学出版社数学规划讲义数学规划讲义马仲蓄等编，人大出版社马仲蓄等编，人大出版社实用线性规划实用线性规划D.MD.M希梅尔布劳著希梅尔布劳著无约束最优化计算方法无约束最优化计算方法邓乃杨等编邓乃杨等编学科总成绩学科总成绩平时成绩平时成绩（=20=80=80）讲授为主，结合习题作业讲授为主，结合习题作业作业以章为单位，本章结束后交作业，部分作业会在课堂上讲评作业以章为单位，本章结束后交作业，部分作业会在课堂上讲评 什么是最优化什么是最优化 最优化问题的数学模型与分类最优化问题的数学模型与分类 最优化问题举例最优化问题举例 最

5、优化是一个重要的数学分支，是一门应用广泛、实最优化是一个重要的数学分支，是一门应用广泛、实用性很强的学科。简单地说用性很强的学科。简单地说, ,最优化就是从所有可能的方最优化就是从所有可能的方案中选择最合理的一种以达到最优目标的学科。案中选择最合理的一种以达到最优目标的学科。 达到最优目标的方案称为最优方案。达到最优目标的方案称为最优方案。 搜索最优方案的方法称为最优化方法。搜索最优方案的方法称为最优化方法。 这种方法的数学理论称为最优化理论。这种方法的数学理论称为最优化理论。n可能的方案可能的方案n追求的目标追求的目标后者是前者的函数后者是前者的函数. .如果第一要素与时间无关就称为静态最优

6、化问题，否则如果第一要素与时间无关就称为静态最优化问题，否则称为动态最优化问题。称为动态最优化问题。本课程主要讨论静态最优化问题。本课程主要讨论静态最优化问题。最优化就是从所有可能的方最优化就是从所有可能的方案中选择最合理的一种以达案中选择最合理的一种以达到最优目标的学科到最优目标的学科 公元前公元前500500年，古希腊在讨论建筑美学中就已发现了长方年，古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为形长与宽的最佳比例为1.618,1.618,称为黄金分割比。其倒数称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。至今在优选法中仍得到广泛应用。 在微积分出现以前，已有许多学者开始研

7、究用数学方法在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。阿基米德证明：给定周长，圆所包围解决最优化问题。阿基米德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。但是最优化方法真正形成为科学方法则在原因。但是最优化方法真正形成为科学方法则在1717世纪世纪以后。以后。 17 世纪，世纪，Newton & Leibniz 提出了函数的极值问题；后提出了函数的极值问题；后来出现了来出现了Lagrange乘数法；乘数法； 1847年，年，Cauchy研究了函数值沿什么方向下降最快的问研究了函数值沿

8、什么方向下降最快的问题，提出了最速下降法；题，提出了最速下降法； 1939年，苏联数学家提出解决下料问题和运输问题这两种年，苏联数学家提出解决下料问题和运输问题这两种线性规划问题的求解方法；线性规划问题的求解方法； 1947年，年，Dantzig 提出解线性规划问题的单纯形法，被称提出解线性规划问题的单纯形法，被称为为“20世纪最伟大的创作之一世纪最伟大的创作之一”； 1948年，年，Fritz John 提出最优性条件；提出最优性条件； 1951年，年，Kuhn和和Tucher 提出最优性条件，完成了非线性规提出最优性条件，完成了非线性规划的基础工作；划的基础工作； 近几十年来，最优化理论和

9、算法发展十分迅速，应用也越近几十年来，最优化理论和算法发展十分迅速，应用也越来越广泛，已成为一个相当庞大的研究领域；来越广泛，已成为一个相当庞大的研究领域； 狭义上主要指非线性规划问题的相关内容；狭义上主要指非线性规划问题的相关内容； 广义上则涵盖：线性规划、非线性规划、动态规划、整数广义上则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等等。最优控制等等。l由实际生产或科技问题形成最优化的数学模型由实际生产或科技问题形成最优化的数学模型. .l对所形成的最优化数学模型进行数学加工和求解

10、。对所形成的最优化数学模型进行数学加工和求解。对于第二方面的工作，目前已有一些较系统成熟的资料对于第二方面的工作，目前已有一些较系统成熟的资料第一方面工作即如何由实际问题抽象出数学模型，目前很少有系第一方面工作即如何由实际问题抽象出数学模型，目前很少有系统的资料，而这一工作在应用最优化技术解决实际问题时是十分统的资料，而这一工作在应用最优化技术解决实际问题时是十分关键的。关键的。 因此，我们在学习本课程时要尽可能了解如何因此，我们在学习本课程时要尽可能了解如何由实际问题形成最优化的数学模型。由实际问题形成最优化的数学模型。数学模型数学模型: : 对现实事物或问题的数学抽象或描述对现实事物或问题

11、的数学抽象或描述。 过于简单的数学模型所得到的结果可能不符合实际情过于简单的数学模型所得到的结果可能不符合实际情况；而过于详细复杂的模型又给分析计算带来困难。况；而过于详细复杂的模型又给分析计算带来困难。 具体建立怎样的数学模型需要丰富的经验和熟练的技具体建立怎样的数学模型需要丰富的经验和熟练的技巧。巧。 建立数学模型时要尽可能简单，而且要能完整地描建立数学模型时要尽可能简单，而且要能完整地描述所研究的系统。述所研究的系统。 一般的模型简化工作包括以下几类：一般的模型简化工作包括以下几类： （1）将离散变量转化为连续变量。）将离散变量转化为连续变量。 （2）将非线性函数线性化。）将非线性函数线

12、性化。 （3）删除一些非主要约束条件。）删除一些非主要约束条件。 在建立了问题的数学模型之后，通常也必须对模在建立了问题的数学模型之后，通常也必须对模型进行必要的数学简化以便于分析、计算。型进行必要的数学简化以便于分析、计算。其中：其中： 为决策变量为决策变量 为已知参数为已知参数 为随机因素为随机因素 为（一般或广义）函数为（一般或广义）函数 min,. .,( , )0,1,2,ijklijkfxys tgxylm 在在 的约束下求决的约束下求决策变量策变量x，使函数，使函数 达到极达到极小小min；若求极大；若求极大max，相当于一个，相当于一个min（-f）。）。ixjyk,lf g

13、,( , )0lijkgxy ,ijkfxy 决策变量是由数学模型的解确定的未知数。参数表示决策变量是由数学模型的解确定的未知数。参数表示系统的控制变量，有确定性的也有随机性的。系统的控制变量，有确定性的也有随机性的。 由于现实系统的客观物质条件限制，模型必须包括把由于现实系统的客观物质条件限制，模型必须包括把决策变量限制在它们可行值之内的约束条件，而这通常是决策变量限制在它们可行值之内的约束条件，而这通常是用约束的数学函数形式来表示的。用约束的数学函数形式来表示的。 其作为系统决策变量的一个数学函数来衡量系统的效其作为系统决策变量的一个数学函数来衡量系统的效率，即系统追求的目标。率，即系统追

14、求的目标。l 无约束最优化问题无约束最优化问题l 约束最优化问题约束最优化问题 等式约束优化问题等式约束优化问题 不等式约束优化问题不等式约束优化问题 minnx Rfx min. .0nx Rifxs t hx min. .01,2,nx Rifxs tgxim 标准形式标准形式1）2） -00iigxgx 0-00iiihxhxhx 一般的约束优化问题一般的约束优化问题 min. .0,1,2,nx Rifxs tgxim l 线性规划：目标函数、约束条件都是线性的线性规划：目标函数、约束条件都是线性的l 非线性规划：目标函数、约束条件中的函数不全是线性非线性规划：目标函数、约束条件中的函

15、数不全是线性 的。的。l 二次规划：目标函数为二次函数，约束条件中的函数为线二次规划：目标函数为二次函数，约束条件中的函数为线 性的。性的。l 动态与静态动态与静态l 随机与确定随机与确定l 单目标与多目标单目标与多目标l 解析方法解析方法: :利用函数的分析性质去构造迭代公式，使之收敛利用函数的分析性质去构造迭代公式，使之收敛 到极值点。到极值点。l 直接方法：按一定的数学原理，用尽量少的计算量，直接比直接方法：按一定的数学原理，用尽量少的计算量，直接比 较函数值的大小。较函数值的大小。1) 1) 提出问题：目标、约束、决策变量、参数提出问题：目标、约束、决策变量、参数2) 2) 建立模型：

16、变量、参数、目标之间的关系表示建立模型：变量、参数、目标之间的关系表示3) 3) 模型求解：数学方法及其他方法模型求解：数学方法及其他方法4) 4) 解的检验：制定检验准则、讨论与现实的一致性解的检验：制定检验准则、讨论与现实的一致性5) 5) 灵敏性分析：参数扰动对解的影响情况灵敏性分析：参数扰动对解的影响情况6) 6) 解的实施：回到实践中解的实施：回到实践中7) 7) 后评估：考察问题是否得到完满解决后评估：考察问题是否得到完满解决 最优化在物质运输、自动控制、机械设计、采矿冶金、经最优化在物质运输、自动控制、机械设计、采矿冶金、经济管理等科学技术各领域中有广泛应用。下面举几个简单的实济

17、管理等科学技术各领域中有广泛应用。下面举几个简单的实例。例。 把半径为把半径为1的实心金属球熔化后，铸成一个实心圆柱体，的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？问圆柱体取什么尺寸才能使它的表面积最小？决定圆柱体表面积大小有两个决策变量：圆柱体底面半决定圆柱体表面积大小有两个决策变量：圆柱体底面半径径r、高、高h。 问题的约束条件是所铸圆柱体重量与球重相等。即问题的约束条件是所铸圆柱体重量与球重相等。即 2343rhR 1. 0.R为金属比重 即：即：问题追求的目标问题追求的目标是圆柱体表面积最小，即是圆柱体表面积最小，即 min 则得原问题的数学模型：则

18、得原问题的数学模型： 利用在高等数学中所学的利用在高等数学中所学的Lagrange乘子法可求解本问题乘子法可求解本问题分别对分别对r, h,求偏导数求偏导数,并令其等于零并令其等于零.有有:0342hr24,3r h 222rhr 22min 224. .03rhrs tr h 224,223L r hrhrr h 所以，圆柱体的表面积为：所以，圆柱体的表面积为：222420202403LhrrhrLrrhrhLr h 32 / 3r 322 / 3h 23263S 多参数曲线拟合问题多参数曲线拟合问题 已知两个物理量已知两个物理量x和和y之间的依赖关系为之间的依赖关系为: 其中其中 为待定参

19、数为待定参数, 为确定这些参数为确定这些参数, 对对x,y测得测得m个实验点个实验点:试将确定参数的问题表示成最优化问题。试将确定参数的问题表示成最优化问题。214351ln 1expayaxaaa 12345,aaaaa 1,12,2,mmx yx yxy很显然对参数很显然对参数 任意给定的一组数值任意给定的一组数值,就由上式确就由上式确定了定了 y关于关于x的一个函数关系式的一个函数关系式,在几何上它对应一条曲线在几何上它对应一条曲线,这条曲线这条曲线不一定通过那不一定通过那m个测量点个测量点,而要产生而要产生“偏差偏差”.xy12345,aaaaa22114351ln 1 expmiii

20、aSyaxaaa 显然偏差显然偏差S越小越小,曲线就拟合得越好曲线就拟合得越好,说明参数值就选择得越好，说明参数值就选择得越好，从而我们的问题就转化为从而我们的问题就转化为5维无约束最优化问题。即：维无约束最优化问题。即：将测量点沿垂线方向到曲线的距离的将测量点沿垂线方向到曲线的距离的平方和作为这种平方和作为这种“偏差偏差”的度量的度量. 即即2211435min1ln 1 expmiiiayaxaaa 有一旅行团从有一旅行团从 出发要遍游城市出发要遍游城市 ，已知从已知从 到到 的旅费为的旅费为 ，问应如何安排行程使总，问应如何安排行程使总费用最小？费用最小？0v12,.,nv vvjviv

21、ijcl变量变量是否从是否从i第个城市到第第个城市到第j个城市个城市l约束约束每个城市只能到达一次、离开一次每个城市只能到达一次、离开一次1,0;ijx 001;0,1,. ,1;0,1,.nnijijjixinxjnl目标目标总费用最小总费用最小00nnijijijc x 0000min1;1,2,.,. .1;1,2,.,1,0,1,2,., ,1,2,.,nnijijijnijjnijiijc xxins txjnxin jn 线性函数又称一次函数，线性函数又称一次函数，一般表达式为一般表达式为y=cTx+bx=0或或1等价与等价与x(x-1)=0,显然不是线性函数显然不是线性函数靠近某

22、河流有两个化工厂，流经第一化工厂的河流流靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天量为每天500万万m3，在两个工厂之间有一条流量为，在两个工厂之间有一条流量为200万万m3的支流。两化工厂每天排放某种有害物质的工业污水的支流。两化工厂每天排放某种有害物质的工业污水分别为分别为2万万m3和和1.4万万m3。从第一化工厂排出的工业污水流。从第一化工厂排出的工业污水流到第二化工厂以前，有到第二化工厂以前，有20%可以自然净化。环保要求河流可以自然净化。环保要求河流中工业污水含量不能大于中工业污水含量不能大于0.2%。两化工厂处理工业污水。两化工厂处理工业污水的成本分别为的成本分别为10

23、00元元/万万m3和和800元元/万万m3。现在要问在满。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小两个工厂处理工业污水的费用最小.工厂工厂1工厂工厂2200万万m3500万万m3 变量变量：x1、x2-分别代表工厂分别代表工厂1和工厂和工厂2处理污水的数量处理污水的数量(万万m3)则目标函数：则目标函数：min z=1000 x1+800 x2约束条件：约束条件：化简有：化简有：第一段河流（工厂第一段河流（工厂1-工厂工厂2之间）：之间）：(2-x1)/500 0.2%第二段河流：第二段河流：

24、 0.8(2-x1) +(1.4-x2)/7000.2%此外有：此外有： x12； x21.4 min z=1000 x1+800 x2 s.t. x1 1 0.8x1 + x2 1.6 x1 2 x2 1.4 x1、x2 0配料配料每磅配料中的营养含量每磅配料中的营养含量钙钙蛋白质蛋白质纤维纤维每磅成本（元）每磅成本（元）石灰石石灰石谷物谷物大豆粉大豆粉0.380 0.00 0.000.001 0.09 0.020.002 0.50 0.08 0.0164 0.0463 0.1250（混合饲料配合）以最低成本确定满足动物所需营养的（混合饲料配合）以最低成本确定满足动物所需营养的最优混合饲料。

25、设每天需要混合饲料的批量为最优混合饲料。设每天需要混合饲料的批量为100磅，这份饲磅，这份饲料必须含：至少料必须含：至少0.8%而不超过而不超过1.2%的钙的钙;至少至少22%的蛋白质的蛋白质;至多至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分为：这些配料的主要营养成分为： 根据前面介绍的建模要素得出此问题的数学模型如下根据前面介绍的建模要素得出此问题的数学模型如下:设设 是生产是生产100磅混合饲料所须的石灰石、谷物、大豆粉磅混合饲料所须的石灰石、谷物、大豆粉的量（磅），的量（磅），123,x xx1231231231232323123min0.01640.04630.1250. .1000.3800.0010.0020.012 1000.3800.0010.0020.008 1000.090.500.22 1000.020.080.05 1000,0,0Zxxxs txxxxxxxxxxxxxxxx 若若 ,使得使得 恒恒 有有 称称 为问题为问题(P)的的最优解或者全局极小最优解或者全局极小 点点。 0,1,