The Simplex Algorithm
John E. Mitchell

Consider the linear programming problem

min        cT x
subject to   Ax   =  b       (P )

              x  ≥  0

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

min        cTBxB   +   cTNxN
subject to  Bx    +   N x    =   b      (P B )
               B          N
                     xb,xN   ≥   0

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{(B-1b)i
   di : 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.

  10. Loop: Return to Step 2.