最最佳化方法

​基本定义

最最佳化方法(也称做运筹学方法)是近几十年形成的，它主要运用数学方法研究各种系统的最佳化途径及方案，为决策者提供科学决策的依据。最最佳化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最最佳化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最最佳化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地套用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。本章将介绍最最佳化方法的研究对象、特点，以及最最佳化方法模型的建立和模型的分析、求解、套用。主要是线性规划问题的模型、求解(线性规划问题的单纯形解法)及其套用――运输问题;以及动态规划的模型、求解、套用――资源分配问题。

最最佳化方法

1.微分学中求极值

2.无约束最最佳化问题

3.常用微分公式

4.凸集与凸函式

5.等式约束最最佳化问题

6.不等式约束最最佳化问题

7.变分学中求极值

详细资讯

数学意义

为了达到最最佳化目的所提出的各种求解方法。从数学意义上说，最最佳化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函式达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大(如产值、利润)，或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。

发展简史

公元前 500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为1.618,称为黄金分割比。其倒数至今在优选法中仍得到广泛套用。在微积分出现以前，已有许多学者开始研究用数学方法解决最最佳化问题。例如阿基米德证明:给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。但是最最佳化方法真正形成为科学方法则在17世纪以后。17世纪，I.牛顿和G.W.莱布尼茨在他们所建立的微积分中，提出求解具有多个自变数的实值函式的最大值和最小值的方法。以后又进一步讨论具有未知函式的函式极值，从而形成变分法。这一时期的最最佳化方法可以称为古典最最佳化方法。第二次世界大战前后，由于军事上的需要和科学技术和生产的迅速发展，许多实际的最最佳化问题已经无法用古典方法来解决，这就促进了近代最最佳化方法的产生。近代最最佳化方法的形成和发展过程中最重要的事件有: 以苏联Л.В.康托罗维奇和美国G.B.丹齐克为代表的线性规划;以美国库恩和塔克尔为代表的非线性规划;以美国R.贝尔曼为代表的动态规划;以苏联Л.С.庞特裏亚金为代表的极大值原理等。这些方法后来都形成体系，成为近代很活跃的学科，对促进运筹学、管理科学、控製论和系统工程等学科的发展起了重要作用。

工作步骤

用最最佳化方法解决实际问题，一般可经过下列步骤:①提出最最佳化问题，收集有关资料和资料;②建立最最佳化问题的数学模型,确定变数,列出目标函式和约束条件;③分析模型，选择合适的最最佳化方法;④求解，一般通过编製程式，用电脑求最优解;⑤最优解的检验和实施。上述 5个步骤中的工作相互支持和相互製约，在实践中常常是反复交叉进行。

模型的基本要素

最最佳化模型一般包括变数、约束条件和目标函式三要素:①变数:指最最佳化问题中待确定的某些量。变数可用x=(x1，x2,…,xn)T表示。②约束条件:指在求最优解时对变数的某些限製,包括技术上的约束、资源上的约束和时间上的约束等。列出的约束条件越接近实际系统，则所求得的系统最优解也就越接近实际最优解。约束条件可用 gi(x)≤0表示i=1,2，…，m，m 表示约束条件数;或x∈R(R表示可行集合)。③目标函式:最最佳化有一定的评价标準。目标函式就是这种标準的数学描述，一般可用f(x)来表示，即f(x)=f(x1，x2,…,xn)。要求目标函式为最大时可写成;要求最小时则可写成。目标函式可以是系统功能的函式或费用的函式。它必须在满足规定的约束条件下达到最大或最小。 问题的分类 最最佳化问题根据其中的变数、约束、目标、问题性质、时间因素和函式关系等不同情况，可分成多种类型(见表)。最最佳化方法

最最佳化方法

