Simplex algorithm
From Academic Kids

In mathematical optimization theory, the simplex algorithm of George Dantzig is the fundamental technique for numerical solution of the linear programming problem. There is also an unrelated method for solving nonlinear programming problems (called the "downhill simplex method" or "NelderMead simplex method", to avoid confusion).
In both cases, the method uses the concept of a simplex, which is a polytope of N + 1 vertices in N dimensions; a line segment on a line, a triangle on a plane, a tetrahedron in threedimensional space and so forth.
The simplex algorithm in linear programming
Simplex_description.png
A linear programming problem consists of a collection of linear inequalities on a number of real variables and a fixed linear functional which is to be maximized (or minimized). Some further details are given in the linear programming article.
In geometric terms we are considering a closed convex polytope P, defined by intersecting a number of halfspaces in ndimensional Euclidean space, which lie to one side of a hyperplane. The objective is to maximise a linear functional L; if we consider the hyperplanes H(c) defined by L(x) = c as c increases, these form a parallel family. If the problem is wellposed, we want to find the largest value of c such that H(c) intersects P (if there is no such largest value of c, this isn't a reasonable question for optimization as it stands). In this case we can show that the optimum value of c is attained, on the boundary of P. Methods for finding this optimum point on P have a choice of improving a possible point by moving through the interior of P (socalled interior point methods), or starting and remaining on the boundary.
The simplex algorithm falls into the latter class of method. The idea is to move along the facets of P in search of the optimum, from point to point. Note that the optimum cannot occur at a midpoint, for example in the middle of an edge lying as a line segment on the boundary of P, unless the whole relevant 'face' is parallel to H. Therefore it is possible to look solely at moves skirting the edge of a simplex, ignoring the interior. The algorithm specifies how this is to be done.
We start at some vertex of the polytope, and at every iteration we choose an adjacent vertex such that the value of the objective function does not decrease. If no such vertex exists, we have found a solution to the problem. But usually, such an adjacent vertex is nonunique, and a pivot rule must be specified to determine which vertex to pick. Various pivot rules exist.
In 1972, Klee and Minty gave an example of a linear programming problem in which the polytope P is a distortion of an ndimensional cube. They showed that the simplex method as formulated by Dantzig visits all 2^{n} vertices before arriving at the optimal vertex. This shows that the worstcase complexity of the algorithm is exponential time. Similar examples have been found for other pivot rules. It is an open question if there is a pivot rule with polynomial time worstcase complexity.
Nevertheless, the simplex method is remarkably efficient in practice. Attempts to explain this employ the notion of average complexity or (recently) smoothed complexity.
Other algorithms for solving linear programming problems are described in the linear programming article.
The simplex algorithm in nonlinear programming
The simplex algorithm finds an optimum solution to a problem with N variables when the solution varies smoothly from one point in the Ndimensional solution space to the neighboring points. For example, a 2dimensional map showing the elevation of a piece of land or the depth of a pool of oil, or optimizing the outcome of an experiment where many conditions are varied over some known range. With an elevation map, simple inspection shows the answer to the question of the highest elevations; thus illustrating that the usefulness of the simplex method lies in cases where the value at various points is hard to come by, and an exhaustive search is infeasible.
A computer program to use the simplex method to automatically find an optimum typically (1) chooses N + 1 points, (2) finds the values (if unknown) at those points (the elevation, depth, speed, cost, execution time ... whatever is being optimized), (3) stop if we found a good enough value (by any of several criteria), else choose a new point CLOSER TO THE OTHER POINTS (typically by half) in place of the worst valued point (creating a new smaller simplex), (4) go to step (2).
Many variations exist depending on the actual nature of problem being solved. The most common, perhaps, is to use a constant size small simplex that climbs local gradients to local maximums. Visualize a small triangle on an elevation map flip flopping its way up a hill to a local peak.
External links
 An Introduction to Linear Programming and the Simplex Algorithm (http://www.isye.gatech.edu/~spyros/LP/LP.html) by Spyros Reveliotis of the Georgia Institute of Technology.
 Javabased interactive simplex tool (http://wwwfp.mcs.anl.gov/otc/Guide/CaseStudies/simplex/) hosted by Argonne National Laboratory.de:SimplexVerfahren