Simplex method

From Glossary

Jump to: navigation, search

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
(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.)

Personal tools