最优化导论课件.ppt

1、2022-3-24Algorithms Design Techniques and Analysis1n目的:q掌握数学建模及最优化的基本理论；q掌握几类最优化问题的算法；q通过学习常用的一些建模的方法,培养分析问题、解决问题的能力.n教材q数学建模与最优化，董文永, 机械工业出版社，2009.n参考书: q见后面的参考书目录.n学习形式:q自学、讲授相结合.n成绩构成: q平时(30%-40%)+期末(60%-70%).2022-3-24Algorithms Design Techniques and Analysis2n数学建模与数学实验 赵静 但琦 高等教育出版社n 系统仿真导论，肖田元

2、 张燕云 陈加栋 ，清华大学出版社 n计算机仿真技术基础，刘瑞叶 任洪林 李志民 ，电子工业出版社 n自动控制原理除第4、8、10三章，庞国仲，中国科大出版社；n计算机仿真技术(吴旭光)， 吴旭光 ，化学工业出版社 n系统仿真技术， 彭晓源 ，北京航空航天大学出版社n数学建模导论 陈理荣 北京邮电大学出版社n数学建模方法 齐 欢 华中理工大学出版社n数学实验 姜启源 高等教育出版社n数学建模 袁震东，洪渊，林武忠等 华东师范大学出版社n数学模型引论 唐焕文 大连理工大学出版社n运筹学 钱颂迪等 清华大学出版社n现代优化计算方法 刑文训 清华大学出版社n最优化原理与方法，薛嘉庆，冶金工业出版社，

3、1986。n最优化计算方法，席少霖，赵凤治，上海科学技术出版社，1983。n非线性方程组解法与最优化方法，王德人，高等教育出版社，1985。n非线性规划，胡毓 达，高等教育出版社，19902022-3-24Algorithms Design Techniques and Analysis3Part 1 Optimization: Theory and Practice1.Introduction: Concept, Background and Progress 2.Linear Programming3.Nonlinear Programming4.Simulation Optimizati

4、on5.Dynamic programming and Optimization Control6.Network OptimizationPart 2 The Technology of Mathematic Modeling1.Fuzzy Modeling and Data Analysis2.System Identification3.Hierarchical Analysis 4. Aggregation Analysis5.Differential Modeling: Theory and PracticePart 3 Meta-Heuristic Optimization Met

5、hodsqAnt AlgorithmsqITO Algorithms2022-3-24Algorithms Design Techniques and Analysis42022-3-24Algorithms Design Techniques and AnalysisIntroduction: Concept, History, Progress and Class of Mathematic Modeling and Optimization2022-3-24Algorithms Design Techniques and Analysis61.引言:数学建模与最优化的背景数学建模的进展最

6、优化技术的进展2.数学建摸的基本概念与分类数学模型与数学建模数学模型的分类数学模型的应用领域数学建模举例数学建模的过程3.最优化的基本概念与分类最优化的基本概念最优化技术分类最优化建模与求解示例4.数学建摸与最优化的关系2022-3-24Algorithms Design Techniques and Analysis7n1.1 数学建模的历史与意义n1.2 最优化的历史与意义2022-3-24Algorithms Design Techniques and Analysis8n数学建模的历史和数学的历史基本上是一样的；n古埃及几何学产生于尼罗河泛滥后土地的重新丈量；n古印度几何学的起源则与宗

7、教密切相关n中国的周批算经是讨论天文学测量的巨著；n大约公元前世纪，毕达哥拉斯学派重视自然及社会中不变因素的研究，把几何、算术、天文、音乐称为“四艺”，在其中追求宇宙的和谐规律性。n17世纪出现了笛卡尔、牛顿、莱布尼兹等数学家，奠定了微积分的基础，其研究的对象包括行星运动、流体运动、机械运动、植物生长等均属于数学建模的范畴；n19世纪后期，数学成为了研究数与形、运动与变化的学问；n可以说，数学是模式的科学，其目的是要揭示人们从自然界和数学本身的抽象世界中所观察到的结构和对称性。2022-3-24Algorithms Design Techniques and Analysis9n最优化问题有相

