最优化方法

最优化方法最优化及最优化方法最优化是一门应用十分广泛的学科，它研究在有限种或无限种可行方案中挑选最优方案，构造寻求最优解的计算方法。达到最优目标的方案，称为最优方案，搜索最优方案的方法，称为最优化方法。这种方法的数学理论，称为最优化理论。最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的研究对象及应用最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到空间技术、军事科学、电子工程、通讯工程、自动控制、系统识别、资源分配、计算数学、公共管理、经济管理等各个领域，发挥着越来越重要的作用。最优化方法的具体应用举例最优化一般可以分为最优设计、最优计划、最优管理和最优控制等四个方面。①最优设计:世界各国工程技术界,尤其是飞机、造船、机械、建筑等部门都已广泛应用最优化方法于设计中，从各种设计参数的优选到最佳结构形状的选取等，结合有限元方法已使许多设计优化问题得到解决。一个新的发展动向是最优设计和计算机辅助设计相结合。电子线路的最优设计是另一个应用最优化方法的重要领域。配方配比的优选方面在化工、橡胶、塑料等工业部门都得到成功的应用,并向计算机辅助搜索最佳配方、配比方向发展(见优选法)。最优化方法的具体应用举例②最优计划:现代国民经济或部门经济的计划，直至企业的发展规划和年度生产计划，尤其是农业规划、种植计划、能源规划和其他资源、环境和生态规划的制订,都已开始应用最优化方法。一个重要的发展趋势是帮助领导部门进行各种优化决策。③最优管理：一般在日常生产计划的制订、调度和运行中都可应用最优化方法。随着管理信息系统和决策支持系统的建立和使用，使最优管理得到迅速的发展。最优化方法的具体应用举例④最优控制：主要用于对各种控制系统的优化。例如，导弹系统的最优控制，能保证用最少燃料完成飞行任务,用最短时间达到目标;再如飞机、船舶、电力系统等的最优控制，化工、冶金等工厂的最佳工况的控制。计算机接口装置不断完善和优化方法的进一步发展，还为计算机在线生产控制创造了有利条件。最优控制的对象也将从对机械、电气、化工等硬系统的控制转向对生态、环境以至社会经济系统的控制。最优化的发展简史最优化是一个古老的课题。长期以来，人们对最优化问题进行着探讨和研究。公元前500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为1.618,称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。例如阿基米德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。最优化的发展简史但是最优化方法真正形成为科学方法则在17世纪以后。17世纪，I.牛顿和G.W.莱布尼茨在他们所创建的微积分中，提出求解具有多个自变量的实值函数的最大值和最小值的方法，后来又出现Lagrange乘数法。以后又进一步讨论具有未知函数的函数极值，从而形成变分法。这一时期的最优化方法可以称为古典最优化方法。最优化的发展简史第二次世界大战前后，由于军事上的需要和科学技术和生产的迅速发展，许多实际的最优化问题已经无法用古典方法来解决，这就促进了近代最优化方法的产生。近代最优化方法的形成和发展过程中最重要的事件有：1847年法国数学家Cauchy研究了函数值沿什么方向下降最快的问题，提出最速下降法。1939年前苏联数学家Л.B.Канторович提出了解决下料问题和运输问题这两种线性规划问题的求解方法。最优化的发展简史以苏联Л.В.康托罗维奇和美国G.B.丹齐克为代表的线性规划；以美国库恩和塔克尔为代表的非线性规划；以美国R.贝尔曼为代表的动态规划；以苏联Л.С.庞特里亚金为代表的极大值原理等。这些方法后来都形成体系，成为近代很活跃的学科，对促进运筹学、管理科学、控制论和系统工程等学科的发展起了重要作用。最优化的发展简史直到20世纪30年代，最优化这个古老课题并未形成独立的有系统的学科。20世纪40年代以来，由于生产和科学研究突飞猛进地发展，特别是电子计算机日益广泛使用，使最优化问题的研究不仅成为一种迫切需要，而且有了求解的有力工具。因此最优化理论和算法迅速发展起来，形成一个新的学科。最优化方法的内容最优化方法包括的内容很广泛，如线性规划、非线性规划、整数规划、几何规划、动态规划、随机规划、多目标规划、组合优化(在给定有限集的所有具备某些条件的子集中，按某种目标找出一个最优子集的一类数学规划)等等。几何规划非线性规划的一个分支,是最有效的最优化的方法之一。几何规划最初是由数学家R.J.达芬和E.L.彼得森及C.M.查纳等人于1961年在研究工程费用极小化问题基础上提出的，直到1967年《几何规划》一书出版后才正式定名。几何规划的数学基础是G.H.哈代的平均理论。由于几何平均不等式的关键性作用，几何规划由此得名。几何规划的目标函数和约束条件均由广义多项式构成，这是一类特殊的非线性规划，利用其对偶原理，可以把高度非线性问题的求解转化为具有线性约束的优化问题求解，使计算大为简化。几何规划理论研究和算法软件开发、发展都很快，并且在化工、机械、土木、电气、核工程等部门的工程优化设计和企业管理、资源分配、环境保护以及技术经济分析等方面都得到广泛应用。整数规划整数规划是指一类要求问题中的全部或一部分变量为整数的数学规划。是近三十年来发展起来的、规划论的一个分支.整数规划问题是要求决策变量取整数值的线性规划或非线性规划问题。一般认为非线性的整数规划可分成线性部分和整数部分，因此常常把整数规划作为线性规划的特殊部分。在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求解答必须是整数。例如，所求解是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是0-1规划，它的变数仅限于0或1。整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的，30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是分支定界法和割平面法，它们都是在上述框架下形成的。0—1规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整数规划都与0—1规划等价，用0—1规划方法还可以把多种非线性规划问题表示成整数规划问题，所以不少人致力于这个方向的研究。求解0—1规划的常用方法是分支定界法，对各种特殊问题还有一些特殊方法，例如求解指派问题用匈牙利方法就比较方便。组合最优化在给定有限集的所有具备某些条件的子集中，按某种目标找出一个最优子集的一类数学规划，又称组合规划。从最广泛的意义上说，组合规划与整数规划这两者的领域是一致的，都是指在有限个可供选择的方案的组成集合中，选择使目标函数达到极值的最优子集。组合最优化发展的初期，研究一些比较实用的基本上属于网络极值方面的问题，如广播网的设计、开关电路设计、航船运输路线的计划、工作指派、货物装箱方案等。自从拟阵概念进入图论领域之后，对拟阵中的一些理论问题的研究成为组合规划研究的新课题，并得到应用。现在应用的主要方面仍是网络上的最优化问题，如最短路问题、最大（小）支撑树问题、最优边无关集问题、最小截集问题、推销员问题等。整数规划与组合最优化的关系整数规划与组合最优化从广泛的意义上说，两者的领域是一致的，都是在有限个可供选择的方案中，寻找满足一定标准的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，背袋（或装载）问题、固定费用问题、和睦探险队问题（组合学的对集问题）、有效探险队问题（组合学的覆盖问题）、送货问题等。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。随机规划随机规划是对含有随机变量的优化问题建模的有效的工具并已有一个世纪的历史。第一种随机规划是美国经济学家丹泽1955年提出的，康托罗维奇在这方面的贡献，不在于这个新方法本身，而在于把它应用于制定最优计划。是广泛使用的期望值模型，即在期望约束条件下，使得期望收益达到最大或期望损失达到最小的优化方法。第二种是由查纳斯（A.Charnes）和库伯(W.W.Cooper）于1959年提出的机会约束规划，是在一定的概率意义下达到最优的理论。第三种即是刘宝碇教授于1997年提出的相关机会规划，是一种使事件的机会在随机环境下达到最优的理论。它与期望值模型和机会约束规划一起构成了随机规划的三个分支。随机规划是处理数据带有随机性的一类数学规划，它与确定性数学规划最大的不同在于其系数中引进了随机变量，这使得随机规划比起确定性数学规划更适合于实际问题。在管理科学、运筹学、经济学、最优控制等领域，随机规划有着广泛的应用。随机规划的求解方法随机规划的求解方法大致分两种。第一种是转化法，即将随机规划转化成各自的确定性等价类，然后利用已有的确定性规划的求解方法解之；另一种是逼近方法，利用随机模拟技术，通过一定的遗传算法程序，得到随机规划问题的近似最优解和目标函数的近似最优值。讲授内容教材：最优化方法及应用案例.绪论.线性规划.非线性规划.动态规划.多目标优化及其应用预备知识、学习要求、考核方式学习该课程的需要具备的基本知识高等数学线性代数学习该课程的要求态度决定一切正确理解基本概念和原理掌握最优化方法的思想能够运用最优化方法分析解决实际问题考核方式：闭卷笔试+讨论报告或大作业最优化问题的数学模型一般形式最优化问题..0,1,2,,1.2istgxim0,1,,,1.3jhxjp目标函数的极小（极大）（不等式约束）（等式约束）其中nTnRxxxx,,21min(max)()(1.1)fx最优化问题的数学模型标准形式最优化问题min()fx..0,1,2,istgxim目标函数的极小（不等式约束）min()fx或0,1,2,,nixDxgximxR其中最优化问题分类经典优化问题和现代优化问题或静态优化问题和动态优化问题。1、经典优化问题（静态优化问题）根据数学模型中有无约束函数分为有约束的最优化问题和无约束的最优化问题；根据目标函数和约束函数的函数类型分类：线性最优化问题(整数规划、０－１规划)、非线性最优化问题、二次规划、多目标规划。2、现代优化问题（动态优化问题）动态规划与最优控制问题组合优化问题最优解的相关定义定义１.1可行解满足约束条(1.2)和(1.3)的x称为可行解，也称为可行点或容许点。定义１.2可行域全体可行解构成的集合称为可行域，也称为容许集，记为D,即：0,1,2,,niDxgximxR定义１.3整体(全局）最优解Dx*,xD若对于一切则称,*xfxf恒有*x为最优化问题的整体(全局）最优解。若,,*xxDx恒有,*xfxf则称*x为最优化问题