不同类型的最最佳化问题可以有不同的最最佳化方法，即使同一类型的问题也可有多种最最佳化方法。反之,某些最最佳化方法可适用于不同类型的模型。最最佳化问题的求解方法一般可以分成解析法、直接法、数值计演算法和其他方法。①解析法:这种方法只适用于目标函式和约束条件有明显的解析表达式的情况。求解方法是:先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用求导数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。②直接法:当目标函式较为复杂或者不能用变数显函式描述时，无法用解析法求必要条件。此时可採用直接搜寻的方法经过若干次迭代搜寻到最优点。这种方法常常根据经验或通过试验得到所需结果。对于一维搜寻(单变数极值问题)，主要用消去法或多项式插值法;对于多维搜寻问题(多变数极值问题)主要套用爬山法。③数值计演算法:这种方法也是一种直接法。它以梯度法为基础，所以是一种解析与数值计算相结合的方法。④其他方法:如网路最最佳化方法等(见网路理论)。

解析性质

根据函式的解析性质，还可以对各种方法作进一步分类。例如，如果目标函式和约束条件都是线性的，就形成线性规划。线性规划有专门的解法，诸如单纯形法、解乘数法、椭球法和卡马卡法等。当目标或约束中有一非线性函式时,就形成非线性规划。当目标是二次的,而约束是线性时，则称为二次规划。二次规划的理论和方法都较成熟。如果目标函式具有一些函式的平方和的形式，则有专门求解平方和问题的最佳化方法。目标函式具有多项式形式时，可形成一类几何规划。

最优解的概念

最最佳化问题的解一般称为最优解。如果只考察约束集合中某一局部範围内的优劣情况，则解称为局部最优解。如果是考察整个约束集合中的情况，则解称为整体最优解。对于不同最佳化问题，最优解有不同的含意，因而还有专用的名称。例如，在对策论和数理经济模型中称为平衡解;在控製问题中称为最优控製或极值控製;在多目标决策问题中称为非劣解(又称帕雷托最优解或有效解)。在解决实际问题时情况错综复杂，有时这种理想的最优解不易求得，或者需要付出较大的代价，因而对解只要求能满足一定限度範围内的条件,不一定过分强调最优。50年代初,在运筹学发展的早期就有人提出次最佳化的概念及其相应的次优解。提出这些概念的背景是:最最佳化模型的建立本身就只是一种近似，因为实际问题中存在的某些因素，尤其是一些非定量因素很难在一个模型中全部加以考虑。另一方面，还缺乏一些求解较为复杂模型的有效方法。1961年H.A.西蒙进一步提出满意解的概念，即只要决策者对解满意即可。

最最佳化方法的套用

最最佳化一般可以分为最优设计、最优计画、最优管理和最优控製等四个方面。①最优设计:世界各国工程技术界,尤其是飞机、造船、机械、建筑等部门都已广泛套用最最佳化方法于设计中，从各种设计参数的优选到最佳结构形状的选取等，结合有限元方法已使许多设计最佳化问题得到解决。一个新的发展动向是最优设计和电脑辅助设计相结合。电子线路的最优设计是另一个套用最最佳化方法的重要领域。配方配比的优选方面在化工、橡胶、塑胶等工业部门都得到成功的套用,并向电脑辅助搜寻最佳配方、配比方向发展(见优选法)。②最优计画:现代国民经济或部门经济的计画，直至企业的发展规划和年度生产计画，尤其是农业规划、种植计画、能源规划和其他资源、环境和生态规划的製订,都已开始套用最最佳化方法。一个重要的发展趋势是帮助领导部门进行各种最佳化决策。③最优管理:一般在日常生产计画的製订、调度和运行中都可套用最最佳化方法。随着管理信息系统和决策支持系统的建立和使用，使最优管理得到迅速的发展。④最优控製:主要用于对各种控製系统的最佳化。例如，飞弹系统的最优控製，能保证用最少燃料完成飞行任务,用最短时间达到目标;再如飞机、船舶、电力系统等的最优控製，化工、冶金等工厂的最佳工况的控製。电脑接口装置不断完善和最佳化方法的进一步发展，还为电脑线上生产控製创造了有利条件。最优控製的对象也将从对机械、电气、化工等硬系统的控製转向对生态、环境以至社会经济系统的控製。

图书信息

书 名: 最最佳化方法

作 者:张立卫

出版社:科学出版社

出版时间: 2010年6月1日

