第1讲最优化理论与方法

1、CUMT第一讲第一讲最优化理论与方法概述最优化理论与方法概述主主讲讲冯颖冯颖 市场营销系市场营销系2022-4-30CUMT1.1 最优化理论与方法的形成和发展1.2 最优化问题的定义和数学模型1.3 最优化问题的分类1.4 最优化方法的解题步骤1.5 广义最优化方法的种类1.6 最优化方法效果举例主要内容主要内容CUMT1.1 最优化理论与方法最优化理论与方法的形成和的形成和发展发展n 公元前 500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为1.618,称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。n 在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。如阿

2、基米德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。17世纪，I.牛顿和G.W.莱布尼茨在他们所创建的微积分中，提出求解具有多个自变量的实值函数的最大值和最小值的方法。以后又进一步讨论具有未知函数的函数极值，从而形成变分法。第二次世界大战前后，形成了近代最优化方法：以苏联.康托罗维奇和美国G.B.丹齐克为代表的线性规划；以美国库恩和塔克尔为代表的非线性规划；以美国R.贝尔曼为代表的动态规划；以苏联.庞特里亚金为代表的极大值原理等。古典最优化方法古典最优化方法近代近代最优化方法最优化方法CUMT1.1 最优化方法的形成和发展最优化方法的形成和发展最优化方法与运筹学

3、的区别与联系最优化方法与运筹学的区别与联系生活中常见的最优化问题生活中常见的最优化问题 测量云测量云龙龙湖水深的最大值问题湖水深的最大值问题 自自驾游旅行的最优路线驾游旅行的最优路线 城市公共自行车租赁点最佳布局问题城市公共自行车租赁点最佳布局问题 城市交通信号灯配时问题城市交通信号灯配时问题 飞机场停机位分配的问题飞机场停机位分配的问题 月球探测器着陆轨道控制月球探测器着陆轨道控制 内容不同。内容不同。最优化方法包括数学规划、最优控制和计算数学，最优化方法包括数学规划、最优控制和计算数学，运筹学运筹学主要主要包含数学规划问题。包含数学规划问题。 侧重点不同。侧重点不同。最优化方法侧重于算法最

4、优化方法侧重于算法，运筹学运筹学侧重于数学侧重于数学建模。建模。CUMT1.1 最优化方法的形成和发展最优化方法的形成和发展参考书籍参考书籍考核方式考核方式1. 最优化理论与方法，袁亚湘，孙文瑜编，科学出版社，1997年版。2. 运筹学与最优化方法，吴祈宗，侯福均编，机械工业出版社，2013年版。3. 最优化方法与最优控制，王晓陵，陆军编，哈尔滨工程大学出版社，2008年版。4. 最优化计算方法及其MATLAB程序实现，马昌凤等编，国防工业出版社，2015年版。平时成绩（30%）；期末成绩（70%）CUMT1.1 最优化方法的形成和发展最优化方法的形成和发展内容章节内容章节l 第一第一讲讲 最

5、优化理论与方法概述最优化理论与方法概述l 第二讲第二讲 线性规划及线性规划及MatlabMatlab求解求解l 第三讲第三讲 无约束最优化问题与无约束最优化问题与MatlabMatlab求解求解l 第四讲第四讲 约束约束最最优化问题的最优性条件优化问题的最优性条件l 第五讲第五讲 约束约束最优化最优化数值算法数值算法l 第六讲第六讲 启发式算法（模拟退火、遗传算法）启发式算法（模拟退火、遗传算法）l 第七讲第七讲 最优控制理论最优控制理论CUMT1.1 最优化方法的形成和发展1.2 最优化问题的定义和数学模型1.3 最优化问题的分类1.4 最优化方法的解题步骤1.5 广义最优化方法的种类1.6

6、 最优化方法效果举例主要内容主要内容CUMT1.2 最优化方法最优化方法的定义和数学模型的定义和数学模型v 最优化方法即是解决最优化问题的方法，主要最优化方法即是解决最优化问题的方法，主要运用数学方法研究各种运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。系统的优化途径及方案，为决策者提供科学决策的依据。v 最优化问题是指在一定的约束条件下，决定某个或某些可控制的因素最优化问题是指在一定的约束条件下，决定某个或某些可控制的因素应有的合理取值，使所选定的目标达到最优的问题。应有的合理取值，使所选定的目标达到最优的问题。v 最优化方法主要研究最优化方法主要研究数学规划数学规划

