GENERALIZED UPPER BOUNDING TECHNIQUES FOR LINEAR PROGRAMMING, 2
CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER
Pagination or Media Count:
A variant of the simplex method is given for solving linear programs with M L equations, L of which have the property that each variable has at most one nonzero coefficient. Special cases include transportation problems, programs with upper bounded variables, assignment and weighted distribution problems. The algorithm described uses a working basis of M rows for pivoting, pricing, and inversion which for large L can result in a substantial reduction of computation. This working basis is only M x M and is a further reduction of the size found in an earlier version, see AD0610950. Unfortunately, to achieve this reduction, row as well as column transformations must now be made.
- Operations Research