最优化基础理论与方法

目录

1．最优化的概念与分类 (2)

2. 最优化问题的求解方法 (3)

2.1线性规划求解 (3)

2.1.1线性规划模型 (3)

2.1.2线性规划求解方法 (3)

2.1.3 线性规划算法未来研究方向 (3)

2.2非线性规划求解 (4)

2.2.1一维搜索 (4)

2.2.2无约束法 (4)

2.2.3约束法 (4)

2.2.4凸规划 (5)

2.2.5二次规划 (5)

2.2.6非线性规划算法未来研究方向 (5)

2.3组合规划求解方法 (5)

2.3.1 整数规划 (5)

2.3.2 网络流规划 (7)

2.4多目标规划求解方法 (7)

2.4.1 基于一个单目标问题的方法 (7)

2.4.2 基于多个单目标问题的方法 (8)

2.4.3多目标规划未来的研究方向 (8)

2.5动态规划算法 (8)

2.5.1 逆推解法 (8)

2.5.2 顺推解法 (9)

2.5.3 动态规划算法的优点及研究方向 (9)

2.6 全局优化算法 (9)

2.6.1 外逼近与割平面算法 (9)

2.6.2 凹性割方法 (9)

2.6.3 分支定界法 (9)

2.6.4 全局优化的研究方向 (9)

2.7随机规划 (9)

2.7.1 期望值算法 (10)

2.7.2 机会约束算法 (10)

2.7.3 相关机会规划算法 (10)

2.7.4 智能优化 (10)

2.8 最优化软件介绍 (11)

3 最优化算法在电力系统中的应用及发展趋势 (12)

3.1 电力系统的安全经济调度问题 (12)

3.1.1电力系统的安全经济调度问题的介绍 (12)

3.1.2电力系统的安全经济调度问题优化算法的发展趋势 (12)

2. 最优化问题的求解方法 最优化方法是近几十年形成的，它主要运用数学方法研究各种优化问题的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。

2.1线性规划求解

2.1.1线性规划模型

线性规划模型的一般表达方式如下所示：

112211221122min .. , 1,2,, 0 , 1, , 1, 0 , 1,2,, , n n

i i in n i i i in n i j j z c x c x c x s t a x a x a x b i p

a x a x a x

b j i p m x j q

q n

x =++???+++==??=?++≥=+???≥+?=?????¤

（2.1） 其中，j x （1,2,,j n =???）为待定的决策变量，己知的系数ij a 组成的矩阵A 称为约束矩

阵。A 的列向量记为j A （1,2,,j n =???）。A 的行向量记为T i

A (1,2,,i m =???)。目标函数记为1n

j j j c x =∑，向量()12,,T

n C c c c =???称为价值向量，j c 称为价值系数；向量12(,)T m b b b b =???称为右端向量。条件0j x ≥称为非负约束；0j x ¤表示变量可取正值、负值、或零值，称这样的变量为自由变量。

2.1.2线性规划求解方法 2.1.2.1 单纯形法

求解线性规划问题的基本方法是单纯形法，是研究得最为透彻的一个方向，且至今仍是最好的应用最广泛的算法之一，已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。

它的理论根据是：线性规划问题的可行域是 n 维向量空间R n 中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。

单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

2.1.2.2 内点算法

除了单纯形算法之外，现在经常使用的线性规划求解方法还包括内点算法，内点算法中的代表即Karmarkar 算法。

Karmarkar 算法运用了求解非线性规划问题的思想来解决线性规划问题。这种算法是在把一般线性规划问题转化为Karmarkar 所特有的标准型，再利用一种求解这种标准型的算法最终求出最优解。

2.1.3 线性规划算法未来研究方向

内点法是最新的设计，实际应用上它也可以与单纯形法相抗衡，不少商业化软件已经上市，前景甚佳。目前线性规划的内点法也趋于成熟，这方面的研究者们目前大都致力于以线性规划作为特例的锥规划，以及如何利用线性规划松弛求解整数规划等方面的研究。

2.2非线性规划求解

非线性规划问题的求解一般要比线性规划困难很多，而且目前尚没有适合于各类非线性问题的一般算法，每种算法都有自己的特定的使用范围。有些情况下，为方便计算，也会把非线性规划问题近似为线性规划问题进行求解。

2.2.1一维搜索

一维搜索是求解单变量非线性规划问题的方法。这类方法不仅有实用价值，而且大量多维最优化方法都依赖于一系列的一维最优化。常用的一维最优化方法有黄金分割法、切线法和插值法。

2.2.1.1黄金分割法

黄金分割法又称0.618法。它适用于单峰函数。其基本思想是：在初始寻查区间中设计一列点，通过逐次比较其函数值，逐步缩小寻查区间，以得出近似最优值点。

2.2.1.2切线法

又称牛顿法。它也是针对单峰函数的。其基本思想是：在一个猜测点附近将目标函数的导函数线性化，用此线性函数的零点作为新的猜测点，逐步迭代去逼近最优点。

2.2.1.3插值法

又称多项式逼近法。其基本思想是用多项式（通常用二次或三次多项式）去拟合目标函数。

此外，还有斐波那契法、割线法、有理插值法、分批搜索法等。

2.2.2无约束法

无约束法是求解无约束条件的非线性规划问题的方法，指寻求n元实函数f在整个n

维向量空间Rn上的最优值点的方法。这类方法的意义在于：虽然实用规划问题大多是有约束的，但许多约束最优化方法可将有约束问题转化为若干无约束问题来求解。

无约束最优化方法大多是逐次一维搜索的迭代算法。这类迭代算法可分为两类。一类需要用目标函数的导函数，称为解析法。另一类不涉及导数，只用到函数值，称为直接法。这些迭代算法的基本思想是：在一个近似点处选定一个有利搜索方向，沿这个方向进行一维寻查，得出新的近似点。然后对新点施行同样手续，如此反复迭代，直到满足预定的精度要求为止。根据搜索方向的取法不同，可以有各种算法。属于解析型的算法有：①梯度法：又称最速下降法。这是早期的解析法，收敛速度较慢。②牛顿法：收敛速度快，但不稳定，计算也较困难。③共轭梯度法：收敛较快，效果较好。④变尺度法：这是一类效率较高的方法。其中达维登-弗莱彻-鲍威尔变尺度法，简称DFP法，是最常用的方法。属于直接型的算法有交替方向法（又称坐标轮换法）、模式搜索法、旋转方向法、鲍威尔共轭方向法和单纯形加速法等。

2.2.3约束法

指前述一般非线性规划模型的求解方法。常用的约束最优化方法有4种。①拉格朗日乘子法：它是将原问题转化为求拉格朗日函数的驻点。②制约函数法：又称系列无约束最小化方法，简称SUMT法。它又分两类，一类叫惩罚函数法，或称外点法；另一类叫障碍函数法，或称内点法。它们都是将原问题转化为一系列无约束问题来求解。③可行方向法：这是一类通过逐次选取可行下降方向去逼近最优点的迭代算法。如佐坦迪克法、弗兰克－沃尔夫法、投影梯度法和简约梯度法都属于此类算法。④近似型算法：这类算法包括序贯线性规划法和序贯二次规划法。前者将原问题化为一系列线性规划问题求解，后者将原问题化为一系列二次规划问题求解。

2.2.4凸规划

这是一类特殊的非线性规划。在前述非线性规划数学模型中，若f 是凸函数，诸i g 都是凹函数，诸j h

都是一次函数，则称之为凸规划。所谓f 是凸函数，是指f 有如下性质：它的定义域是凸集，且对于定义域中任意两点x 和y 及任一小于1的正数α，下式都成立：

((1)x y)(1)(x)(y)f f f ααααα-+≤-+ （2.1）

将上述不等式中的不等号反向即得凹函数的定义。所谓凸集，是指具有如下性质的集合：连结集合中任意两点的直线段上的点全部属于该集合。

对于一般的非线性规划问题，局部解不一定是整体解。但凸规划的局部解必为整体解，而且凸规划的可行集和最优解集都是凸集。

2.2.5二次规划

二次规划是一类特殊的非线性规划。它的目标函数是二次函数，约束条件是线性的。求解二次规划的方法很多。常用方法是拉格朗日法，较简便易行的是沃尔夫法。它是依据库恩－塔克条件，在线性规划单纯形法的基础上加以修正而成的。此外还有莱姆基法、毕尔法、凯勒法等。

2.2.6非线性规划算法未来研究方向

就算法的发展来看，早期的方法以最速下降法和共轭梯度法为主，目前，序贯二次规划法是一类被用于广泛求解一般非线性规划的有效算法，同时也还有许多研究者在为改善这类算法作努力，其中包括序列线性规划算法以及内点算法等。非线性规化算法通常使用线搜索策略选取步长，或通过求解信赖域子问题而得到新的迭代点。这两个方面的研究非常基本，但仍有改善的空间。对于大规模问题，如何设计子空间算法；以及如何有效求解一般非线性规划的全局最优，和一些来自于图像处理等领域的特殊的非光滑问题是目前非线性规划比较重要的研究问题。总之，尽管在表面上看非线性规划已经有许许多多的研究，但由于非线性的存在，好的研究结果还将会不断出现，并且随着问题的不同而产生更加具有针对性的特殊算法。 2.3组合规划求解方法

