COMPACT BASIS TRIANGULARIZATION FOR THE SIMPLEX METHOD
Abstract
The inv rse of the basis in the simplex method serves no function except as a means for obtaining the representation of the vector entering the basis and for determining the new price vector. For this purpose one of the many forms of substitute inverses (such as the well known product form of the inverse) would do just as well, in fact, may have certain advantages in computation. There is interest in developing, for a sparce matrix, a substitute inverse with as few nonzero entries as possible. Two ways to do this are: (1) the basis could be reduced to triangular form by successively selecting for pivot position t at row and t at column whose product of nonzero entries (excluding the pivot) is minimum, and (2) for bases whose nonzeros appear in a band on staircase about the diagonal, proper selection of pivots could result in a compact substitute inverse with no more nonzeros than the original basis.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 03, 1962
- Accession Number
- AD0286897
Entities
People
- George Bernard Dantzig
Organizations
- University of California, Berkeley