Simplex Algorithm | Sahithyan's Notes

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

Named after simplices. It moves along the edges between adjacent extreme points (vertices) of the feasible polyhedron, which can be decomposed into simplices, improving the objective at each step.

Conditions for Use

All of the following must hold:

LP in standard form
Objective to maximize, constraints as equalities, all variables $\ge 0$ , RHS $\ge 0$ . Per the fundamental theorem.
An initial basic feasible solution is available
With all $\le$ constraints and non-negative RHS, the slack variables give one directly. Otherwise use artificial variable methods (big-M or two-phase) to start.
Feasible region is non-empty
Infeasible LPs have no basic feasible solution to iterate from.

Cycling on degenerate solutions is possible but preventable with anti-cycling rules (Bland’s rule). The algorithm handles unboundedness by detecting it during the ratio test.

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

In the entering variable’s column, for each constraint 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 the entering column, the problem is unbounded. Stop.

Pivot

The intersection of the entering column and leaving row.

Divide the pivot row by the pivot element, making its entering-column entry 1.
For every other row (constraint rows and the objective row), subtract $c_r$ times the new pivot row, where $c_r$ is that row’s current entering-column entry. Applied across all columns including RHS.

This zeroes the entering column everywhere except the pivot row, making the entering column a unit vector. On the objective row the same operation removes the negative reduced cost and updates $z$ .

Worked Example

\begin{aligned} \text{maximize} \quad & z = 3x_1 + 5x_2 \\ \text{subject to} \quad & x_1 \le 4 \\ & 2x_2 \le 12 \\ & 3x_1 + 2x_2 \le 18 \\ & x_1, x_2 \ge 0 \end{aligned} \tag{1}

Standard form adds slacks $s_1, s_2, s_3$ , one per constraint:

\begin{aligned} x_1 + s_1 &= 4 \\ 2x_2 + s_2 &= 12 \\ 3x_1 + 2x_2 + s_3 &= 18 \end{aligned} \tag{2}

The objective row is written as $z - 3x_1 - 5x_2 = 0$ . Initial basis $(s_1, s_2, s_3) = (4, 12, 18)$ .

1 /

entering column leaving row pivot element updated this step

Basic	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	RHS
$z$	$-3$	$-5$	$0$	$0$	$0$	$0$
$s_1$	$1$	$0$	$1$	$0$	$0$	$4$
$s_2$	$0$	$2$	$0$	$1$	$0$	$12$
$s_3$	$3$	$2$	$0$	$0$	$1$	$18$

Basic feasible solution $x_1 = x_2 = 0$ , $z = 0$ . Two negative objective coefficients ( $-3$ , $-5$ ), so not optimal.

Basic	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	RHS	Ratio
$z$	$-3$	$-5$	$0$	$0$	$0$	$0$
$s_1$	$1$	$0$	$1$	$0$	$0$	$4$	skip (0)
$s_2$	$0$	$2$	$0$	$1$	$0$	$12$	12/2 = 6
$s_3$	$3$	$2$	$0$	$0$	$1$	$18$	18/2 = 9

Most negative objective coefficient is $-5$ , so $x_2$ enters. Minimum ratio is $6$ in row $s_2$ , so $s_2$ leaves. Pivot element is $a_{s_2, x_2} = 2$ .

Basic	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	RHS	Ratio
$z$	$-3$	$0$	$0$	$5/2$	$0$	$30$
$s_1$	$1$	$0$	$1$	$0$	$0$	$4$	4/1 = 4
$x_2$	$0$	$1$	$0$	$1/2$	$0$	$6$	skip (0)
$s_3$	$3$	$0$	$0$	$-1$	$1$	$6$	6/3 = 2

After the pivot $z = 30$ . Now $-3$ is the most negative, so $x_1$ enters. Minimum ratio is $2$ in row $s_3$ , so $s_3$ leaves. Pivot element is $a_{s_3, x_1} = 3$ .

Basic	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	RHS
$z$	$0$	$0$	$0$	$3/2$	$1$	$36$
$s_1$	$0$	$0$	$1$	$1/3$	$-1/3$	$2$
$x_2$	$0$	$1$	$0$	$1/2$	$0$	$6$
$x_1$	$1$	$0$	$0$	$-1/3$	$1/3$	$2$

All objective coefficients are non-negative. Optimal at $x_1 = 2$ , $x_2 = 6$ , $z = 36$ .

.simplex [data-live] { display: none; } .simplex .stack { display: block; } .simplex .stack > .step { opacity: 1; visibility: visible; margin-top: 16px; } .simplex .stack .step > .tableau { display: table; } .simplex .foot { display: none; }

Special Cases

Read off the final tableau:

Unique optimal solution
Every non-basic variable has a strictly positive objective row coefficient.
Alternate (infinite) optimal solutions
A non-basic variable has a 0 objective row coefficient. Every convex combination of the corresponding basic feasible solutions is also optimal.
Unbounded solution
No positive entry in the entering variable’s column during the minimum ratio test.

Tie in Entering Variable

Several non-basic variables share the most negative objective row coefficient. Break the tie arbitrarily; any choice reaches an optimal solution, though the iteration count may differ.

Tie in Leaving Variable

Several rows share the minimum ratio. Breaking the tie arbitrarily leaves a basic variable at 0, giving a degenerate basic feasible solution. This risks cycling (revisiting a basis without improving the objective), avoided by a fixed tie-breaking rule (Bland’s rule: prefer the lowest-indexed variable).

Other Uses of Simplex

Constructing a tableau for a given set of basic variables
Row-reduce the constraint matrix on those columns until they form an identity matrix.
Solving a system of linear equations
Add an artificial objective (minimize the sum of artificial variables) and run simplex; a 0 optimal value with all artificial variables out of the basis gives a solution.
Finding the inverse of a matrix
Run simplex with each column of the identity matrix as a separate RHS; the columns under the original identity’s position in the final tableau form the inverse.