最优化方法绪论

1、第第1页页最优化方法最优化方法张芳芳Q：519882394E-mail：第第2页页课程要求课程要求作业要求作业要求-独立完成独立完成, ,不得抄袭不得抄袭. . 上课要求上课要求-认真听课认真听课, ,适度记笔记适度记笔记. .成绩构成成绩构成-平时成绩平时成绩(10%(10%，点名三次不，点名三次不到取消考试资格到取消考试资格)+)+作业作业(20%)+(20%)+考试成绩考试成绩(70%)(70%)考试方式考试方式-闭卷笔试闭卷笔试第第3页页运筹学方法运筹学方法近几十年形成，主要运用近几十年形成，主要运用数学方法数学方法研究各种系统的研究各种系统的优化途径及方案，

2、为决策者提供科学决策的依据。优化途径及方案，为决策者提供科学决策的依据。最优化方法最优化方法 主要研究对象主要研究对象: 各种有各种有组织系统组织系统的管理问题及其生的管理问题及其生产经营活动。产经营活动。目的目的: 求得一个合理运用人力、物求得一个合理运用人力、物 力和财力的最佳力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。统的最优目标。第第4页页 数学意义数学意义为了达到最优化目的所提出的各种求解方法。从为了达到最优化目的所提出的各种求解方法。从数学数学意义上说，最优化方法是一种求极值的方法，意义上说，最优化方法是一种求

3、极值的方法，即在一组约束为等式或不等式的条件下，使系统即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。的目标函数达到极值，即最大值或最小值。 经济意义经济意义 在一定的人力、物力和财力资源条件下，使经济在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或完成规定的效果达到最大（如产值、利润），或完成规定的生产或经济任务下，使投入的人力、物力和财力生产或经济任务下，使投入的人力、物力和财力等资源最少。等资源最少。 第第5页页 发展简史发展简史公元前公元前 500年年, 建筑美学中发现长方形长与宽的最佳建筑美学中发现长方形长与宽的最佳比例比例1

4、. 618( 黄金分割比黄金分割比)。其倒数在优选法中得到广。其倒数在优选法中得到广泛应用。泛应用。 阿基米德证明：给定周长，圆所包围的面积为最大。阿基米德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。这就是欧洲古代城堡几乎都建成圆形的原因。 最优化方法真正形成在最优化方法真正形成在17世纪后。世纪后。17世纪，世纪，I.牛顿和牛顿和G.W.莱布尼茨在他们所创建的微积分中，提出求解莱布尼茨在他们所创建的微积分中，提出求解具有多个自变量的实值函数的最大值和最小值的方具有多个自变量的实值函数的最大值和最小值的方法。又进一步讨论具有未知函数的函数极值，从而法。又进一步

5、讨论具有未知函数的函数极值，从而形成形成变分法变分法。这一时期的最优化方法可以称为。这一时期的最优化方法可以称为古典古典最优化方法。最优化方法。第第6页页 第二次世界大战第二次世界大战前后，由于军事、科学技术和生前后，由于军事、科学技术和生产的发展，许多实际的最优化问题无法用古典方产的发展，许多实际的最优化问题无法用古典方法来解决，促进了法来解决，促进了近代最优化方法近代最优化方法的产生。的产生。 代表事件：代表事件： 以苏联以苏联 .康托罗维奇和美国康托罗维奇和美国G.B.丹齐克为代表丹齐克为代表的的线性规划线性规划； 以美国以美国库恩库恩和塔克尔为代表的和塔克尔为代表的非线性规划非线性规划

