Simplex Method
The Simplex Method for Linear Programming · Also known as: simplex algorithm
The Simplex Method, developed by George Dantzig in 1947, is a foundational algorithm for solving linear programming problems. It systematically explores vertices of the feasible region to find the optimal solution where the objective function is maximized or minimized subject to linear constraints.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Apply the simplex method when solving linear programming problems with bounded feasible regions and a linear objective function. It is particularly effective for problems with hundreds or thousands of variables and constraints. Avoid using it if the problem is nonlinear or unbounded. Interior point methods may be preferred for very large-scale problems.
Strengths & limitations
- Guaranteed to find optimal solution in finite time for linear programs
- Efficient in practice with careful implementation and degeneracy handling
- Widely implemented and supported by mature optimization libraries
- Foundation for understanding more advanced optimization algorithms
- Exponential worst-case time complexity (though rare in practice)
- Can perform poorly on highly degenerate problems
- Less competitive than interior point methods on very large-scale problems
- Requires problems to be in standard form with explicit constraint handling
Frequently asked
Why is the simplex method called 'simplex'?
The term 'simplex' refers to the simplest form of a polytope in any given dimension. The algorithm works by moving along edges and vertices of the polytope defined by the constraints.
What is the difference between the simplex method and the interior point method?
The simplex method stays on the boundary of the feasible region at vertices, while interior point methods traverse through the interior. Interior point methods have better worst-case complexity but simplex is often faster in practice for medium-sized problems.
How do you handle infeasibility or unboundedness?
Use the two-phase simplex method: phase one solves an auxiliary problem to find a basic feasible solution or determine infeasibility; phase two applies the standard simplex method to the original problem.
What is degeneracy and why does it matter?
Degeneracy occurs when a basic feasible solution has more than one basis representation, which can cause cycling. Handle it using Bland's rule (choose variables by index order) or perturbation methods.
Sources
- Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press. DOI: 10.1515/9781400884179 ↗
- Vanderbei, R. J. (2014). Linear Programming: Foundations and Extensions (4th ed.). Springer. DOI: 10.1007/978-1-4614-7630-6 ↗
How to cite this page
ScholarGate. (2026, June 3). The Simplex Method for Linear Programming. ScholarGate. https://scholargate.app/en/operations-research/simplex-method
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Augmented Lagrangian MethodOperations Research↔ compare
- Benders DecompositionOperations Research↔ compare
- Column Generation (Dantzig-Wolfe)Operations Research↔ compare
- Dijkstra AlgorithmOperations Research↔ compare