The Simplex Algorithm

Consider the linear programming problem

$$\begin{array}{lrclr} \min & c^Tx \\ \mbox{subject to} & Ax &=& b & \qquad (P) \\ & x &\geq & 0 \end{array}$$

Here, A is m x 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 \geq 0$. (P) can be written

$$\begin{array}{lrcrclr} \min & c_B^Tx_B & + & c_N^Tx_N \\ ... ...(PB) \\ & \multicolumn{3}{r}{x_b, x_N} &\geq & 0 \end{array}$$

The Algorithm (Phase II):

1.

Initialize: Set x_B=B^-1b, x_N=0. Basics $\leftarrow$ {indices of variables in x_B }, Nonbasics $\leftarrow$ {indices of variables in x_N }.

2.

Calculate reduced costs: c_N^T-c_B^TB^-1N.  

3.

Check for optimality: If $c_N^T-c_B^TB^{-1}N\geq 0$, STOP with optimality.

4.

Choose entering variable: Pick a nonbasic variable x_k with c_k-c_B^TB^-1a^k<0. Calculate d:=B^-1a^k, the column of B^-1N corresponding to x_k.

5.

Check for unboundedness: If $d \leq 0$ STOP with unbounded optimal value. Ray: x_B=-d, x_k=1, x_j=0 otherwise.

6.

Calculate minimum ratio: Find $\Delta:=\min\{ \frac{(B^{-1}b)_i}{d_i} : d_i > 0 \}$.

7.

Update basic variables and entering variable: $x_B=B^{-1}b - \Delta d$, $x_k=\Delta$. (Note: for this notation to be correct, it is necessary that the variables have been ordered so that the basic variables are the first m variables. This reordering needs to be done every iteration.)

8.

Choose leaving variable: Pick a basic variable x_j that is equal to zero and has d_j>0 to leave the basis.

9.

Update the set of basic variables:

Basics $\leftarrow$ Basics $\cup \; k \setminus j$
Nonbasics $\leftarrow$ Nonbasics $\cup \; j \setminus k$

Update B and N appropriately.

10.

Loop: Return to Step 2.

Note: In a practical implementation, only quantities that are actually needed are calculated, and the quantities are calculated more efficiently. For example, the inverse matrix B^-1 is never calculated explicitly.