SIMPLEX METHOD OF LINEAR PROGRAMMING USING LU DECOMPOSITION

被引：117

作者：

BARTELS, RH

GOLUB, GH

机构：

[1] Stanford Univ., CA

来源：

COMMUNICATIONS OF THE ACM | 1969年 / 12卷 / 05期

关键词：

computational stability; linear programming; LU decomposition; round-off errors; simplex method;

D O I：

10.1145/362946.362974

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Standard computer implementations of dantzig's simplex method for linear programming are based upon forming the inverse of the basic matrix and updating the inverse after every step of the method. These implementations have bad round-off error properties. this paper gives the theoretical background for an implementation which is based upon the lu decomposition, computed with row interchanges, of the basic matrix. the implementation is slow, but has good round-off error behavior. The implementation appears as cacm algorithm 350. © 1969, ACM. All rights reserved.

引用

页码：266 / &