组合优化是20世纪60年代逐渐发展起来的一个交叉学科分支，它的研究对象是有限集合上的极值问题。一个组合优化问题由三部分构成：已知条件的输入、可行解的描述、目标函数的定义。经典的组合优化问题包括网络流、旅行商、排序、装箱、着色、覆盖、最短网络等等。

组合优化的一个理论基础是计算复杂性理论，据此组合优化的可以分为两类：P 问题类和NP 难问题类；属于前者的问题有多项式时间算法，属于后者的问题一般认为不存在多项式时间算法，通常采用精确算法、启发式算法和近似算法等方法求解。精确算法包括简单枚举法、分而治之法、分支定界法、动态规划法等；启发式算法包括贪婪策略、局部搜索、禁忌搜索、神经网络、模拟退火、遗传算法等；近似算法包括贪婪策略法、局部搜索法、原始对偶法、划分法、松弛法、内点算法、半定规划等；其中启发式算法在实际工程中应用较广。

2.3.1整数规划

在组合规划中，有一个特殊的类型，其变量（全部或部分）限制为整数，称为整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是0-1规划，它的变数仅限于0或1。

从约束条件的构成又可细分为线性，二次和非线性的整数规划。目前所流行的求解整数规划的方法往往只适用于整数线性规划，除上述介绍的启发式算法，现今比较成功又流行的方法是分支定界法、割平面法和分解算法。随着社会的发展，实际规划问题的规模越来越庞大，模型也越来越复杂，现在经常将几类算法混合使用。

2.3.1.1分支定界法

分支定界法是一种搜索与迭代的方法，选择不同的分支变量和子问题进行分支。步骤如下：

(1)求整数规划的松弛问题最优解。

(2)若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步。

(3)任意选一个非整数解的变量i x，在松弛问题中加上约束

[]

i i

x x

≤

及

[]1

i i

x x

≤+

组成两

个新的松弛问题，称为分支。新的松弛问题具有如下特征：当原问题是求最大值时，目标值是分支问题的上界；当原问题足求最小值时，目标值是分支问题的下界。

(4)检查所有分支的解及目标函数值，若某分支的解是整数并且目标函数值大于(max)

等于其他分支的目标值，则将其他分支剪去不再计算，若还存在非整数解并且目标值大于( max)整数解的目标值，需要继续分支，再检查，直到得到最优解。

2.3.1.2割平面法

割平面法是1958年由美国学者高莫利提出的求解全整数规划的一种比较简单的方法。用割平面法求解整数规划的基本思路是：先不考虑整数约束条件，求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止．如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解．这个新增加的约束条件的作用就是去切割相应松弛问题的可行域，即割去松弛问题的部分非整数解(包括原已得到的非整数最优解)．而把所有的整数解都保留下来，故称新增加的约束条件为割平面．当经过多次切割后，就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点，它恰好就是所求问题的整数最优解．即切割后所对应的松弛问题，与原整数规划问题具有相同的最优解。

步骤如下：

(1)先不考虑变量的取整约束，用单纯形法求解相应的线性规划问题，如果该问题没有可行解或最优解已是整数则停止，否则转下步。

在求解相应的线性规划时，首先要将原问题的数学模型进行标准化。这里的“标准化”有两个含义：第一是将所有的不等式约束全部转化成等式约束，这是因为要采用单纯形表进行计算的缘故。第二是将整数规划中所有非整数系数全部转换成整数，这是出于构造“切割不等式”的需要。

(2)求一个“切割不等式”及添加到整数规划的约束条件中去，即对上述线性规划问题的可行域进行“切割”，然后返回步骤1。

2.3.1.3分解算法

分解算法的基本思想是，对整数规划问题的约束函数或者目标函数进行适当的区分和变换，得到另一个或者一系列相对简单的优化问题，通过求解比较简单的优化问题得到整数规划问题的最优解。从本质上说，分解算法也算是一种松弛方法，但他同前面介绍的割平面法、分支定界法不同之处在于，分解算法常常要将多个约束或变量的作用加以区别，分别对待。

分解算法包括基于拉格朗日松弛的分解算法和Benders分解法。

(1)基于拉格朗日松弛的分解算法

拉格朗日松弛算法是将约束与其相应拉格朗日乘子的乘积作为惩罚项加入目标函数,形成拉格朗日问题,进而通过求解拉格朗日问题的对偶问题来实现原问题的求解,该方法是目

前求解大规模整数规划问题最有效的方法之一。

拉格朗日松弛算法是将问题分解为双层优化问题,上层为最大化以拉格朗日乘子为变量的对偶问题,下层是对给定的拉格朗日乘子,最小化拉格朗日问题,可以分解为若干单机组问

题分别进行求解,通过不断交替求解上下层优化问题实现对问题的求解。由于对偶问题不可微,通常釆用次梯度法、束方法等不可微方法进行求解。

(2)Benders分解法

分解法是求解整数规划问题的一类常用的数学规划方法，它的基本思想是将问题的变量分为离散变量和连续变量两类，将问题分解为处理离散变量的混合整数线性规划主问题和处理连续变量的（非）线性规划子问题，通过求解混合整数线性规划主问题得到的整数最优解来产生（非）线性规划子问题，再用求解（非）线性规划子问题得到的解来构造新的线性不等式约束并添加到主问题中，通过逐次交替求解混合整数线性规划主问题和（非）线性规划子问题来获得原问题的最优解。

2.3.1.4整数规划未来研究方向

随着整数规划理论和算法的发展，整数规划已成为应用最广泛的最优化方法之一，特别是近年来整数规划算法技术和软件系统的发展和推广，整数规划得到了广泛的应用和发展。

整数规划问题的困难和挑战来源于三个方面：一是大部分整数规划问题都是NP-难的，故本质上不太可能存在和线性规划和凸规划一样有效的算法；二是对整数点集合(如多面体格点理论和全单模理论)和整数变量的函数在数学上缺乏有力的理论和工具；三是实际问题的规模往往超过现有算法的求解能力，尽管现有的一些整数规划软件可以求解任意线性、二次和非线性整数规划问题，但往往不能处理来源于实际问题的整数规划模型，例如运输和交通中的大规模。0-1混合线性整数规划问题，金融优化中的离散约束问题等。整数规划未来发展方向和关键问题包括：(1)整数多面体凸包的刻画；(2)随机整数规划；(3)多层整数规划；

(4)混合0-1二次整数规划；(5)协正规划；(6)半定整数规划。

2.3.2网络流规划

组合规划问题中有一种特殊的问题叫做网络流规划，网络流是一种类比水流的解决问题方法，与线性规划密切相关。一般包括最短路问题，最大流与最小割问题、最小费用网络问题、最大森林问题。

网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络

流的分解与合成等新课题。

2.4多目标规划求解方法

多目标规划问题的直接求法通常是寻找它的整个最优解集，除了特殊的情况，计算所有最优解是比较困难的。由于这个原因，对直接解法的研究结果还比较少。本节只介绍一些间接的求解多目标规划的方法，这些方法的共同特点是将多目标规划问题转换成一个或多个单目标规划问题，然后，通过求解单目标优化问题得到一个或多个最优解。一般的，并不要求间接解法给出问题的所有最优解。

2.4.1 基于一个单目标问题的方法

这类方法的基本思想如下：首先，将原来的多目标规划问题转换成一个单目标优化问题，然后，利用非线性优化算法求解该单目标问题，把所求得的最优解作为问题的最优解。这种方法的核心在于，保证所构造的单目标问题的最优解是有效解或若有效解。包括线性加权和法、主要目标法、极小极大法。

2.4.1.1 线性加权和法

线性加权和法是根据p个目标函数的重要程度，分别赋予一定的权系数，然后将所有的目标函数加权求和作为新的目标函数，在多目标规划问题的可行域上求出新的目标函数的最优值。

2.4.1.2 主要目标法

对于多目标问题，主要目标法是根据实际情况，首先确定一个目标函数为主要目标，而把其余p-1个目标函数作为次要目标，然后，借助于决策者的经验，通过选定一定的界限值把次要目标函数转化为约束条件，通过求解这样一个单目标问题获得原问题的解。

2.4.1.3 极小极大法

极小极大法的基本思想是在目标函数的p个分量中，极小化目标函数的最大分量，将该问题的最优解作为原问题的弱有效解。一般的，通过引入目标函数的权向量将问题转换为单目标问题，把该情况下的最优解称为原问题的极小化极大意义下的最优解。

2.4.2 基于多个单目标问题的方法

