The Simplex Algorithm

Author: Aster Santana, Andrea Rujano.

Consider the following linear program (LP) in standard form:

\[ \begin{eqnarray} \begin{array}{rcl} & \min & c^Tx\\ & \text{s.t.}& Ax = b\\ && x \geq 0. \end{array} \end{eqnarray} \] where \(A\) is a \(m\times n\) matrix and \(b,c\) and \(x\) are vectors of appropriate length. Suppose that the rows of \(A\) are linearly independent (which implies that \(n\geq m\), i.e., the LP has more variables than constraints).
We rewrite the LP above by decomposing the decision variables between basic and non-basic variables. Let \(B\) and \(N\) be the set of indices of the basic and non-basic variables, respectively, where \(B\) has \(m\) elements and \(N\) has \(n-m\) elements. Then we write \(x\) as follows: $$ x = \begin{bmatrix} x_B\\ x_N \end{bmatrix}. $$
Similarly, we decompose \(c\) and \(A\) as follows: $$ c = \begin{bmatrix} c_B\\ c_N \end{bmatrix}, \quad A = \begin{bmatrix} A_B & A_N \end{bmatrix}. $$
Now we rewrite the problem as follows: $$ \begin{eqnarray} \begin{array}{rcl} & \min & c^T_B x_B + c^T_N x_N\\ & \text{s.t.}& A_B x_B + A_N x_N = b\\ && x_B, x_N \geq 0. \end{array} \end{eqnarray} $$
Since we have assumed that the rows of \(A\) are linearly independent, we know that \(A_B\) is an invertible matrix. Therefore, we can rewrite the constraints as follows: $$ A_B x_B + A_N x_N = b\\ A_B x_B = b - A_N x_N\\ x_B = A_B^{-1}(b - A_N x_N)\\ x_B = A_B^{-1}b - A_B^{-1}A_N x_N. $$
By using this expression for \(x_B\), the objective function can be re-written as: $$ \begin{align*} c^T_B x_B + c^T_N x_N &= c^T_B (A_B^{-1}b - A_B^{-1}A_N x_N) + c^T_N x_N\\ &= c^T_B A_B^{-1}b - c^T_BA_B^{-1}A_N x_N + c^T_N x_N\\ &= c^T_B A_B^{-1}b - (c^T_BA_B^{-1}A_N + c^T_N) x_N\\ &= c^T_B A_B^{-1}b + (c^T_N - c^T_BA_B^{-1}A_N) x_N. \end{align*} $$
The problem now becomes: $$ \begin{eqnarray} \begin{array}{rcl} & \min & c^T_B A_B^{-1}b + (c^T_N - c^T_BA_B^{-1}A_N) x_N\\ & \text{s.t.}& x_B = A_B^{-1}b - A_B^{-1}A_N x_N\\ && x_B, x_N \geq 0. \end{array} \end{eqnarray} $$
At any iteration of the simplex method, the non-basic variables are set to zero, i.e., \(x_N=0\). As a result, the values of the basic variables are given by \(x_B = A_B^{-1}b\). And the objective value is given by \(c^T_B A_B^{-1}b\).

To perform a simplex iteration (which is called a pivoting), we attempt to increase one of the non-basic variables from zero. But which one should we choose?

To answer this question, we re-write the problem using summation notation:

$$ \begin{eqnarray} \begin{array}{rcl} & \min & c^T_B A_B^{-1}b + \sum_{j\in N}(c_j - c^T_BA_B^{-1}A^j) x_j\\ & \text{s.t.}& x_B = A_B^{-1}b - \sum_{j\in N}A_B^{-1}A^j x_j\\ && x_B \geq 0, x_j \geq 0, \forall j \in N. \end{array} \end{eqnarray} $$
From here, it’s easy to see that it only makes sense to increase from zero a non-basic variable \(x_j\) if its coefficient \(c_j - c^T_BA_B^{-1}A^j\) is negative. This coefficient is called the reduced cost of \(x_j\). In fact, if the reduced cost of \(x_j\) is negative, then increasing \(x_j\) will decrease the objective value, which is desirable since this is a minimization problem. On the other hand, if the reduced cost of every non-basic variable is non-negative, we conclude that the current solution is optimal.
Now that we have a way to decide which non-basic variables can be made a basic variable (i.e., pick one with negative reduced cost), suppose \(x_1\) is non-basic and has a negative reduced cost. From an optimization perspective, we want to increase \(x_1\) as much as possible. What can stop us from increasing \(x_1\) indefinitely?
The answer comes from the expression $$ x_B = A_B^{-1}b - \sum_{j\in N}A_B^{-1}A^j x_j. $$ Which is the same as $$ x_B = A_B^{-1}b - A_B^{-1}A^1 x_1 $$ since \(x_j=0\) for all \(j\in N\) such that \(j\neq 1\).
Therefore, if the vector \(A_B^{-1}A^1\) has any positive component, as we increase \(x_1\) the corresponding basic variables on the right-hand-side will decrease, and eventually, one of them will reach zero and become a non-basic variable! If we were to keep increasing \(x_1\), then some basic variables would become negative, which is not allowed as all variables must be non-negative. This completes one iteration of the simplex method.
 

If you have any questions, comments, or would like to chat more about this topic, just reach out to us.