7、和和最优控制最优控制两类问题的求解方法。两类问题的求解方法。v Optimal method，Optimization of methods，Optimization，Optimum“Opt”1.2.1 最优化方法的定义最优化方法的定义CUMT1.2 最优化方法的定义和数学模型最优化方法的定义和数学模型( )f X设计向量目标函数约束条件性能指标1.2.2 最优化方法的数学模型最优化方法的数学模型CUMT最优化方法数学模型基本要素最优化方法数学模型基本要素CUMT约束条件约束条件CUMT约束条件约束条件v 不等式约束将设计空间划分为两部分，一部分满足约束条件，另一部分不满足约束条件。 可行域：

8、满足约束条件的区域； 非可行域：不满足约束条件的区域，也叫不可行域； 可行点：可行域内的点，对应一个可行方案； 非可行点：非可行域内的点，对应一个不可行方案，也叫不可行点。CUMT1x2x约束条件约束条件CUMT目标函数目标函数max()f Xm in ( )f X*()f X*()f X-()f X*XXCUMT目标函数目标函数()f X 最优化问题数学模型的典型形式最优化问题数学模型的典型形式CUMT1.1 最优化方法的定义1.2 最优化问题数学模型的构成1.3 最优化问题的分类1.4 最优化方法的解题步骤1.5 广义最优化方法的种类1.6 最优化方法效果举例主要内容主要内容CUMT按约束

9、条件有无及其约束式的性质分按约束条件有无及其约束式的性质分等式约束不等式约束CUMT2min()()f Xxab=-+*xa=*()f Xb=()g Xxc=*xc=*2()()f Xcab=-+0()f Xaxbxc=2()xab-+CUMTv 按所包含方程式的特性分 线性规划：目标函数和约束条件均为线性函数关系的最优化问题，即 都是一次函数； 非线性规划：目标函数和约束条件中有一个或一个以上非线性关系函数式的最优化问题。v 按目标函数的个数分 单目标最优化问题：只有一个目标函数的最优化问题； 多目标最优化问题：含有多个目标函数的最优化问题。()()f Xg X与CUMT针对决策变量针对决策

10、变量x1, x2,xn来进行分类来进行分类连续型连续型线性规划线性规划 LP(有、无约束有、无约束)非线性规划非线性规划NLP(有、无约束有、无约束)离散型离散型整数规划整数规划动态规划动态规划网络网络与与组合组合优化优化泛函极值泛函极值最优控制问题最优控制问题数值数值算法算法解析方法解析方法精确精确算法算法启发式启发式算法算法最优化方法最优化方法CUMT1.1 最优化方法的定义1.2 最优化问题数学模型的构成1.3 最优化问题的分类1.4 最优化方法的解题步骤1.5 广义最优化方法的种类1.6 最优化方法效果举例主要内容主要内容CUMT 了解、分析待最优化的问题了解、分析待最优化的问题建立数

11、学模型建立数学模型（性能指标、设计变量、目标函数、约束条件）（性能指标、设计变量、目标函数、约束条件）选择最优化方法选择最优化方法编写计算程序编写计算程序（给出初始数据）（给出初始数据）上机计算上机计算结果检讨与决策结果检讨与决策输出输出最优化最优化结果结果CUMT1.1 最优化方法的定义1.2 最优化问题数学模型的构成1.3 最优化问题的分类1.4 最优化方法的解题步骤1.5 广义最优化方法的种类1.6 最优化方法效果举例主要内容主要内容CUMT利用古典的微分学、变分学及拉格朗日乘子法等数学工具，利用古典的微分学、变分学及拉格朗日乘子法等数学工具，求出函数极值。对于高次非线性问题等复杂问题求

12、解困难。求出函数极值。对于高次非线性问题等复杂问题求解困难。利用函数局部区域的一些特性及一些点的函数值等条件，通利用函数局部区域的一些特性及一些点的函数值等条件，通过数学迭代程序进行计算，逐步调优并逼近函数的最优点。过数学迭代程序进行计算，逐步调优并逼近函数的最优点。用几何作图的方法，画出图形，从图形上直接观察，找出函用几何作图的方法，画出图形，从图形上直接观察，找出函数的极值点。只适用于容易作图的较简单问题。数的极值点。只适用于容易作图的较简单问题。通过直接实验，进行结果的比较，获得函数的极值或问题的通过直接实验，进行结果的比较，获得函数的极值或问题的最佳参数。最佳参数。把同一问题的许多可能

13、的典型解进行估计、研究分析，以确把同一问题的许多可能的典型解进行估计、研究分析，以确定其最优解。定其最优解。解析法解析法数值法数值法图解法图解法实验法实验法情况研究法情况研究法数学规划法CUMT1.1 最优化方法的定义1.2 最优化问题数学模型的构成1.3 最优化问题的分类1.4 最优化方法的解题步骤1.5 广义最优化方法的种类1.6 最优化方法效果举例主要内容主要内容CUMT车轮轴的优化下料方法车轮轴的优化下料方法v 某车辆厂要生产长度为1080、1040及970毫米的轴，其生产数量分别为100、150和600根。现只能用长度为3000毫米的原料钢管。问应该怎样安排下料才能使料头最少？规格每

