最优化导论课件.ppt
2023/3/13,Algorithms Design Techniques and Analysis,1,教学目的、内容和形式,目的:掌握数学建模及最优化的基本理论；掌握几类最优化问题的算法；通过学习常用的一些建模的方法,培养分析问题、解决问题的能力.教材数学建模与最优化，董文永,机械工业出版社，2009.参考书:见后面的参考书目录.学习形式:自学、讲授相结合.成绩构成:平时(30%-40%)+期末(60%-70%).,2023/3/13,Algorithms Design Techniques and Analysis,2,参考文献,数学建模与数学实验 赵静 但琦 高等教育出版社 系统仿真导论，肖田元 张燕云 陈加栋，清华大学出版社 计算机仿真技术基础，刘瑞叶 任洪林 李志民，电子工业出版社 自动控制原理除第4、8、10三章，庞国仲，中国科大出版社；计算机仿真技术(吴旭光)，吴旭光，化学工业出版社 系统仿真技术，彭晓源，北京航空航天大学出版社数学建模导论 陈理荣 北京邮电大学出版社数学建模方法 齐 欢 华中理工大学出版社数学实验 姜启源 高等教育出版社数学建模 袁震东，洪渊，林武忠等 华东师范大学出版社数学模型引论 唐焕文 大连理工大学出版社运筹学 钱颂迪等 清华大学出版社现代优化计算方法 刑文训 清华大学出版社最优化原理与方法，薛嘉庆，冶金工业出版社，1986。最优化计算方法，席少霖，赵凤治，上海科学技术出版社，1983。非线性方程组解法与最优化方法，王德人，高等教育出版社，1985。非线性规划，胡毓 达，高等教育出版社，1990,2023/3/13,Algorithms Design Techniques and Analysis,3,Main contents,Part 1 Optimization:Theory and PracticeIntroduction:Concept,Background and Progress Linear ProgrammingNonlinear ProgrammingSimulation OptimizationDynamic programming and Optimization ControlNetwork OptimizationPart 2 The Technology of Mathematic ModelingFuzzy Modeling and Data AnalysisSystem IdentificationHierarchical Analysis Aggregation AnalysisDifferential Modeling:Theory and PracticePart 3 Meta-Heuristic Optimization MethodsAnt AlgorithmsITO Algorithms,2023/3/13,Algorithms Design Techniques and Analysis,4,数学家名人录,2023/3/13,Algorithms Design Techniques and Analysis,Chapter 1,Introduction:Concept,History,Progress and Class of Mathematic Modeling and Optimization,2023/3/13,Algorithms Design Techniques and Analysis,6,Contents of CH1,引言:数学建模与最优化的背景数学建模的进展最优化技术的进展数学建摸的基本概念与分类数学模型与数学建模数学模型的分类数学模型的应用领域数学建模举例数学建模的过程最优化的基本概念与分类最优化的基本概念最优化技术分类最优化建模与求解示例数学建摸与最优化的关系,2023/3/13,Algorithms Design Techniques and Analysis,7,1 引言:数学建模与最优化的背景,1.1 数学建模的历史与意义1.2 最优化的历史与意义,2023/3/13,Algorithms Design Techniques and Analysis,8,1.1 数学建模的历史与意义,数学建模的历史和数学的历史基本上是一样的；古埃及几何学产生于尼罗河泛滥后土地的重新丈量；古印度几何学的起源则与宗教密切相关中国的周批算经是讨论天文学测量的巨著；大约公元前世纪，毕达哥拉斯学派重视自然及社会中不变因素的研究，把几何、算术、天文、音乐称为“四艺”，在其中追求宇宙的和谐规律性。17世纪出现了笛卡尔、牛顿、莱布尼兹等数学家，奠定了微积分的基础，其研究的对象包括行星运动、流体运动、机械运动、植物生长等均属于数学建模的范畴；19世纪后期，数学成为了研究数与形、运动与变化的学问；可以说，数学是模式的科学，其目的是要揭示人们从自然界和数学本身的抽象世界中所观察到的结构和对称性。,2023/3/13,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发展了该技术。,2023/3/13,Algorithms Design Techniques and Analysis,10,构成现代优化理论的相关技术是模拟退火SA、遗传算法GA等现代启发式最优化算法，他们均是从60年代发展起来的。SA算法是一种组合优化算法，足模拟材半l)Jl日一中的退火处理(Annealing)得名的优化算法。退火是材料加工的一种处理方式，即首先将固体加工到融化状态，再逐渐冷却，直到材料达到结品状态。在这个过程中，固体内的自由能最终被降低到最小状态。在实践中，冷却过程必须非常小心控制，以防止固体结晶到局部最小能量状态，即局部最优解，从而影响材料的强度等各种性能。模拟退火算法模拟这样的物理过程，将组合最小化能量状态模拟为最终晶体状态，并设计一个类似的处理过程，达到优化的目的。,2023/3/13,Algorithms Design Techniques and Analysis,11,1.2 数学建摸的基本概念与分类,数学模型与数学建模数学模型的分类数学模型的应用领域数学建模举例数学建模的过程,2023/3/13,Algorithms Design Techniques and Analysis,12,1.2.1 数学建模与数学模型,模型是把对象实体通过适当的过滤,用适当的表现规则描绘出的简洁的模仿品.通过这个模仿品,人们可以了解到所研究实体的本质,而且在形式上便于人们对实体进行分析和处理。,模型概念,模型是人们十分熟悉的东西，例如：玩具、照片及展览会里的电站模型、火箭模型等实物模型；地图、电路图、分子结构图等经过一定抽象的符号模型；大型水箱中的舰艇模型、风洞中的飞机模型等物理模型。,2023/3/13,Algorithms Design Techniques and Analysis,13,数学模型(Mathematical Model)和数学建模（Mathematical Modeling),对于一个现实对象，为了一个特定目的，根据其内在规律，作出必要的简化假设，运用适当的数学工具，得到的一个数学结构。,建立数学模型的全过程（包括表述、求解、解释、检验等）,数学模型,数学建模,2023/3/13,Algorithms Design Techniques and Analysis,14,数学建模的具体应用,分析与设计,预报与决策,控制与优化,规划与管理,数学建模,计算机技术,知识经济,2023/3/13,Algorithms Design Techniques and Analysis,15,数学模型的分类,按模型的应用领域分类,生物数学模型,医学数学模型,地质数学模型,数量经济学模型,数学社会学模型,2023/3/13,Algorithms Design Techniques and Analysis,16,数学模型的分类,按是否考虑随机因素分类,确定性模型,随机性模型,2023/3/13,Algorithms Design Techniques and Analysis,17,数学模型的分类(续),按是否考虑模型的变化分类 静态模型动态模型,按建立模型的数学方法分类 几何模型微分方程模型图论模型规划论模型马氏链模型,按应用离散方法或连续方法 离散模型连续模型,2023/3/13,Algorithms Design Techniques and Analysis,18,数学模型的分类(续),按人们对事物发展过程的了解程度分类,白箱模型：指那些内部规律比较清楚的模型。如力学、热学、电学以及相关的工程技术问题。,灰箱模型：指那些内部规律尚不十分清楚，在建立和改善模型方面都还不同程度地有许多工作要做的问题。如气象学、生态学经济学等领域的模型。,黑箱模型：指一些其内部规律还很少为人们所知的现象。如生命科学、社会科学等方面的问题。但由于因素众多、关系复杂，也可简化为灰箱模型来研究。,2023/3/13,Algorithms Design Techniques and Analysis,19,数学建模示例,椅子能在不平的地面上放稳吗,问题分析,模型假设,通常 三只脚着地,放稳 四只脚着地,四条腿一样长，椅脚与地面点接触，四脚连线呈正方形;,地面高度连续变化，可视为数学上的连续曲面;,地面相对平坦，使椅子在任意位置至少三只脚同时着地。,2023/3/13,Algorithms Design Techniques and Analysis,20,模型构成,用数学语言把椅子位置和四只脚着地的关系表示出来,椅子位置,利用正方形(椅脚连线)的对称性,用(对角线与x轴的夹角)表示椅子位置,四只脚着地,距离是的函数,四个距离(四只脚),A,C 两脚与地面距离之和 f(),B,D 两脚与地面距离之和 g(),两个距离,椅脚与地面距离为零,正方形ABCD绕O点旋转,2023/3/13,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.,模型构成,地面为连续曲面,椅子在任意位置至少三只脚着地,2023/3/13,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()的确定,2023/3/13,Algorithms Design Techniques and Analysis,23,商人们怎样安全过河,问题(智力游戏),3名商人 3名随从,随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货.,但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?,问题分析,多步决策过程,决策 每一步(此岸到彼岸或彼岸到此岸)船上的人员,要求在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河.,2023/3/13,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).,多步决策问题,2023/3/13,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,2023/3/13,Algorithms Design Techniques and Analysis,26,Demo,2023/3/13,Algorithms Design Techniques and Analysis,27,数学建模的基本方法,机理分析,测试分析,根据对客观事物特性的认识，找出反映内部机理的数量规律,将对象看作“黑箱”,通过对量测数据的统计分析，找出与数据拟合最好的模型,机理分析没有统一的方法，主要通过实例研究(Case Studies)来学习。,二者结合,用机理分析建立模型结构,用测试分析确定模型参数,数学建模的方法和步骤,2023/3/13,Algorithms Design Techniques and Analysis,28,数学建模的一般步骤,模型准备,了解实际背景,明确建模目的,搜集有关信息,掌握对象特征,形成一个比较清晰的问题,2023/3/13,Algorithms Design Techniques and Analysis,29,模型假设,针对问题特点和建模目的,作出合理的、简化的假设,在合理与简化之间作出折中,模型构成,用数学的语言、符号描述问题,发挥想像力,使用类比法,尽量采用简单的数学工具,数学建模的一般步骤,2023/3/13,Algorithms Design Techniques and Analysis,30,模型求解,各种数学方法、软件和计算机技术,如结果的误差分析、统计分析、模型对数据的稳定性分析,模型分析,模型检验,与实际现象、数据比较，检验模型的合理性、适用性,模型应用,数学建模的一般步骤,2023/3/13,Algorithms Design Techniques and Analysis,31,数学建模的全过程,现实对象的信息,数学模型,现实对象的解答,数学模型的解答,(归纳),(演绎),表述,求解,解释,验证,根据建模目的和信息将实际问题“翻译”成数学问题,选择适当的数学方法求得数学模型的解答,将数学语言表述的解答“翻译”回实际对象,用现实对象的信息检验得到的解答,实践,现实世界,数学世界,2023/3/13,Algorithms Design Techniques and Analysis,32,1.3 最优化的基本概念与分类,最优化的基本概念最优化技术分类最优化建模与求解示例,2023/3/13,Algorithms Design Techniques and Analysis,33,最优化的基本概念,最优化技术是一门较新的学科分支。它是在本世纪五十年代初在电子计算机广泛应用的推动下才得到迅速发展，并成为一门直到目前仍然十分活跃的新兴学科。最优化所研究的问题是在众多的可行方案中怎样选择最合理的一种以达到最优目标。将达到最优目标的方案称为最优方案或最优决策，搜寻最优方案的方法称为最优化方法，关于最优化方法的数学理论称为最优化论。最优化问题至少有两要素：一是可能的方案；二是要追求的目标。后者是前者的函数。如果第一要素与时间无关就称为静态最优化问题，否则称为动态最优化问题。,2023/3/13,Algorithms Design Techniques and Analysis,34,最优化技术应用范围十分广泛，在我们日常生活中，在工农业生产、社会经济、国防、航空航天工业中处处可见其用途。比如我们自己所接触过的课题有：结构最优设计、电子器件最优设计、光学仪器最优设计、化工工程最优设计、标腔最优配方、运输方案、机器最优配备、油田开发、水库调度、饲料最优配方、食品结构优化等等。,2023/3/13,Algorithms Design Techniques and Analysis,35,最优化技术工作被分成两个方面，一是由实际生产或科技问题形成最优化的数学模型，二是对所形成的数学问题进行数学加工和求解。对于第二方面的工作，目前已有一些较系统成熟的资料，但对于第一方面工作即如何由实际问题抽象出数学模型，目前很少有系统的资料，而这一工作在应用最优化技术解决实际问题时是十分关键的基础，没有这一工作，最优化技术将成为无水之源，难以健康发展。,2023/3/13,Algorithms Design Techniques and Analysis,36,最优化问题举例,最优化在物质运输、自动控制、机械设计、采矿冶金、经济管理等科学技术各领域中有广泛应用。下面举几个专业性不强的实例。例1.把半径为1的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？解：决定圆柱体表面积大小有两个决策变量：圆柱体底面半径r、高h。问题的约束条件是所铸圆柱体重量与球重相等。即,2023/3/13,Algorithms Design Techniques and Analysis,37,即 即 问题追求的目标是圆柱体表面积最小。即 min 则得原问题的数学模型：s.t.Subject to.固定.,2023/3/13,Algorithms Design Techniques and Analysis,38,利用在高等数学中所学的Lagrange乘子法可求解本问题 分别对r.h.求偏导数,并令其等于零.有:,2023/3/13,Algorithms Design Techniques and Analysis,39,例2.多参数曲线拟合问题 已知两个物理量x和y之间的依赖关系为:其中 和 待定参数,为确定这些参数,对x.y测得m个实验点:试将确定参数的问题表示成最优化问题.,2023/3/13,Algorithms Design Techniques and Analysis,40,解:很显然对参数 和 任意给定的一组数值,就由上式确定了 y关于x的一个函数关系式,在几何上它对应一条曲线,这条曲线不一定通过那m个测量点,而要产生“偏差”.将测量点沿垂线方向到曲线的距离的平方和作为这种“偏差”的度量.即显然偏差S越小,曲线就拟合得越好,说明参数值就选择得越好，从而我们的问题就转化为5维无约束最优化问题。即：,2023/3/13,Algorithms Design Techniques and Analysis,41,例3：两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，弹性模量为E，屈吸强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。,受力分析图,圆杆截面图,桁杆示意图,2023/3/13,Algorithms Design Techniques and Analysis,42,解：桁杆的截面积为：桁杆的总重量为：负载2p在每个杆上的分力为：于是杆截面的应力为：此应力要求小于材料的屈吸极限，即,2023/3/13,Algorithms Design Techniques and Analysis,43,圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为 由此得稳定约束：,2023/3/13,Algorithms Design Techniques and Analysis,44,另外还要考虑到设计变量d和h有界。从而得到两杆桁架最优设计问题的数学模型：,2023/3/13,Algorithms Design Techniques and Analysis,45,例4.（混合饲料配合）以最低成本确定满足动物所需营养的最优混合饲料。下面举一个简化了的例子予以说明。设每天需要混合饲料的批量为100磅，这份饲料必须含：至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分为：,2023/3/13,Algorithms Design Techniques and Analysis,46,配料,每磅配料中的营养含量,钙,蛋白质,纤维,每磅成本（元）,石灰石谷物大豆粉,0.380 0.00 0.000.001 0.09 0.020.002 0.50 0.08,0.0164 0.0463 0.1250,解:根据前面介绍的建模要素得出此问题的数学模型如下:设 是生产100磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。,2023/3/13,Algorithms Design Techniques and Analysis,47,2023/3/13,Algorithms Design Techniques and Analysis,48,最优化问题的基本概念,n维欧氏空间 向量向量变量实值函数：无约束最优问题：,2023/3/13,Algorithms Design Techniques and Analysis,49,最优化问题的基本概念,向量变量向量值函数：其中 是向量变量实值函数则有m个式约束的最优化问题为：,2023/3/13,Algorithms Design Techniques and Analysis,50,在本课程我们讨论的是如下形式的静态最优化问题：其中 均为向量Z的实值连续函数，有二阶连续偏导数.,2023/3/13,Algorithms Design Techniques and Analysis,51,采用向量表示法即为：其中 这就是最优化问题的一般形式，又称非线性规划。注意等式约束通常可用不等式约束表示出来，有时,2023/3/13,Algorithms Design Techniques and Analysis,52,因此，一般不考虑等式约束。称满足所有约束条件的向量Z为容许解或可行解，容许点的集合称为容许集或可行集。在容许集中找一点，使目标函数 在该点取最小值，即满足：的过程即为最优化的求解过程。称为问题的最优点，称为最优值，称为最优解。,2023/3/13,Algorithms Design Techniques and Analysis,53,最优化问题模型统一化：在上述最优化问题的一般式中只是取极小值，如果遇到极大化问题，只须将目标函数反号就可以化为求极小的问题。例如：函数 在 有极大值，将它改变符号后，在同一点 处 有极小值 由此可见：有相同最优点。,2023/3/13,Algorithms Design Techniques and Analysis,54,如果约束条件中有“小于等于“的，即 则转化为，另外，等式约束 可以由下面两个不等式来代替：因而最优化问题的一般形式又可写成：,2023/3/13,Algorithms Design Techniques and Analysis,55,其中求解一维无约束问题的方法称为一维搜索或直线搜索，这在最优化方法中起十分重要的作用。,对于最优化问题一般可作如下分类：,
