Simplex Algorithm | Sahithyan's Notes

The simplex algorithm iterates between vertices of the feasible region, improving the objective each step. It stops when no adjacent vertex improves it further.

Definitions

Slack Variable

A non-negative variable added to a $\le$ constraint. Absorbs unused capacity, converting it to an equality.

Surplus Variable

A non-negative variable subtracted from a $\ge$ constraint. Absorbs excess over the minimum, converting it to an equality.

Artificial Variable

A non-negative variable added to a $\ge$ or $=$ constraint. Provides a starting basic feasible solution when slack or surplus can’t.

Basic Variable

A variable solved for from the constraints rather than set to 0.

Non-basic Variable

A variable fixed at 0 while solving the constraints for the basic variables.

Standard Form

Convert the LP to standard form before applying simplex.

Objective should be maximization
Negate if a minimization objective.
Constraints must be equalities
All inequalities must be converted via slack, surplus, or artificial variables.
Variables must be non-negative

Simplex Tableau

Represents the system of equations and objective row together for iteration.

Suppose a linear program with $m$ constraints and $n$ variables is in standard form.

$m+1$ Rows
1 objective row, plus $m$ rows (1 per constraint).
$n+1$ Columns
1 per variable, plus 1 for right-hand-side (RHS).

A basic feasible solution reads basic variables directly from the RHS. Non-basic variables are 0.

Iteration Steps

Each iteration moves from one basic feasible solution to an adjacent one with a better or equal objective value.

Repeat the following steps until an optimal solution is found:

Check optimality

Inspect the objective row coefficients. If all are $\ge 0$ (maximization, standard form), the current solution is optimal. Stop.

Select Entering Variable

Entering variable is the non-basic variable selected to become basic. Chosen as the variable with the most negative objective row coefficient.

Select Leaving Variable

Leaving variable is the basic variable selected to become non-basic. Chosen by the minimum ratio test on the entering variable’s column.

Minimum Ratio Test

For each row with $a_{i,\text{entering}} > 0$ , compute:

\frac{\text{RHS}_i}{a_{i,\text{entering}}}

The row with the smallest non-negative ratio determines the leaving variable.

If no $a_{i,\text{entering}} > 0$ exists in step 3, the problem is unbounded. Stop.

Pivot

The intersection of the entering column and leaving row is the pivot element.

Divide the pivot row by the pivot element, making it 1.
Eliminate the entering variable from every other row, including the objective row, by elementary row operations.