最优化方法课件(1)详解

最优化方法OptimizationApproaches李冬妮[e-mail]1•学习形式/Pattern–Lectures+Labs+Reports.•成绩构成/CreditConstitution–3assignments(reports)2参考书ReferenceBooks•Nemhauser,G.L.;RinnooyKan,A.H.G.;,eds.(1989).Optimization.HandbooksinOperationsResearchandManagementScience.1.Amsterdam:North-HollandPublishingCo.•WilliamJ.Cook,WilliamH.Cunningham,WilliamR.Pulleyblank,AlexanderSchrijver;CombinatorialOptimization;JohnWiley&Sons;1edition(November12,1997)•JonLee;AFirstCourseinCombinatorialOptimization;CambridgeUniversityPress;2004.•ChristosH.PapadimitriouandKennethSteiglitzCombinatorialOptimization:AlgorithmsandComplexity;DoverPubns;(paperback,Unabridgededition,July1998)•最优化方法（第二版），施光燕，钱伟懿，庞丽萍，高等教育出版社，2007年•最优化方法，何坚勇，清华大学出版社，2007年•最优化方法及其应用，郭科，陈聆，魏友华，高等教育出版社，2007年•最优化理论与算法，陈宝林，清华大学出版社•最优化理论与方法，袁亚湘，科学出版社•近代优化方法，徐成贤，科学出版社3IntroductiontoMathematicModelingandOptimization4数学家名人录5Introduction:Concept,History,ProgressandClassofMathematicModelingandOptimization6Contents1.引言:数学建模与最优化的背景①数学建模的进展②最优化技术的进展2.数学建摸的基本概念与分类①数学模型与数学建模②数学模型的分类③数学模型的应用领域④数学建模举例⑤数学建模的过程3.最优化的基本概念与分类①最优化的基本概念②最优化技术分类③最优化建模与求解示例4.数学建摸与最优化的关系71引言:数学建模与最优化的背景•数学建模–数学建模的历史和数学的历史基本上是一样的；–古埃及几何学产生于尼罗河泛滥后土地的重新丈量；–古印度几何学的起源则与宗教密切相关–中国的《周批算经》是讨论天文学测量的巨著；–大约公元前５世纪，毕达哥拉斯学派重视自然及社会中不变因素的研究，把几何、算术、天文、音乐称为“四艺”，在其中追求宇宙的和谐规律性。–17世纪出现了笛卡尔、牛顿、莱布尼兹等数学家，奠定了微积分的基础，其研究的对象包括行星运动、流体运动、机械运动、植物生长等均属于数学建模的范畴；–19世纪后期，数学成为了研究数与形、运动与变化的学问；–可以说，数学是模式的科学，其目的是要揭示人们从自然界和数学本身的抽象世界中所观察到的结构和对称性。81引言:数学建模与最优化的背景•最优化–最优化问题有相当长的发展历史，最一早可以追溯到牛顿、拉格朗日时代。由于牛顿等对微积分的重要贡献，才使得差分方程法解决最优化问题成为可能。这其中的先锋者包括贝诺利(Bemot)，欧拉(Eller)和拉格郎日等。–Lagrange发明了有名的拉格郎日乘子法。柯西(Canchy)首先提出了最速下降法(解决无约束最小化问题)。尽管有这些早期的成果，最优化的发展相当缓慢，直到50年代高速计算机的出现。50年代后，最优化的发展进入旺盛期，出现了大量的新算法。Dantzig提出了解决线性规划问题的simplex方法，Bellman提出了动态规划最优化最优性原理，使得约束最优化成为可能性。Kuhn和Tucher提出的最优化规划问题的充分和必要条件开创了非线性规划优化技术的基础。–几何规划优化由Zountijker和Rosen在60年代提出，Gomory同–时提出了积分规划技术。随机(或统计)规划技术最早山Danzig和charnes提出，Cooper发展了该技术。91引言:数学建模与最优化的背景•最优化（续）–构成现代优化理论的相关技术是模拟退火SA、遗传算法GA等现代启发式最优化算法，他们均是从60年代发展起来的。–SA算法是一种组合优化算法，足模拟材半l)Jl日一中的退火处理(Annealing)得名的优化算法。退火是材料加工的一种处理方式，即首先将固体加工到融化状态，再逐渐冷却，直到材料达到结品状态。在这个过程中，固体内的自由能最终被降低到最小状态。在实践中，冷却过程必须非常小心控制，以防止固体结晶到局部最小能量状态，即局部最优解，从而影响材料的强度等各种性能。模拟退火算法模拟这样的物理过程，将组合最小化能量状态模拟为最终晶体状态，并设计一个类似的处理过程，达到优化的目的。102数学建摸的基本概念与分类1.数学模型与数学建模2.数学模型的分类3.数学模型的应用领域4.数学建模举例5.数学建模的过程11数学建模与数学模型•模型概念–把对象实体通过适当的过滤,用适当的表现规则描绘出的简洁的模仿品.通过这个模仿品,人们可以了解到所研究实体的本质,而且在形式上便于人们对实体进行分析和处理。•数学模型(MathematicalModel)–对于一个现实对象，为了一个特定目的，–根据其内在规律，作出必要的简化假设，–运用适当的数学工具，得到的一个数学结构。•数学建模（MathematicalModeling)–建立数学模型的全过程（包括表述、求解、解释、检验等）12数学模型的分类•按模型的应用领域分类–生物数学模型–医学数学模型–地质数学模型–数量经济学模型–数学社会学模型13数学模型的分类•按是否考虑随机因素分类–确定性模型–随机性模型•按是否考虑模型的变化分类–静态模型–动态模型•按应用离散方法或连续方法–离散模型–连续模型•按建立模型的数学方法分类–几何模型–微分方程模型–图论模型–规划论模型–马氏链模型1415数学建模示例椅子能在不平的地面上放稳吗问题分析模型假设通常~三只脚着地放稳~四只脚着地•四条腿一样长，椅脚与地面点接触，四脚连线呈正方形;•地面高度连续变化，可视为数学上的连续曲面;•地面相对平坦，使椅子在任意位置至少三只脚同时着地。16模型构成用数学语言把椅子位置和四只脚着地的关系表示出来•椅子位置利用正方形(椅脚连线)的对称性xBADCOD´C´B´A´用(对角线与x轴的夹角)表示椅子位置•四只脚着地距离是的函数四个距离(四只脚)A,C两脚与地面距离之和~f()B,D两脚与地面距离之和~g()两个距离椅脚与地面距离为零正方形ABCD绕O点旋转正方形对称性17用数学语言把椅子位置和四只脚着地的关系表示出来f(),g()是连续函数对任意,f(),g()至少一个为0数学问题已知：f(),g()是连续函数;对任意，f()•g()=0;且g(0)=0，f(0)0.证明：存在0，使f(0)=g(0)=0.模型构成地面为连续曲面椅子在任意位置至少三只脚着地2020/2/12AlgorithmsDesignTechniquesandAnalysis18模型求解给出一种简单、粗糙的证明方法将椅子旋转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()的确定19数学建模的基本方法•机理分析•测试分析根据对客观事物特性的认识，找出反映内部机理的数量规律将对象看作“黑箱”,通过对量测数据的统计分析，找出与数据拟合最好的模型机理分析没有统一的方法，主要通过实例研究(CaseStudies)来学习。•二者结合用机理分析建立模型结构,用测试分析确定模型参数数学建模的方法和步骤20数学建模的一般步骤模型准备模型假设模型构成模型求解模型分析模型检验模型应用模型准备了解实际背景明确建模目的搜集有关信息掌握对象特征形成一个比较清晰的‘问题’21模型假设针对问题特点和建模目的作出合理的、简化的假设在合理与简化之间作出折中模型构成用数学的语言、符号描述问题发挥想像力使用类比法尽量采用简单的数学工具数学建模的一般步骤22模型求解各种数学方法、软件和计算机技术如结果的误差分析、统计分析、模型对数据的稳定性分析模型分析模型检验与实际现象、数据比较，检验模型的合理性、适用性模型应用数学建模的一般步骤23数学建模的全过程现实对象的信息数学模型现实对象的解答数学模型的解答表述求解解释验证(归纳)(演绎)表述求解解释验证根据建模目的和信息将实际问题“翻译”成数学问题选择适当的数学方法求得数学模型的解答将数学语言表述的解答“翻译”回实际对象用现实对象的信息检验得到的解答实践现实世界数学世界理论实践1.最优化的基本概念2.最优化技术分类3.最优化建模与求解示例3最优化的基本概念与分类24最优化的基本概念•最优化技术是一门较新的学科分支。它是在本世纪五十年代初在电子计算机广泛应用的推动下才得到迅速发展，并成为一门直到目前仍然十分活跃的新兴学科。最优化所研究的问题是在众多的可行方案中怎样选择最合理的一种以达到最优目标。•将达到最优目标的方案称为最优方案或最优决策，搜寻最优方案的方法称为最优化方法，关于最优化方法的数学理论称为最优化论。•最优化问题至少有两要素：一是可能的方案；二是要追求的目标。后者是前者的函数。如果第一要素与时间无关就称为静态最优化问题，否则称为动态最优化问题。25最优化的基本概念1.最优化技术工作被分成两个方面，一是由实际生产或科技问题形成最优化的数学模型，二是对所形成的数学问题进行数学加工和求解。2.对于第二方面的工作，目前已有一些较系统成熟的资料，但对于第一方面工作即如何由实际问题抽象出数学模型，目前很少有系统的资料，而这一工作在应用最优化技术解决实际问题时是十分关键的基础，没有这一工作，最优化技术将成为无水之源，难以健康发展。27最优化问题举例最优化在物质运输、自动控制、机械设计、采矿冶金、经济管理等科学技术各领域中有广泛应用。下面举几个专业性不强的实例。例1.把半径为1的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？解：决定圆柱体表面积大小有两个决策变量：圆柱体底面半径r、高h。问题的约束条件是所铸圆柱体重量与球重相等。即3234Rhr1.0.R为金属比重28即即问题追求的目标是圆柱体表面积最小。即min则得原问题的数学模型：s.t.Subjectto.固定.342hr0342hr222rrh22min224..03rhrstrh29利用在高等数学中所学的Lagrange乘子法可求解本问题分别对r.h.λ求偏导数,并令其等于零.有:3422..22hrrrhhrLrhhrLrrhLrhrhrL203402024222.323r3322h最优化方法分类•常见最优化方法：–线性规划–整数规划–非线性规划–动态规划–多目标规划连续优化离散规划•线性规划LP目标和约束均为线性函数•非线性规划NLP目标和约束均为非线性函数二次规划