Introduction to Simplex

Optimization · Axiom Academy

LESSON Introduction to Simplex Understanding the geometric intuition behind the simplex method for linear programming 1. The Core Idea: Walking Along Edges Linear programming seeks to optimize a linear objective function subject to linear constraints. The feasible region forms a polytope (multi-dimensional polygon). The simplex method's key insight: the optimum always occurs at a vertex . Rather than checking all possible points, we walk along the edges of the polytope, moving from vertex to vertex. 2. Basic Feasible Solutions: Vertices in Algebra Each vertex of the polytope corresponds to a basic feasible solution (BFS) . Algebraically, a BFS is found by setting enough variables to zero to solve the constraint equations uniquely. Geometrically, this is where constraint boundaries intersect. The animation shows how the algebraic concept maps to geometric vertices. 3. Adjacent Vertices: Moving to Neighbors Two vertices are adjacent if they share an edge. Algebraically, this means their basic feasible solutions differ by exactly one basic variable (we "pivot" by swapping one variable in and one out). The simplex method moves from one BFS to an adjacent BFS by traversing an edge of the polytope. 4. Improving Direction: Always Move Upward At each vertex, we examine all adjacent vertices (neighboring edges). We choose the direction that increases the objective function most rapidly .

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