Abstract
The purpose of this paper is to describe a synthesis of Wolfe's composite simplex algorithm1 and Dantzig's upper bounding technique2 to give a variation of the simplex method of obtaining a feasible solution to a linear programming problem. | The term, composite, refers to a technique for handling negative values of variables in a linear programming problem. It is often desirable to let variables have (temporary) negative values rather than perhaps multiplying by -1 and adding artificial variables. This happens, for instance, when an optimal solution to a problem has been obtained and a small change in the original data is required. | An upper bounding algorithm is useful when a problem has constraints of the form x < b and is especially useful in computer applications. Most computer routines have restrictions on the number of constraints but the upper bounding algorithm makes it unnecessary to use explicit upper-bound equations. | With upper-bounding there exists the problem of a variable having a value greater than its upper bound as well as the problem of negative values of variables. Since these two problems are similar, it seems natural to extend the composite simplex algorithm to handle both situations and to combine the two techniques.