The Simplex Algorithm

John E. Mitchell

Consider the linear programming problem

Here, A is m × n and has rank n. The vectors c, b, and x are dimensioned appropriately. Let a^{k}
denote the kth column of A.

Assume we have a subset B of m linearly independent columns of A such that B^{-1}b ≥ 0. (P)
can be written

The Algorithm (Phase II):

- Initialize: Set x
_{B}= B^{-1}b, x_{ N}= 0. Basics ←{indices of variables in x_{B}}, Nonbasics ←{indices of variables in x_{N}}. - Calculate reduced costs: c
_{N}^{T }- c_{ B}^{T }B^{-1}N. - Check for optimality: If c
_{N}^{T }- c_{ B}^{T }B^{-1}N ≥ 0, STOP with optimality. - Choose entering variable: Pick a nonbasic variable x
_{k}with c_{k}- c_{B}^{T }B^{-1}a^{k}< 0. Calculate d := B^{-1}a^{k}, the column of B^{-1}N corresponding to x_{ k}. - Check for unboundedness: If d ≤ 0 STOP with unbounded optimal value.
Ray: x
_{B}= -d, x_{k}= 1, x_{j}= 0 otherwise. - Calculate minimum ratio: Find Δ := min{ : d
_{i}> 0}. - Update basic variables and entering variable: x
_{B}= B^{-1}b - Δd, x_{ k}= Δ. - Choose leaving variable: Pick a basic variable x
_{j}that is equal to zero and has d_{j}> 0 to leave the basis. - Update the set of basic variables:
Basics ← Basics ∪ k \ j

Nonbasics ← Nonbasics ∪ j \ kUpdate B and N appropriately.

- Loop: Return to Step 2.