8、当长的发展历史，最一早可以追溯到牛顿、拉格朗日时代。由于牛顿等对微积分的重要贡献，才使得差分方程法解决最优化问题成为可能。这其中的先锋者包括贝诺利(Bemot)，欧拉(Eller)和拉格郎日等。nLagrange发明了有名的拉格郎日乘子法。柯西(Canchy)首先提出了最速下降法(解决无约束最小化问题)。尽管有这些早期的成果，最优化的发展相当缓慢，直到50年代高速计算机的出现。50年代后，最优化的发展进入旺盛期，出现了大量的新算法。Dantzig提出了解决线性规划问题的simplex方法，Bellman提出了动态规划最优化最优性原理，使得约束最优化成为可能性。Kuhn和Tucher提出的最优化

9、规划问题的充分和必要条件开创了非线性规划优化技术的基础。n几何规划优化由Zountijker和Rosen在60年代提出，Gomory同n时提出了积分规划技术。随机(或统计)规划技术最早山Danzig和charnes提出，Cooper发展了该技术。2022-3-24Algorithms Design Techniques and Analysis10n构成现代优化理论的相关技术是模拟退火SA、遗传算法GA等现代启发式最优化算法，他们均是从60年代发展起来的。nSA算法是一种组合优化算法，足模拟材半l)Jl日一中的退火处理(Annealing)得名的优化算法。退火是材料加工的一种处理方式，即首先将

10、固体加工到融化状态，再逐渐冷却，直到材料达到结品状态。在这个过程中，固体内的自由能最终被降低到最小状态。在实践中，冷却过程必须非常小心控制，以防止固体结晶到局部最小能量状态，即局部最优解，从而影响材料的强度等各种性能。模拟退火算法模拟这样的物理过程，将组合最小化能量状态模拟为最终晶体状态，并设计一个类似的处理过程，达到优化的目的。2022-3-24Algorithms Design Techniques and Analysis111.数学模型与数学建模2.数学模型的分类3.数学模型的应用领域4.数学建模举例5.数学建模的过程2022-3-24Algorithms Design Techniq

11、ues and Analysis12n模型是把对象实体通过适当的过滤,用适当的表现规则描绘出的简洁的模仿品.通过这个模仿品,人们可以了解到所研究实体的本质,而且在形式上便于人们对实体进行分析和处理。n模型概念模型概念n模型是人们十分熟悉的东西，例如：玩具、照片及展览会里的电站模型、火箭模型等实物模型；地图、电路图、分子结构图等经过一定抽象的符号模型；大型水箱中的舰艇模型、风洞中的飞机模型等物理模型。 2022-3-24Algorithms Design Techniques and Analysis13数学模型数学模型 (Mathematical Model) 和和数学建模（数学建模（Math

12、ematical Modeling)对于一个对于一个现实对象现实对象，为了一个，为了一个特定目的特定目的，根据其根据其内在规律内在规律，作出必要的，作出必要的简化假设简化假设，运用适当的运用适当的数学工具数学工具，得到的一个，得到的一个数学结构数学结构。建立数学模型的全过程建立数学模型的全过程（包括表述、求解、解释、检验等）（包括表述、求解、解释、检验等）数学模型数学模型数学建模数学建模2022-3-24Algorithms Design Techniques and Analysis14数学建模的具体应用数学建模的具体应用 分析与设计分析与设计 预报与决策预报与决策 控制与优化控制与优化 规

13、划与管理规划与管理数学建模计算机技术知识经济知识经济如虎添翼如虎添翼2022-3-24Algorithms Design Techniques and Analysis15n按模型的应用领域分类按模型的应用领域分类生物数学模型生物数学模型医学数学模型医学数学模型地质数学模型地质数学模型数量经济学模型数量经济学模型数学社会学模型数学社会学模型 2022-3-24Algorithms Design Techniques and Analysis16n按是否考虑随机因素分类按是否考虑随机因素分类确定性模型确定性模型随机性模型随机性模型 2022-3-24Algorithms Design Techn

