Generalized upper bounding techniques

摘要

A variant of the revised 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 in them. 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×M and is a further reduction of the size found in an earlier version.