这类方法的基本思想是，根据某种规则，首先将多目标规划问题转换成有一定次序的多个单目标优化问题；然后，依次分别求解这些单目标优化问题，并且把最后一个单目标优化问题的最优解作为原问题的最优解。基于多个单目标问题的方法的核心是，保证最后一个单目标优化问题的最优解是多目标问题的有效解或弱有效解。包括分层排序法，重点目标法，分组排序法。

2.4.2.1分层排序法

分层排序法是根据目标的重要程度将它们一一排序，然后，分别在前一个目标的最优解集中，需求后一个目标的最优解集，并把最后一个目标函数的最优解作为原问题的最优解。

2.4.2.2重点目标法

重点目标法是在p个目标函数中，首先确定最重要的目标，并求出其最优解集，然后在此最优解集上求解其余p-1个目标对应的多目标规划问题.

2.4.2.3分组排序法

分组排序法的基本思想是根据某种规则，首先将多目标函数的目标分成若干组，使得在每个组内的目标的重要程度相差不多，此时，每组目标实际上对应着一个新的多目标规划问题，然后，依次在前一组目标对应问题的最优解集中，寻找后一组目标对应问题的最优解集，并把最后一组目标对应问题的最优解作为原问题的最优解。

2.4.3多目标规划未来的研究方向

在很多实际问题中，例如经济、管理、军事、科学和工程设计等领域，衡量一个方案的好坏往往难以用一个指标来判断，而需要用多个目标来比较，而这些目标有时不甚协调，甚至是矛盾的，因此有许多学者致力于这方面的研究。然而至今关于多目标最优解尚无一种完全令人满意的定义，所以在理论上多目标规划仍处于发展阶段。

2.5动态规划算法

当系统模型具备马尔科夫性，同时目标函数可分且嵌套单调时，基于贝尔曼提出的最优性原理，可将求解多阶段全局最优决策问题分解为一系列在各个时间段上的局部优化问题进行求解，这种算法叫做动态规划法。

动态规划是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。

同时值得注意的是，虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

下面介绍两种常用的动态规划算法思路：

2.5.1 逆推解法

逆推解法的步骤是利用已知条件从最后一个阶段开始有后向前推算，求得各阶段的最优决策和最优指标函数，最后算出第一阶段的目标函数时便得到最优指标函数值，然后再从第一阶段利用状态转移方程确定最优轨线和最优策略。

2.5.2 顺推解法

顺推解法和逆推解法的递推顺序正好相反，在顺推解法中从第一阶段开始，利用状态转移方程从前向后推算。

2.5.3 动态规划算法的优点及研究方向

相比其它解法，特别是在有扰动或在随机情况下，动态规划总是能有效地提供一个在当前信息集下的最优反馈控制策略。在过去的若干年里，动态规划取得了不少可喜的进展，特别是它被扩展到多目标动态规划；动态规划应用在本世纪前后的一个重大突破是其在海量数据分析中的应用，特别是人类基因组计划完成以后，它成为生物信息学的一个基本模型和工具。

然而，在克服被贝尔曼称之为“维数灾”的这一动态规划致命弱点的方面，至今尚未取得突破性的进展。所以寻求克服维数灾的有效算法对动态规划在高维问题中的应用具有它的紧迫性。另外，求解不可分优化问题得到的最优策略并不满足最优性原理，或不具备时间一致性。这牵涉到不可分优化问题模型本身的合理性。因此怎样找出一组可分优化问题来逼近一个给定的不可分优化问题也对动态规划发展具有显然的重要性。

2.6 全局优化算法

全局优化研究的是非线性目标函数在某个特定区域上全局最优的特征和计算方法。由于目标函数通常不是凸的函数，特定区域也有可能不是凸集，所以全局优化也可以称为非凸优化。由于很可能在一个全局优化问题里存在多个局部最优解，且它们不同于问题的全局最优解，因此人们无法借助于经典的局部优化方法求解这些问题，下面介绍三种经典的全局优化算法。

2.6.1 外逼近与割平面算法

外逼近的基本思想是，先将可行域D 松弛成一个相对简单的集合1D D ?，并且在这个

松弛集合上极小化目标函数。若松弛问题的解是可行的，那么原问题的求解过程完成，否则，添加一个辅助性约束割去1\D D 的一部分，生成一个新的松弛集合2D D ?。令松弛集合2D 替代原松弛集合，重复以上过程，以此类推，循环往复，就得到一个逼近原问题的松弛问题序列，求解松弛形式的子问题，得到一个最优解k x ，若k x D ∈，则k x 为问题的最优解。

2.6.2凹性割方法

在外逼近和割平面算法中，割作为一种工具是以合取方式使用的，即添加的割一般不会去掉可行点，并且所有割平面的交集构成整个可行域，因此，这种技术非常适合处理可行域是闭凸集这种情形。此时，支撑超平面能够将该凸集和它之外的点分离开来。然而，某些优化问题的可行域是非凸的，我们希望对非凸的集合进行逼近，用某种特定的割将非凸集与它之外的点分离开来，这就是凹形割方法，这是一种以析取方式使用割的技术，即每一割可能会去掉感兴趣区域的一部分，但是所有割的并集会覆盖我们感兴趣的区域。

2.6.3 分支定界法

分支定界法不但能够求解整数规划问题，而且也能够求解全局优化问题，在利用分支定界法求解全局优化问题时，首先，要对优化问题的可行域进行松弛；然后，将松弛集合依次分割成一些小集合（称为分支），在每个分支中确定待极小化的目标函数的下界（称为定界，有时，也需要确定目标函数最优值的上界，以便加快分支定界的收敛过程）；通过比较不同分支对应的目标函数最优值的界的关系，选择需要进一步分割的分支。依次类推，直至得到优化问题的最优解，或者满足要求的近似解。

2.6.4 全局优化的研究方向

全局优化问题的困难在于非凸性使卡罗胥一库恩一塔克条件一般不足以保证全局最优性，从而我们无法利用局部优化算法寻找全局最优点。本质上，由于导数是局部性质，因而不能期望基于导数性质的传统优化算法有希望求到全局解，全局算法需要函数和问题的全局性质。目前的数学理论很难或无法刻画一般多元函数的全局性质，这是全局优化问题的本质困难所在。全局优化的未来发展方向和关键问题包括：(1)凸逼近和凸松弛方法；(2)非凸二次规划；(3)基于模拟仿真技术的全局优化算法；(4)特殊结构的全局优化问题。

2.7随机规划

随机最优化问题是特指带有随机因素的最优化问题，需要利用概率统计、随机过程以及随机分析等工具。

2.7.1 期望值算法

通常人们处理随机因素的第一种方法是期望值方法，将随机的因素用它的期望值代替，将问题转化为确定性问题考虑。

2.7.2 机会约束算法

第二种方法是在概率意义下考虑优化问题。例如在置信区间范围内考虑优化问题，将问题转换为概率约束或者是机会约束的优化问题；又例如考虑极大化某些事件的概率问题，也称为机会约束算法。第二种方法相对于期望值方法的优点是考虑到各种风险的影响，缺点是使得问题的处理变得相对困难。

2.7.3 相关机会规划算法

第三种即是刘宝碇教授于1997年提出的相关机会规划，是一种使事件的机会在随机环境下达到最优的理论。

2.7.4 智能优化

智能优化是涉及数学、运筹学、生命科学、计算机科学等的一个交叉研究方向。智能优化主要是借鉴仿生学和拟物的思想，基于人们对生物体智能机理和某些自然规律的认识，采用数值计算的方法去模拟和实现人类的智能、生物智能和其它社会与自然的规律。智能优化本质上也属于随机优化，包括：遗传算法、粒子群算法、蚁群算法、人工神经网络算法等。

2.7.4.1 遗传算法

遗传算法是模拟达尔文生物进化论的遗传学机理和自然选择的生物进化过程的计算模型，是通过模拟自然界的进化过程来搜索最优解的一种方法。

遗传算法是从一个问题的可行解的种群开始的，通过对所产生的每个染色体进行评价，并根据适应度来选择染色体，使适应度好的染色体比适应度差的染色体有更多的繁殖机会。末代种群中的最优个体可以作为问题近似最优解。它的主要特点是群体搜索策略和群体之间的信息交换。与解析法、穷举法、随机法等传统搜索方法相比，遗传算法具有不需搜索空间的知识、并行爬峰、编码方法适应性广等特点。

遗传算法尤其适用于处理传统搜索方法难以解决的复杂的非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，是21世纪有关智能计算中的关键技术之一。

2.7.4.2 神经网络算法

神经网络是一种运算模型，由大量的节点(或称神经元)和之间相互连接构成。每个节点代表一种特定的输出函数，称为激励函数。每两个节点间的连接都代表一个对于通过该连接信号的加权值，即为权重，相当于人工神经网络的记忆功能。网络的输出则依据网络的连接方式，权重值和激励函数的不同而不同。