6、； 以美国以美国R.贝尔曼为代表的贝尔曼为代表的动态规划动态规划； 以苏联以苏联.庞特里亚金为代表的庞特里亚金为代表的极大值原理极大值原理等。等。第第7页页 工作步骤工作步骤 提出最优化问题，收集有关数据和资料；提出最优化问题，收集有关数据和资料； 建立最优化问题的建立最优化问题的数学模型数学模型, 确定变量确定变量, 列出列出 目标函数和约束条件；目标函数和约束条件； 分析模型，选择合适的最优化方法；分析模型，选择合适的最优化方法； 求解，一般通过编制程序，用求解，一般通过编制程序，用计算机计算机求最优求最优解；解； 最优解的检验和实施。最优解的检验和实施。 上述上述 5个步骤中的工作相互支

7、持和相互制约，个步骤中的工作相互支持和相互制约， 在实践中常常反复交叉进行。在实践中常常反复交叉进行。 第第8页页 几种最优化方法几种最优化方法不同类型的最优化问题可以有不同的最优化方法，不同类型的最优化问题可以有不同的最优化方法，即使同一类型的问题即使同一类型的问题 ，也可有多种最优化方法。，也可有多种最优化方法。 解析法：只适用于目标函数和约束条件有明显的解解析法：只适用于目标函数和约束条件有明显的解析表达式的情况。析表达式的情况。 求解方法是：先求出最优的必要条件，得到一组方求解方法是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用程或不等式，再求解这组方程

8、或不等式，一般是用求导数的方法或变分法求出必要条件，通过必要条求导数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。件将问题简化，因此也称间接法。第第9页页 直接法：当目标函数较为复杂或者不能用变量直接法：当目标函数较为复杂或者不能用变量显函数描述时，无法用解析法求必要条件。此时显函数描述时，无法用解析法求必要条件。此时可采用直接搜索的方法经过若干次迭代搜索到最可采用直接搜索的方法经过若干次迭代搜索到最优点。这种方法常常根据经验或通过试验得到所优点。这种方法常常根据经验或通过试验得到所需结果。对于一维搜索需结果。对于一维搜索(单变量极值问题单变量极值问题)，主要，主要用消去

9、法或多项式用消去法或多项式插值法插值法；对于多维搜索问题；对于多维搜索问题(多多变量极值问题变量极值问题)主要应用爬山法。主要应用爬山法。 数值计算法：以梯度法为基础的一种直接法，数值计算法：以梯度法为基础的一种直接法，是一种解析与数值计算相结合的方法。是一种解析与数值计算相结合的方法。 其他方法：如网络最优化方法等其他方法：如网络最优化方法等(见见网络理论网络理论)。 第第10页页 最优解最优解最优化问题的解一般称为最优解。最优化问题的解一般称为最优解。如果只考察约束集合中某一局部范围内的优劣情况，则解如果只考察约束集合中某一局部范围内的优劣情况，则解称为称为局部最优解局部最优解。如果是考察

10、整个约束集合中的情况，则解称为如果是考察整个约束集合中的情况，则解称为总体最优解总体最优解。 对于不同优化问题，最优解有不同的含意，还有专用的对于不同优化问题，最优解有不同的含意，还有专用的名称。名称。 例如，在例如，在对策论对策论和数理经济模型中称为平衡解；和数理经济模型中称为平衡解； 在控制问题中称为最优控制或极值控制；在控制问题中称为最优控制或极值控制； 在多目标决策问题中称为非劣解（又称帕雷托最优解或在多目标决策问题中称为非劣解（又称帕雷托最优解或有效解）。有效解）。第第11页页 在解决实际问题时情况错综复杂，有时这种理想的在解决实际问题时情况错综复杂，有时这种理想的最优解不易求得，或

11、者需要付出较大的代价，因而最优解不易求得，或者需要付出较大的代价，因而对解只要求能满足一定限度范围内的条件对解只要求能满足一定限度范围内的条件,不一定过不一定过分强调最优。分强调最优。 50年代初年代初,在运筹学发展的早期就有人提出次优化的在运筹学发展的早期就有人提出次优化的概念及其相应的次优解。概念及其相应的次优解。 最优化模型的建立本身就只是一种近似，因为实际最优化模型的建立本身就只是一种近似，因为实际问题中存在的某些因素，尤其是一些非定量因素很问题中存在的某些因素，尤其是一些非定量因素很难在一个模型中全部加以考虑。另一方面，还缺乏难在一个模型中全部加以考虑。另一方面，还缺乏一些求解较为复

