Simplex Algorithm

The simplex algorithm is an iterative method that moves between vertices of the feasible region, improving the objective at each step, until no adjacent vertex gives further improvement.

Standard Form

Before applying simplex, convert the LP to standard form.

• Objective
  Maximization (negate a minimization objective).
• Constraints
  All equalities, obtained by adding slack, surplus, or artificial variables.
• Variables
  All non-negative.

Basic Feasible Solution

For a standard form LP with $m$ constraints and $n$ variables, a basic solution sets $n - m$ variables to 0 (the non-basic variables) and solves the constraints for the remaining $m$ (the basic variables).

A basic feasible solution is a basic solution with all variables $\ge 0$.

Basic feasible solutions correspond to vertices of the feasible region. Each simplex iteration exchanges 1 basic variable for 1 non-basic variable, moving to an adjacent vertex.

Iteration Steps

Each simplex iteration operates on a tableau representing the current vertex.

• Unbounded solution
  Occurs when the entering column has no positive entry, so no ratio test can be formed.
• Degenerate pivot
  Occurs when a basic variable equals 0, giving a minimum ratio of 0, so the objective does not improve on that iteration. A tie in the ratio test produces a degenerate basic variable in the next tableau.

All Slack Starting Method

Used when every constraint is $\le$ with $b_i \ge 0$, so the origin is a feasible starting vertex.

• Add a slack variable to each constraint.
• Use the slack variables as the initial basic feasible solution.
• Run the iteration steps directly.

Big M Method

Used when constraints are mixed ($\ge$ or $=$ present), so the origin is not feasible and artificial variables are needed.

• Feasible
  All artificial variables equal 0 at optimality, so the solution is feasible for the original problem.
• Infeasible
  Any artificial variable is positive at optimality, so the original problem has no feasible solution.

Two Phase Method

Used as an alternative to Big M when a symbolic large constant is undesirable.

• Phase 1 minimum $> 0$
  The original problem is infeasible, stop.
• Phase 1 minimum $= 0$
  Proceed to phase 2 with the feasible vertex found.

Dual Simplex Algorithm

Starts from a dual-feasible but primal-infeasible solution and iterates toward primal feasibility. Dual feasibility is defined by the dual of the LP.

Used when a tableau is optimal but has a negative right-hand side, for example after adding a new constraint to an already-solved LP.