神经网络的特点和优越性主要有三点：(1)自学习功能；(2)联想存储功能；(3)高速寻找优化解的能力，神经网络主要应用在模式识别、自动控制、人工智能领域。近年来，神经网络与其他方法相结合的策略也得到了广泛的应用，且取得了很大的进展。

2.7.4.3粒子群算法

它是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。通常被认为是群集智能的一种。在这类算法中，每个优化问题的解都是搜索空间中的一只鸟，称之为“粒子”。粒子群算法初始化为一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。一个就是粒子本身所找到的最优解，这个解叫做个体极值，另一个极值是整个种群目前找到的最优解，这个极值是全局极值。

目前它已广泛应用于函数优化，神经网络训练，模糊系统控制以及其它应用领域。

2.7.4.4 蚁群算法

蚁群算法的基本思想来源于蚂蚁在寻找食物过程中发现路径的行为。它是一种用来在图中寻找优化路径的机率型算法。每只蚂蚁在事先不知道食物在什么地方的情况下开始寻找食物。当一只蚂蚁找到食物后，它就会向周围发出信息，吸引其他的蚂蚁过来，这样就会有越来越多的蚂蚁找到食物。然而并不是每只蚂蚁的路径都是一样的。如果有一只蚂蚁的路径比之前其他的蚂蚁的路径要短，就会吸引后面的蚂蚁走这条短的路径。经过一段时间后，可能

会出现一条最短的路径被大多数蚂蚁重复着。

2.7.5随机规划研究方向

随机模拟是针对实际问题含有随机因素所建立的模型进行的模拟。这种模型的定量描述往往用随机变量和随机过程，由此随机模拟研究中所形成的理论问题有：(1)均匀或非均匀随机数的生成；(2)离散时间的马氏或半马氏过程的模拟；(3)模拟输出的分析(包括用自回归过程、再生过程、谱分析、平稳非平稳时间序列方法)；(4)方差缩小方法(如使用对偶变量法、共同随机数法、重要抽样法、控制变量法)；(5)随机优化(如极大似然法、扰动分析、随机逼近等)。可以说随机模拟是运筹学理论研究和实际应用之间的一个桥梁，它受到越来越多的运筹学理论研究工作者和计算机领域学者的重视，它是运筹学、管理科学、计算机科学领域的一个重要分支。

2.8 最优化软件介绍

最优化算法主要是用于解决复杂大系统的各种最优化问题的，涉及的变量非常多，约束条件非常复杂，因而实际的最优化模型往往非常庞大，随着计算机的诞生及信息科技的飞速发展，为了在较短的时间内，求出优化问题的解，使用最优化软件称为了求解最优化问题的一大趋势，下面介绍一些现如今被广泛使用的最优化软件：

3 最优化算法在电力系统中的应用及发展趋势

早在50年代末、60年代初国内外即有应用线性规划进行电力系统电源优化规划的工作出现。60年代计算机软硬件迅速发展，计算能力迅速提高，逐渐解决了电力系统规划中变量多，要求计算机内存容量大，计算速度高的困难，使之逐步完善。现在最优化算法在电力系统的长期规划、调度运行、网架规划等方面都起到了重要的作用。

3.1 电力系统的安全经济调度问题

3.1.1电力系统的安全经济调度问题的介绍

电力系统的安全经济调度问题以系统成本最小为目标函数，考虑发电机自身约束、机组群约束、系统性约束及网络约束，是一个混合整数非线性规划问题，需要利用最优化方法求解。

一般，采用分段线性的方法将问题化为混合整数线性规划问题求解，求解方法包括优先顺序法、动态规划法、拉格朗日松弛法、分支定界法、benders分解法及智能优化算法等多种方法。

3.1.2电力系统的安全经济调度问题优化算法的发展趋势

当前，求解电力系统的安全经济调度问题的主流算法是拉格朗日松弛法和混合整数规划法，而在过去半个多世纪以来，伴随着最优化理论的发展，商业数学优化软件取得了显著进步，以CPLEX为例，从1991年的1.2版本(第一个能够求解混合整数规划问题的版本)，到2007年的11.0版本，其混合整数规划的求解效率提升了65倍以上。随着数学优化软件的发展，混合整数规划法逐渐成为国内外研究和应用的新热点。

同时，随着电网规模的不断扩大，简单地调用商业数学优化软件已经无法满足工业应用的要求。大规模电力系统的安全经济调度问题的研究，必须在算法流程设计上，深度嵌入人类智能思维方式，结合电力系统自身特点，避免寻优过程的盲目性，从而另辟蹊径地提升大规模混合整数规划问题的求解效率。

《最优化方法》复习题(含答案)

《最优化方法》复习题(含答案)

