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

Loading...
Thumbnail Image

Authors

Higgs, Robert Duane

Issue Date

1967

Type

Thesis

Language

en_US

Keywords

Research Projects

Organizational Units

Journal Issue

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.

Journal

Volume

Issue

PubMed ID

DOI

ISSN

EISSN