Two-Phase Simplex

Optimization · Axiom Academy

Solving linear programs when no obvious initial basic feasible solution exists 1. The Problem: No Obvious Initial BFS Consider a constraint like x₁ + x₂ ≥ 4 . After converting to standard form with a surplus variable, we get x₁ + x₂ - s₁ = 4 . The obvious BFS (setting x₁ = x₂ = 0) gives s₁ = -4, which is infeasible since all variables must be non-negative. 2. Phase 1: Minimize Sum of Artificial Variables We introduce an artificial variable a₁ to obtain an obvious BFS: x₁ + x₂ - s₁ + a₁ = 4 . Phase 1 solves an auxiliary problem: minimize the sum of all artificial variables while satisfying the constraints. 3. Phase 1 Optimality: Feasibility Check When Phase 1 terminates at an optimal solution, we check the objective value: If optimal value = 0: All artificial variables are zero, and we have found a feasible BFS for the original problem. If optimal value > 0: At least one artificial variable is positive at optimality, indicating the original problem is infeasible. 4. Phase 2: Drop Artificials, Solve Original Once we've verified feasibility (Phase 1 optimal = 0), we proceed to Phase 2: 1. Remove all artificial variable columns from the tableau 2. Replace the Phase 1 objective with the original objective function 3. Continue with standard simplex to find the optimal solution 5. Infeasibility Detection: Phase 1 Optimal > 0 If Phase 1 terminates with a positive objective value, the original problem has no feasible solution.

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