14、根原料可下件数（根）每根原料料头共有料头长度10802840（840100/2）=4200010402920（920150/2）=69000970390（ 90600/3）=18000（总计）129000（mm）CUMTv 最优化方法 列出所有可能的下料方案，择其方案中料头最短的3种设计成如表的优化下料方案：（mm）10801040970每根棒料料头长度根数（根）I0123000-11040-2970=20II0033000-3970=90III2003000-21080=840规格规格方案方案CUMT123,x x x123min()2090840f Xxxx=+CUMTv 该数学模型的最优

15、化求解是一个很简单的数学问题，其最优解为： 其最优值是： 优化下料方法与原顺序下料方法相比较，有明显效果：料头减少为129000-54000=75000（mm），节约钢材58%*12315010050 xxx=CUMT说明和提示说明和提示v 节约的比例数大，效果明显。有的问题，如果基数大，即节约的比例数大，效果明显。有的问题，如果基数大，即便节约费用百分之一二，也很有意义，如空间技术；便节约费用百分之一二，也很有意义，如空间技术；v 有一些问题，在求解之前或求解过程中，还要用到数学优有一些问题，在求解之前或求解过程中，还要用到数学优化方法以外的其他优化方法，如实验法、情况研究优化，化方法以外的

16、其他优化方法，如实验法、情况研究优化，甚至设计者的经验与技能。在前提限制条件确定和总体方甚至设计者的经验与技能。在前提限制条件确定和总体方案优选以后，才能用数学优化的方法进行参数的优化设计。案优选以后，才能用数学优化的方法进行参数的优化设计。 v 一种数学方法可以求解一个最优化问题；而一个最优化问一种数学方法可以求解一个最优化问题；而一个最优化问题可以先后用几种数学方法找到最终的最优值。即其数学题可以先后用几种数学方法找到最终的最优值。即其数学方法与求解的问题不应视为只有唯一的对应性。为了提高方法与求解的问题不应视为只有唯一的对应性。为了提高运算速度和求解效果，对有的问题可以相互联系地选用具运

17、算速度和求解效果，对有的问题可以相互联系地选用具有不同特点的方法。有不同特点的方法。CUMT数学预备知识数学预备知识1. 向量与范数向量与范数设向量设向量 maxixx 范数，是具有范数，是具有“长度长度”概念的概念的函数函数。在线性代数、泛。在线性代数、泛函分析及相关的数学领域，是一个函数，其为向量空间内函分析及相关的数学领域，是一个函数，其为向量空间内的所有向量赋予非零的正长度或大小。用的所有向量赋予非零的正长度或大小。用 表示表示x -范数范数2-范数范数1-范数范数1212,.,.,Tnnxx xxyy yy1ixx1222ixxCUMT范数不等式范数不等式xyxy范数的内积范数的内积

18、1nTiiix yx yTx yxy三角不等式三角不等式柯西不等式柯西不等式2. 多元函数的微分多元函数的微分 对于多元函数对于多元函数u=f(x)， ，若在点，若在点 处对于自变量处对于自变量 的各的各分量的偏导数都存在，分量的偏导数都存在， 则称函数则称函数u=f(x)在在该点的一阶导数。该点的一阶导数。 0120 ,0 ,.,0TnxxxxnxSR12,.,Tnxx xx01,2,.,if xinxCUMT(1) 梯度梯度 00012,.,nf xf xf xf xxxx(2) Hession矩阵矩阵 222000211212220002221222220002112.nnnnf xf

19、xf xxx xx xf xf xf xf xH xx xxx xf xf xf xx xxxx (海塞矩阵海塞矩阵)CUMT(3) 多元函数的多元函数的Taylor展开展开2000012TTf xxf xf xxxf xxx 01220000102TTf xxf xf xxf xxxx 02000102TTf xxf xf xxxxxHx 二阶二阶Taylor展开展开或或一阶一阶Taylor展开展开CUMT3.凸集与凸函数凸集与凸函数 (在无约束规划中常用到，具有很好的极值性在无约束规划中常用到，具有很好的极值性)对任意的对任意的有有,0,1x yC则则C为凸集为凸集(1) 凸集凸集1xyC凸集凸集非凸集非凸集CUMT (2) 下下凸函数：凸函数：； 下下凹函数：凹函数： (3) 凸函数的定义：凸函数的定义： 设设f(x)为