第1讲 最优化理论与方法概述

CUMT第一讲最优化理论与方法概述主讲冯颖市场营销系[e-mail]2020/1/24CUMT1.1最优化理论与方法的形成和发展1.2最优化问题的定义和数学模型1.3最优化问题的分类1.4最优化方法的解题步骤1.5广义最优化方法的种类1.6最优化方法效果举例主要内容CUMT1.1最优化理论与方法的形成和发展公元前500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为1.618,称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。如阿基米德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。17世纪，I.牛顿和G.W.莱布尼茨在他们所创建的微积分中，提出求解具有多个自变量的实值函数的最大值和最小值的方法。以后又进一步讨论具有未知函数的函数极值，从而形成变分法。第二次世界大战前后，形成了近代最优化方法：以苏联Л.В.康托罗维奇和美国G.B.丹齐克为代表的线性规划；以美国库恩和塔克尔为代表的非线性规划；以美国R.贝尔曼为代表的动态规划；以苏联Л.С.庞特里亚金为代表的极大值原理等。古典最优化方法近代最优化方法CUMT1.1最优化方法的形成和发展最优化方法与运筹学的区别与联系生活中常见的最优化问题测量云龙湖水深的最大值问题自驾游旅行的最优路线城市公共自行车租赁点最佳布局问题城市交通信号灯配时问题飞机场停机位分配的问题月球探测器着陆轨道控制①内容不同。最优化方法包括数学规划、最优控制和计算数学，运筹学主要包含数学规划问题。②侧重点不同。最优化方法侧重于算法，运筹学侧重于数学建模。CUMT1.1最优化方法的形成和发展参考书籍考核方式1.最优化理论与方法，袁亚湘，孙文瑜编，科学出版社，1997年版。2.运筹学与最优化方法，吴祈宗，侯福均编，机械工业出版社，2013年版。3.最优化方法与最优控制，王晓陵，陆军编，哈尔滨工程大学出版社，2008年版。4.最优化计算方法及其MATLAB程序实现，马昌凤等编，国防工业出版社，2015年版。平时成绩（30%）；期末成绩（70%）CUMT1.1最优化方法的形成和发展内容章节第一讲最优化理论与方法概述第二讲线性规划及Matlab求解第三讲无约束最优化问题与Matlab求解第四讲约束最优化问题的最优性条件第五讲约束最优化数值算法第六讲启发式算法（模拟退火、遗传算法）第七讲最优控制理论CUMT1.1最优化方法的形成和发展1.2最优化问题的定义和数学模型1.3最优化问题的分类1.4最优化方法的解题步骤1.5广义最优化方法的种类1.6最优化方法效果举例主要内容CUMT1.2最优化方法的定义和数学模型最优化方法即是解决最优化问题的方法，主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化问题是指在一定的约束条件下，决定某个或某些可控制的因素应有的合理取值，使所选定的目标达到最优的问题。最优化方法主要研究数学规划和最优控制两类问题的求解方法。Optimalmethod，Optimizationofmethods，Optimization，Optimum…“Opt”1.2.1最优化方法的定义CUMT1.2最优化方法的定义和数学模型数学模型：根据对所研究问题的分析、了解及实践经验，为了一个特定的目的，建立出的用以描述问题的变化规律、反映其数量关系并有具体算法的一组数学表达式。最优化问题数学模型：求𝑋=𝑋1𝑋2⋯𝑋𝑛，使极小或极大（1-1）满足于约束𝑔𝑖𝑋≤0,𝑖=1,2,⋯,𝑚和𝑔𝑗𝑋=0,𝑗=1,2,⋯,𝑝()fX设计向量目标函数约束条件性能指标1.2.2最优化方法的数学模型CUMT最优化方法数学模型基本要素目标函数性能指标约束条件设计变量CUMT约束条件约束条件求目标函数极值时的某些限制称为约束条件，简称约束。它也是对设计变量取值范围的限制（条件）。约束式常用g字母表示，也有用h、C’等其他字母表示的。如果列出来的约束条件式越接近实际系统，则所求得的最优化问题的解，也是接近于实际情况的最优解。约束函数式可以是等式约束和不等式约束。𝑔𝑖𝑥1,𝑥2,⋯,𝑥𝑛=0𝑔𝑖𝑥1,𝑥2,⋯,𝑥𝑛≥0𝑔𝑖𝑋≤0,𝑋∈𝐸𝑛,𝑖=1,2,⋯,𝑚𝑔𝑖𝑥1,𝑥2,⋯,𝑥𝑛≤0当𝑔𝑖𝑋=0时，为一n维空间曲面；当𝑔𝑖𝑋≤0时，对设计空间的取值范围分为两部分。CUMT约束条件不等式约束将设计空间划分为两部分，一部分满足约束条件，另一部分不满足约束条件。可行域：满足约束条件的区域；非可行域：不满足约束条件的区域，也叫不可行域；可行点：可行域内的点，对应一个可行方案；非可行点：非可行域内的点，对应一个不可行方案，也叫不可行点。CUMT1x2x约束条件假若某一组约束条件为：𝑔1𝑋=𝑥2−5≤0𝑔2𝑋=𝑥1+𝑥2−4≥0𝑔3𝑋=𝑥1−12𝑥2−8≤0CUMT目标函数评价设计方案优劣的数学表达式，是设计变量的函数，也称评价函数。目标函数的数学描述为：𝑓𝑥1,𝑥2,⋯,𝑥𝑛𝑓𝑋,𝑋∈𝐸𝑛,用效果、效率、利润等作为目标函数时，最优化设计是要求极大值；而若用费用、消耗、成本等作为目标函数时，最优化设计则是要求极小值。𝑚𝑖𝑛𝑓𝑋=−max{−𝑓X}max()fXmin()fX*()fX*()fX-()fX*XXCUMT目标函数最优化问题的数学模型是要对具体的实际问题进行抽象，得出一个描述在设计变量𝑋(𝑋∈𝐸𝑛)满足约束条件𝑔𝑖𝑋≤0或𝑔𝑖𝑋=0，求目标函数极值的数学表达式。𝑚𝑖𝑛𝑓𝑋，𝑋∈𝐸𝑛𝑆.𝑡.𝑔𝑖𝑋≥0或𝑔𝑖𝑋=0，𝑖=1,2,⋯,𝑚（1-2）()fX最优化问题数学模型的典型形式CUMT1.1最优化方法的定义1.2最优化问题数学模型的构成1.3最优化问题的分类1.4最优化方法的解题步骤1.5广义最优化方法的种类1.6最优化方法效果举例主要内容CUMT按约束条件有无及其约束式的性质分无约束最优化问题有约束无约束最优化问题数学模型𝑚𝑖𝑛𝑓𝑋，𝑋∈𝐸𝑛（1-3）等式约束最优化问题的数学模型𝑚𝑖𝑛𝑓𝑋=𝑚𝑖𝑛𝑓(𝑥1,𝑥2,⋯,𝑥𝑛)，𝑋∈𝐸𝑛𝑔𝑖𝑋=0，𝑖=1,2,⋯,𝑚，𝑚≤𝑛（1-4）不等式约束最优化问题的数学模型𝑚𝑖𝑛𝑓𝑋=𝑚𝑖𝑛𝑓(𝑥1,𝑥2,⋯,𝑥𝑛)，𝑋∈𝐸𝑛𝑔𝑖𝑋≥0，𝑖=1,2,⋯,𝑚，𝑚没有限制（1-5）等式约束不等式约束CUMT若有目标函数为的最优化问题，在不同的约束条件下会有不同的最优解：当无约束时，其最优解最优值当有等式约束时，其最优解最优值当有不等式约束时，若𝑔𝑋=𝑥≥𝑐其解同等式约束；若𝑔𝑋=𝑥𝑐其解同无约束情况。2min()()fXxab=-+*xa=*()fXb=()gXxc==*xc=*2()()fXcab=-+0()fXaxbxc=2()xab-+CUMT按所包含方程式的特性分线性规划：目标函数和约束条件均为线性函数关系的最优化问题，即都是一次函数；非线性规划：目标函数和约束条件中有一个或一个以上非线性关系函数式的最优化问题。按目标函数的个数分单目标最优化问题：只有一个目标函数的最优化问题；多目标最优化问题：含有多个目标函数的最优化问题。()()fXgX与CUMT针对决策变量x1,x2,…xn来进行分类连续型线性规划LP(有、无约束)非线性规划NLP(有、无约束)离散型整数规划动态规划网络与组合优化泛函极值最优控制问题数值算法解析方法精确算法启发式算法最优化方法CUMT1.1最优化方法的定义1.2最优化问题数学模型的构成1.3最优化问题的分类1.4最优化方法的解题步骤1.5广义最优化方法的种类1.6最优化方法效果举例主要内容CUMT了解、分析待最优化的问题建立数学模型（性能指标、设计变量、目标函数、约束条件）选择最优化方法编写计算程序（给出初始数据）上机计算结果检讨与决策输出最优化结果CUMT1.1最优化方法的定义1.2最优化问题数学模型的构成1.3最优化问题的分类1.4最优化方法的解题步骤1.5广义最优化方法的种类1.6最优化方法效果举例主要内容CUMT利用古典的微分学、变分学及拉格朗日乘子法等数学工具，求出函数极值。对于高次非线性问题等复杂问题求解困难。利用函数局部区域的一些特性及一些点的函数值等条件，通过数学迭代程序进行计算，逐步调优并逼近函数的最优点。用几何作图的方法，画出图形，从图形上直接观察，找出函数的极值点。只适用于容易作图的较简单问题。通过直接实验，进行结果的比较，获得函数的极值或问题的最佳参数。把同一问题的许多可能的典型解进行估计、研究分析，以确定其最优解。解析法数值法图解法实验法情况研究法数学规划法CUMT1.1最优化方法的定义1.2最优化问题数学模型的构成1.3最优化问题的分类1.4最优化方法的解题步骤1.5广义最优化方法的种类1.6最优化方法效果举例主要内容CUMT车轮轴的优化下料方法某车辆厂要生产长度为1080、1040及970毫米的轴，其生产数量分别为100、150和600根。现只能用长度为3000毫米的原料钢管。问应该怎样安排下料才能使料头最少？规格每根原料可下件数（根）每根原料料头共有料头长度10802840（840×100/2）=4200010402920（920×150/2）=69000970390（90×600/3）=18000（总计）129000（mm）CUMT最优化方法列出所有可能的下料方案，择其方案中料头最短的3种设计成如表的优化下料方案：（mm）10801040970每根棒料料头长度根数（根）I0123000-1×1040-2×970=20II0033000-3×970=90III2003000-2×1080=840规格方案CUMT设每一种方案中分别用原料数，则下料料头最少的目标函数为：约束条件为每种规格的生产数量，即0𝑥1+0𝑥2+2𝑥3=1001𝑥1+0𝑥2+0𝑥3=1502𝑥1+3𝑥2+0𝑥3=600故该优化问题的数学模型为𝑚𝑖𝑛𝑓𝑋=20𝑥1+90𝑥2+840𝑥32𝑥3=1001𝑥1=1502𝑥1+3𝑥2=600且𝑥1，𝑥2，𝑥3≥0123,,xxx123min()2090840fXxxx=++CUMT该数学模型的最优化求解是一个很简单的数学问题，其最优解为：其最优值是：优化下料方法与原顺序下料方法相比较，有明显效果：料头减少为129000-54000=75000（mm），节约钢材58%***12315010050xxx===𝑓𝑋∗=20×150+90×100+840×50=54000CUMT说明和提示节约的比例数大，效果明显。有的问题，如果基数大，即便节约费用百分之一二，也很有意义，如空间技术；有一些问题，在求解之前或求解过程中，还要用到数学优化方法以外的其他优化方法，如实验法、情况研究优化，甚至设计者的经验与技能。在前提限制条件确定和总体方案优选以后，才能用数学优化的方法进行参数的优化设计。一种数学方法可以求解一个最优化问题；而一个最优化问题可以先后用几种数学方法找到最终的最优值。即其数学方法与求解的问题不应视为只有唯一的对应性。为了提高运算速度和求解效果，对有的问题可以相互联系地选用具有不同特点的方法。CUMT数学预备知识1.向量与范数设向量maxixx范数，是具有“长度”概念的函数。在线性代数、泛函分析及相关的数学领域，是一个函数，其为向量空间内的所有向量赋予非零的正长度或大小。用表示x-范数2-范数1-范数1212,,...,,,,...,Tnnxxxxyyyy1ixx1