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.

Algorithm

• Choose an initial BF as shown above
• While nonoptimal solution:
• Determine direction of highest gradient
• : Choose the variable associated with the c coefficient of highest positive magnitude. This nonbasic variable, which we call the entering basic, will be increased to help maximize the problem.
• Determine maximum step length
• : Use the equation to determine which basic variable reaches zero first when the entering basic is increased. This variable, which we call the leaving basic then becomes nonbasic. This operation only involves a single division for each basic variable.
• Rewrite problem
• : Rewrite c, A and b to make the problem matrix diagonal for the existing and new basic variables. This involves some simple Gaussian elimination.
• Check for improvement
• : Repeat procedure until no further improvement is possible, meaning all the coefficients of c are negative. Procedure is also terminated if all coefficients are zero, and the algorithm have been walking in a circle and revisited a previous state.