Simplex Algorithm

Optimization · Axiom Academy

A systematic procedure for solving linear programming problems by moving from vertex to vertex along the edges of the feasible region 1. Basic and Non-Basic Variables The simplex algorithm works with variables partitioned into two groups: A basic feasible solution corresponds to a vertex of the feasible region. The partition determines which vertex we're at. 2. Choosing the Entering Variable To improve the objective function, we select a non-basic variable to enter the basis. The entering variable is chosen using the most negative reduced cost rule: If all reduced costs are non-negative, the current solution is optimal. 3. Choosing the Leaving Variable Once an entering variable is chosen, we must determine which basic variable leaves the basis. This is done using the minimum ratio test : This ensures we maintain feasibility as we move to the adjacent vertex. The pivot operation performs row operations on the tableau to swap the entering and leaving variables: After pivoting, we have a new basic feasible solution at an adjacent vertex with an improved objective value. 5. Complete Algorithm Flowchart The simplex algorithm follows a systematic decision-making process:

This is the written version of the interactive lesson above. See the full Optimization course.