可变维核心矩阵LU分解方法.pdfVIP

第16卷第6期 中国管理科学 V01．16，No．6 1 Science Dec．， 2008 2008年 2月 ChineseJoumalofManagement 文章编号：1003—207(2008)06—0067--08 可变维核心矩阵LU分解方法 姜波，蓝伯雄 (清华大学经济管理学院，北京 100084) 擒要：在线性规划问题的发展过程中，基的分解技术一直是求解线性规划问题算法实现的一个重要问题。在传 统的线性规划算法中，基逆的乘积形式(PFI)方法和LU分解方法很好的解决了基逆的稀疏性、累计误差等问题。 随着线性规划动态分解和核心矩阵的出现，矩阵的动态分解成为了一个新的研究课题。本文主要研究和分析单纯 形算法中的核心矩阵的动态分解和存储方法。将经典的LU分解方法应用于核心矩阵的动态分解和存储中，保持 了核心距阵的数值稳定性和稀疏性。同时，本文提出置换消元方法可以大大减少LU更新的时间。 关键词：线性规划；核心矩阵；动态分解；LU分解 中图分类号：0221．1 文献标识码：A l 引言 一种新的LU分解方法[1引，克服了Bartels方法中 大规模线性规划问题的约束矩阵往往是非常稀 疏的，因此有关稀疏矩阵的处理技术在大规模线性 和LU方法进行了比较[1“，验证了LU方法的优越 规划求解技术的研究中得到广泛应用。大规模稀疏 矩阵的处理技术的研究主要集中在以下两个领域。 的重要性，提出了具有更好数值稳定性的基逆更新 1．稀疏矩阵的存储和处理问题，已经有很多人 进行了系统的研究[1t2]。 该方法进行了后续的改进。 2．基逆的获得与维护，如基逆的分解与更新方 在一些具有特殊结构的线性规划问题出现以 法。 后，人们开始研究线性规划问题的结构分解(Fac- torization)算法。该类算法将线性规划的约束进行 为了更好的应用改进单纯形算法(Revised Method)，1 分解，而且在迭代过程中具有统一的单纯形表结构。 Simplex 954年Dantzig第一次提出了用 初等矩阵的乘积表示基逆的分解方法PFI(Product FormofInverse)[引。该方法既可以保持基的稀疏 性，又可以减小了运算过程中的累计误差。接着，一 结构分解算法，并应用于广义上界线性规划问题。 些学者[4_6]对PFI方法进行了一定的改进。 在文章中，他们提出了一个由结构变量组成的基的 子矩阵，称之为核(Kernel)，利用这个核可以构造出 1957年，Markowitz[7]提出的逆的消元形式 新的单纯形表结构。后续的研究进展可以参见文献 (EFI)发展了基的LU分解方法。Dantzig(1963)[81 [zo，21]。 用该方法解决了具有阶梯构造的特殊线性规划问 胡亦工，蓝伯雄(1999)[22]指出在线性规划的基 题。Bennett和Green(1966)[钉将该方法应用于一 中存在一个维数更小的核心矩阵，并提出了基于核 般的稀疏矩阵上。Dantzig(1968)[I引，Brayton 心矩阵的单纯形算法，从而大大减少线性规划求解 (1969)…3等人指出LU