Simplex Method

The algorithm navigates the feasible polytope by moving along its edges. Starting from an initial basic feasible solution, it pivots to an adjacent vertex that improves the objective function. This geometric interpretation of algebraic pivoting ensures that the search remains within the feasible region defined by linear constraints. Each iteration swaps one basic variable for a non-basic variable, effectively moving to a new corner point.

The algorithm is often executed using a tableau, a structured matrix representation of the linear program. The tableau organizes:

• Objective function coefficients
• Constraint coefficients
• Right-hand side values
• Basic and non-basic variable indicators The pivot operation updates this tableau using elementary row operations, maintaining the system's equivalence while progressing toward optimality.

A solution is optimal when all reduced costs in the objective row are non-negative for a minimization problem (or non-positive for maximization). The reduced cost of a non-basic variable represents the rate of change in the objective function if that variable were to enter the basis. When no improving direction exists, the Karush-Kuhn-Tucker (KKT) conditions are satisfied, and the algorithm terminates.

Degeneracy occurs when a basic variable has a value of zero, causing the pivot to stall without improving the objective. In rare cases, this can lead to cycling, where the algorithm revisits the same sequence of bases indefinitely. Bland's Rule—selecting the entering and leaving variables with the smallest index—is a theoretical safeguard that prevents cycling, though practical implementations often use perturbation or lexicographic ordering.

While the simplex method exhibits exponential worst-case complexity—as demonstrated by the Klee-Minty cube—it performs remarkably well in practice. The average-case complexity is polynomial, typically requiring between 2m and 3m iterations for m constraints. This practical efficiency, combined with its ability to perform sensitivity analysis on optimal solutions, explains its enduring dominance over interior-point methods for many real-world applications.

To find an initial basic feasible solution, auxiliary techniques are required:

• Two-Phase Method: Phase I introduces artificial variables to minimize their sum, finding a feasible starting point. Phase II then optimizes the original objective.
• Big-M Method: Adds artificial variables with a large penalty coefficient M to the objective, forcing them out of the optimal basis. Both methods handle constraints that lack an obvious initial slack variable.

The mathematical foundation upon which the Simplex Method operates. LP seeks to maximize or minimize a linear objective function subject to a set of linear equality and inequality constraints. The Simplex Method is the standard algorithm for solving LP problems, exploiting the fact that if an optimal solution exists, it lies at a vertex of the feasible polytope.

Every LP problem (the primal) has a corresponding dual problem. The dual variables, or shadow prices, represent the marginal value of relaxing a constraint by one unit. The Simplex Method simultaneously solves both, and the Strong Duality Theorem guarantees that at optimality, the primal and dual objective values are equal. This provides deep economic interpretation of resource scarcity.

A fundamental concept in the Simplex Method's mechanics. At each iteration, the algorithm partitions variables into basic (non-zero) and non-basic (set to zero) sets. The current solution corresponds to a vertex of the polytope. The method pivots by swapping one basic and one non-basic variable, moving to an adjacent vertex with an improved objective value.