A Composite-Upper Bounding Method of Finding a Feasible Solution to a Linear Programming Problem

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.

Grantor dc:publisher

Creighton University

Year dc:date.issued

1967

Author dc:creator

• Higgs, Robert Duane

Advisor dc:contributor.advisor

• Mordeson, John N.

Statement dc:rights

• A non-exclusive distribution right is granted to Creighton University and to ProQuest following the publishing model selected above.

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/10504/111605

OAI identifier oai:identifier

oai:cdr.creighton.edu:10504/111605