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 ak denote the kth column of A.

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

The Algorithm (Phase II):

1. Initialize: Set xB = B-1b, x N = 0. Basics ←{indices of variables in xB}, Nonbasics ←{indices of variables in xN}.
2. Calculate reduced costs: cNT - c BT B-1N.
3. Check for optimality: If cNT - c BT B-1N 0, STOP with optimality.
4. Choose entering variable: Pick a nonbasic variable xk with ck - cBT B-1ak < 0. Calculate d := B-1ak, the column of B-1N corresponding to x k.
5. Check for unboundedness: If d 0 STOP with unbounded optimal value. Ray: xB = -d, xk = 1, xj = 0 otherwise.
6. Calculate minimum ratio: Find Δ := min{ : di > 0}.
7. Update basic variables and entering variable: xB = B-1b - Δd, x k = Δ.
8. Choose leaving variable: Pick a basic variable xj that is equal to zero and has dj > 0 to leave the basis.
9. Update the set of basic variables:

Basics Basics k \ j
Nonbasics Nonbasics j \ k

Update B and N appropriately.