最优化导论课件

2023/8/9AlgorithmsDesignTechniquesandAnalysis1教学目的、内容和形式目的:掌握数学建模及最优化的基本理论；掌握几类最优化问题的算法；通过学习常用的一些建模的方法,培养分析问题、解决问题的能力.教材《数学建模与最优化》，董文永,机械工业出版社，2009.参考书:见后面的参考书目录.学习形式:自学、讲授相结合.成绩构成:平时(30%-40%)+期末(60%-70%).2023/8/1AlgorithmsDesignTech12023/8/9AlgorithmsDesignTechniquesandAnalysis2参考文献数学建模与数学实验赵静但琦高等教育出版社

系统仿真导论，肖田元张燕云陈加栋，清华大学出版社计算机仿真技术基础，刘瑞叶任洪林李志民，电子工业出版社《自动控制原理》除第4、8、10三章，庞国仲，中国科大出版社；计算机仿真技术(吴旭光)，吴旭光，化学工业出版社系统仿真技术，彭晓源，北京航空航天大学出版社数学建模导论陈理荣北京邮电大学出版社数学建模方法齐欢华中理工大学出版社数学实验姜启源高等教育出版社数学建模袁震东，洪渊，林武忠等华东师范大学出版社数学模型引论唐焕文大连理工大学出版社运筹学钱颂迪等清华大学出版社现代优化计算方法刑文训清华大学出版社最优化原理与方法，薛嘉庆，冶金工业出版社，1986。最优化计算方法，席少霖，赵凤治，上海科学技术出版社，1983。非线性方程组解法与最优化方法，王德人，高等教育出版社，1985。非线性规划，胡毓达，高等教育出版社，19902023/8/1AlgorithmsDesignTech22023/8/9AlgorithmsDesignTechniquesandAnalysis3MaincontentsPart1Optimization:TheoryandPracticeIntroduction:Concept,BackgroundandProgressLinearProgrammingNonlinearProgrammingSimulationOptimizationDynamicprogrammingandOptimizationControlNetworkOptimizationPart2TheTechnologyofMathematicModelingFuzzyModelingandDataAnalysisSystemIdentificationHierarchicalAnalysisAggregationAnalysisDifferentialModeling:TheoryandPracticePart3Meta-HeuristicOptimizationMethodsAntAlgorithmsITOAlgorithms2023/8/1AlgorithmsDesignTech32023/8/9AlgorithmsDesignTechniquesandAnalysis4数学家名人录2023/8/1AlgorithmsDesignTech42023/8/9AlgorithmsDesignTechniquesandAnalysisChapter1Introduction:Concept,History,ProgressandClassofMathematicModelingandOptimization2023/8/1AlgorithmsDesignTech52023/8/9AlgorithmsDesignTechniquesandAnalysis6ContentsofCH1引言:数学建模与最优化的背景数学建模的进展最优化技术的进展数学建摸的基本概念与分类数学模型与数学建模数学模型的分类数学模型的应用领域数学建模举例数学建模的过程最优化的基本概念与分类最优化的基本概念最优化技术分类最优化建模与求解示例数学建摸与最优化的关系2023/8/1AlgorithmsDesignTech62023/8/9AlgorithmsDesignTechniquesandAnalysis71引言:数学建模与最优化的背景1.1数学建模的历史与意义1.2最优化的历史与意义2023/8/1AlgorithmsDesignTech72023/8/9AlgorithmsDesignTechniquesandAnalysis81.1数学建模的历史与意义数学建模的历史和数学的历史基本上是一样的；古埃及几何学产生于尼罗河泛滥后土地的重新丈量；古印度几何学的起源则与宗教密切相关中国的《周批算经》是讨论天文学测量的巨著；大约公元前５世纪，毕达哥拉斯学派重视自然及社会中不变因素的研究，把几何、算术、天文、音乐称为“四艺”，在其中追求宇宙的和谐规律性。17世纪出现了笛卡尔、牛顿、莱布尼兹等数学家，奠定了微积分的基础，其研究的对象包括行星运动、流体运动、机械运动、植物生长等均属于数学建模的范畴；19世纪后期，数学成为了研究数与形、运动与变化的学问；可以说，数学是模式的科学，其目的是要揭示人们从自然界和数学本身的抽象世界中所观察到的结构和对称性。2023/8/1AlgorithmsDesignTech82023/8/9AlgorithmsDesignTechniquesandAnalysis91.2最优化的历史最优化问题有相当长的发展历史，最一早可以追溯到牛顿、拉格朗日时代。由于牛顿等对微积分的重要贡献，才使得差分方程法解决最优化问题成为可能。这其中的先锋者包括贝诺利(Bemot)，欧拉(Eller)和拉格郎日等。Lagrange发明了有名的拉格郎日乘子法。柯西(Canchy)首先提出了最速下降法(解决无约束最小化问题)。尽管有这些早期的成果，最优化的发展相当缓慢，直到50年代高速计算机的出现。50年代后，最优化的发展进入旺盛期，出现了大量的新算法。Dantzig提出了解决线性规划问题的simplex方法，Bellman提出了动态规划最优化最优性原理，使得约束最优化成为可能性。Kuhn和Tucher提出的最优化规划问题的充分和必要条件开创了非线性规划优化技术的基础。几何规划优化由Zountijker和Rosen在60年代提出，Gomory同时提出了积分规划技术。随机(或统计)规划技术最早山Danzig和charnes提出，Cooper发展了该技术。2023/8/1AlgorithmsDesignTech92023/8/9AlgorithmsDesignTechniquesandAnalysis10构成现代优化理论的相关技术是模拟退火SA、遗传算法GA等现代启发式最优化算法，他们均是从60年代发展起来的。SA算法是一种组合优化算法，足模拟材半l)Jl日一中的退火处理(Annealing)得名的优化算法。退火是材料加工的一种处理方式，即首先将固体加工到融化状态，再逐渐冷却，直到材料达到结品状态。在这个过程中，固体内的自由能最终被降低到最小状态。在实践中，冷却过程必须非常小心控制，以防止固体结晶到局部最小能量状态，即局部最优解，从而影响材料的强度等各种性能。模拟退火算法模拟这样的物理过程，将组合最小化能量状态模拟为最终晶体状态，并设计一个类似的处理过程，达到优化的目的。2023/8/1AlgorithmsDesignTech102023/8/9AlgorithmsDesignTechniquesandAnalysis111.2数学建摸的基本概念与分类数学模型与数学建模数学模型的分类数学模型的应用领域数学建模举例数学建模的过程2023/8/1AlgorithmsDesignTech112023/8/9AlgorithmsDesignTechniquesandAnalysis121.2.1数学建模与数学模型模型是把对象实体通过适当的过滤,用适当的表现规则描绘出的简洁的模仿品.通过这个模仿品,人们可以了解到所研究实体的本质,而且在形式上便于人们对实体进行分析和处理。模型概念

