《最优化基础理论与方法》由会员分享，可在线阅读，更多相关《最优化基础理论与方法（13页珍藏版）》请在金锄头文库上搜索。
1、目录1最优化的概念与分类22. 最优化问题的求解方法32.1 线性规划求解32.1.1线性规划模型32.1.2线性规划求解方法32.1.3 线性规划算法未来研究方向32.2 非线性规划求解42.2.1一维搜索42.2.2无约束法42.2.3约束法42.2.4凸规划52.2.5二次规划52.2.6非线性规划算法未来研究方向52.3组合规划求解方法52.3.1 整数规划52.3.2 网络流规划72.4多目标规划求解方法72.4.1 基于一个单目标问题的方法72.4.2 基于多个单目标问题的方法82.4.3多目标规划未来的研究方向82.5动态规划算法82.5.1 逆推解法82.5.2 顺推解法92.
2、5.3 动态规划算法的优点及研究方向92.6 全局优化算法92.6.1 外逼近与割平面算法92.6.2 凹性割方法92.6.3 分支定界法92.6.4 全局优化的研究方向92.7随机规划92.7.1 期望值算法102.7.2 机会约束算法102.7.3 相关机会规划算法102.7.4 智能优化102.8 最优化软件介绍113 最优化算法在电力系统中的应用及发展趋势123.1 电力系统的安全经济调度问题123.1.1电力系统的安全经济调度问题的介绍123.1.2电力系统的安全经济调度问题优化算法的发展趋势121最优化的概念与分类最优化是应用数学的一个重要分支，最优化可定义为一种数学方法，用它可以
3、对各种生产活动进行规划，在可供利用资源(资源泛指矿藏、水能、人力、设备、原料、运输条件、生态环境、资金、时间、空问等等)的限制条件下，使生产活动得到最大的效益或用最少的资源完成指定的生产活动。最优化问题的数学表现形式为： 式中，称为目标函数，若具体问题是求，则令，于是最大值问题就转化为最小值问题。称为等式约束条件，称为不等式约束条件，如果约束条件中有，则可令，于是原来的“”就变为了“”。满足约束条件的一组称之为一组可行解。满足目标函数的可行解称为最优解，即我们需要寻求的答案。许多现实和理论问题都可以建模成这样的一般性框架，最优化问题种类繁多，分类的方法也有许多。（1）按照变量的性质分类：1）确
4、定性规划：当最优化模型中所有变量都是确定性变量时，称为确定性规划。2）随机性规划：当模型中包含随机变量时，称为随机性规划。3）连续性规划：当模型中所有变量均是连续变量时，称为连续性规划。根据连续最优化模型中的函数的光滑与否，又分为光滑最优化和非光滑最优化，如果模型中所有的函数都连续可微，称为光滑最优化问题，否则为非光滑最优化问题。4）离散性规划：当模型中的变量取离散值时，称为离散性规划，又称组合优化。特别的，若问题的部分或所有的变量局限于整数值时，称这一类问题为整数规划问题。（2）按照有无约束条件分类：1）无约束规划：当最优化模型中不存在约束条件时，称为无约束规划。2）有约束规划：当模型中存在
5、约束条件时，称为有约束规划。（3）按目标函数的个数分类：1）单目标规划:只存在一个目标函数时，称这一类问题为单目标规划。2）多目标规划：当存在多个目标函数时，称为多目标规划。（4）按约束条件和目标函数是否是线性函数分类：1）线性规划：当目标函数是线性函数，而且约束条件是由线性等式函数和线性不等式函数来确定的，称这一类问题为线性规划。2）非线性规划：非线性规划研究的是目标函数或约束函数中含有非线性函数的问题。特别的，当目标函数是二次函数，而且约束条件是由线性等式函数和线性不等式函数来确定的时，称为二次规划。（4）根据是否和时间有关分类：1）动态规划：动态规划是解决多阶段决策过程的最优化的一种数学
6、算法，主要用于以时间或地域划分阶段的动态过程的最优化。2）静态规划：与时间无关的最优化问题。不同类型的最优化问题具有各自的求解方法，下面内容着重说明最优化问题的求解方法及未来研究方向，并介绍最优化方法在电力系统规划中的应用及发展。2. 最优化问题的求解方法最优化方法是近几十年形成的，它主要运用数学方法研究各种优化问题的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和
7、生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。2.1 线性规划求解2.1.1线性规划模型线性规划模型的一般表达方式如下所示： （2.1）其中，（）为待定的决策变量，己知的系数组成的矩阵A称为约束矩阵。A的列向量记为（）。A的行向量记为()。目标函数记为，向量称为价值向量，称为价值系数；向量称为右端向量。条件称为非负约束；表示变量可取正值、负值、或零值，称这样的变量为自由变量。2.1.2线性规划求解方法2.1.2.1 单纯形法求解线性规划问题的基本方法是单纯形法，是研究得最为
8、透彻的一个方向，且至今仍是最好的应用最广泛的算法之一，已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法的一般解题步骤可归纳如下：把线性规
9、划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基可行解。若基本可行解不存在，即约束条件有矛盾，则问题无解。若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。若迭代过程中发现问题的目标函数值无界，则终止迭代。2.1.2.2 内点算法除了单纯形算法之外，现在经常使用的线性规划求解方法还包括内点算法，内点算法中的代表即Karmarkar算法。Karmarkar算法运用了求解非线性规划问题的思想来解决线性规划
10、问题。这种算法是在把一般线性规划问题转化为Karmarkar所特有的标准型，再利用一种求解这种标准型的算法最终求出最优解。2.1.3 线性规划算法未来研究方向内点法是最新的设计，实际应用上它也可以与单纯形法相抗衡，不少商业化软件已经上市，前景甚佳。目前线性规划的内点法也趋于成熟，这方面的研究者们目前大都致力于以线性规划作为特例的锥规划，以及如何利用线性规划松弛求解整数规划等方面的研究。2.2 非线性规划求解非线性规划问题的求解一般要比线性规划困难很多，而且目前尚没有适合于各类非线性问题的一般算法，每种算法都有自己的特定的使用范围。有些情况下，为方便计算，也会把非线性规划问题近似为线性规划问题进
11、行求解。2.2.1一维搜索一维搜索是求解单变量非线性规划问题的方法。这类方法不仅有实用价值，而且大量多维最优化方法都依赖于一系列的一维最优化。常用的一维最优化方法有黄金分割法、切线法和插值法。2.2.1.1黄金分割法黄金分割法又称0.618法。它适用于单峰函数。其基本思想是：在初始寻查区间中设计一列点，通过逐次比较其函数值，逐步缩小寻查区间，以得出近似最优值点。2.2.1.2切线法又称牛顿法。它也是针对单峰函数的。其基本思想是：在一个猜测点附近将目标函数的导函数线性化，用此线性函数的零点作为新的猜测点，逐步迭代去逼近最优点。2.2.1.3插值法又称多项式逼近法。其基本思想是用多项式（通常用二次
12、或三次多项式）去拟合目标函数。此外，还有斐波那契法、割线法、有理插值法、分批搜索法等。2.2.2无约束法无约束法是求解无约束条件的非线性规划问题的方法，指寻求 n元实函数f在整个n维向量空间Rn上的最优值点的方法。这类方法的意义在于：虽然实用规划问题大多是有约束的，但许多约束最优化方法可将有约束问题转化为若干无约束问题来求解。无约束最优化方法大多是逐次一维搜索的迭代算法。这类迭代算法可分为两类。一类需要用目标函数的导函数，称为解析法。另一类不涉及导数，只用到函数值，称为直接法。这些迭代算法的基本思想是：在一个近似点处选定一个有利搜索方向，沿这个方向进行一维寻查，得出新的近似点。然后对新点施行同
13、样手续，如此反复迭代，直到满足预定的精度要求为止。根据搜索方向的取法不同，可以有各种算法。属于解析型的算法有：梯度法：又称最速下降法。这是早期的解析法，收敛速度较慢。牛顿法：收敛速度快，但不稳定，计算也较困难。共轭梯度法：收敛较快，效果较好。变尺度法：这是一类效率较高的方法。其中达维登-弗莱彻-鲍威尔变尺度法，简称 DFP法，是最常用的方法。属于直接型的算法有交替方向法（又称坐标轮换法）、模式搜索法、旋转方向法、鲍威尔共轭方向法和单纯形加速法等。2.2.3约束法指前述一般非线性规划模型的求解方法。常用的约束最优化方法有4种。拉格朗日乘子法：它是将原问题转化为求拉格朗日函数的驻点。制约函数法：又
14、称系列无约束最小化方法，简称SUMT法。它又分两类，一类叫惩罚函数法，或称外点法；另一类叫障碍函数法，或称内点法。它们都是将原问题转化为一系列无约束问题来求解。可行方向法：这是一类通过逐次选取可行下降方向去逼近最优点的迭代算法。如佐坦迪克法、弗兰克沃尔夫法、投影梯度法和简约梯度法都属于此类算法。近似型算法：这类算法包括序贯线性规划法和序贯二次规划法。前者将原问题化为一系列线性规划问题求解，后者将原问题化为一系列二次规划问题求解。2.2.4凸规划这是一类特殊的非线性规划。在前述非线性规划数学模型中，若f是凸函数，诸都是凹函数，诸都是一次函数，则称之为凸规划。所谓f是凸函数，是指f有如下性质：它的
15、定义域是凸集，且对于定义域中任意两点x和y及任一小于1的正数，下式都成立： （2.1）将上述不等式中的不等号反向即得凹函数的定义。所谓凸集，是指具有如下性质的集合：连结集合中任意两点的直线段上的点全部属于该集合。对于一般的非线性规划问题，局部解不一定是整体解。但凸规划的局部解必为整体解，而且凸规划的可行集和最优解集都是凸集。2.2.5二次规划二次规划是一类特殊的非线性规划。它的目标函数是二次函数，约束条件是线性的。求解二次规划的方法很多。常用方法是拉格朗日法，较简便易行的是沃尔夫法。它是依据库恩塔克条件，在线性规划单纯形法的基础上加以修正而成的。此外还有莱姆基法、毕尔法、凯勒法等。2.2.6非线性规划算法未来研究方向就算法的发展来看，早期的方法以最速下降法和共轭梯度法为主，目前，序贯二次规划法是一类被用于广泛求解一般非线性规划的有效算法，同时也还有许多研究者在为改善这类算法作努力，其中包括序列线性规划算法以及内点算法等。非线性规化算法通常使用线搜索策略选取步长，或通过求解信赖域子问题而得到新的迭代点。这两个方面的研究非常基本，但仍有改善的空间。对于大规模问题，如何设计子空间算法；以及如何有效求解一般非线性规划的全局最优，和