14、iques and Analysis17n按是否考虑模型的变化分类按是否考虑模型的变化分类 静态模型动态模型 n按建立模型的数学方法分类按建立模型的数学方法分类 几何模型微分方程模型图论模型规划论模型马氏链模型 n按应用离散方法或连续方法按应用离散方法或连续方法 离散模型连续模型 2022-3-24Algorithms Design Techniques and Analysis18按人们对事物发展过程的了解程度分类按人们对事物发展过程的了解程度分类 n白箱模型白箱模型： 指那些内部规律比较清楚的模型。如力学、热学、电学以及相关的工程技术问题。n灰箱模型：灰箱模型： 指那些内部规律尚不十分清楚

15、，在建立和改善模型方面都还不同程度地有许多工作要做的问题。 如气象学、生态学经济学等领域的模型。n黑箱模型：黑箱模型： 指一些其内部规律还很少为人们所知的现象。如生命科学、社会科学等方面的问题。但由于因素众多、关系复杂，也可简化为灰箱模型来研究。 2022-3-24Algorithms Design Techniques and Analysis19数学建模示例数学建模示例椅子能在不平的地面上放稳吗椅子能在不平的地面上放稳吗问题分析问题分析模模型型假假设设通常通常 三只脚着地三只脚着地放稳放稳 四只脚着地四只脚着地 四条腿一样长，椅脚与地面点接触，四脚连线呈四条腿一样长，椅脚与地面点接触，四脚

16、连线呈正方形正方形; 地面高度连续变化，可视为数学上的连续曲面地面高度连续变化，可视为数学上的连续曲面; 地面相对平坦，使椅子在任意位置至少三只脚同地面相对平坦，使椅子在任意位置至少三只脚同时着地。时着地。2022-3-24Algorithms Design Techniques and Analysis20模型构成模型构成用数学语言把椅子位置和四只脚着地的关系表示出来用数学语言把椅子位置和四只脚着地的关系表示出来 椅子位置椅子位置利用正方形利用正方形(椅脚连线椅脚连线)的对称性的对称性xBADCOD C B A 用用 (对角线与对角线与x轴的夹角轴的夹角)表示椅子位置表示椅子位置 四只脚着地

17、四只脚着地距离是距离是 的函数的函数四个距离四个距离(四只脚四只脚)A,C 两脚与地面距离之和两脚与地面距离之和 f( )B,D 两脚与地面距离之和两脚与地面距离之和 g( )两个距离两个距离 椅脚与地面距离为零椅脚与地面距离为零正方形正方形ABCD绕绕O点旋转点旋转正方形正方形对称性对称性2022-3-24Algorithms Design Techniques and Analysis21用数学语言把椅子位置和四只脚着地的关系表示出来用数学语言把椅子位置和四只脚着地的关系表示出来f( ) , g( )是是连续函数连续函数对任意对任意 , f( ), g( )至少一个为至少一个为0数学数学问

18、题问题已知：已知： f( ) , g( )是是连续函数连续函数 ; 对任意对任意 ， f( ) g( )=0 ; 且且 g(0)=0， f(0) 0. 证明：存在证明：存在 0，使，使f( 0) = g( 0) = 0.模型构成模型构成地面为连续曲面地面为连续曲面 椅子在任意位置椅子在任意位置至少三只脚着地至少三只脚着地2022-3-24Algorithms Design Techniques and Analysis22模型求解模型求解给出一种简单、粗糙的证明方法给出一种简单、粗糙的证明方法将椅子旋转将椅子旋转900，对角线，对角线AC和和BD互换。互换。由由g(0)=0， f(0) 0 ，

19、知，知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( )的确定的确定2022-3-24Algorithms Design

