最优化导论

2020/2/23AlgorithmsDesignTechniquesandAnalysis1教学目的、内容和形式目的:掌握数学建模及最优化的基本理论；掌握几类最优化问题的算法；通过学习常用的一些建模的方法,培养分析问题、解决问题的能力.教材《数学建模与最优化》，董文永,机械工业出版社，2009.参考书:见后面的参考书目录.学习形式:自学、讲授相结合.成绩构成:平时(30%-40%)+期末(60%-70%).2020/2/23AlgorithmsDesignTechniquesandAnalysis2参考文献数学建模与数学实验赵静但琦高等教育出版社系统仿真导论，肖田元张燕云陈加栋，清华大学出版社计算机仿真技术基础，刘瑞叶任洪林李志民，电子工业出版社《自动控制原理》除第4、8、10三章，庞国仲，中国科大出版社；计算机仿真技术(吴旭光)，吴旭光，化学工业出版社系统仿真技术，彭晓源，北京航空航天大学出版社数学建模导论陈理荣北京邮电大学出版社数学建模方法齐欢华中理工大学出版社数学实验姜启源高等教育出版社数学建模袁震东，洪渊，林武忠等华东师范大学出版社数学模型引论唐焕文大连理工大学出版社运筹学钱颂迪等清华大学出版社现代优化计算方法刑文训清华大学出版社最优化原理与方法，薛嘉庆，冶金工业出版社，1986。最优化计算方法，席少霖，赵凤治，上海科学技术出版社，1983。非线性方程组解法与最优化方法，王德人，高等教育出版社，1985。非线性规划，胡毓达，高等教育出版社，19902020/2/23AlgorithmsDesignTechniquesandAnalysis3MaincontentsPart1Optimization:TheoryandPractice1.Introduction:Concept,BackgroundandProgress2.LinearProgramming3.NonlinearProgramming4.SimulationOptimization5.DynamicprogrammingandOptimizationControl6.NetworkOptimizationPart2TheTechnologyofMathematicModeling1.FuzzyModelingandDataAnalysis2.SystemIdentification3.HierarchicalAnalysis4.AggregationAnalysis5.DifferentialModeling:TheoryandPracticePart3Meta-HeuristicOptimizationMethodsAntAlgorithmsITOAlgorithms2020/2/23AlgorithmsDesignTechniquesandAnalysis4数学家名人录2020/2/23AlgorithmsDesignTechniquesandAnalysisChapter1Introduction:Concept,History,ProgressandClassofMathematicModelingandOptimization2020/2/23AlgorithmsDesignTechniquesandAnalysis6ContentsofCH11.引言:数学建模与最优化的背景①数学建模的进展②最优化技术的进展2.数学建摸的基本概念与分类①数学模型与数学建模②数学模型的分类③数学模型的应用领域④数学建模举例⑤数学建模的过程3.最优化的基本概念与分类①最优化的基本概念②最优化技术分类③最优化建模与求解示例4.数学建摸与最优化的关系2020/2/23AlgorithmsDesignTechniquesandAnalysis71引言:数学建模与最优化的背景1.1数学建模的历史与意义1.2最优化的历史与意义2020/2/23AlgorithmsDesignTechniquesandAnalysis81.1数学建模的历史与意义数学建模的历史和数学的历史基本上是一样的；古埃及几何学产生于尼罗河泛滥后土地的重新丈量；古印度几何学的起源则与宗教密切相关中国的《周批算经》是讨论天文学测量的巨著；大约公元前５世纪，毕达哥拉斯学派重视自然及社会中不变因素的研究，把几何、算术、天文、音乐称为“四艺”，在其中追求宇宙的和谐规律性。17世纪出现了笛卡尔、牛顿、莱布尼兹等数学家，奠定了微积分的基础，其研究的对象包括行星运动、流体运动、机械运动、植物生长等均属于数学建模的范畴；19世纪后期，数学成为了研究数与形、运动与变化的学问；可以说，数学是模式的科学，其目的是要揭示人们从自然界和数学本身的抽象世界中所观察到的结构和对称性。2020/2/23AlgorithmsDesignTechniquesandAnalysis91.2最优化的历史最优化问题有相当长的发展历史，最一早可以追溯到牛顿、拉格朗日时代。由于牛顿等对微积分的重要贡献，才使得差分方程法解决最优化问题成为可能。这其中的先锋者包括贝诺利(Bemot)，欧拉(Eller)和拉格郎日等。Lagrange发明了有名的拉格郎日乘子法。柯西(Canchy)首先提出了最速下降法(解决无约束最小化问题)。尽管有这些早期的成果，最优化的发展相当缓慢，直到50年代高速计算机的出现。50年代后，最优化的发展进入旺盛期，出现了大量的新算法。Dantzig提出了解决线性规划问题的simplex方法，Bellman提出了动态规划最优化最优性原理，使得约束最优化成为可能性。Kuhn和Tucher提出的最优化规划问题的充分和必要条件开创了非线性规划优化技术的基础。几何规划优化由Zountijker和Rosen在60年代提出，Gomory同时提出了积分规划技术。随机(或统计)规划技术最早山Danzig和charnes提出，Cooper发展了该技术。2020/2/23AlgorithmsDesignTechniquesandAnalysis10构成现代优化理论的相关技术是模拟退火SA、遗传算法GA等现代启发式最优化算法，他们均是从60年代发展起来的。SA算法是一种组合优化算法，足模拟材半l)Jl日一中的退火处理(Annealing)得名的优化算法。退火是材料加工的一种处理方式，即首先将固体加工到融化状态，再逐渐冷却，直到材料达到结品状态。在这个过程中，固体内的自由能最终被降低到最小状态。在实践中，冷却过程必须非常小心控制，以防止固体结晶到局部最小能量状态，即局部最优解，从而影响材料的强度等各种性能。模拟退火算法模拟这样的物理过程，将组合最小化能量状态模拟为最终晶体状态，并设计一个类似的处理过程，达到优化的目的。2020/2/23AlgorithmsDesignTechniquesandAnalysis111.2数学建摸的基本概念与分类1.数学模型与数学建模2.数学模型的分类3.数学模型的应用领域4.数学建模举例5.数学建模的过程2020/2/23AlgorithmsDesignTechniquesandAnalysis121.2.1数学建模与数学模型模型是把对象实体通过适当的过滤,用适当的表现规则描绘出的简洁的模仿品.通过这个模仿品,人们可以了解到所研究实体的本质,而且在形式上便于人们对实体进行分析和处理。模型概念模型是人们十分熟悉的东西，例如：玩具、照片及展览会里的电站模型、火箭模型等实物模型；地图、电路图、分子结构图等经过一定抽象的符号模型；大型水箱中的舰艇模型、风洞中的飞机模型等物理模型。2020/2/23AlgorithmsDesignTechniquesandAnalysis13数学模型(MathematicalModel)和数学建模（MathematicalModeling)对于一个现实对象，为了一个特定目的，根据其内在规律，作出必要的简化假设，运用适当的数学工具，得到的一个数学结构。建立数学模型的全过程（包括表述、求解、解释、检验等）数学模型数学建模2020/2/23AlgorithmsDesignTechniquesandAnalysis14数学建模的具体应用•分析与设计•预报与决策•控制与优化•规划与管理数学建模计算机技术知识经济如虎添翼2020/2/23AlgorithmsDesignTechniquesandAnalysis15数学模型的分类按模型的应用领域分类生物数学模型医学数学模型地质数学模型数量经济学模型数学社会学模型2020/2/23AlgorithmsDesignTechniquesandAnalysis16数学模型的分类按是否考虑随机因素分类确定性模型随机性模型2020/2/23AlgorithmsDesignTechniquesandAnalysis17数学模型的分类(续)按是否考虑模型的变化分类静态模型动态模型按建立模型的数学方法分类几何模型微分方程模型图论模型规划论模型马氏链模型按应用离散方法或连续方法离散模型连续模型2020/2/23AlgorithmsDesignTechniquesandAnalysis18数学模型的分类(续)按人们对事物发展过程的了解程度分类白箱模型：指那些内部规律比较清楚的模型。如力学、热学、电学以及相关的工程技术问题。灰箱模型：指那些内部规律尚不十分清楚，在建立和改善模型方面都还不同程度地有许多工作要做的问题。如气象学、生态学经济学等领域的模型。黑箱模型：指一些其内部规律还很少为人们所知的现象。如生命科学、社会科学等方面的问题。但由于因素众多、关系复杂，也可简化为灰箱模型来研究。2020/2/23AlgorithmsDesignTechniquesandAnalysis19数学建模示例椅子能在不平的地面上放稳吗问题分析模型假设通常~三只脚着地放稳~四只脚着地•四条腿一样长，椅脚与地面点接触，四脚连线呈正方形;•地面高度连续变化，可视为数学上的连续曲面;•地面相对平坦，使椅子在任意位置至少三只脚同时着地。2020/2/23AlgorithmsDesignTechniquesandAnalysis20模型构成用数学语言把椅子位置和四只脚着地的关系表示出来•椅子位置利用正方形(椅脚连线)的对称性xBADCOD´C´B´A´用(对角线与x轴的夹角)表示椅子位置•四只脚着地距离是的函数四个距离(四只脚)A,C两脚与地面距离之和~f()B,D两脚与地面距离之和~g()两个距离椅脚与地面距离为零正方形ABCD绕O点旋转正方形对称性2020/2/23AlgorithmsDesignTechniquesandAnalysis21用数学语言把椅子位置和四只脚着地的关系表示出来f(),g()是连续函数对任意,f(),g()至少一个为0数学问题已知：f(),g()是连续函数;对任意，f()•g()=0;且g(0)=0，f(0)0.证明：存在0，使f(0)=g(0)=0.模型构成地面为连续曲面椅子在任意位置至少三只脚着地2020/2/23AlgorithmsDesignTechniquesandAnalysis22模型求解给出一种简单、粗糙的证明方法将椅子旋转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()的确定2020/2/23AlgorithmsDesignTechniquesandAnalysis23商人们怎样安全过河问题(智力游戏)3名商人3名随从随从们密