附录5 《最优化方法》复习题 1、设n n A R ?∈是对称矩阵，,n b R c R ∈∈，求1()2 T T f x x Ax b x c =++在任意点x 处的梯度和Hesse 矩阵． 解 2(),()f x Ax b f x A ?=+?=． 2、设()()t f x td ?=+，其中:n f R R →二阶可导，,,n n x R d R t R ∈∈∈，试求()t ?''． 解 2()(),()()T T t f x td d t d f x td d ??'''=?+=?+． 3、设方向n d R ∈是函数()f x 在点x 处的下降方向，令 ()()()()() T T T T dd f x f x H I d f x f x f x ??=--???， 其中I 为单位矩阵，证明方向()p H f x =-?也是函数()f x 在点x 处的下降方向． 证明 由于方向d 是函数()f x 在点x 处的下降方向，因此()0T f x d ?<，从而 ()()()T T f x p f x H f x ?=-?? ()()()()()()()() T T T T T dd f x f x f x I f x d f x f x f x ??=-?--???? ()()()0T T f x f x f x d =-??+?<， 所以，方向p 是函数()f x 在点x 处的下降方向． 4、n S R ?是凸集的充分必要条件是12122,,,,,,,,m m m x x x S x x x ?≥?∈L L 的一切凸组合都属于S ． 证明 充分性显然．下证必要性．设S 是凸集，对m 用归纳法证明．当2m =时，由凸集的定义知结论成立，下面考虑1m k =+时的情形．令1 1k i i i x x λ+==∑， 其中,0,1,2,,1i i x S i k λ∈≥=+L ，且1 1 1k i i λ+==∑．不妨设11k λ+≠（不然1k x x S +=∈， 结论成立），记11 1k i i i k y x λλ=+=-∑ ，有111(1)k k k x y x λλ+++=-+，

北航最优化方法大作业参考

北航最优化方法大作业参考

1 流量工程问题 1.1 问题重述 定义一个有向网络G=(N,E)，其中N是节点集，E是弧集。令A是网络G的点弧关联矩阵，即N×E阶矩阵，且第l列与弧里(I,j)对应，仅第i行元素为1，第j行元素为-1，其余元素为0。再令b m=(b m1,…,b mN)T，f m=(f m1,…,f mE)T，则可将等式约束表示成： Af m=b m 本算例为一经典TE算例。算例网络有7个节点和13条弧，每条弧的容量是5个单位。此外有四个需求量均为4个单位的源一目的对，具体的源节点、目的节点信息如图所示。这里为了简单，省区了未用到的弧。此外，弧上的数字表示弧的编号。此时，c=((5,5…,5)1 )T， ×13 根据上述四个约束条件，分别求得四个情况下的最优决策变量x=((x12,x13,…,x75)1× )。 13 图 1 网络拓扑和流量需求

1.2 7节点算例求解 1.2.1 算例1（b1=[4;-4;0;0;0;0;0]T） 转化为线性规划问题： Minimize c T x1 Subject to Ax1=b1 x1>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x1*=[4 0 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x1=20 1.2.2 算例2（b2=[4;0;-4;0;0;0;0]T） Minimize c T x2 Subject to Ax2=b2 X2>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x2*=[0 4 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x2=20 1.2.3 算例3（b3=[0;-4;4;0;0;0;0]T） Minimize c T x3 Subject to Ax3=b3 X3>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x3*=[4 0 0 0 4 0 0 0 0 0 0 0 0]T 对应的最优值c T x3=40

最优化方法及其应用 - 更多gbj149 相关pdf电子书下载

最优化方法及其应用 作者：郭科 出版社：高等教育出版社 类别：不限 出版日期：20070701 最优化方法及其应用 的图书简介 系统地介绍了最优化的理论和计算方法,由浅入深,突出方法的原则,对最优化技术的理论作丁适当深度的讨论,着重强调方法与应用的有机结合,包括最优化问题总论,线性规划及其对偶问题,常用无约束最优化方法,动态规划,现代优化算法简介,其中前八章为传统优化算法,最后一章还给出了部分优化问题的设计实例,也可供一般工科研究生以及数学建模竞赛参赛人员和工程技术人员参考, 最优化方法及其应用 的pdf电子书下载 最优化方法及其应用 的电子版预览 第一章 最优化问题总论1.1 最优化问题数学模型1.2 最优化问题的算法1.3 最优化算法分类1.4

组合优化问題简卉习题一第二章 最优化问题的数学基础2.1 二次型与正定矩阵2.2 方向导数与梯度2.3 Hesse矩阵及泰勒展式2.4 极小点的判定条件2.5 锥、凸集、凸锥2.6 凸函数2.7 约束问题的最优性条件习题二第三章 线性规划及其对偶问题3.1线性规划数学模型基本原理3.2 线性规划迭代算法3.3 对偶问题的基本原理3.4 线性规划问题的灵敏度习题三第四章 一维搜索法4.1 搜索区间及其确定方法4.2 对分法4.3 Newton切线法4.4 黄金分割法4.5 抛物线插值法习题四第五章 常用无约束最优化方法5.1 最速下降法5.2 Newton法5.3 修正Newton法5.4 共轭方向法5.5 共轭梯度法5.6 变尺度法5.7 坐标轮换法5.8 单纯形法习題五第六章 常用约束最优化方法6.1外点罚函数法6.2 內点罚函数法6.3 混合罚函数法6.4 约束坐标轮换法6.5 复合形法习题六第七章 动态规划7.1 动态规划基本原理7.2 动态规划迭代算法7.3 动态规划有关说明习题七第八章 多目标优化8.1 多目标最优化问题的基本原理8.2 评价函数法8.3 分层求解法8.4目标规划法习题八第九章 现代优化算法简介9.1 模拟退火算法9.2遗传算法9.3 禁忌搜索算法9.4 人工神经网络第十章 最优化问题程序设计方法10.1 最优化问题建模的一般步骤10.2 常用最优化方法的特点及选用标准10.3 最优化问题编程的一般过程10.4 优化问题设计实例参考文献 更多 最优化方法及其应用 相关pdf电子书下载

最优化方法试题

《最优化方法》试题 一、 填空题 1.设()f x 是凸集n S R ?上的一阶可微函数，则()f x 是S 上的凸函数的一阶充要条件是（ ），当n=2时，该充要条件的几何意义是（ ）； 2.设()f x 是凸集n R 上的二阶可微函数，则()f x 是n R 上的严格凸函数（ ）（填‘当’或‘当且仅当’）对任意n x R ∈，2()f x ?是 （ ）矩阵； 3.已知规划问题22211212121212min 23..255,0z x x x x x x s t x x x x x x ?=+---?--≥-??--≥-≥?，则在点55(,)66T x =处的可行方向集为（ ），下降方向集为（ ）。 二、选择题 1.给定问题222121212min (2)..00f x x s t x x x x ?=-+??-+≤??-≤?? ，则下列各点属于K-T 点的是（ ） A) (0,0)T B) (1,1)T C) 1(,22 T D) 11(,)22T 2.下列函数中属于严格凸函数的是（ ） A) 211212()2105f x x x x x x =+-+ B) 23122()(0)f x x x x =-< C) 2 222112313()226f x x x x x x x x =+++- D) 123()346f x x x x =+- 三、求下列问题

()22121212121211min 51022 ..2330420 ,0 f x x x x x s t x x x x x x =+---≤+≤≥ 取初始点()0,5T 。 四、考虑约束优化问题 ()221212min 4..3413f x x x s t x x =++≥ 用两种惩罚函数法求解。 五．用牛顿法求解二次函数 222123123123()()()()f x x x x x x x x x x =-++-++++- 的极小值。初始点011,1,22T x ??= ???。 六、证明题 1.对无约束凸规划问题1min ()2 T T f x x Qx c x =+，设从点n x R ∈出发，沿方向n d R ∈ 作最优一维搜索，得到步长t 和新的点y x td =+ ，试证当1T d Q d = 时， 22[() ()]t f x f y =-。 2.设12*** *3(,,)0T x x x x =>是非线性规划问题()112344423min 23..10f x x x x s t x x x =++++=的最优解，试证*x 也 是非线性规划问题 144423* 123min ..23x x x s t x x x f ++++=的最优解，其中****12323f x x x =++。

最优化方法的Matlab实现(公式(完整版))

第九章最优化方法的MatIab实现 在生活和工作中，人们对于同一个问题往往会提出多个解决方案，并通过各方面的论证从中提取最佳方案。最优化方法就是专门研究如何从多个方案中科学合理地提取出最佳方案的科学。由于优化问题无所不在，目前最优化方法的应用和研究已经深入到了生产和科研的各个领域，如土木工程、机械工程、化学工程、运输调度、生产控制、经济规划、经济管理等，并取得了显著的经济效益和社会效益。 用最优化方法解决最优化问题的技术称为最优化技术，它包含两个方面的内容： 1）建立数学模型即用数学语言来描述最优化问题。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。 2）数学求解数学模型建好以后，选择合理的最优化方法进行求解。 最优化方法的发展很快，现在已经包含有多个分支，如线性规划、整数规划、非线性规划、动态规划、多目标规划等。 9.1 概述 利用Matlab的优化工具箱，可以求解线性规划、非线性规划和多目标规划问题。 具体而言，包括线性、非线性最小化，最大最小化，二次规划，半无限问题，线性、非线性方程（组）的求解，线性、非线性的最小二乘问题。另外，该工具箱还提供了线性、非线性最小化，方程求解，曲线拟合，二次规划等问题中大型课题的求解方法，为优化方法在工程中的实际应用提供了更方便快捷的途径。 9.1.1优化工具箱中的函数 优化工具箱中的函数包括下面几类： 1 ?最小化函数

2.方程求解函数 3.最小—乘（曲线拟合）函数

4?实用函数 5 ?大型方法的演示函数 6.中型方法的演示函数 9.1.3参数设置 利用OPtimSet函数，可以创建和编辑参数结构；利用OPtimget函数，可以获得o PtiOns优化参数。 ? OPtimget 函数 功能：获得OPtiOns优化参数。 语法：

最优化原理大作业

基于粒子群算法的神经网络在电液伺服系统中的应用 摘要：由于人工神经网络在解决具有非线性、不确定性等系统的控制问题上具有极大的潜力，因而在控制领域正引起人们的极大关注，并且已在一些响应较慢的过程控制中获得成功应用。由于电液伺服系统属 于非线性系统，因此本文利用神经网络控制电液伺服系统，并利用粒子群优化算法训练该神经网络的 权值。通过对神经网络的优化实现对电液伺服系统的控制。 关键词：神经网络电液伺服系统粒子群算法优化 近年来，由于神经网络具有大规模并行性、冗余性、容错性、本质的非线性及自组织自学习自适应能力，所以已成功地应用于众多领域。但在具有复杂非线性特性的机电设备的实时控制方面，虽然也有一些神经网络技术的应用研究，但距实用仍有一段距离。电液伺服系统就属于这类设备[1]。 神经网路在用于实时控制时，主要是利用了网络所具有的其输人——输出间的非线性映射能力。它实际上是通过学习来逼近控制对象的动、静态特性。也就是构造实际系统的神经网络模型[2]。本文利用神经网络控制一电液伺服系统，并利用粒子群优化算法训练该神经网络的权值，将结果与BP神经网络控制该系统的结果进行比较。从而得在电液伺服系统中引入神经网络是可行的。 1、粒子群算法 粒子群优化算法(Particle Swarm optimization, PSO)是一种进化计算技术, 由Eberhart博士和kennedy博士发明, 源于对鸟群捕食的行为研究, 粒子群优化算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解[3]。算法最初受到飞鸟和鱼类集群活动的规律性启发，利用群体智能建立了一个简化模型，用组织社会行为代替了进化算法的自然选择机制，通过种群间个体协作来实现对问题最优解的搜索[4]。 在找到这两个最优值时, 粒子根据如下的公式来更新自己的速度和新的位置 v[]=v[]+c1*rand()*(pbest[]-present[]) + c2*rand()*(gbest[]-present[]) present[]=persent[]+v[] 式中ω为惯性权重，ω取大值可使算法具有较强的全局搜索能力，ω取小值则算法倾向于局部搜索。一般的做法是将ω初始取0.9并使其随迭代次数的增加而线性递减至0.4，这样就可以先侧重于全局搜索，使搜索空间快速收敛于某一区域，然后采用局部精细搜索以获得高精度的解；c1、c2为两个学习因子，一般取为2；randl和rand2为两个均匀分布在(0，l)之间的随机数；i=1，2，?，m；k=1，2，?，d。另外，粒子在每一维的速度Vi都被一个最大速度Vmax所限制。如果当前粒子的加速度导致它在某一维的速度 超过该维上的最大速度Vmax，则该维的速度被限制为最大速度[5]。 粒子群算法流程如下： (一)初始化粒子群。设群体规模为m，在允许的范围内随机设置粒子的初始位置和速 度。 (二)评价每个粒子的适应值。 (三)调整每一个粒子的位置和速度。 (四)如果达到最大迭代次数genmax或误差达到最初设定数值终止迭代，否则返回(2)。 2、神经网络 神经网络一般由输入层、隐含层、输出层组成。对于输入信号，先向前传播到隐节点，经过节点作用函数后，再把隐节点的输出信息传播到输出节点，最后输出结果。节点的作用函数通常选取S 型函数f（x）=1/（1+e-x）。神经网络算法的学习过程分为正

天津大学《最优化方法》复习题(含答案)

天津大学《最优化方法》复习题（含答案） 第一章 概述(包括凸规划) 一、 判断与填空题 1 )].([arg )(arg min max x f x f n n R x R x -=∈∈ √ 2 {}{} .:)(m in :)(m ax n n R D x x f R D x x f ?∈-=?∈ ? 3 设.:R R D f n →? 若n R x ∈*，对于一切n R x ∈恒有)()(x f x f ≤*，则称*x 为最优化问题)(min x f D x ∈的全局最优解. ? 4 设.:R R D f n →? 若D x ∈*，存在*x 的某邻域)(*x N ε，使得对一切)(*∈x N x ε恒有)()(x f x f <*，则称*x 为最优化问题)(min x f D x ∈的 严格局部最优解. ? 5 给定一个最优化问题，那么它的最优值是一个定值. √ 6 非空集合n R D ?为凸集当且仅当D 中任意两点连线段上任一点属于D . √ 7 非空集合n R D ?为凸集当且仅当D 中任意有限个点的凸组合仍

属于D . √ 8 任意两个凸集的并集为凸集. ? 9 函数R R D f n →?:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √ 10 设R R D f n →?:为凸集D 上的可微凸函数，D x ∈*. 则对D x ∈?，有).()()()(***-?≤-x x x f x f x f T ? 11 若)(x c 是凹函数，则}0)( {≥∈=x c R x D n 是凸集。 √ 12 设{}k x 为由求解)(min x f D x ∈的算法A 产生的迭代序列，假设算法 A 为下降算法，则对{} ,2,1,0∈?k ，恒有 )()(1k k x f x f ≤+ . 13 算法迭代时的终止准则（写出三种）：_____________________________________。 14 凸规划的全体极小点组成的集合是凸集。 √ 15 函数R R D f n →?:在点k x 沿着迭代方向}0{\n k R d ∈进行精确一维线搜索的步长k α，则其搜索公式

第九章 最优化方法

第九章 最优化方法 本章主要介绍线性规划、0-1规划、非线性规划等问题的MATLAB 求解。 9.1 线性规划（Linear Programming ，简写为LP ）问题 线性规划问题就是求多变量线性函数在线性约束条件下的最优值。满足约束条件的解称为可行解，所有可行解构成的集合称为可行域，满足目标式的可行解称为最优解。 MATLAB 解决的线性规划问题的标准形式为： min z f x ￠ =? .. A x b s t Aeq x beq lb x ub ì祝??? ?í??＃??? 其中,,,,,f x b beq lb ub 为列向量，,A Aeq 为矩阵。 其它形式的线性规划问题都可经过适当变换化为此标准形式。 在MATLAB 中求解线性规划问题函数为linprog ，其使用格式为： [x, fval, exitflag, output, lambda] = linprog(f, A, b, Aeq, beq, lb, ub) 输入部分：其中各符号对应线性规划问题标准形式中的向量和矩阵，如果约束条件中有缺少，则其相应位置用空矩阵[]代替。 输出部分：其中x 为最优解，用列向量表示；fval 为最优值；exitflag 为退出标志，若exitflag=1表示函数有最优解，若exitflag=0表示超过设定的迭代最大次数，若exitflag=-2，表示约束区域不可行，若exitflag=-3，表示问题无解，若exitflag=-4，表示执行迭代算法时遇到NaN ，若exitflag=-5，表示原问题和对偶问题均不可行，若exitflag=-7，表示搜索方向太小，不能继续前进；output 表明算法和迭代情况；lambda 表示存储情况。 例1 用linprog 函数求下面的线性规划问题

最优化方法大作业答案

1.用薄钢板制造一体积5m 3，长度不小于4m ，无上盖的货箱，要求钢板耗量最小。确定货箱的长x 1、宽x 2和高x 3。试列出问题的数学模型。 解：min 32312122x x x x x x z ++= s.t 5321=x x x 41≥x 0,,321≥x x x 2.将下面的线性规划问题表示为标准型并用单纯形法求解 max f=x 1+2x 2+x 3 s ．t ．2x 1+x 2-x 3≤2 -2x 1+x 2-5x 3≥-6 4x 1+x 2+x 3≤6 x i ≥0 i=1，2，3 解：先化标准形： Min 321x x x z -+= 224321=+-+x x x x 6525321=++-x x x x 646321=+++x x x x 列成表格：

1 2 1 610011460105122001112----- 可见此表已具备1°，2°，3°三个特点，可采用单纯形法。首先从底行中选元素-1，由2/2,6/2,6/4最小者决定选第一行第一列的元素2，标以记号，迭代一次得 1 2 1 2102310401162010021212 11-------- 再从底行中选元素-2/3，和第二列正元素1/2，迭代一次得 1 2 12 32 30 210231040116201002121211- ------ 再从底行中选元素-3，和第二列正元素2，迭代一次得 4 2 3 3 410120280114042001112--- 再迭代一次得 10 2 30 2 10 6 221023 1010213000421021013-- 选取最优解：

(完整版)机械优化设计试卷期末考试及答案

第一、填空题 1.组成优化设计的数学模型的三要素是 设计变量 、目标函数 和 约束条件 。 2.可靠性定量要求的制定，即对定量描述产品可靠性的 参数的选择 及其 指标的确定 。 3.多数产品的故障率随时间的变化规律，都要经过浴盆曲线的 早期故障阶段 、 偶然故障阶段 和 耗损故障阶段 。 4.各种产品的可靠度函数曲线随时间的增加都呈 下降趋势 。 5.建立优化设计数学模型的基本原则是在准确反映 工程实际问题 的基础上力求简洁 。 6.系统的可靠性模型主要包括 串联模型 、 并联模型 、 混联模型 、 储备模型 、 复杂系统模型 等可靠性模型。 7. 函数f(x 1,x 2)=2x 12 +3x 22-4x 1x 2+7在X 0=[2 3]T 点处的梯度为 ，Hession 矩阵为 。 （2.）函数()22121212,45f x x x x x x =+-+在024X ??=????点处的梯度为120-?? ????，海赛矩阵为2442-???? -?? 8.传统机械设计是 确定设计 ；机械可靠性设计则为 概率设计 。 9.串联系统的可靠度将因其组成单元数的增加而 降低 ，且其值要比可靠 度 最低 的那个单元的可靠度还低。 10.与电子产品相比，机械产品的失效主要是 耗损型失效 。 11. 机械可靠性设计 揭示了概率设计的本质。 12. 二元函数在某点处取得极值的充分条件是()00f X ?=必要条件是该点处的海赛矩阵正定。 13.对数正态分布常用于零件的 寿命疲劳强度 等情况。 14.加工尺寸、各种误差、材料的强度、磨损寿命都近似服从 正态分布 。 15.数学规划法的迭代公式是 1k k k k X X d α+=+ ，其核心是 建立搜索方向， 模型求解 两方面的内容。 17.无约束优化问题的关键是 确定搜索方向 。 18.多目标优化问题只有当求得的解是 非劣解 时才有意义，而绝对最优解存在的可能性很小。 19.可靠性设计中的设计变量应具有统计特征，因而认为设计手册中给出的数据

最优化计算方法课后习题答案----高等教育出版社。施光燕

习题二包括题目：P36页5（1）（4） 5（4）

习题三 包括题目：P61页1(1)(2); 3; 5; 6; 14；15(1) 1(1)(2)的解如下 3题的解如下

5,6题 14题解如下 14. 设22121212()(6)(233)f x x x x x x x =+++---, 求点在(4,6)T -处的牛顿方向。 解：已知 (1) (4,6)T x =-，由题意得 121212212121212(6)2(233)(3)()2(6)2(233)(3)x x x x x x x f x x x x x x x x +++-----?? ?= ?+++-----?? ∴ (1)1344()56g f x -?? =?= ??? 21212122211212122(3)22(3)(3)2(233)()22(3)(3)2(233)22(3)x x x x x x x f x x x x x x x x +--+--------? ??= ? +--------+--?? ∴ (1)2(1)1656()()564G x f x --?? =?= ?-?? (1)1 1/8007/400()7/4001/200G x --?? = ?--?? ∴ (1)(1)11141/100()574/100d G x g -?? =-= ?-?? 15（1）解如下 15. 用DFP 方法求下列问题的极小点 （1）22 121212min 353x x x x x x ++++ 解：取 (0) (1,1)T x =，0H I =时，DFP 法的第一步与最速下降法相同 2112352()156x x f x x x ++???= ?++??， (0)(1,1)T x =，(0) 10()12f x ???= ??? (1)0.07800.2936x -??= ?-??， (1) 1.3760() 1.1516f x ???= ?-?? 以下作第二次迭代 (1)(0) 1 1.07801.2936x x δ-??=-= ?-??， (1)(0) 18.6240()()13.1516f x f x γ-??=?-?= ?-?? 0110 111011101 T T T T H H H H H γγδδδγγγ=+-

《最优化方法》期末试题

作用： ①仿真的过程也是实验的过程，而且还是系统地收集和积累信息的过程。尤其是对一些复杂的随机问题，应用仿真技术是提供所需信息的唯一令人满意的方法。 ②仿真技术有可能对一些难以建立物理模型或数学模型的对象系统，通过仿真模型来顺利地解决预测、分析和评价等系统问题。 ③通过系统仿真，可以把一个复杂的系统化降阶成若干子系统以便于分析，并能指出各子系统之间的各种逻辑关系。 ④通过系统仿真，还能启发新的策略或新思想的产生，或能暴露出在系统中隐藏着的实质性问题。同时，当有新的要素增加到系统中时，仿真可以预先指出系统状态中可能会出现的瓶颈现象或其它的问题。 2.简述两个Wardrop 均衡原理及其适用范围。 答： Wardrop提出的第一原理定义是：在道路的利用者都确切知道网络的交通状态并试图选择最短径路时，网络将会达到平衡状态。在考虑拥挤对行驶时间影响的网络中，当网络达到平衡状态时，每个 OD 对的各条被使用的径路具有相等而且最小的行驶时间；没有被使用的径路的行驶时间大于或等于最小行 驶时间。 Wardrop提出的第二原理是：系统平衡条件下，拥挤的路网上交通流应该按照平均或总的出行成本 最小为依据来分配。 第一原理对应的行为原则是网络出行者各自寻求最小的个人出行成本，而第二原理对应的行为原则是网络的总出行成本最小。 3.系统协调的特点。 答： （1）各子系统之间既涉及合作行为，又涉及到竞争行为。 （2）各子系统之间相互作用构成一个反馈控制系统，通过信息作为“中介”而构成整体 （3）整体系统往往具有多个决策人，构成竞争决策模式。 （4）系统可能存在第三方介入进行协调的可能。 6．对已经建立了概念模型的系统处理方式及其特点、适用范围。答：对系统概念模型有三种解决方式。 1.建立解析模型方式 对简单系统问题，如物流系统库存、城市公交离线调度方案的确定、交通量不大的城市交叉口交通控制等问题，可以运用专业知识建立系统的量化模型（如解析数学模型），然后采用优化方法确定系统解决方案，以满足决策者决策的需要，有关该方面的内容见第四、五章。 在三种方式中，解析模型是最科学的，但仅限于简单交通运输系统问题，或仅是在实际工程中一定的情况下（仅以一定的概率）符合。所以在教科书上很多漂亮的解析模型，无法应用于工程实际中。 2.建立模拟仿真模型方式 对一般复杂系统，如城市轨道交通调度系统、机场调度系统、城市整个交通控制系统等问题，可以对系统概念模型中各个部件等采用变量予以量化表示，并通过系统辨识的方式建立这些变量之间关系的动力学方程组，采用一定的编程语言、仿真技术使其转化为系统仿真模型，通过模拟仿真寻找较满意的优化方案，包括离线和在线均可以，有关该方面的内容见第七章。 模拟仿真模型比解析模型更能反映系统的实际，所以在交通运输系统中被更高层次的所使用，包括

最优化方法大作业答案

武工院你们懂的 1.用薄钢板制造一体积5m 3，长度不小于4m ，无上盖的货箱，要求钢板耗量最小。确定货箱的长x 1、宽x 2和高x 3。试列出问题的数学模型。 解：min 32312122x x x x x x z ++= s.t 5321=x x x 41≥x 0,,321≥x x x 2.将下面的线性规划问题表示为标准型并用单纯形法求解 max f=x 1+2x 2+x 3 s ．t ．2x 1+x 2-x 3≤2 -2x 1+x 2-5x 3≥-6 4x 1+x 2+x 3≤6 x i ≥0 i=1，2，3 解：先化标准形： Min 321x x x z -+= 224321=+-+x x x x 6525321=++-x x x x 646321=+++x x x x

列成表格： 00001216 100114 60105122001112----- 可见此表已具备1°，2°，3°三个特点，可采用单纯形法。首先从底行中选元素-1，由2/2,6/2,6/4最小者决定选第一行第一列的元素2，标以记号，迭代一次得 0000 1 2 121023 10 40116201002 1 21 211-------- 再从底行中选元素-2/3，和第二列正元素1/2，迭代一次得 1 002 1232 30210231 040116201002121211-- ----- 再从底行中选元素-3，和第二列正元素2，迭代一次得 4002 3 03410120280114042001112--- 再迭代一次得

10 23021 062 21023 1010 213 000421 2 10 13- - 选取最优解： 01=x 42=x 23=x 3. 试用DFP 变尺度法求解下列无约束优化问题。 min f （X ）=4（x 1-5）2+（x 2-6）2 取初始点X=（8，9）T ，梯度精度ε=0.01。 解：取I H =0,初始点()T X 9,8= 2221)6()5(4)(-+-=x x x f ??????--=?122408)(21x x x f ???? ??=?624)() 0(x f T x f d )6,24()()0()0(--=-?= )0(0)0()1(d x x α+= T )69,248(00αα--= ])669()5248(4min[)(min 2020)0(0)0(--+--?=+αααd x f )6()63(2)24()2458(8) (00)0(0)0(=-?-+-?--=+ααααd d x df 13077.013017 0≈= α ???? ??=???? ??--?+???? ??=21538.886153.462413077.098)1(x

《最优化方法》复习题(含答案)

x zD 天津大学《最优化方法》复习题(含答案) 第一章 概述(包括凸规划) 判断与填空题 arg max f(x)二 arg min 以儿 “ max(x): x D 二 R n 』=-min(x): x D 二 R n ； 设f : D 5 R n > R.若x ： R n ，对于一切R n 恒有f(x”)^f(x)，则称x”为 设f : D 5 R n >R.若x ” ? D ,存在x ”的某邻域N ；(x”)，使得对一切 x ?N .(x)恒有f(x”)：：： f (x)，则称x”为最优化问题 min f (x)的严格局部最 优解? 给定一个最优化问题，那么它的最优值是一个定值 ? V 非空集合D R n 为凸集当且仅当 D 中任意两点连线段上任一点属于 D . V 非空集合D R n 为凸集当且仅当D 中任意有限个点的凸组合仍属于 D . V 任意两个凸集的并集为凸集? 函数f:D R n >R 为凸集D 上的凸函数当且仅当 -f 为D 上的凹函数? V 设f : D R n >R 为凸集D 上的可微凸函数，X ：D ?则对-D ,有 f (x) - f(x )乞 f (x )T (X —X )? 若c(x)是凹函数，则 D={x^R n C(x)启0}是凸集。 V f(x)的算法A 产生的迭代序列，假设算法 A 为下降算法, 则对-k ? 5,1, 2,…匚恒有 ________________ f(x k1)乞 f(x k ) ______________ ? 算法迭代时的终止准则(写出三种) ： ___________________________________________________ 凸规划的全体极小点组成的集合是凸集。 V 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

第九章 试验设计与方差分析

第九章试验设计与方差分析 在科学试验中我们常常要研究参加试验的各种条件的改变对试验结果的影响，从中选出最好的试验组合，以达到最佳试验结果。试验结果也称试验指标，试验中变化的条件称为因素( facter ) , 因素在试验中所取的每一个状态称为因素的一个水平（level ）。如在考察不同温度对收率有无显著影响的药物生产中，药物收率为试验指标，温度为一个因素，生产中所取的不同温度为水平。“方差分析”是研究各个因素各个水平对试验结果影响大小的一种常用方法。本章将简要介绍试验设计的原则和方法，着重讨论单因素试验，双因素试验，多因素正交试验及其方差分析。 第一节试验设计 一、试验设计原则 任何试验都包含三个基本要素：因素，对象和效应。例如在研究用有机溶液提取中药有效成分的试验中，溶液的种类和浓度，催化剂，温度等可视为因素；所选择的中药样品为对象；而浸出率则可视为效应。根据试验的目的选择参加试验的因素，并从质量或数量上对每个因素确定不同的水平，因素及其水平在试验全过程中应保持不变。试验中选择多一些因素和水平可以提高试验效率，但并不是愈多愈好；试验对象需要具有同质性，如以小白鼠为对象做某种药理试验，小白鼠的年龄，体重及其某些生理条件必须大体相同。效应即试验指标，有数量和非数量的两种，指标要求必须是客观的和精确的。为了准确地考查因素的不同水平所产生的效应，在试验设计中应注意以下基本原则。 1．对照（control ）为了更好地说明试验因素的影响和作用，常在试验中设立对照组。对照的目的在于抵消或减少非试验因素的干扰，以避免对试验效应作出错误的判断。 2．均衡( balance) 通过对照抵消非试验因素干扰的关键是试验设计的均衡性，即在试验中应使试验组和对照组在非试验因素上大致相同。如在考察某种药物疗效的试验中，试验组和对照组的对象（病人）的性别，年龄，病情等应尽量一致，而观察指标，方法，仪器，人员等应相同，以保持试验对象和试验条件的均衡。 3．随机化（randomization ）利用均衡原则还不能使所有非试验因素达到真正均衡。随机化是均衡的一种补救方法，使各对象或试验条件享有均等的机会。以利于非试验因素对结果的影响。随机化的常用工具是随机数字表。 4．重复( replication ) 重复是指在相同条件下对每个个体独立进行多次的试验，它可以避免由于试验次数太少而导致非试验因素的个别极端影响而产

最优化方法大作业

发动机空燃比控制器 引言：我主要从事自动化相关研究。这里介绍我曾经接触过的发动机空燃比控制器设计中的优化问题。 发动机空燃比控制器设计中的最优化问题 AFR =a f m m && (1) 空燃比由方程（1）定义，在发动机运行过程中如果控制AFR 稳定在14.7可以获 得最好的动力性能和排放性能。如果假设进入气缸的空气流量a m &可以由相关单元检测得到，则可以通过控制进入气缸的燃油流量f m &来实现空燃比的精确控制。由于实际发动机的燃油喷嘴并不是直接对气缸喷燃油，而是通过进气歧管喷燃油，这么做会在进 气歧管壁上液化形成油膜，因此不仅是喷嘴喷出的未液化部分燃油会进入气缸，油膜 蒸发部分燃油也会进入气缸，如方程（2）。这样如何更好的喷射燃油成为了一个问题。 1110101122211ττττ?? ?? -?? ??????????=+????????-????????????-???? ? ??? ?? ????????? ?f f f v X x x u x x X x y =x && (2) 其中12、,==ff fv x m x m &&=f y m &,=fi u m &这里面，表示油膜蒸发量ff m &、fv m &表示为液化部分燃油、fi m &表示喷嘴喷射的燃油，在τf 、τv 、X 都已知的情况下，由现代控制理论知识，根据系统的增广状态空间模型方程（3） 0000001 1 011011114.70ττττ????-?? ??????????=-+-??????????????? ??????????????? ?? ??=?????? f f v v a X X u +q q m y q x x x &&& (3) 其中()0 14.7?t a q = y -m &。由极点配置方法，只要设计控制器方程（4），就可以 使得y 无差的跟踪阶跃输入，那么y 也能较好的跟踪AFR *a m /&。 12-- u =K q K x (4) 这里面的12、K K 确定，可由主导极点概念降维成两个参数12C ,C ，虽然都是最终稳态无差，但是目标是使得瞬态过程中y 和阶跃输入y r 的差异尽可能的小。所以原问

修订过的最优化方法复习题

《最优化方法》复习题 第一章 引论 一、 判断与填空题 1 )].([arg )(arg m in m ax x f x f n n R x R x -=∈∈ √ 2 {}{}.:)(min :)(max n n R D x x f R D x x f ?∈-=?∈ ? 3 设.:R R D f n →? 若n R x ∈*，对于一切n R x ∈恒有)()(x f x f ≤*，则称*x 为最优化问题 )(min x f D x ∈的全局最优解. ? 4 设.:R R D f n →? 若D x ∈*，存在*x 的某邻域)(*x N ε，使得对一切)(*∈x N x ε恒有)()(x f x f <*，则称*x 为最优化问题)(min x f D x ∈的严格局部最 优解. ? 5 给定一个最优化问题，那么它的最优值是一个定值. √ 6 非空集合n R D ?为凸集当且仅当D 中任意两点连线段上任一点属于D . √ 7 非空集合n R D ?为凸集当且仅当D 中任意有限个点的凸组合仍属于D . √ 8 任意两个凸集的并集为凸集. ? 9 函数R R D f n →?:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √ 10 设R R D f n →?:为凸集D 上的可微凸函数，D x ∈*. 则对D x ∈?，有).()()()(***-?≤-x x x f x f x f T ? 11 若)(x c 是凹函数，则}0)( {≥∈=x c R x D n 是凸集。 √ 12 设{}k x 为由求解)(min x f D x ∈的算法A 产生的迭代序列，假设算法A 为单调下降算 法，则对{} ,2,1,0∈?k ，恒有 )()(1k k x f x f ≤+ .

最优化方法(试题+答案)

一、 填空题 1 ． 若 ()()??? ? ??+???? ?????? ??=212121 312112)(x x x x x x x f ，则 =?)(x f ，=?)(2x f . ２．设f 连续可微且0)(≠?x f ，若向量d 满足 ，则它是f 在x 处的一个下降方向。 3.向量T ) 3,2,1(关于3阶单位方阵的所有线性无关的共轭向量 有 ． 4. 设R R f n →:二次可微，则f 在x 处的牛顿方向为 . 5.举出一个具有二次终止性的无约束二次规划算 法: . 6.以下约束优化问题： )(01)(..)(min 212121 ≥-==+-==x x x g x x x h t s x x f 的K-K-T 条件为： . 7．以下约束优化问题： 1 ..)(min 212 2 21=++=x x t s x x x f 的外点罚函数为(取罚参数为μ) . 二、证明题（７分+8分) 1.设1,2,1,:m i R R g n i =→和m m i R R h n i ,1,:1+=→都是线性函数,证明下 面的约束问题: } ,,1{, 0)(},1{, 0)(..)(min 1112 m m E j x h m I i x g t s x x f j i n k k +=∈==∈≥=∑= 是凸规划问题。

2.设R R f →2 :连续可微，n i R a ∈,R h i ∈,m i ,2,1=,考察如下的约束条件问题: } ,1{,0} 2,1{,0..) (min 11m m E i b x a m I i b x a t s x f i T i i T i +=∈=-=∈≥- 设d 是问题 1 ||||,0,0..)(min ≤∈=∈≥?d E i d a I i d a t s d x f T i T i T 的解，求证：d 是f 在x 处的一个可行方向。 三、计算题（每小题１2分) １.取初始点T x )1,1() 0(=.采用精确线性搜索的最速下降法求解下面的无约束优化问题 (迭代２步）: 2 2212)(m in x x x f += 2.采用精确搜索的BFGS 算法求解下面的无约束问题： 212 2212 1)(min x x x x x f -+= 3.用有效集法求解下面的二次规划问题: . 0,001..42)(min 21212 12 221≥≥≥+----+=x x x x t s x x x x x f 4．用可行方向算法(Zoutend ｉj ｋ算法或Ｆrank Wol ｆｅ算法）求解下面的问题（初值设为)0,0() 0(=x ,计算到)2(x 即可）： . 0,033..22 1)(min 212112 22121≥≥≤+-+-= x x x x t s x x x x x x f

大连理工优化方法大作业MATLAB编程

function [x,dk,k]=fjqx(x,s) flag=0; a=0; b=0; k=0; d=1; while(flag==0) [p,q]=getpq(x,d,s); if (p<0) b=d; d=(d+a)/2; end if(p>=0)&&(q>=0) dk=d; x=x+d*s; flag=1; end k=k+1;

if(p>=0)&&(q<0) a=d; d=min{2*d,(d+b)/2}; end end %定义求函数值的函数fun，当输入为x0=（x1，x2）时，输出为f function f=fun(x) f=(x(2)-x(1)^2)^2+(1-x(1))^2; function gf=gfun(x) gf=[-4*x(1)*(x(2)-x(1)^2)+2*(x(1)-1),2*(x(2)-x(1)^2)]; function [p,q]=getpq(x,d,s) p=fun(x)-fun(x+d*s)+0.20*d*gfun(x)*s'; q=gfun(x+d*s)*s'-0.60*gfun(x)*s'; 结果： x=[0,1]; s=[-1,1]; [x,dk,k]=fjqx(x,s) x =-0.0000 1.0000 dk =1.1102e-016 k =54

function f= fun( X ) %所求问题目标函数 f=X(1)^2-2*X(1)*X(2)+2*X(2)^2+X(3)^2+ X(4)^2- X(2)*X(3)+2*X(1)+3*X(2)-X(3); end function g= gfun( X ) %所求问题目标函数梯度 g=[2*X(1)-2*X(2)+2,-2*X(1)+4*X(2)-X(3)+3,2*X(3)-X(2)-1,2*X(4)]; end function [ x,val,k ] = frcg( fun,gfun,x0 ) %功能：用FR共轭梯度法求无约束问题最小值 %输入：x0是初始点，fun和gfun分别是目标函数和梯度 %输出：x、val分别是最优点和最优值，k是迭代次数 maxk=5000;%最大迭代次数 rho=0.5;sigma=0.4;