模型是人们十分熟悉的东西，例如：玩具、照片及展览会里的电站模型、火箭模型等实物模型；地图、电路图、分子结构图等经过一定抽象的符号模型；大型水箱中的舰艇模型、风洞中的飞机模型等物理模型。

2023/8/1AlgorithmsDesignTech122023/8/9AlgorithmsDesignTechniquesandAnalysis13数学模型(MathematicalModel)和数学建模（MathematicalModeling)对于一个现实对象，为了一个特定目的，根据其内在规律，作出必要的简化假设，运用适当的数学工具，得到的一个数学结构。建立数学模型的全过程（包括表述、求解、解释、检验等）数学模型数学建模2023/8/1AlgorithmsDesignTech132023/8/9AlgorithmsDesignTechniquesandAnalysis14数学建模的具体应用

分析与设计

预报与决策

控制与优化

规划与管理数学建模计算机技术知识经济如虎添翼2023/8/1AlgorithmsDesignTech142023/8/9AlgorithmsDesignTechniquesandAnalysis15数学模型的分类按模型的应用领域分类

生物数学模型

医学数学模型地质数学模型

数量经济学模型

数学社会学模型2023/8/1AlgorithmsDesignTech152023/8/9AlgorithmsDesignTechniquesandAnalysis16数学模型的分类按是否考虑随机因素分类 确定性模型随机性模型2023/8/1AlgorithmsDesignTech162023/8/9AlgorithmsDesignTechniquesandAnalysis17数学模型的分类(续)按是否考虑模型的变化分类