20、 Techniques and Analysis23商人们怎样安全过河商人们怎样安全过河问题问题( (智力游戏智力游戏) ) 3名商人名商人 3名随从名随从随从们密约随从们密约, , 在河的任一在河的任一岸岸, , 一旦随从的人数比商一旦随从的人数比商人多人多, , 就杀人越货就杀人越货. .但是乘船渡河的方案由商人决定但是乘船渡河的方案由商人决定. .商人们怎样才能安全过河商人们怎样才能安全过河?问题分析问题分析多步决策过程多步决策过程决策决策 每一步每一步( (此岸到彼岸或彼岸到此岸此岸到彼岸或彼岸到此岸) )船上的人员船上的人员要求要求在安全的前提下在安全的前提下( (两岸的随从数不比商

21、人多两岸的随从数不比商人多),),经有经有限步使全体人员过河限步使全体人员过河. .河河小船小船(至多至多2人人)2022-3-24Algorithms Design Techniques and Analysis24模型构成模型构成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,2S 允许状态集合允许状态集合uk第第k次渡船上的商人数次渡船上的商人数vk第第

22、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状态转移律状态转移律求求dk D(k=1,2, n), 使使sk S, 并按并按转移律转移律由由 s1=(3,3)到达到达 sn+1=(0,0).多步决策多步决策问题问题2022-3-24Algorithms Design Techniques and Analysis25模型求解模型求解xy3322110 穷举法穷举法 编程上机编程上机 图解法图解法状态状态s=(x,y) 16个格点个格点

23、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,22022-3-24Algorithms Design Techniques and Analysis26nDemo2022-3-24Algorithms Design Techniques and Analysis27 数学建模的基本方法数学建模的基本

24、方法机理分析机理分析测试分析测试分析根据对客观事物特性的认识，根据对客观事物特性的认识，找出反映内部机理的数量规律找出反映内部机理的数量规律将对象看作将对象看作“黑箱黑箱”,通过对量测数据的通过对量测数据的统计分析，找出与数据拟合最好的模型统计分析，找出与数据拟合最好的模型机理分析没有统一的方法，主要通过实例研究机理分析没有统一的方法，主要通过实例研究(Case Studies)来学习。来学习。二者结合二者结合用机理分析建立模型结构用机理分析建立模型结构,用测试分析确定模型参数用测试分析确定模型参数数学建模的方法和步骤数学建模的方法和步骤2022-3-24Algorithms Design T

25、echniques and Analysis28 数学建模的一般步骤数学建模的一般步骤模型准备模型准备模型假设模型假设模型构成模型构成模型求解模型求解模型分析模型分析模型检验模型检验模型应用模型应用模模型型准准备备了解实际背景了解实际背景明确建模目的明确建模目的搜集有关信息搜集有关信息掌握对象特征掌握对象特征形成一个形成一个比较清晰比较清晰的的问题问题2022-3-24Algorithms Design Techniques and Analysis29模模型型假假设设针对问题特点和建模目的针对问题特点和建模目的作出合理的、简化的假设作出合理的、简化的假设在合理与简化之间作出折中在合理与简化之

26、间作出折中模模型型构构成成用数学的语言、符号描述问题用数学的语言、符号描述问题发挥想像力发挥想像力使用类比法使用类比法尽量采用简单的数学工具尽量采用简单的数学工具 数学建模的一般步骤数学建模的一般步骤2022-3-24Algorithms Design Techniques and Analysis30模型模型求解求解各种数学方法、软件和计算机技术各种数学方法、软件和计算机技术如结果的误差分析、统计分析、如结果的误差分析、统计分析、模型对数据的稳定性分析模型对数据的稳定性分析模型模型分析分析模型模型检验检验与实际现象、数据比较，与实际现象、数据比较，检验模型的合理性、适用性检验模型的合理性、适

27、用性模型应用模型应用 数学建模的一般步骤数学建模的一般步骤2022-3-24Algorithms Design Techniques and Analysis31数学建模的全过程数学建模的全过程现实对象的信息现实对象的信息数学模型数学模型现实对象的解答现实对象的解答数学模型的解答数学模型的解答表述表述求解求解解释解释验证验证(归纳)(演绎)表述表述求解求解解释解释验证验证根据建模目的和信息将实际问题根据建模目的和信息将实际问题“翻译翻译”成数学问成数学问题题选择适当的数学方法求得数学模型的解答选择适当的数学方法求得数学模型的解答将数学语言表述的解答将数学语言表述的解答“翻译翻译”回实际对象回实

