The Simplex Method was developed by George Dantzing in 1947. It is without a doubt the most popular algorithm when it comes to solving a Linear Programming (LP) model, and it plays a major role in the introduction to Operations Research (OR).
Today we’re presenting a summary of 10 main concepts about the use and application of the Simplex Method for our users to be able to have a first approach to the method, while paying attention to some characteristic aspects:
Simplex Method (10 Things You need to know)
- History: In 1947 it was first published by George Dantzing, an American mathematician.
- Standard Form: The Simplex Method’s application requires the Linear Programming model to be on its standard form.
- Basic Feasible Solution (BFS): A basic feasible solution matches a vertices in domain of a Linear Programming model’s feasible solutions.
- Optimality Criterion: The Basic feasible solution is optimal if and only if the reduced costs of all the nonbasic variables are higher or equal to zero.
- Infinite Solutions: This case is seen when there are reduced costs equal to zero in one or more optimal nonbasic variables.
- Unbounded Problem: This case is seen when, while doing the calculus of the variable which leaves the base, all the elements ykj of the column j in the tableau are negative.
- Infeasible Problem: This is the case when the optimal value of the problem in Phase 1 (in a Two Phase Simplex Method) is nonzero.
- Rate of Convergence: If two or more nonbasic variables have negative reduced cost, the entrance to the base goes to the lowest reduced cost.
- Postoptimal Analysis: Once we achieve the optimal solution through the Simplex Method, we can analyze the impact in the results with the alteration of the parameters.
- Excel Solver: The Excel complement Solver allows us to use the Simplex Method as a solving method (Simplex LP)
This review is based on the experience we have teaching Operations Research and on the most frequent questions we receive daily from undergraduate students.
You can download the infographic as a PDF file here: Simplex Method
We encourage you to check and share this infographic on your social webs. Also, if you think there’s an important aspect missing in the previous list, you can use the commentary section at the bottom of this page to let us know. This is how we can keep updating the article with the main characteristics of the Simplex Method.