Simplex algorithm

In mathematical optimization theory, the simplex algorithm of George Dantzig is the fundamental technique for numerical solution of the linear programming problem. A variation commonly used in nonlinear regression programs is the Nelder-Mead method or Simplex method or downhill simplex method due to Nelder & Mead (1965) and is a numerical method for solving many-dimensional problems, belonging to the more general class of search algorithms.

Problem input

The simplex algorithm requires the linear programming problem to be in augmented form. The problem can then be written as follows in matrix form:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Maximize Z in:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

egin{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

1 & -mathbf{c}^T & 0 \

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0 & mathbf{A} & mathbf{I}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

end{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

egin{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Z \ mathbf{x} \ mathbf{x}_s

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

end{bmatrix} =

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

egin{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0 \ mathbf{b}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

end{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: mathbf{x}, , mathbf{x}_s ge 0

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where x are the variables from the standard form, xs are the introduced slack variables from the augmentation process, c contains the optimization coefficients, A and b describe the system of constraint equations, and Z is the variable to be maximized.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The system is typically underdetermined, since the number of variables exceed the number of equations. The difference between the number of variables and the number of equations gives us the degrees of freedom associated with the problem. Any solution, optimal or not, will therefore include a number of variables of arbitrary value. The simplex algorithm uses zero as this arbitrary value, and the number of variables with value zero equals the degrees of freedom.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Values of nonzero value are called basic variables, and values of zero values are called nonbasic variables in the simplex algorithm.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This form simplifies finding the initial basic feasible solution (BF), since all variables from the standard form can be chosen to be nonbasic (zero), while all new variables introduced in the augmented form are basic (nonzero), since their value can be trivially calculated (mathbf{x}_{s,i} = mathbf{b}_{j} for them, since the augmented problem matrix is diagonal on its right half).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~