# Simplex method

### From Glossary

An algorithm invented to solve a linear program by progressing from one extreme point of the feasible polyhedron to an adjacent one. The method is an *algorithm strategy*, where some of the tactics include [1]ricing and [2]ivot selection.

The *elementary simplex method* is the name of Dantzig's original (1947) algorithm, with the following rules applied to the standard form:

- Let reduced cost of terminate if

- Select as one of greatest magnitude.
- In the associated column () of the tableau, compute the
*min ratio*: (If LP is unbounded). - Enter into the basic set, in exchange for , and update the tableau.

Among the variations are:

- select the incoming variable (j) differently;
- select the outgoing variable (i) differently, especially to avoid cycling;
- do not maintain a tableau (use a factored form of the basis).

The *revised simplex method* is the use of a particular factored form of the basis:
(after k iterations), where each is an elementary matrix. Then, the revised simplex method uses forward transformation to pivot and backward transformation to update the pricing vector. (For this distinction, the elementary simplex method is sometimes called the *tableau method*.)

The simplex method draws its name from imagining a normalization constraint, and thinking of the j-th column of to be selected by the weight in Then, at an iteration, an m-simplex is specified by the basic variables, and an adjacent simplex is chosen to improve the objective value. This view is in requirements space.

(For a different algorithm, used as a heuristic in NLP, see the Nelder-Mead simplex method.)