A Composite-Upper Bounding Method of Finding a Feasible Solution to a Linear Programming Problem
Loading...
Authors
Higgs, Robert Duane
Issue Date
1967
Type
Thesis
Language
en_US
Keywords
Alternative Title
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.
Description
Citation
Publisher
Creighton University
License
A non-exclusive distribution right is granted to Creighton University and to ProQuest following the publishing model selected above.