Browse Prior Art Database

# THE SIMPLEX METHOD

IP.com Disclosure Number: IPCOM000128832D
Original Publication Date: 1956-Jul-09
Included in the Prior Art Database: 2005-Sep-19
Document File: 9 page(s) / 102K

## Publishing Venue

Software Patent Institute

## Related People

Dantzig, G.B.: AUTHOR [+2]

## Abstract

The simplex method of solution of a linear program first transforms the original system to an equivalent system of m equations in canonical form by an elimination of m of the n unknowns. If the right choice of m variables is made, then by equating the remaining variables to zero, an optimal solution is obtained to the original problem. If not, the method produces an ";improved"; set of m variables and a corresponding canonical form. The procedure is iterated until an optimum solution is obtained.

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

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE SIMPLEX METHOD

G. B. Dantzig P-891 July 9, 1956

The RAND Corporation 1700 MAIN ST. SANTA MONICA CALIFORNIA

SUMMARY

The simplex method of solution of a linear program first transforms the original system to an equivalent system of m equations in canonical form by an elimination of m of the n unknowns. If the right choice of m variables is made, then by equating the remaining variables to zero, an optimal solution is obtained to the original problem. If not, the method produces an "improved" set of m variables and a corresponding canonical form. The procedure is iterated until an optimum solution is obtained.

CONTENTS

SUMMARY.....ii
Section

I. ALGEBRA OF THE SIMPLEX METHOD.....1
Introduction.....1
The Problem.....2
The Canonical Form.....3
The Initial Basic Feasible Solution and Test for Optimality.....5
Improving a Non-Optimal Basic Feasible Solution.....6
Iterative Procedure.....10
Degeneracy.....10
Appendix: Systems of Linear Equations.....12

Equivalent Systems.....12
Elementary Operations.....14
Equivalent Triangular and Canonical m x m Systems.....14
Reduction of m by n system to an equivalent canonical system.....16
II. THE SIMPLEX TABLEAU: AN EXAMPLE.....18
III. FINDING AN INITIAL BASIC FEASIBLE SOLUTION.....22

THE SIMPLEX METHOD [ title ]

Rand Corporation Page 1 Jul 09, 1956

Page 2 of 9

THE SIMPLEX METHOD

I. ALGEBRA OF THE SIMPLEX METHOD

Introduction
"Simplex" is a mathematical term meaning a k-dimensional "triangle"; i.e., it is the generalization of the word triangle for two dimensions or of a tetrahedron for three dimensions. The term "simplex method" is derived from one of several geometric interpretations of the technique in which this figure plays a role. In this lecture its mathematical characteristics will be developed. It will be shown that, except possibly for a member of a class of cases called "degenerate," the simplex algorithm will produce in a finite number of iterations a solution (if one exists) which minimizes a linear form in non-negative variables subject to a system of linear equations. The excepted class, which is important from the viewpoint of theory (rather than practice) will not be considered here. However the rule of random choice given for resolving the degenerate case can be shown to lead to an optimal solution in a finite number of iterations with probability one.

The chief feature of the method is that it calls for elimination of variables from the equations in a manner quite analagous to ordinary (Gaussian) elimination for solving a simultaneous system involving m equations in m unknowns. After an elimination, using some selected set of m variables, a solution is obtained by setting all remaining variables equal to zero. If this solution is feasible it can be used as a starting solution for the standard simplex algorithm. The next step is a test to determine whether it is a minimum solution. If not, a new variable is chosen to... 