28、际对象用现实对象的信息检验得到的解答用现实对象的信息检验得到的解答实践现现实实世世界界数数学学世世界界理论实践2022-3-24Algorithms Design Techniques and Analysis321.最优化的基本概念2.最优化技术分类3.最优化建模与求解示例2022-3-24Algorithms Design Techniques and Analysis33 最优化的基本概念1. 最优化技术是一门较新的学科分支。它是在本世纪五十年代初在电子计算机广泛应用的推动下才得到迅速发展，并成为一门直到目前仍然十分活跃的新兴学科。最优化所研究的问题是在众多的可行方案中怎样选择最合理的一

29、种以达到最优目标。2. 将达到最优目标的方案称为最优方案或最优决策，搜寻最优方案的方法称为最优化方法，关于最优化方法的数学理论称为最优化论。3. 最优化问题至少有两要素：一是可能的方案；二是要追求的目标。后者是前者的函数。如果第一要素与时间无关就称为静态最优化问题，否则称为动态最优化问题。2022-3-24Algorithms Design Techniques and Analysis341. 最优化技术应用范围十分广泛，在我们日常生活中，在工农业生产、社会经济、国防、航空航天工业中处处可见其用途。2. 比如我们自己所接触过的课题有：结构最优设计、电子器件最优设计、光学仪器最优设计、化工工程

30、最优设计、标腔最优配方、运输方案、机器最优配备、油田开发、水库调度、饲料最优配方、食品结构优化等等。 2022-3-24Algorithms Design Techniques and Analysis351. 最优化技术工作被分成两个方面，一是由实际生产或科技问题形成最优化的数学模型，二是对所形成的数学问题进行数学加工和求解。2. 对于第二方面的工作，目前已有一些较系统成熟的资料，但对于第一方面工作即如何由实际问题抽象出数学模型，目前很少有系统的资料，而这一工作在应用最优化技术解决实际问题时是十分关键的基础，没有这一工作，最优化技术将成为无水之源，难以健康发展。2022-3-24Algori

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

32、 min 则得原问题的数学模型： s.t. Subject to.固定.342hr0342hr222rrh22min 224. .03rhrstr h2022-3-24Algorithms Design Techniques and Analysis38利用在高等数学中所学的Lagrange乘子法可求解本问题 分别对r.h.求偏导数,并令其等于零.有:3422.22hrrrhhrLrhhrLrrhLrhrhrL203402024222.323 r3322h2022-3-24Algorithms Design Techniques and Analysis39例2.多参数曲线拟合问题 已知两个物

33、理量x和y之间的依赖关系为: 其中 和 待定参数,为确定这些参数,对x.y测得m个实验点:试将确定参数的问题表示成最优化问题.54321exp1ln1aaxaaay4321aaaa5a .,2, 21, 1mmyxyxyx2022-3-24Algorithms Design Techniques and Analysis40解:很显然对参数 和 任意给定的一组数值,就由上式确定了 y关于x的一个函数关系式,在几何上它对应一条曲线,这条曲线不一定通过那m个测量点,而要产生“偏差”.将测量点沿垂线方向到曲线的距离的平方和作为这种“偏差”的度量.即显然偏差S越小,曲线就拟合得越好,说明参数值就选择得

34、越好，从而我们的问题就转化为5维无约束最优化问题。即：4321aaaa5amiiiaaxaaayS1254321exp1ln1xy2022-3-24Algorithms Design Techniques and Analysis41例3：两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，弹性模量为E，屈吸强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。miiiaxxaaay1254321exp1ln1min 1p1p2pp2h hhL2 受力分析图圆杆截面图Bp2hL2桁杆示意图

35、d2022-3-24Algorithms Design Techniques and Analysis42解：桁杆的截面积为 ： 桁杆的总重量为： 负载2p在每个杆上的分力为： 于是杆截面的应力为： 此应力要求小于材料的屈吸极限，即 dBS222hLdBWhhLppp221cosdhBhLsp2211dhBhLp222022-3-24Algorithms Design Techniques and Analysis43 圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为 由此得稳定约束：222228hLBdE082222222dhBhLphLBdE2022-3-24Alg

