Browse Prior Art Database

THE REVISED SIMPLEX METHOD

IP.com Disclosure Number: IPCOM000128833D
Original Publication Date: 1956-Aug-06
Included in the Prior Art Database: 2005-Sep-19

Publishing Venue

Software Patent Institute

Related People

Orchard-Hays, William: AUTHOR [+3]

Abstract

A revision of the simplex method is presented which makes explicit use of columns of the restraint coefficients associated with a basic set of variables. The development is based on the single assumption of linearly independent restraint equations. An algebraic method of resolving degeneracy is given in conclusion.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE REVISED SIMPLEX METHOD

William Orchard-Hays P-911 August 6, 1956

The RAND Corporation 1700 MAIN ST. SANTA MONICA CALIFORNIA

SUMMARY

A revision of the simplex method is presented which makes explicit use of columns of the restraint coefficients associated with a basic set of variables. The development is based on the single assumption of linearly independent restraint equations. An algebraic method of resolving degeneracy is given in conclusion.

CONTENTS

SUMMARY.....ii

INTRODUCTION.....1
LINEAR EQUATIONS; NOTATION.....2
CENTRAL MATHEMATICAL PROBLEM OF LP.....6
LINEAR INDEPENDENCE.....7
ELEMENTARY ROW TRANSFORMATIONS.....8
THE BASIS IN THE SIMPLEX METHOD.....16
THE TRANSFORMATION OF THE COST ROW.....18
THE REVISED SIMPLEX METHOD.....19
DEGENERACY.....22

THE REVISED SIMPLEX METHOD

Wm. Orchard-Hays

INTRODUCTION

Although this course was designed for those interested in LP computations, it was felt that a considerable amount of theoretical background should be included. While this might be in the nature of a review for some people, I believe you will all agree that the material presented thus

Rand Corporation Page 1 Aug 06, 1956

Page 2 of 11

THE REVISED SIMPLEX METHOD

far has been very instructive and has provided us with a necessary solid and common foundation upon which to continue. In fact, a natural question now might be, that except for computational tricks, what is there to say further? Indeed we have enough mathematical theory at this point to carry out the computations required by a given LP model, at least with a little luck and provided it is not too large. There is, of course, a great deal that has not and can not be said in our limited time about model formulation. For example, linear approximations to convex functionals are interesting mathematically. The transportation problem, which will be discussed in the next two lectures, has at least one result of primary importance. But insofar as a general method of solution is concerned, the preceding theory is more or less complete except for the matter of degeneracy. Nevertheless, we have not yet begun, in reality, to speak about the practical computational difficulties that confront us nor how we propose to resolve them. These matters will be taken up in more detail during the second three days of the course. In preparation for this, the present lecture takes up a revision of the simplex method which is computationally desirable.

In later lectures, we will find it convenient to use a slightly different notation than was used in the last one. Also, in the transportation problem, you will find an array of quantities with double subscripts used in a different sense than in the general simplex method. Hence this seems like a good place to introduce the notation to be used later on. To those of you familiar with matrix theory, the viewpoint taken in some of what follows may seem narrow but the presentation is not i...