二次规划的理论与算法(Ⅵ)

六、带约束的凸二次规划的解法(续)我们现要证明 Lemke 方法的有限步终止性,也就是要证:当 C 是正定矩阵时,经过有限次迭代运算后得到规划(6.20)的最优解.这里我们总假定原规划(6.15)有可行解,再由于C 是正定的,所以规划(6.15)有最优解,所以规划(6.20)也有最优解.如果在迭代中得到的点 y~l 是可行集的内点,即 y~l>0,它满足 q+Qy~l=0,则 y~l 为最优解,此时 J~i=φ.如果 y~l是可行集的边界点,即 J~l≠φ,利用等式(6.21),g(y)在点 y 的梯度可表为λ=sum form i-1 tow_ib_i、其     

非线性规划在线性约束退化时可行方向算法类的统一处理及其收敛性

对最优化算法的统一研究已有不少方法,诸如无约束最优化问题中的Broyden和Huang算法类,带线性约束的非线性规划问题中越民义等人引进的可行方向算法类。对非线性规划的退化问题理论上也有一些处理方法。例如,在迭代的每一次开始都求解一个线性     

线性规划的一种Benders型分解算法

大型线性规划问题因其含有许多约束条件和许多变量,即使利用计算机来解也是很困难的。但是,有不少这样的问题,虽其约束条件的系数矩阵很大,却有特殊的结构,我们可以把它分解成若干个规模较小的线性规划来解,由此得到原规划的最优解。Dantzig—Wolfe分解方法是早期提出的一种方法,在很多线性规划的书籍中都有介绍。Benders分解方法是为解混合整数规划而提出的,后被改造用来解某种结构的线性规划。本文给出一种简化的     

并行的菲波那契序贯搜索法的最优性的一个简单证明

非线性规划问题的多数算法都归结为解一系列的一维最优化问题,所以一维最优化的算法是非线性规划的许多方法的基础。序贯搜索法是一维最优化的一类重要的寻优方法。这类方法序贯地选取若干批观察点(即观察这些点对应的函数值),每批观察点的位置将依赖于以前的观察点上的函数值以及一定的搜索策略。由于这类方法不涉及函数的导数,故比较简单。在讨论序贯搜索法的效果之前,需要介绍几个定义。     

二次规划的理论与算法(续)

三、二次规划的对偶理论对偶理论是数学规划的重要基础理论之一。线性规划的对偶理论在五十年代初期即已被提出(对偶理论的思想则最初是由Von Neumann在1947年提出的),它对线性规划的算法研究起了推动作用。线性规划的对偶定理指出:     

非线性规划方法简介(Ⅲ)

五、带线性约束的最优化问题这一章我们讨论如下的非线性规划问题 minf(x) Ax=b, (5.1) Dx≥d,其中A和D分别是m_1×n和m_2×n矩阵,且A是行满秩的矩阵。符号A_1和D_1分别表示矩阵A的第t行和矩阵D的第i行。如果(?)是问题(5.1)的一个可行解,定义标号集(?),我们称(?)中的标号对应的约束条件为点(?)的“起作用约束”(或主动约束),同时每一等式约束条件A_ix=b_i也是点(?)的起作用约束。起作用约束这一概     

非线性规划方法简介(Ⅱ)

四、n维空间R~n中无约束最优化问题这一章我们考虑无约束的非线性规划问题■ (4.1)当f(x)为R~n中一般的实函数时,这个问题的解决是很困难的。目前的方法只能近似地得到某个点x~*,它是f(x)的平稳点(满足最优解的必要条件的点),但不能保证x~*一定是整体极小解。对于实际问题,我们往往满足于求出一个近似的局部极小解。§4.1 直接搜索方法这类方法大多是一些直觉方法,它们只需要在若干被选择的点上比较f(x)的函数值,而不需要计算导数。一般而言,当f(x)是比较光滑的函数时,这类方法比下降方法和梯度方法     

非线性规划方法简介

这个简介是为了读者了解非线性规划的方法的概貌而编写的,它扼要地介绍了无约束的和有约束的非线性规划问题的一些重要的方法。有兴趣的读者可由此而进一步去阅读非线性规划的专门书籍。非线性规划是运筹学中的一门重要科学。它的一些问题早在十九世纪就已经被研究过,但是它在理论方面和应用方面的蓬勃发展却是近三十年来的事。现在,它在生产、管理、工程、经济、军事……等不同领域中越来越起重要的作用;同时在理论方面,不论是对于最优解的定性研究,或是对最优解的有效的数值解法,以及对于有关的其他问题,都已有丰富的研究成果。尤其应提及的是,我国的非线性规划工作者在算法方面也有不少的研究成果。由于篇幅所限,我们在介绍每一种方法时没有附带计算的实例,也没有介绍国内的一些成果,     

“全国最优化理论与应用学术交流会”简讯

由中国数学会运筹学会主办的全国最优化理论与应用学术交流会于1982年10月16～21日在武汉市华中工学院召开。这是最优化方面的第一次全国性学术会议。会议的主要内容是交流国内最优化各分支     

运筹学在应急物流中的一些应用

本文首先简述了突发事件和应急物流的概况,总结出应急物流具有突发性、紧迫性、弱经济性、信息不确定和物资需求量大等特点.其次介绍了国外关于应急物流中应急物资选址问题和配置问题的研究中运筹学模型的应用.早期文献中多针对常规突发事件进行研究,选址模型主要为覆盖模型、p-center模型、p-median模型3类.目前关于大规模...