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

The LU Decomposition of Dynamic Kernel Matrix

作　　者：姜波[1] 蓝伯雄[1] 

机构地区：[1]清华大学经济管理学院,北京100084

出　　处：《中国管理科学》2008年第6期67-74,共8页Chinese Journal of Management Science

摘　　要：在线性规划问题的发展过程中,基的分解技术一直是求解线性规划问题算法实现的一个重要问题。在传统的线性规划算法中,基逆的乘积形式(PFI)方法和LU分解方法很好的解决了基逆的稀疏性、累计误差等问题。随着线性规划动态分解和核心矩阵的出现,矩阵的动态分解成为了一个新的研究课题。本文主要研究和分析单纯形算法中的核心矩阵的动态分解和存储方法,将经典的LU分解方法应用于核心矩阵的动态分解和存储中,保持了核心距阵的数值稳定性和稀疏性。同时,本文提出置换消元方法可以大大减少LU更新的时间。With the development of linear programming, the decomposition technology has been playing a significant role in the implementation of the algorithm. In the traditional simplex method, product form of inverse （PFI） and LU decomposition keep the sparsity of the A matrix and decrease the round--off error. Decomposition of dynamic matrix becomes a new research topic as soon as the LP dynamic factorization and kernel matrix came out. This paper discusses the decomposition and storage of kernel matrix hy applying the LU decomposition method, which makes a good result on matrix sparsity and round--off error. Additionally, the permutation elimination method proposed in this paper makes the LU update process more efficient.

关 键 词：线性规划 核心矩阵 动态分解 LU分解 

分 类 号：O221.1[理学—运筹学与控制论]