12、杂模型的有效方法。一些求解较为复杂模型的有效方法。1961年年H.A.西西蒙进一步提出蒙进一步提出满意解满意解的概念，即只要决策者对解满的概念，即只要决策者对解满意即可。意即可。第第12页页 最优化方法的应用最优化方法的应用 最优设计最优设计: 世界各国工程技术界世界各国工程技术界, 尤其是飞机、造尤其是飞机、造船、机械、建筑等部门都已广泛应用最优化方法于船、机械、建筑等部门都已广泛应用最优化方法于设计中，从各种设计参数的优选到最佳结构形状的设计中，从各种设计参数的优选到最佳结构形状的选取等，结合选取等，结合有限元方法有限元方法已使许多设计优化问题得已使许多设计优化问题得到解决。到解决。 新的

13、发展动向是新的发展动向是最优设计和最优设计和计算机辅助设计计算机辅助设计相结合。相结合。电子线路的最优设计是另一个应用最优化方法的重电子线路的最优设计是另一个应用最优化方法的重要领域。配方配比的优选方面在化工、橡胶、塑料要领域。配方配比的优选方面在化工、橡胶、塑料等工业部门都得到成功的应用等工业部门都得到成功的应用,并向计算机辅助搜并向计算机辅助搜索最佳配方、配比方向发展索最佳配方、配比方向发展(见见优选法优选法)。第第13页页 最优计划最优计划: 现代国民经济或部门经济的计划，直现代国民经济或部门经济的计划，直至企业的发展规划和年度生产计划，尤其是农业规至企业的发展规划和年度生产计划，尤其是

14、农业规划、种植计划、能源规划和其他资源、环境和生态划、种植计划、能源规划和其他资源、环境和生态规划的制订规划的制订,都已开始应用最优化方法。都已开始应用最优化方法。 一个重要的发展趋势是帮助领导部门进行各种优化一个重要的发展趋势是帮助领导部门进行各种优化决策。决策。 最优管理：一般在日常生产计划的制订、调度和最优管理：一般在日常生产计划的制订、调度和运行中都可应用最优化方法。随着管理信息系统和运行中都可应用最优化方法。随着管理信息系统和决策支持系统决策支持系统的建立和使用，使最优管理得到迅速的建立和使用，使最优管理得到迅速的发展。的发展。第第14页页 最优控制：最优控制： 主要用于对各种控制系

15、统的优化。例如，导弹系统的主要用于对各种控制系统的优化。例如，导弹系统的最优控制，能保证用最少燃料完成飞行任务最优控制，能保证用最少燃料完成飞行任务,用最短用最短时间达到目标时间达到目标;再如飞机、船舶、电力系统等的最优再如飞机、船舶、电力系统等的最优控制，化工、冶金等工厂的最佳工况的控制。控制，化工、冶金等工厂的最佳工况的控制。 计算机接口计算机接口装置不断完善和优化方法的进一步发展，装置不断完善和优化方法的进一步发展，还为计算机在线生产控制创造了有利条件。最优控制还为计算机在线生产控制创造了有利条件。最优控制的对象也将从对机械、电气、化工等硬系统的控制转的对象也将从对机械、电气、化工等硬系统的控制转向对生态、环境以至社会经济系统的控制。向对生态、环境以至社会经济系统的控制。 第第15页页线性规划线性规划数数学学规规划划非线性规划非线性规划整数规划整数规划动态规划动态规划学学科科内内容容多目标规划多目标规划组组合合优优化化组合优化和最优计数问题组合优化和最优计数问题图论和网络优化图论和网络优化排序问题排序问题随随机机优优化化博弈论博弈论排队论排队论