《数模与最优化》PPT课件.ppt

2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,1,加工数模与优化 The Mathematical Model and Optimality Principle in Plastic Working of Metals,材料加工过程中最优化原理与方法 材料加工过程中数学模型,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,2,课程简介,学时安排： 计划学时数：40学时，授课学时数：32学时，上机学时数：8学时 课程性质： 本课程是一门限定性选修专业基础课程，是帮助学生掌握解决现场问题的一个工具，最优化方法可以帮助工程技术人员对现有工艺进行改造，以期达到降耗、节能、高效的目的，数学模型则是计算机控制中必不可少的部分，是企业实现自动化控制的基础。 目的及任务： 通过本课程的学习，要求学生掌握最基本的现代最优化方法和一般的数学建模方法，使学生能将现代最优化原理及数学建模用在本专业。本课程教学的任务是从应用的角度出发，使学生将所学的数学知识与本专业很好地结合，从而开拓其思路，增加其基本技能。 对优化技术入门，能编制简单的优化程序，最好能在毕业设计和论文中加以应用。,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,3,教材及参考书,教材： 最优化方法，施光燕，董加礼编，高等教育出版社，1999 主要参考书目： 最优化方法，解可新，韩立兴，林友联，天津大学出版社，1998 最优化原理与方法，薛嘉庆，冶金工业出版社，1986 最优化计算方法，席少霖，赵凤治，上海科学技术出版社，1983 非线性方程组解法与最优化方法，王德人，高等教育出版社，1985 非线性规划，胡毓达，高等教育出版社，1990 轧制过程数学模型，杨节，冶金工业出版社，1983 轧制变形规程优化设计，刘战英编著，冶金工业出版社，1997,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,4,学习要求,学习方法 认真听课，认真做笔记，基本概念和基本方法一定要掌握，要及时复习。 认真完成作业 上机操作 考核方式 作业完成情况 上机情况 笔试（闭卷） 最终成绩组成： 平时2030%（包括上课听讲情况、上机情况、作业完成情况），闭卷考试7080%,2019/7/24,Algorithms Design Techniques and Analysis,5,数学家名人录,2019/7/24,Algorithms Design Techniques and Analysis,6,Contents of CH1,引言:数学建模与最优化的背景 数学建模的进展 最优化技术的进展 数学建摸的基本概念与分类 数学模型与数学建模 数学模型的分类 数学模型的应用领域 数学建模举例 数学建模的过程 最优化的基本概念与分类 最优化的基本概念 最优化技术分类 最优化建模与求解示例 数学建摸与最优化的关系,2019/7/24,Algorithms Design Techniques and Analysis,7,1 引言:数学建模与最优化的背景,1.1 数学建模的历史与意义 1.2 最优化的历史与意义,2019/7/24,Algorithms Design Techniques and Analysis,8,1.1 数学建模的历史与意义,数学建模的历史和数学的历史基本上是一样的； 古埃及几何学产生于尼罗河泛滥后土地的重新丈量； 古印度几何学的起源则与宗教密切相关 中国的周批算经是讨论天文学测量的巨著； 大约公元前世纪，毕达哥拉斯学派重视自然及社会中不变因素的研究，把几何、算术、天文、音乐称为“四艺”，在其中追求宇宙的和谐规律性。 17世纪出现了笛卡尔、牛顿、莱布尼兹等数学家，奠定了微积分的基础，其研究的对象包括行星运动、流体运动、机械运动、植物生长等均属于数学建模的范畴； 19世纪后期，数学成为了研究数与形、运动与变化的学问； 可以说，数学是模式的科学，其目的是要揭示人们从自然界和数学本身的抽象世界中所观察到的结构和对称性。,2019/7/24,Algorithms Design Techniques and Analysis,9,1.2 最优化的历史,最优化问题有相当长的发展历史，最一早可以追溯到牛顿、拉格朗日时代。由于牛顿等对微积分的重要贡献，才使得差分方程法解决最优化问题成为可能。这其中的先锋者包括贝诺利(Bemot)，欧拉(Eller)和拉格郎日等。 Lagrange发明了有名的拉格郎日乘子法。柯西(Canchy)首先提出了最速下降法(解决无约束最小化问题)。尽管有这些早期的成果，最优化的发展相当缓慢，直到50年代高速计算机的出现。50年代后，最优化的发展进入旺盛期，出现了大量的新算法。Dantzig提出了解决线性规划问题的simplex方法，Bellman提出了动态规划最优化最优性原理，使得约束最优化成为可能性。Kuhn和Tucher提出的最优化规划问题的充分和必要条件开创了非线性规划优化技术的基础。 几何规划优化由Zountijker和Rosen在60年代提出，Gomory同 时提出了积分规划技术。随机(或统计)规划技术最早山Danzig和charnes提出，Cooper发展了该技术。,2019/7/24,Algorithms Design Techniques and Analysis,10,构成现代优化理论的相关技术是模拟退火SA、遗传算法GA等现代启发式最优化算法，他们均是从60年代发展起来的。 SA算法是一种组合优化算法，足模拟材半l)Jl日一中的退火处理(Annealing)得名的优化算法。退火是材料加工的一种处理方式，即首先将固体加工到融化状态，再逐渐冷却，直到材料达到结品状态。在这个过程中，固体内的自由能最终被降低到最小状态。在实践中，冷却过程必须非常小心控制，以防止固体结晶到局部最小能量状态，即局部最优解，从而影响材料的强度等各种性能。模拟退火算法模拟这样的物理过程，将组合最小化能量状态模拟为最终晶体状态，并设计一个类似的处理过程，达到优化的目的。,2019/7/24,Algorithms Design Techniques and Analysis,11,1.2 数学建摸的基本概念与分类,数学模型与数学建模 数学模型的分类 数学模型的应用领域 数学建模举例 数学建模的过程,2019/7/24,Algorithms Design Techniques and Analysis,12,1.2.1 数学建模与数学模型,模型是把对象实体通过适当的过滤,用适当的表现规则描绘出的简洁的模仿品.通过这个模仿品,人们可以了解到所研究实体的本质,而且在形式上便于人们对实体进行分析和处理。,模型概念,模型是人们十分熟悉的东西，例如：玩具、照片及展览会里的电站模型、火箭模型等实物模型；地图、电路图、分子结构图等经过一定抽象的符号模型；大型水箱中的舰艇模型、风洞中的飞机模型等物理模型。,2019/7/24,Algorithms Design Techniques and Analysis,13,数学模型 (Mathematical Model) 和 数学建模（Mathematical Modeling),对于一个现实对象，为了一个特定目的， 根据其内在规律，作出必要的简化假设， 运用适当的数学工具，得到的一个数学结构。,建立数学模型的全过程 （包括表述、求解、解释、检验等）,数学模型,数学建模,2019/7/24,Algorithms Design Techniques and Analysis,14,数学建模的具体应用,分析与设计,预报与决策,控制与优化,规划与管理,数学建模,计算机技术,知识经济,2019/7/24,Algorithms Design Techniques and Analysis,15,数学模型的分类,按模型的应用领域分类,生物数学模型,医学数学模型,地质数学模型,数量经济学模型,数学社会学模型,2019/7/24,Algorithms Design Techniques and Analysis,16,数学模型的分类,按是否考虑随机因素分类,确定性模型,随机性模型,2019/7/24,Algorithms Design Techniques and Analysis,17,数学模型的分类(续),按是否考虑模型的变化分类 静态模型 动态模型,按建立模型的数学方法分类 几何模型 微分方程模型 图论模型 规划论模型 马氏链模型,按应用离散方法或连续方法 离散模型 连续模型,2019/7/24,Algorithms Design Techniques and Analysis,18,数学模型的分类(续),按人们对事物发展过程的了解程度分类,白箱模型： 指那些内部规律比较清楚的模型。如力学、热学、电学以及相关的工程技术问题。,灰箱模型： 指那些内部规律尚不十分清楚，在建立和改善模型方面都还不同程度地有许多工作要做的问题。 如气象学、生态学经济学等领域的模型。,黑箱模型： 指一些其内部规律还很少为人们所知的现象。如生命科学、社会科学等方面的问题。但由于因素众多、关系复杂，也可简化为灰箱模型来研究。,2019/7/24,Algorithms Design Techniques and Analysis,19,数学建模示例,椅子能在不平的地面上放稳吗,问题分析,模型假设,通常 三只脚着地,放稳 四只脚着地,四条腿一样长，椅脚与地面点接触，四脚连线呈正方形;,地面高度连续变化，可视为数学上的连续曲面;,地面相对平坦，使椅子在任意位置至少三只脚同时着地。,2019/7/24,Algorithms Design Techniques and Analysis,20,模型构成,用数学语言把椅子位置和四只脚着地的关系表示出来,椅子位置,利用正方形(椅脚连线)的对称性,用(对角线与x轴的夹角)表示椅子位置,四只脚着地,距离是的函数,四个距离(四只脚),A,C 两脚与地面距离之和 f(),B,D 两脚与地面距离之和 g(),两个距离,椅脚与地面距离为零,正方形ABCD绕O点旋转,2019/7/24,Algorithms Design Techniques and Analysis,21,用数学语言把椅子位置和四只脚着地的关系表示出来,f() , g()是连续函数,对任意, f(), g()至少一个为0,数学问题,已知： f() , g()是连续函数 ; 对任意， f() g()=0 ; 且 g(0)=0， f(0) 0. 证明：存在0，使f(0) = g(0) = 0.,模型构成,地面为连续曲面,椅子在任意位置至少三只脚着地,2019/7/24,Algorithms Design Techniques and Analysis,22,模型求解,给出一种简单、粗糙的证明方法,将椅子旋转900，对角线AC和BD互换。 由g(0)=0， f(0) 0 ，知f(/2)=0 , g(/2)0. 令h()= f()g(), 则h(0)0和h(/2)0. 由 f, g的连续性知 h为连续函数, 据连续函数的基本性质, 必存在0 , 使h(0)=0, 即f(0) = g(0) . 因为f() g()=0, 所以f(0) = g(0) = 0.,评注和思考,建模的关键 ,假设条件的本质与非本质,考察四脚呈长方形的椅子,和 f(), g()的确定,2019/7/24,Algorithms Design Techniques and Analysis,23,商人们怎样安全过河,问题(智力游戏), 3名商人 3名随从,随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.,但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?,问题分析,多步决策过程,决策 每一步(此岸到彼岸或彼岸到此岸)船上的人员,要求在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河.,2019/7/24,Algorithms Design Techniques and Analysis,24,模型构成,xk第k次渡河前此岸的商人数,yk第k次渡河前此岸的随从数,xk, yk=0,1,2,3; k=1,2, ,sk=(xk , yk)过程的状态,S=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2,S 允许状态集合,uk第k次渡船上的商人数,vk第k次渡船上的随从数,dk=(uk , vk)决策,D=(u , v) u+v=1, 2 允许决策集合,uk, vk=0,1,2; k=1,2, ,sk+1=sk dk,+(-1)k,状态转移律,求dkD(k=1,2, n), 使skS, 并按转移律由 s1=(3,3)到达 sn+1=(0,0).,多步决策问题,2019/7/24,Algorithms Design Techniques and Analysis,25,模型求解,穷举法 编程上机,图解法,状态s=(x,y) 16个格点,允许决策 移动1或2格; k奇,左下移; k偶,右上移.,s1,sn+1,d1, ，d11给出安全渡河方案,评注和思考,规格化方法,易于推广,允许状态,S=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2,2019/7/24,Algorithms Design Techniques and Analysis,26,数学建模的基本方法,机理分析,测试分析,根据对客观事物特性的认识， 找出反映内部机理的数量规律,将对象看作“黑箱”,通过对量测数据的 统计分析，找出与数据拟合最好的模型,机理分析没有统一的方法，主要通过实例研究(Case Studies)来学习。,二者结合,用机理分析建立模型结构,用测试分析确定模型参数,数学建模的方法和步骤,2019/7/24,Algorithms Design Techniques and Analysis,27,数学建模的一般步骤,模 型 准 备,了解实际背景,明确建模目的,搜集有关信息,掌握对象特征,形成一个 比较清晰 的问题,2019/7/24,Algorithms Design Techniques and Analysis,28,模 型 假 设,针对问题特点和建模目的,作出合理的、简化的假设,在合理与简化之间作出折中,模 型 构 成,用数学的语言、符号描述问题,发挥想像力,使用类比法,尽量采用简单的数学工具,数学建模的一般步骤,2019/7/24,Algorithms Design Techniques and Analysis,29,模型 求解,各种数学方法、软件和计算机技术,如结果的误差分析、统计分析、 模型对数据的稳定性分析,模型 分析,模型 检验,与实际现象、数据比较， 检验模型的合理性、适用性,模型应用,数学建模的一般步骤,2019/7/24,Algorithms Design Techniques and Analysis,30,数学建模的全过程,现实对象的信息,数学模型,现实对象的解答,数学模型的解答,(归纳),(演绎),表述,求解,解释,验证,根据建模目的和信息将实际问题“翻译”成数学问题,选择适当的数学方法求得数学模型的解答,将数学语言表述的解答“翻译”回实际对象,用现实对象的信息检验得到的解答,实践,现实世界,数学世界,2019/7/24,Algorithms Design Techniques and Analysis,31,1.3 最优化的基本概念与分类,最优化的基本概念 最优化技术分类 最优化建模与求解示例,2019/7/24,Algorithms Design Techniques and Analysis,32,最优化的基本概念,最优化技术是一门较新的学科分支。它是在本世纪五十年代初在电子计算机广泛应用的推动下才得到迅速发展，并成为一门直到目前仍然十分活跃的新兴学科。最优化所研究的问题是在众多的可行方案中怎样选择最合理的一种以达到最优目标。 将达到最优目标的方案称为最优方案或最优决策，搜寻最优方案的方法称为最优化方法，关于最优化方法的数学理论称为最优化论。 最优化问题至少有两要素：一是可能的方案；二是要追求的目标。后者是前者的函数。如果第一要素与时间无关就称为静态最优化问题，否则称为动态最优化问题。,2019/7/24,Algorithms Design Techniques and Analysis,33,最优化技术应用范围十分广泛，在我们日常生活中，在工农业生产、社会经济、国防、航空航天工业中处处可见其用途。 比如我们自己所接触过的课题有：结构最优设计、电子器件最优设计、光学仪器最优设计、化工工程最优设计、标腔最优配方、运输方案、机器最优配备、油田开发、水库调度、饲料最优配方、食品结构优化等等。,2019/7/24,Algorithms Design Techniques and Analysis,34,最优化技术工作被分成两个方面，一是由实际生产或科技问题形成最优化的数学模型，二是对所形成的数学问题进行数学加工和求解。 对于第二方面的工作，目前已有一些较系统成熟的资料，但对于第一方面工作即如何由实际问题抽象出数学模型，目前很少有系统的资料，而这一工作在应用最优化技术解决实际问题时是十分关键的基础，没有这一工作，最优化技术将成为无水之源，难以健康发展。,2019/7/24,Algorithms Design Techniques and Analysis,35,最优化问题举例,最优化在物质运输、自动控制、机械设计、采矿冶金、经济管理等科学技术各领域中有广泛应用。下面举几个专业性不强的实例。 例1.把半径为1的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？ 解：决定圆柱体表面积大小有两个决策变量：圆柱体底面半径r、高h。 问题的约束条件是所铸圆柱体重量与球重相等。即,2019/7/24,Algorithms Design Techniques and Analysis,36,即 即 问题追求的目标是圆柱体表面积最小。即 min 则得原问题的数学模型： s.t. Subject to.固定.,2019/7/24,Algorithms Design Techniques and Analysis,37,利用在高等数学中所学的Lagrange乘子法可求解本问题 分别对r.h.求偏导数,并令其等于零.有:,2019/7/24,Algorithms Design Techniques and Analysis,38,例2.多参数曲线拟合问题 已知两个物理量x和y之间的依赖关系为: 其中 和 待定参数,为确定这些参数, 对x.y测得m个实验点: 试将确定参数的问题表示成最优化问题.,2019/7/24,Algorithms Design Techniques and Analysis,39,解:很显然对参数 和 任意给定的一组数值,就由上式确定了 y关于x的一个函数关系式,在几何上它对应一条曲线,这条曲线不一定通过那m个测量点,而要产生“偏差”. 将测量点沿垂线方向到曲线的距离的 平方和作为这种“偏差”的度量.即 显然偏差S越小,曲线就拟合得越好,说明参数值就选择得越好，从而我们的问题就转化为5维无约束最优化问题。即：,2019/7/24,Algorithms Design Techniques and Analysis,40,例3：两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，弹性模量为E，屈吸强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。,受力分析图,圆杆截面图,桁杆示意图,2019/7/24,Algorithms Design Techniques and Analysis,41,解：桁杆的截面积为 ： 桁杆的总重量为： 负载2p在每个杆上的分力为： 于是杆截面的应力为： 此应力要求小于材料的屈吸极限，即,2019/7/24,Algorithms Design Techniques and Analysis,42,圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为 由此得稳定约束：,2019/7/24,Algorithms Design Techniques and Analysis,43,另外还要考虑到设计变量d和h有界。 从而得到两杆桁架最优设计问题的数学模型：,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,44,最优化原理及方法,最优化原理建模与数学预备知识 直线搜索 无约束条件下多变量函数的寻优方法 等式约束条件下多变量函数的寻优问题 不等式约束条件下多变量函数的寻优方法 轧制变形过程的优化设计,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,45,1 最优化原理建模与数学预备知识,1.1 引言 1.2 经典极值问题 1.3 最优化问题基本概念 1.4 二维问题的图解法 1.5 二次函数 1.6 梯度与Hesse矩阵 1.7 函数的极值 1.8 非线性规划寻优方法概念 1.9 下降迭代算法及其终止准则,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,46,1.1 引言,最优化技术是一门较新的学科分支。它是在本世纪五十年代初在电子计算机广泛应用的推动下才得到迅速发展，并成为一门直到目前仍然十分活跃的新兴学科。最优化所研究的问题是在众多的可行方案中怎样选择最合理的一种以达到最优目标。 将达到最优目标的方案称为最优方案或最优决策，搜寻最优方案的方法称为最优化方法，关于最优化方法的数学理论称为最优化论。 最优化问题至少有两要素：一是可能的方案；二是要追求的目标。后者是前者的函数。如果第一要素与时间无关就称为静态最优化问题，否则称为动态最优化问题。 本科程专门讲授静态最优化问题。,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,47,1.1 引言,最优化技术工作被分成两个方面，一是由实际生产或科技问题形成最优化的数学模型，二是对所形成的数学问题进行数学加工和求解。对于第二方面的工作，目前已有一些较系统成熟的资料，但对于第一方面工作即如何由实际问题抽象出数学模型，目前很少有系统的资料，而这一工作在应用最优化技术解决实际问题时是十分关键的基础，没有这一工作，最优化技术将成为无水之源，难以健康发展。,最优化技术应用范围十分广泛，在我们日常生活中，在工农业生产、社会经济、国防、航空航天工业中处处可见其用途。 比如我们专业所接触过的有： 安排生产计划方面，如何在现有人力、物力条件下，合理安排产品生产，使总产值为最高： 产品设计方面，工字钢（截面抗弯能力，宽高比或面模量）机械零件 工厂布局、物资调动方面； 配料方面，如何合理配料，在保证质量前提下使成本最低； 自动控制中参数的设定：如轧钢自动控制系统中连轧机各架轧机压下量的设定；在坯料厚度H和成品限制条件都能满足的情况下，如何分配各架轧机的压下量，使达到最优工作状态,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,48,1.1 引言,数学模型：就是对现实事物或问题的数学抽象或描述。 建立数学模型时要尽可能简单，而且要能完整地描述所研究的系统，但要注意到过于简单的数学模型所得到的结果可能不符合实际情况，而过于详细复杂的模型又给分析计算带来困难。因此，具体建立怎样的数学模型需要丰富的经验和熟练的技巧。即使在建立了问题的数学模型之后，通常也必须对模型进行必要的数学简化以便于分析、计算。 一般的模型简化工作包括以下几类： （1）将离散变量转化为连续变量。 （2）将非线性函数线性化。 （3）删除一些非主要约束条件。,因此，我们在学习本科程时要尽可能了解如何由实际问题形成最优化的数学模型。 为了便于大家今后在处理实际问题时建立最优化数学模型，下面我们先把有关数学模型的一些事项作一些说明。,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,49,建立最优化问题数学模型的三要素： （1）决策变量和参数 决策变量是由数学模型的解确定的未知数。参数表示系统的控制变量，有确定性的也有随机性的。 （2）约束或限制条件 由于现实系统的客观物质条件限制，模型必须包括把决策变量限制在它们可行值之内的约束条件，而这通常是用约束的数学函数形式来表示的。 （3）目标函数 这是作为系统决策变量的一个数学函数来衡量系统的效率，即系统追求的目标。,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,50,1.2 经典极值问题,最优化在物质运输、自动控制、机械设计、采矿冶金、经济管理等科学技术各领域中有广泛应用。下面举几个专业性不强的实例。 例1 ：对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？ 解：,由此解得两个驻点：,第一个驻点不合实际意义。现在来判断第二个驻点是否为最大点,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,51,1.2 经典极值问题,例2：用长为L,宽为B的一块薄板，弯成梯形槽，x和a为多少时，容积最大？ 【分析】对本题：V=F*L，即如何弯时横断面积F最大,是极值点，极值为：,这是一个具有两个变量的无约束的非线性优化问题。,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,52,1.2 经典极值问题,例3.把半径为1的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？ 解：决定圆柱体表面积大小有两个决策变量：圆柱体底面半径r、高h。所以原问题就是在铸成圆柱体重量与球重相等的前提下，计算铸成圆柱体表面积最小。即,st.,或,这是一个具有约束条件的二个变量(r,H)的非线性最优化问题。 该问题可用拉格朗日乘子法求解。,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,53,1.2 经典极值问题,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,54,1.2 经典极值问题,例4.多参数曲线拟合问题 已知两个物理量x和y之间的依赖关系为: 其中 待定参数,为确定这些参数,对x.y测得m个实验点: 试将确定参数的问题表示成最优化问题,以上都是微积分中典型的求极值问题。二次大战前，人们把优化狭隘地理解为，取导数求极值，但是有些函数难以求导，或根本不可能求导，但又明显地具有极大值或极小值，所以这种古典的极值理论或古典微分法就无能为力了。二次大战时，由于军事业的需要，产生了运筹学，从而产生了解决多变量大型问题的新的最优化理论和方法，我们把它称为近代最优化理论与方法，与此相对，我们把古典的极值理论或古典微分法就称为经典最优化理论与方法。,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,55,1.2 经典极值问题,近代最优化理论与方法和经典最优化理论与方法之间的差别在于： 函数是否可微，经典最优化理论与方法一般研究的目标函数是可微的，而近代最优化理论与方法则对目标函数和可微性没有要求； 变量个数的多少，经典 带不带约束方程，特别是带不带不等式约束方程 最优化是一门崭新的学科，有关的理论和方法还很不完善，有许多问题有待解决，目前正处于迅速发展之中。,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,56,最1.3 最优化问题基本概念,1.3.1最优化问题的向量表示法,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,57,最1.3 最优化问题基本概念,1.3.1最优化问题的向量表示法,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,58,最1.3 最优化问题基本概念,1.3.2最优化问题的一般形式,式中f(X)称为目标函数(或求它的极小，或求它的极大)。 优化过程就是优选X，使目标函数达到最优值：f(X)-Optimization si(X)称为不等式约束，它的向量表示法可以写成： s(X)= s1(X), s2(X), ,sm(X)T hj(X)称为等式约束 X,称为集约束，在我们的问题中集约束是无关重要的，这是因为有时Rn,不然的话，也可以用不等式约束表达出来,每个容许点都是一种可能的方案（可计算出一个目标函数），所谓优化就是要在容许集中找一点 ，使得,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,59,最1.3 最优化问题基本概念,1.3.2最优化问题的一般形式,容许解或容许点,满足所有约束的向量区称为容许解或容许点。 容许点的集合称为容许集。,一般式 （1-3）中是取极小，如果遇到取极大值的问题，只须把目标函数反号就可以转化为求极小的问题,与 具有相同的最优点,以后为了简便，只研究求极小的问题 如果约束中含有“小于等于”的，两边同乘以负号，就变成“大于等于”。注意：不等式约束都要写成这种形式,最优化问题模型统一化：,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,60,最1.3 最优化问题基本概念,1.3.3 分类,其中求解一维无约束问题的方法称为一维搜索或直线搜索，这在最优化方法中起十分重要的作用。,动态问题，也称动态规划。人们在生产和科学实验活动中，往往要按照预定的任务实现某种受控过程，以期最好地完成预定任务，这叫做过程最优化。动态规划的基本概念和原理是和过程最优化紧密地联系在一起的。,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,61,最1.3 最优化问题基本概念,1.3.3最优化问题的分类,动态规划举例,如有一可逆式钢坯轧机，坯料厚度为H,成品原为h,道次数为N,要求确定各道次的压下量（或厚度），条件是：既能满足电机设备等限制条件，而又使总的轧制能耗最小？ 如图，设为5道次，每道次都有满足设备、电机等限制条件的多种方案（厚度），现在要求找出一条方案，使总的能耗最小（每一种方案都可算出一个能耗值），其特点：这是一个多阶段的过程最优化问题。,又如最短路问题：如有右图所示，希望找到一条从A点到E点的最短路线，由A经过B、C、D到E的可能路线如图中所示，相应两点连线上的数字表示此两点间的距离，问如何走法路程最短？,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,62,最1.4 二维问题图解法,目标函数的等值线,在某一条曲线上任何一点的目标函数值都等于同一常数时，该曲线称为目标函数的等值线,等值线就相当于地图上的等高线,求极小问题，在几何上无非是在容许集上找一点，使得这点所在的等值线具有最小值，由上述目标函数的等值线图可以看出，目标函数的极小点处函数值为0，即,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,63,最1.4 二维问题图解法,图解法举例,例：用图解法求解：,解：先画出目标函数的等值线，再画出约束曲线（实际上这是一条直线，这条直线就是容许集）。因为最优点是容许集上使得等值线具有最小值的点，由图可以看出，约束直线与等直线的切点正是最优点。,利用解析几何的有关方法可求得：最优点（切点）是,最优值是,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,64,最1.4 二维问题图解法,图解法举例,例：用图解法求解：,解：先画出目标函数的等值线，再画出约束曲线（实际上这是一条直线，这条直线就是容许集）。因为最优点是容许集上使得等值线具有最小值的点，由图可以看出，约束直线与等直线的切点正是最优点。,利用解析几何的有关方法可求得：最优点（切点）是,最优值是,由上例可以看出，对于二维最优问题，可以利用图解法求解。但是，三维问题和多维问题，已不便在平面上画图，此法失效。,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,65,最1.4 二维问题图解法,图解法举例,例：用图解法求解：,可得：最优点是,最优值是,由上例可以看出，对于二维最优问题，可以利用图解法求解。但是，三维问题和多维问题，已不便在平面上画图，此法失效。,利用解析几何联立求解：,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,66,最1.4 二维问题图解法,目标函数的等值面,在三维和多维空间中，使目标函数取常数值的点集：,目标函数的等值面(线)的性质,不同值的等值面（线）之间不相交，这是因为目标函数是单值函数的缘故； 除了极值点所在的等值面（线）以外，不会在区域的内部中断，这是因为目标函数是连续函数的缘故； 等值面（线）稠密的地方，目标函数值变化得比较快，稀疏的地方变化的比较慢； 一般地，在极值点附近，等值面（线）近似地呈现为同心椭球面族（椭球族）。,通过目标函数的等值面(线)图可以较清楚地理解求目标函数的意义，但对于非线性程度较严重的函数来说，其等值线的形状也就更为复杂，且可能丰在多个相对极小点，这样会给优化带来麻烦 ，由于此时找到的极值只是其中一个，可能只是局部最优，并非全局最优,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,67,最1.4 二维问题图解法,不同值的等值面之间不相交，这是因为目标函数是单值函数的缘故； 除了极值点所在的等值面以外，不会在区域的内部中断，这是因为目标函数是连续函数的缘故。 等值面稠密的地方，目标函数值变化得比较快，稀疏的地方变化的比较慢。 一般地，在极值点附近，等值面（线）近似地呈现为同心椭球面族（椭球族）。,等值线 性质,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,68,最1.5 二次函数,在n元目标函数中，除了线性函数，最简单也最重要的一类可以说就是二次函数。二次函数的一般形式是：,式中：,矩阵形式是：,式中：,Q是对称矩阵,二次型,我们最关心的是矩阵Q是正定的二次函数。,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,69,最1.5 二次函数,霍尔维茨（sylvester）定理,一个n*n阶对称矩阵Q是正定矩阵的充要条件是：矩阵Q的各阶主子式都是正的。,意义：如果矩阵Q是正定的，则（1-5）式或（1-6）式的等值面是同心椭球面族，而且它的中心是,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,70,最1.6 梯度与Hesse矩阵,1.6.1梯度及其性质,1）梯度,2）性质,梯度方向是目标函数的最速上升方向，负梯度方向是函数的最速下降方向。,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,71,最1.6 梯度与Hesse矩阵,1.6.1梯度及其性质,第一条性质说明图,第二条性质说明图,方向导数,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,72,最1.6 梯度与Hesse矩阵,1.6.1梯度及其性质,结论：梯度方向是目标函数的最速上升方向，函数的负梯度方向是目标函数的最速下降方向。,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,73,最1.6 梯度与Hesse矩阵,1.6.2 Hesse矩阵,微积分中证明，若f(x)的所有二阶偏导数连续，则：,此时Hesse矩阵为对称矩阵,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,74,最1.7 函数的极值,1.7.1 极值与极值点,现以一元函数说明之。在图所示为定义在区间a,b上的一元函数f(x)，图上有两个特殊的点x1和x3。在x1附近函数f(x)的值以f(x1)最大，在x3附近函数f(x)的值以f(x3)为最小。因此，x1和x3为函数的极大、极小点，统称为极值点。f(x1)和f(x3)相应地为函数的极大值和极小值，统称为极值。可见，极值是相对于一点附近而言的，仅有局部的性质。而函数的最大值和最小值是指整个区域而言的。一般来说，函数的极值不一定是最优值。最优值是否为极值？,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,75,最1.7 函数的极值,1.7.2 极值存在的条件,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,76,最1.7 函数的极值,1.7.2 极值存在的条件,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,77,最1.7 函数的极值,1.7.2 极值存在的条件,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,78,最1.8 非线性规划寻优方法概述,1.8.1 间接寻优方法（也称解析法）,非线性规划寻优方法大致可以归纳为两大类：间接寻优法（也称解析法）和直接寻优法（也称搜索法）。,这类方法要求把一个非线性规划问题用数学方程式描述出来，然后按照函数极值的必要条件用数学分析的方法，求出其解析解，再按照极值存在的充分条件或者问题的实际物理意义间接地确定最优解，因此称为间接法。 利用求导数寻求函数极值的方法，即古典的微分法就属于这一类 这类间接寻优方法，适用于求解目标函数具有简单而明确的数学形式的非线性规划问题。而对于目标函数比较复杂，或甚至无明确的数学表达式的情况，难以解析处理时，间接法就无能为力了。,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,79,最1.8 非线性规划寻优方法概述,1.8.2 直接寻优方法（也称搜索法）,这是一种数值方法。利用函数在某一区域的性质或一些已知点的数值，来确定下一步计算的点，这样一步步搜索逼近，最后达到最优点。直接寻优法又分为两大类：消去法和爬山法。,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,80,最1.8 非线性规划寻优方法概述,非线性规划的寻优方法是非常多的，但似乎没有一种计算方法对非线性规划问题是普通有效的，而是不同的方法适用于不同的情况，且各有优缺点。 几乎所有的非线性规划的寻优方法求解的结果往往都是局部最优解。但若非线性规划中的目标函数都是凸函数，则局部最优解决是全局最优解。 在实际工作中，当我们处理一个具体的非线性规划问题时，目标函数是否为凸函数的问题，有时可以验证，有时验证也不那么容易。而一般我们求出的极小值往往是局部最小解，这种情况下，对于许多具有迭代特性的方法为了求出全局最极小值时，可以从多个初始点出发进行迭代，求出多个局部极小值解，然后再进行比较，其中最小者即为全局最小解。,凸集：在这个集合中任取两点，所联成线段上的所有点仍在这个集合内。 凸函数：,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,81,1.9下降迭代算法及其终止准则,下降迭代算法,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,82,1.9下降迭代算法及其终止准则,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,83,1.9下降迭代算法及其终止准则,计算终止准则,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,84,1.9下降迭代算法及其终止准则,计算终止准则,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,85,2 直线搜索,2.1 一维搜索常用到的方法 2.2 消去法的基本原理 2.3 搜索区间确定 2.4 平分法 2.5 黄金分割法 2.6 牛顿法,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,86,2.1 一维搜索常用方法,高等数学 即求 df(x)/dx = 0 消去法 逐步缩小搜索区间来寻优：平分法，黄金分割法等 函数逼近法 利用目标函数的某些信息，构造新的简单函数，从而以简单曲线近似代替原来曲线，用简单曲线的极小点来估计原曲线的极小点：牛顿法等,设函数f(x)是一个单峰函数，其初始区间为a0,b0，在此区间内任取两点x1与x2 ， 且 x1f(x2) ，构成新区间x1,b0 f(x1)=f(x2) ，构成新区间a0, x2 或x1,b0 因此，只需在搜索区间内取两点，计算它们的函数值并加以比较后，总可以将搜索区间缩小，这就是消去法的原理 存在问题：,2019/7/24,西安建筑科技大学 冶金工程学院 金属材料加工研究所 压力加工数模与优化,88,2.2 消去法的基本原理,如何确定初始区间？ 如何确定插入的两点x1与x2 ？ (由于这个过程是一个迭代计算过程),不同的确定插入两点x1与x2 的方法构成了不同的直线搜索法,逐步缩小搜索区间，直至最小点所在范围达到允许的误差范围为止。,基本原理,(图),2019/7/24,西安建筑科技大学 冶金工程