36、orithms Design Techniques and Analysis44 另外还要考虑到设计变量d和h有界。 从而得到两杆桁架最优设计问题的数学模型：minmaxminmax22222222222080. .2minhhhddddhBhLphLBdEdhBhLptshLdB2022-3-24Algorithms Design Techniques and Analysis45n例4.（混合饲料配合）以最低成本确定满足动物所需营养的最优混合饲料。下面举一个简化了的例子予以说明。n设每天需要混合饲料的批量为100磅，这份饲料必须含：n至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至

37、多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分为：2022-3-24Algorithms Design Techniques and Analysis46配料每磅配料中的营养含量钙蛋白质纤维每磅成本（元）石灰石谷物大豆粉0.380 0.00 0.000.001 0.09 0.020.002 0.50 0.08 0.0164 0.0463 0.1250解:根据前面介绍的建模要素得出此问题的数学模型如下:设 是生产100磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。321xxx2022-3-24Algorithms Design Techniques and Ana

38、lysis4700010005. 008. 002. 010022. 050. 009. 0100008. 0002. 0001. 0380. 0100012. 0002. 0001. 0380. 0100. .1250. 00463. 00164. 0min3213232321321321321xxxxxxxxxxxxxxxxtsxxxZ2022-3-24Algorithms Design Techniques and Analysis48最优化问题的基本概念n维欧氏空间 向量向量变量实值函数： 无约束最优问题： nRnnnxxxxxxZRZ2121,.:1RRfn Zfmin2022-3-

39、24Algorithms Design Techniques and Analysis49最优化问题的基本概念向量变量向量值函数：其中 是向量变量实值函数则有m个式约束的最优化问题为：.:mnRRH .,21ZhZhZhZHm1:RRhni.1mi 0. .minZHtsZf2022-3-24Algorithms Design Techniques and Analysis50在本课程我们讨论的是如下形式的静态最优化问题：其中 均为向量Z的实值连续函数，有二阶连续偏导数. nlljZhmiZtsZfjiZ.1. 01. 0. .minjihf.2022-3-24Algorithms Desig

40、n Techniques and Analysis51采用向量表示法即为：其中 这就是最优化问题的一般形式，又称非线性规划。 注意等式约束通常可用不等式约束表示出来，有时 等式约束不等式约束目标函数约束集. 0. 0. .minZHZStsZfZ ZhZhZhZHxxxZSlm,.,2121.nR2022-3-24Algorithms Design Techniques and Analysis52因此，一般不考虑等式约束。 称满足所有约束条件的向量Z为容许解或可行解，容许点的集合称为容许集或可行集。 在容许集中找一点 ，使目标函数 在该点取最小值，即满足： 的过程即为最优化的求解过程。 称为

41、问题的最优点， 称为最优值， 称为最优解。 *Z Zf 0. 0. .min*ZHZStsZfZf*Z*Zf*,ZfZ2022-3-24Algorithms Design Techniques and Analysis53最优化问题模型统一化： 在上述最优化问题的一般式中只是取极小值，如果遇到极大化问题，只须将目标函数反号就可以化为求极小的问题。 例如：函数 在 有极大值 ， 将它改变符号后， 在同一点 处 有极小值 由此可见： 有相同最优点。 222xxxf1*x 222xxxf1*x 1*xf ZfZfminmax与 1*xf2022-3-24Algorithms Design Techniques and Analysis54f xf *xf *xf xfx4如果约束条件中有“小于等于“的，即 则转化为 ，另外，等式约束 可以由下面两个不等式来代替：因而最优化问题的一般形式又可写成： . 0ZS 0ZS 0ZH 00ZHZH 0. .minZStsZf2022-3-24Algorithms Design Techniques and Analysis55约束无约束动态问题非线性规划线性规划约束问题维问题一维问题非线性问题线性问题无约束问题静态问题最优化问题n其中求解一维无约束问题的方法称为一维搜索或直线搜索，这在最优化方法中起十分重要的作用。对于最优化问题一般可作如下分类：