静态模型

动态模型按建立模型的数学方法分类

几何模型

微分方程模型

图论模型

规划论模型

马氏链模型按应用离散方法或连续方法

离散模型

连续模型2023/8/1AlgorithmsDesignTech172023/8/9AlgorithmsDesignTechniquesandAnalysis18数学模型的分类(续)按人们对事物发展过程的了解程度分类

白箱模型：

指那些内部规律比较清楚的模型。如力学、热学、电学以及相关的工程技术问题。

灰箱模型：

指那些内部规律尚不十分清楚，在建立和改善模型方面都还不同程度地有许多工作要做的问题。如气象学、生态学经济学等领域的模型。黑箱模型：

指一些其内部规律还很少为人们所知的现象。如生命科学、社会科学等方面的问题。但由于因素众多、关系复杂，也可简化为灰箱模型来研究。2023/8/1AlgorithmsDesignTech182023/8/9AlgorithmsDesignTechniquesandAnalysis19数学建模示例椅子能在不平的地面上放稳吗问题分析模型假设通常~三只脚着地放稳~四只脚着地

四条腿一样长，椅脚与地面点接触，四脚连线呈正方形;

地面高度连续变化，可视为数学上的连续曲面;

地面相对平坦，使椅子在任意位置至少三只脚同时着地。2023/8/1AlgorithmsDesignTech192023/8/9AlgorithmsDesignTechniquesandAnalysis20模型构成用数学语言把椅子位置和四只脚着地的关系表示出来

椅子位置利用正方形(椅脚连线)的对称性xBADCOD´C´B´A´用(对角线与x轴的夹角)表示椅子位置

四只脚着地距离是的函数四个距离(四只脚)A,C两脚与地面距离之和~f()B,D两脚与地面距离之和~g()两个距离椅脚与地面距离为零正方形ABCD绕O点旋转正方形对称性2023/8/1AlgorithmsDesignTech202023/8/9AlgorithmsDesignTechniquesandAnalysis21用数学语言把椅子位置和四只脚着地的关系表示出来f(),g()是连续函数对任意,f(),g()至少一个为0数学问题已知：f(),g()是连续函数;

对任意，f()•g()=0;

且g(0)=0，f(0)>0.证明：存在0，使f(0)=g(0)=0.模型构成地面为连续曲面

椅子在任意位置至少三只脚着地2023/8/1AlgorithmsDesignTech212023/8/9AlgorithmsDesignTechniquesandAnalysis22模型求解给出一种简单、粗糙的证明方法将椅子旋转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/8/1AlgorithmsDesignTech222023/8/9AlgorithmsDesignTechniquesandAnalysis23商人们怎样安全过河问题(智力游戏)3名商人3名随从随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货.但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?问题分析多步决策过程决策~每一步(此岸到彼岸或彼岸到此岸)船上的人员要求~在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河.河小船(至多2人)2023/8/1AlgorithmsDesignTech232023/8/9AlgorithmsDesignTechniquesandAnalysis24模型构成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/8/1AlgorithmsDesignTech242023/8/9AlgorithmsDesignTechniquesandAnalysis25模型求解xy3322110

穷举法~编程上机

图解法状态s=(x,y)~16个格点~10个点允许决策~移动1或2格;k奇,左下移;k偶,右上移.s1sn+1d1,，d11给出安全渡河方案评注和思考规格化方法,易于推广d1d11允许状态S={(x

,y)x=0,y=0,1,2,3;

x=3,y=0,1,2,3;x=y=1,2}2023/8/1AlgorithmsDesignTech252023/8/9AlgorithmsDesignTechniquesandAnalysis26Demo2023/8/1AlgorithmsDesignTech262023/8/9AlgorithmsDesignTechniquesandAnalysis27