ISBN: 9787030276490

开本: 16开

定价: 27.00元

内容简介

《最最佳化方法》介绍最最佳化模型的理论与计算方法，其中理论包括对偶理论、非线性规划的最优性理论、非线性半定规划的最优性理论、非线性二阶锥最佳化的最优性理论;计算方法包括无约束最佳化的线搜寻方法、线性规划的单纯形方法和内点方法、非线性规划的序列二次规划方法、非线性规划的增广Lagrange方法、非线性半定规划的增广Lagrange方法、非线性二阶锥最佳化的增广Lagrange方法以及整数规划的Lagrange松弛方法。《最最佳化方法》注重知识的準确性、系统性和演算法论述的完整性，是学习最最佳化方法的一本入门书。

《最最佳化方法》可用作高等院校数学系高年级大学部生和管理专业研究生的教材，也可作为相关工程技术人员的参考用书。

图书目录

前言

第1章 变分分析的相关素材

1.1 凸分析素材

1.1.1 凸集合

1.1.2 凸函式的闭包

1.1.3 共轭函式

1.1.4 次可微性

1.2 集值对应的极限

1.3 方向导数

1.4 集合的切锥与二阶切集

1.4.1 集合的切锥

1.4.2 二阶切集

1.4.3 函式水準集的切锥与二阶切集

1.4.4 负卦限锥的切锥与二阶切集

1.5 有限维系统的稳定性

1.5.1线性系统

1.5.2 集契约束的线性系统

1.5.3 集契约束的非线性系统

第2章 无约束最佳化

2.1 引言

2.2 线搜寻方法

2.2.1 线搜寻原则

2.2.2 下降方法的收敛性

2.3 最速下降方法

2.3.1 最速下降方法的全局收敛性

2.3.2 最速下降方法的收敛速度

2.4 Newton法

2.4.1 经典Newton法

2.4.2 带线搜寻的:Newton法

2.4.3 自协调函式的Newton法

2.5 拟Newton法

2.5.1 拟Newton方程和着名的拟Newton公式

2.5.2 拟Newton法求解凸二次规划

2.5.3 Dixon定理

2.5.4 DFP方法的收敛性

2.5.5 BFGS方法的收敛性

2.5.6 限製Broyden类方法的收敛性

2.6 共轭梯度方法

2.6.1 共轭方向

2.6.2 共轭梯度方法求解二次规划

2.6.3 求解无约束最佳化问题的FR方法

2.7 信赖域方法

2.7.1 信赖域基本演算法

2.7.2 Cauchy点与模型下降

2.7.3 信赖域演算法的收敛性

第3章 线性规划

3.1 线性规划问题及其性质

3.2 单纯形法

3.3 Bland原则

3.4 线性规划的对偶定理

3.5 对偶单纯形方法

3.6 线性规划的Karmakar内点法

3.6.1 解析中心与势函式

3.6.2 线性规划的势函式

3.6.3 线性规划的中心路径

3.6.4 线性规划的Karmarkar演算法

第4章 对偶理论

4.1 共轭对偶性

4.2 Lagrange对偶性

4.3 对偶理论的套用

第5章 最优性条件

5.1 一阶最优性条件

5.2 广义Lagrange乘子

5.3 二阶最优性条件

第6章 增广Lagrange函式方法

6.1 惩罚与障碍函式方法

6.1.1 惩罚函式方法

6.1.2 经典障碍函式方法

6.2 增广Lagrange函式方法

6.2.1 增广Lagrange函式

6.2.2 Bertsekas的经典结果

6.2.3 对偶收敛率

第7章 序列二次规划(SQP)方法

7.1 等式约束最佳化问题的局部方法

7.1.1 Newton法

7.1.2 KKT系统

7.1.3 既约Hesse阵方法

7.2 一般约束最佳化问题的局部方法

7.2.1 序列二次规划方法

7.2.2 原始.对偶二次收敛性

7.2.3 原始超线性收敛性

7.3 线搜寻全局方法

7.3.1 不可微惩罚函式

7.3.2 线搜寻SQP方法

7.3.3 Maratos效应

参考文献