Simplex method

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: $LaTeX: \textstyle \min \left \{ cx: Ax=b, x \ge 0 \right \}.$

Let $LaTeX: d_j =$ reduced cost of $LaTeX: x_j \;$ terminate if $LaTeX: d_j \ge 0 \mbox{ for all } j.$
1. Select $LaTeX: d_j < 0$ as one of greatest magnitude.
2. In the associated column ($LaTeX: j$) of the tableau, compute the min ratio: $LaTeX: x_i / a(i, j): a(i, j) > 0.$ (If $LaTeX: a(., j) \le 0,$ LP is unbounded).
3. Enter $LaTeX: x_j$ into the basic set, in exchange for $LaTeX: x_i$, and update the tableau.

Among the variations are:

The revised simplex method is the use of a particular factored form of the basis: $LaTeX: \textstyle B = \begin{bmatrix} E_1 & E_2 & \dots & E_k \end{bmatrix}$ (after k iterations), where each $LaTeX: E_i$ 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, $LaTeX: \textstyle \sum_{j} x_j = 1,$ and thinking of the j-th column of $LaTeX: A$ to be selected by the weight $LaTeX: x_j$ in $LaTeX: S_w.$ 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.)