数学建模的基本方法机理分析测试分析根据对客观事物特性的认识，找出反映内部机理的数量规律将对象看作“黑箱”,通过对量测数据的统计分析，找出与数据拟合最好的模型机理分析没有统一的方法，主要通过实例研究(CaseStudies)来学习。二者结合用机理分析建立模型结构,用测试分析确定模型参数数学建模的方法和步骤2023/8/1AlgorithmsDesignTech272023/8/9AlgorithmsDesignTechniquesandAnalysis28

数学建模的一般步骤模型准备模型假设模型构成模型求解模型分析模型检验模型应用模型准备了解实际背景明确建模目的搜集有关信息掌握对象特征形成一个比较清晰的‘问题’2023/8/1AlgorithmsDesignTech282023/8/9AlgorithmsDesignTechniquesandAnalysis29模型假设针对问题特点和建模目的作出合理的、简化的假设在合理与简化之间作出折中模型构成用数学的语言、符号描述问题发挥想像力使用类比法尽量采用简单的数学工具

数学建模的一般步骤2023/8/1AlgorithmsDesignTech292023/8/9AlgorithmsDesignTechniquesandAnalysis30模型求解各种数学方法、软件和计算机技术如结果的误差分析、统计分析、模型对数据的稳定性分析模型分析模型检验与实际现象、数据比较，检验模型的合理性、适用性模型应用

数学建模的一般步骤2023/8/1AlgorithmsDesignTech302023/8/9AlgorithmsDesignTechniquesandAnalysis31数学建模的全过程现实对象的信息数学模型现实对象的解答数学模型的解答表述求解解释验证(归纳)(演绎)表述求解解释验证根据建模目的和信息将实际问题“翻译”成数学问题选择适当的数学方法求得数学模型的解答将数学语言表述的解答“翻译”回实际对象用现实对象的信息检验得到的解答实践现实世界数学世界理论实践2023/8/1AlgorithmsDesignTech312023/8/9AlgorithmsDesignTechniquesandAnalysis321.3最优化的基本概念与分类最优化的基本概念最优化技术分类最优化建模与求解示例2023/8/1AlgorithmsDesignTech322023/8/9AlgorithmsDesignTechniquesandAnalysis33

最优化的基本概念最优化技术是一门较新的学科分支。它是在本世纪五十年代初在电子计算机广泛应用的推动下才得到迅速发展，并成为一门直到目前仍然十分活跃的新兴学科。最优化所研究的问题是在众多的可行方案中怎样选择最合理的一种以达到最优目标。将达到最优目标的方案称为最优方案或最优决策，搜寻最优方案的方法称为最优化方法，关于最优化方法的数学理论称为最优化论。最优化问题至少有两要素：一是可能的方案；二是要追求的目标。后者是前者的函数。如果第一要素与时间无关就称为静态最优化问题，否则称为动态最优化问题。2023/8/1AlgorithmsDesignTech332023/8/9AlgorithmsDesignTechniquesandAnalysis34最优化技术应用范围十分广泛，在我们日常生活中，在工农业生产、社会经济、国防、航空航天工业中处处可见其用途。比如我们自己所接触过的课题有：结构最优设计、电子器件最优设计、光学仪器最优设计、化工工程最优设计、标腔最优配方、运输方案、机器最优配备、油田开发、水库调度、饲料最优配方、食品结构优化等等。2023/8/1AlgorithmsDesignTech342023/8/9AlgorithmsDesignTechniquesandAnalysis35最优化技术工作被分成两个方面，一是由实际生产或科技问题形成最优化的数学模型，二是对所形成的数学问题进行数学加工和求解。对于第二方面的工作，目前已有一些较系统成熟的资料，但对于第一方面工作即如何由实际问题抽象出数学模型，目前很少有系统的资料，而这一工作在应用最优化技术解决实际问题时是十分关键的基础，没有这一工作，最优化技术将成为无水之源，难以健康发展。2023/8/1AlgorithmsDesignTech352023/8/9AlgorithmsDesignTechniquesandAnalysis36

