67数值分析

最优化理论与方法主要内容第一章绪论第二章线性规划第三章整数规划第四章非线性优化基本理论第五章无约束最优化方法第六章约束最优化方法第七章动态规划第八章现代优化方法第一章绪论1.1学科简介最优化方法是一个重要的数学分支，它研究讨论在众多的方案中什么样的方案最优以及怎样找出最优方案。应用领域如下：工程设计中如何确定设计参数，使设计方案既能满足设计要求又能降低成本，使得设计在某种意义上是最好的；资源分配中，怎样分配有限资源，使得分配方案既能满足各方面的基本要求，又能获得好的经济效益；生产计划安排中，选择怎样的计划才能提高产值和利润；原料配比问题中，怎样确定各种成分的比例，才能提高质量，降低成本；城建规划中，怎样安排工厂、机关、学校、商店、医院、住户和其他单位的合理布局，才能方便群众，有利于城市各行业的发展；农田规划中，怎样安排各种农作物的合理布局，才能保持高产稳产，发挥地区优势；军事指挥中，怎样确定最佳作战方案，才能有效地消灭敌人，保护自己，有利于战争的全局；等等。最优化理论与方法为这些问题的解决，提供理论基础和求解方法。最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科，它是一门应用广泛、实用性强的学科。最优化理论与技术发展历程早在17世纪，英国的伟大科学家Newton发明微积分的时代，已经提出了极值问题，后来Lagrange在研究一个函数在一组等式约束条件下的极值问题时提出了乘数法。1847年法国数学家柯西（Cauchy）研究了函数值沿什么方向下降最快的问题，提出了最速下降法。1939年前苏联数学家康托诺维奇提出了解决下料问题和运输问题这两种线性规划的求解方法。1947年美国数学家旦泽（G.B.Dantzig）在研究美国空军资源的优化配置时提出了线性规划的通用解法——单纯形法。最优化理论与技术发展历程（续）20世纪50年代初，使用电子计算机求解线性规划获得成功。20世纪50年代以后，人们从一些自然现象和规律中受得到启发，提出了许多求解复杂优化问题的新方法。如遗传算法、蚁群算法、禁忌搜索算法、模拟退火算法等，取得了一系列较好的实验及应用结果。20世纪60年代初，从生物进化的机理中受到启发，美国密执根（Michigan）大学的霍兰（Holland）教授提出了遗传算法。20世纪80年代中期遗传算法的研究蓬勃发展；受蚂蚁觅食时的通信机制的启发，20世纪90年代Dorigo提出了蚁群优化算法(AntColonyOptimization，ACO)来解决经典的“货郎担问题”，近年来该方法也受到了广泛重视。最优化理论与技术发展历程（续）1995年，Kennedy和Ebe出art提出粒子群优化(ParticleSwarmOptimization)算法。这种算法模仿鸟类和鱼类群体觅食迁徙中，个体与群体协调一致的机理，通过群体最优方向、个体最优方法和惯性方向的协调来求解实数优化问题。近年来该方法已经成为新的研究热点。1999年，Linhares提出捕食搜索(PredatorySearch)算法。这种算法模拟猛兽捕食中大范围搜寻和局部蹲守的特点，通过设置全局搜索和局部搜索间变换的阔值来协调两种不同的搜索模式，从而实现了对全局搜索能力和局部搜索能力的兼顾。最优化理论与技术发展历程（续）此外，近年来，还有模仿食物链中物种相互依存的人工生命算法(ArtificialLifeAlgorithms);模拟人类社会多种文化间的认同、排斥、交流和改变等特性的文化算法(CulturalAlgorithms)等一些各具特点但知名度不够高的智能优化算法提出。最优化理论与技术研究意义由于生产和科学技术的迅猛发展，特别是计算机科学与技术的发展，使得最优化问题的研究不仅成为一种迫切需要，而且有了求解的有力工具。最优化在本质上是一门交叉学科。它对许多学科产生了重大影响，并已成为不同领域中很多工作都不可缺少的工具。近半个多世纪以来，最优化方法得到了充分的研究，在理论上取得了非常重要的研究成果，在实际应用中正在发挥越来越大的作用。广泛的应用于军事与国防、市场销售、生产计划、库存管理、运输问题、财政会计与金融、人才资源管理、设备维修与更新、项目选择与评价、工程优化设计、计算机与信息系统、城市管理等领域。1.2最优化问题的数学模型例1-1某工厂生产A，B两种产品，若生产A产品每吨需煤9吨，木材4立方米，人力3个劳动日，生产B产品每吨需煤4吨，木材5立方米，人力10个劳动日。已知A，B两种产品每吨的价格分别为700元和1200元，并知该厂现有的资源为：煤360吨，木材200立方米，可提供人力300个劳动日，试问应安排A，B产品各生产多少吨，能使该厂的产值最高？产品AB资源煤94360木材45200人力310300单价7001200表1-1已知数剧列表建立其数学模型。设计划生产A，B产品的吨数为x1、x2，产值为s，该问题的数学模型如下：.max)11(120070021xxs..ts)51(0,)41(300103)31(20054)21(3604921212121xxxxxxxxTX1剖面YXXY2L2PX2例1-2两个构件组成对称桁(heng)架如图1-1所示。已知桁架的跨度2L，高度x2的上限H，承受负荷2P，钢管的厚度T，材料比重ρ，纵向弹性模数E及容许应力σy。试确定钢管的平均直径x1及桁架的高度x2，使桁架的重量最小。图1-1对称桁架示意图（1）由于空间限制，要求x2不能超过高度上限H，即x2≤H212221)(2xLTxG约束条件：目标函数：桁架的重量（2）钢管上的压应力不能超过材料的容许应力σyyxTxxLP2121222)(（3）参数的选择还必须保证的负荷2P的作用下钢管不发生弯曲，这就要求压就力不超过临界应力σl。)(8)()(22222122121222xLTxExTxxLP优化数学模型：0,)(8)()()(..)(2),(min21222221221212222121222221222121xxxLTxExTxxLPxTxxLPHxtsxLTxxxfy优化模型一般形式：)61(},,2,1{0)(},,2,1{0)(..)(minlJjxhmIixgtsxfji其中nTnRxxxx),,,(21:决策变量或设计向量，n为向量维数。RRfn::目标函数。)(0Iigi)(0Jjhj和:约束函数或约束条件。)(:IiRRgni:不等式约束。)(:JjRRhnj:等式约束。令},0,,0|{JjhIigxDji称D为问题（1-6）的可行域；几个概念与优化问题分类：D中的点，即满足约束条件的点称为可行点或可行解。若一个最优化问题的可行域是整个空间，则称该问题为无约束问题。若可行域是有限集，则该问题为组合优化问题。如果设计变量与时间无关，则该问题属于静态最优化问题；否则称为动态最优化问题。如果目标函数和约束条件均为设计变量的线性函数，则称该问题为线性规划问题，否则称该问题为非线性规划问题。如果约束中要求设计变量取整数值，则称该问题为整数规划问题。最优化问题的数学模型包含三个要素：目标函数；设计变量；约束条件。最优化问题的最优解概念：对于极大化问题，可类似地定义整体最优解和局部最优解。根据上述定义，整体最优解也是局部最优解，而局部最优解不一定是整体最优解。对于凸规划，局部最优解也是整体最优解。小结：1.3最优化问题的求解方法1.解析法利用高等数学中求极值的解析方法。优点：概念简明，计算精确等。缺点：只能适用于简单或特殊问题的寻优，对于复杂的工程实际问题通常无能为力。应用：极少使用。例1-3对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？axa-2xxa-2x解：设剪去的正方形边长为x，由题意易知，水槽容积为xxaxf2)2()(求导得两个驻点：axax61,21第一个驻点不合实际，这是因为剪去4个边长为的正方形相当于将铁板全部剪去。第二个驻点：axf824)(''04)6(''aaf因为所以6ax是极大点。因此，每个角剪去边长为a/6的正方形可使所制成的水槽容积最大。xzy2.图解法适用范围：二维最优化问题。求解布骤：把可行域用图示的方式在坐标系中画出，。把目标函数用等高线的形式在坐标系中画出。根据等高线的变化趋势求出二维最优化问题的最优解。例1-5用图解法求解二维最优化问题0,01..22min2122212221xxxxtsxx图1-2图解法举例3.经典算法包括单纯形法、动态规划方法、分枝定界法等传统算法。该类算法理论上比较完善，对于特定类型的最优化问题求解，优势明显。4.迭代搜索型方法从某一选定的初始点出发，根据目标函数、约束函数在该点的某些信息，按照某种迭代搜索的方式方法，到达一个更好的新点，从该新点出发用同样的方法再搜索更好的点，如此不断重复，直到满足某种迭代终止的准则。如步长加速法、旋转方向法、可行方向法等。5.转化型方法先将将问题转化为另一最优化问题，然后求解。如罚函数法等。6.演化型方法将优化过程转化为系统动态的演化过程，用基于系统动态的演化来实现优化，如遗传算法、蚁群优化算法等。