可变维核心矩阵lu分解方法

《可变维核心矩阵lu分解方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第16卷第6期中国管理科学V01．16，No．62008年12月ChineseJoumalofManagementScienceDec．，2008文章编号：1003—207(2008)06—0067--08可变维核心矩阵LU分解方法姜波，蓝伯雄(清华大学经济管理学院，北京100084)擒要：在线性规划问题的发展过程中，基的分解技术一直是求解线性规划问题算法实现的一个重要问题。在传统的线性规划算法中，基逆的乘积形式(PFI)方法和LU分解方法很好的解决了基逆的稀疏性、累计误差等问题。随着线性规划动态分解和核心矩阵的出现，矩阵的动态分解成为了一个新的研究课题。本文主要研究和分析

2、单纯形算法中的核心矩阵的动态分解和存储方法。将经典的LU分解方法应用于核心矩阵的动态分解和存储中，保持了核心距阵的数值稳定性和稀疏性。同时，本文提出置换消元方法可以大大减少LU更新的时间。关键词：线性规划；核心矩阵；动态分解；LU分解中图分类号：0221．1文献标识码：Al引言大规模线性规划问题的约束矩阵往往是非常稀疏的，因此有关稀疏矩阵的处理技术在大规模线性规划求解技术的研究中得到广泛应用。大规模稀疏矩阵的处理技术的研究主要集中在以下两个领域。1．稀疏矩阵的存储和处理问题，已经有很多人进行了系统的研究[1t2]。2．基逆的获得与维护，如基逆的分解与更新方法。为了更好的应用改进单纯

3、形算法(RevisedSimplexMethod)，1954年Dantzig第一次提出了用初等矩阵的乘积表示基逆的分解方法PFI(ProductFormofInverse)[引。该方法既可以保持基的稀疏性，又可以减小了运算过程中的累计误差。接着，一些学者[4_6]对PFI方法进行了一定的改进。1957年，Markowitz[7]提出的逆的消元形式(EFI)发展了基的LU分解方法。Dantzig(1963)[81用该方法解决了具有阶梯构造的特殊线性规划问题。Bennett和Green(1966)[钉将该方法应用于一般的稀疏矩阵上。Dantzig(1968)[I引，Brayton(19

4、69)⋯3等人指出LU分解方法在计算速度、精度以及保持稀疏性方面都要优于PFI方法。Bartels(1969)[12]将LU分解方法应用于线性规划的求解，收稿日期：2008—01—29：修订日期：2008—10—15作者简介：姜波(1980一)，男(满族)，清华大学经济管理学院博士研究生．研究方向：大规模线性规划算法．并取得很好的数值稳定性。Forrest(1972)提出了一种新的LU分解方法[1引，克服了Bartels方法中的缺点，但数值稳定性稍差。Tomlin(1972)对PFI和LU方法进行了比较[1“，验证了LU方法的优越性。Bartels和Golub[12“5]首先认识到

5、数值稳定性的重要性，提出了具有更好数值稳定性的基逆更新方法。Reid(1975)[16]，Saunders(1976)[17]分别对该方法进行了后续的改进。在一些具有特殊结构的线性规划问题出现以后，人们开始研究线性规划问题的结构分解(Fac-torization)算法。该类算法将线性规划的约束进行分解，而且在迭代过程中具有统一的单纯形表结构。Gerald，Michael(1994)[18]对此进行了详细的讨论。Graves，Mcbride(1976)[19]第一次提出线性规划的结构分解算法，并应用于广义上界线性规划问题。在文章中，他们提出了一个由结构变量组成的基的子矩阵，称之为核(

6、Kernel)，利用这个核可以构造出新的单纯形表结构。后续的研究进展可以参见文献[zo，21]。胡亦工，蓝伯雄(1999)[22]指出在线性规划的基中存在一个维数更小的核心矩阵，并提出了基于核心矩阵的单纯形算法，从而大大减少线性规划求解的计算工作量。具有挑战性的问题是，上述核心矩阵是一个维数可变的方阵，而以前研究的PFI和LU分解方法都是针对维数不变的基逆进行的。如何将基逆的分解技术应用于维数可变的核心矩阵是该算法实现中的关键问题。胡亦工(2002)[2朝简单描述了一个LU分解方法，但是没有通过数值试验万方数据·68·中国管理科学验证分解方法的有效性。本文在其工作的基础上进一步提出

7、一个更为有效的LU分解方法，论文首先讨论分析了核心矩阵变化的三种情况。提出行列置换消元方法，并将该方法应用到三角矩阵的更新运算中。新的LU分解方法能够充分利用稀疏矩阵的特点，需要的存储空间的运算量小，显著提高LU分解的计算效率。2线性规划问题中的核心矩阵胡亦工和蓝伯雄(1999)[221给出了一个更加严谨的核心矩阵定义，将线性规划的核心矩阵定义为原始问题的基矩阵与对偶问题的基矩阵的交集。如果不考虑在线性规划中加入的松弛变量和结构变量，我们称线性规划原问题中的变量为结构