最优化问题举例最优化在物质运输、自动控制、机械设计、采矿冶金、经济管理等科学技术各领域中有广泛应用。下面举几个专业性不强的实例。例1.把半径为1的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？解：决定圆柱体表面积大小有两个决策变量：圆柱体底面半径r、高h。问题的约束条件是所铸圆柱体重量与球重相等。即2023/8/1AlgorithmsDesignTech362023/8/9AlgorithmsDesignTechniquesandAnalysis37即即问题追求的目标是圆柱体表面积最小。即

min则得原问题的数学模型：

s.t.Subjectto.固定.2023/8/1AlgorithmsDesignTech372023/8/9AlgorithmsDesignTechniquesandAnalysis38利用在高等数学中所学的Lagrange乘子法可求解本问题

分别对r.h.λ求偏导数,并令其等于零.有:2023/8/1AlgorithmsDesignTech382023/8/9AlgorithmsDesignTechniquesandAnalysis39例2.多参数曲线拟合问题已知两个物理量x和y之间的依赖关系为:

其中和待定参数,为确定这些参数,对x.y测得m个实验点:试将确定参数的问题表示成最优化问题.2023/8/1AlgorithmsDesignTech392023/8/9AlgorithmsDesignTechniquesandAnalysis40解:很显然对参数和任意给定的一组数值,就由上式确定了y关于x的一个函数关系式,在几何上它对应一条曲线,这条曲线不一定通过那m个测量点,而要产生“偏差”.将测量点沿垂线方向到曲线的距离的平方和作为这种“偏差”的度量.即显然偏差S越小,曲线就拟合得越好,说明参数值就选择得越好，从而我们的问题就转化为5维无约束最优化问题。即：2023/8/1AlgorithmsDesignTech402023/8/9AlgorithmsDesignTechniquesandAnalysis41例3：两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为ρ，弹性模量为E，屈吸强度为δ。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。

受力分析图圆杆截面图桁杆示意图2023/8/1AlgorithmsDesignTech412023/8/9AlgorithmsDesignTechniquesandAnalysis42解：桁杆的截面积为：桁杆的总重量为：负载2p在每个杆上的分力为：于是杆截面的应力为：此应力要求小于材料的屈吸极限，即

2023/8/1AlgorithmsDesignTech422023/8/9AlgorithmsDesignTechniquesandAnalysis43

圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为由此得稳定约束：2023/8/1AlgorithmsDesignTech432023/8/9AlgorithmsDesignTechniquesandAnalysis44

另外还要考虑到设计变量d和h有界。从而得到两杆桁架最优设计问题的数学模型：2023/8/1AlgorithmsDesignTech442023/8/9AlgorithmsDesignTechniquesandAnalysis45例4.（混合饲料配合）以最低成本确定满足动物所需营养的最优混合饲料。下面举一个简化了的例子予以说明。设每天需要混合饲料的批量为100磅，这份饲料必须含：至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分为：2023/8/1AlgorithmsDesignTech452023/8/9AlgorithmsDesignTechniquesandAnalysis46配料每磅配料中的营养含量钙蛋白质纤维每磅成本（元）石灰石谷物大豆粉0.3800.000.000.0010.090.020.0020.500.08

0.01640.04630.1250解:根据前面介绍的建模要素得出此问题的数学模型如下:设是生产100磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。2023/8/1AlgorithmsDesignTech462023/8/9AlgorithmsDesignTechniquesandAnalysis472023/8/1AlgorithmsDesignTech472023/8/9AlgorithmsDesignTechniquesandAnalysis48最优化问题的基本概念n维欧氏空间向量向量变量实值函数：无约束最优问题：2023/8/1AlgorithmsDesignTech482023/8/9AlgorithmsDesignTechniquesandAnalysis49最优化问题的基本概念向量变量向量值函数：其中是向量变量实值函数则有m个式约束的最优化问题为：2023/8/1AlgorithmsDesignTech