An iterative algorithm for solving linear programming problems by moving along edges of the feasible polytope between basic feasible solutions until an optimal extreme point is reached.

Principle

Exploit the polyhedral structure of a linear program: vertices correspond to basic feasible solutions and optimality can be reached by local pivot operations that improve the objective.

Demonstration

Solve a diet problem by initializing a basic feasible solution, compute reduced costs, pivot to adjacent vertices with negative reduced cost, and stop when no improving pivot exists.

Misapplication

Applying the simplex method without checking degeneracy or cycling safeguards can lead to infinite loops or repeated tableaux when multiple bases share the same vertex.

Consequence

When applied correctly the method yields a vertex optimal solution and provides dual information (shadow prices) and certificates of infeasibility or unboundedness when appropriate.

Reversal

Instead of walking the boundary, interior algorithms traverse the feasible interior using barrier terms; these methods trade explicit vertex pivots for central-path progress.

Boundary

Applies only to linear programs (affine constraints and linear objective); nonlinear, integer, or nonconvex programs require modification or different algorithms.

Semantic Tension

Tension exists between 'combinatorial pivoting' (discrete basis changes) and 'continuous path following' (interior methods) as alternative routes to optimum in convex optimization.

Synthesis

The simplex method frames linear programming as a combinatorial navigation of a convex polytope: perform algebraic pivots that correspond to geometric moves between vertices until optimality conditions hold.