The Simplex Algorithm

What is the simplex algorithm?

The simplex algorithm is a cornerstone of linear programming (LP), widely used in operations research to tackle optimization problems. It was introduced by George Dantzig in 1947 and has since become one of the most influential algorithms in applied mathematics.

What’s a simplex? A simplex is a polytope with N+1 vertices in N dimensions. In other words, it’s the higher-dimensional geometric analogue of a triangle or tetrahedron, used to represent optimization problems in multiple dimensions.

The simplex algorithm seeks either to maximize or minimize a linear objective function, subject to the constraints imposed on the decision variables of the optimization model.

A worked example

Consider the following optimization problem:

$$ \begin{cases} \min z(x)=-3x_1 -x_2 + 2x_3 \\ \\ x_1 \le 2 \\ x_1+x_2+x_3 = 6 \\ 3x_1 + 2x_3 = 10 \\ \\ x_1, x_2, x_3 \ge 0 \end{cases} $$

First, let’s rewrite it in standard form:

$$ \begin{cases} \min z(x)=-3x_1 -x_2 + 2x_3 \\ \\ x_1 +x_4 = 2 \\ x_1+x_2+x_3 = 6 \\ 3x_1 + 2x_3 = 10 \\ \\ x_1, x_2, x_3, x_4 \ge 0 \end{cases} $$

The coefficient matrix is:

$$ A = \begin{pmatrix} 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 3 & 0 & 2 & 0 \end{pmatrix} $$

The rank r(A) is 3.

Since r(A) = r(A|B), by the Rouché-Capelli theorem, the system admits one or more solutions.

Next, I select three linearly independent columns to form a basis.

For simplicity, let’s pick columns 2, 3, and 4-denoted [2,3,4].

$$ A_B = \begin{pmatrix} 0 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 2 & 0 \end{pmatrix} $$

The non-basic variable (x₁) is set to zero.

Now, let’s check whether this basis is feasible:

$$ x_B = A_B^{-1} b $$

$$ x_B = \begin{pmatrix} 0 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 2 & 0 \end{pmatrix}^{-1} \begin{pmatrix} 2 \\ 6 \\ 10 \end{pmatrix} $$

$$ x_B = \begin{pmatrix} 0 & 1 & -0.5 \\ 0 & 0 & 0.5 \\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} 2 \\ 6 \\ 10 \end{pmatrix} $$

$$ x_B = \begin{pmatrix} 1 \\ 5 \\ 2 \end{pmatrix} $$

This basis assigns the values x₂=1, x₃=5, x₄=2 to the basic variables.

It is a feasible basic solution since all variables satisfy the non-negativity constraints.

At these values, the objective function becomes:

$$ \min z(x)=-3x_1 -x_2+2x_3 $$

$$ \min z(x)=-3(0) -(1)+2(5) $$

$$ \min z(x)= -1 + 10 $$

$$ \min z(x)= 9 $$

Now, I reformulate the model in its canonical form relative to basis [2,3,4]:

$$ \begin{cases} \min c_B^T A_B^{-1}b + c_N^T x_N \\ x_B = A_B^{-1}b - A_B^{-1} A_N x_N \\ x_B,x_N \ge 0 \end{cases} $$

$$ \begin{cases} \min \begin{pmatrix} -2 \\ 1 \\ 0 \end{pmatrix} \begin{pmatrix} 1 \\ 5 \\ 2 \end{pmatrix} + c_N^T x_N \\ \begin{pmatrix} x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} 1 \\ 5 \\ 2 \end{pmatrix} - \begin{pmatrix} 0 & 1 & -0.5 \\ 0 & 0 & 0.5 \\ 1 & 0 & 0 \end{pmatrix} A_N x_N \\ x_B,x_N \ge 0 \end{cases} $$

$$ \begin{cases} \min 9 + c_N^T x_N \\ \begin{pmatrix} x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} 1 \\ 5 \\ 2 \end{pmatrix} - \begin{pmatrix} 0 & 1 & -0.5 \\ 0 & 0 & 0.5 \\ 1 & 0 & 0 \end{pmatrix} A_N x_N \\ x_B,x_N \ge 0 \end{cases} $$

Next, I bring in the coefficients A_N for the non-basic variable.

In this case, that’s just x₁.

Carrying out the multiplication gives:

$$ \begin{cases} 9 + c_N^T x_N \\ \begin{pmatrix} x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} 1 \\ 5 \\ 2 \end{pmatrix} - \begin{pmatrix} -0.5 \\ 1.5 \\ 1 \end{pmatrix} \begin{pmatrix} x_1 \end{pmatrix} \\ x_B,x_N \ge 0 \end{cases} $$

Rewriting in parametric form:

$$ \begin{cases} \min 9 + c_N^T x_N \\ \\ x_2 = 1 + 0.5 x_1 \\ x_3 = 5 - 1.5 x_1 \\ x_4 = 2 - x_1 \\ \\ x_B,x_N \ge 0 \end{cases} $$

Now I compute the reduced costs c_N for the non-basic variables:

$$ c - c_B A^{-1}_B A $$

$$ ( -3 , -1 , 2 , 0 ) - ( -1, 2, 0 ) \begin{pmatrix} 0 & 1 & -0.5 \\ 0 & 0 & 0.5 \\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 3 & 0 & 2 & 0 \end{pmatrix} $$

$$ ( -3 , -1 , 2 , 0 ) - ( -1, 2, 0 ) \begin{pmatrix} -0.5 & 1 & 0 & 0 \\ 1.5 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix} $$

$$ ( -3 , -1 , 2 , 0 ) - ( 3.5, -1, 2, 0 ) $$

$$ ( -6.5 , 0 , 0 , 0 ) $$

Thus, the reduced cost of the non-basic variable is c₁ = -6.5.

Note. If all reduced costs are nonnegative, the current solution is optimal and the algorithm terminates. Since we still have a negative reduced cost here, this solution is not optimal.

Substituting back into the canonical form gives:

$$ \begin{cases} \min 9 + c_N^T x_N \\ \\ x_2 = 1 + 0.5 x_1 \\ x_3 = 5 - 1.5 x_1 \\ x_4 = 2 - x_1 \\ \\ x_B,x_N \ge 0 \end{cases} $$

$$ \begin{cases} \min 9 - 6.5 x_1 \\ \\ x_2 = 1 + 0.5 x_1 \\ x_3 = 5 - 1.5 x_1 \\ x_4 = 2 - x_1 \\ \\ x_1,x_2,x_3,x_4 \ge 0 \end{cases} $$

At this step, I set all non-basic variables x_N to zero:

So x₁=0.

$$ x_N = 0 $$

Finally-and this is crucial-I move the constants of the constraints to the right-hand side, leaving all variable terms on the left:

$$ \begin{cases} \min 9 - 6.5 x_1 \\ \\ x_2 - 0.5 x_1 = 1 \\ x_3 + 1.5 x_1 = 5 \\ x_4 + x_1 = 2 \\ \\ x_1,x_2,x_3,x_4 \ge 0 \end{cases} $$

At this point, I select the entering variable-the one in the objective function with the coefficient that promises the steepest decrease.

That variable is x₁, since its coefficient is -6.5.

$$ \min z(x) = 9 - 6.5 x_1 $$

Because it’s the first variable, I record its index as k = 1:

$$ k = 1 $$

However, that alone isn’t sufficient. I also need to check that the variable actually appears in the system with at least one positive coefficient.

Note. If the entering variable has no positive coefficients in the constraint equations, the algorithm halts immediately-the problem is unbounded.

In this case, x₁ does have positive coefficients in the second and third constraints:

$$ \begin{cases} x_2 - 0.5 x_1 = 1 \\ x_3 + 1.5 x_1 = 5 \\ x_4 + x_1 = 2 \end{cases} $$

Which variable should leave the basis?

To decide, I use the minimum ratio test:

$$ h = \arg \min \left( \frac{b_i}{a_{ik}} : a_{ik} \ge 0 \right) $$

Here, h is the row index where the pivot element lies.

Practically speaking, I look for the constraint where the coefficient of x₁ is positive and the ratio b_i/a_i1 is the smallest.

From the system: $$ \begin{cases} x_2 - 0.5 x_1 = 1 \\ x_3 + 1.5 x_1 = 5 \\ x_4 + x_1 = 2 \end{cases} $$

The ratios are:

$$ h = \arg \min \left( \tfrac{5}{1.5}, \tfrac{2}{1} : a_{ik} \ge 0 \right) $$

$$ h = \arg \min (2) $$

$$ h = \arg(2) $$

The minimum ratio, 2, occurs in the third constraint (h = 3), which corresponds to the basic variable x₄.

$$ h = \arg(2) = 3 $$

Thus, x₁ enters the basis and x₄ leaves it. The new basis is [2,3,1].

$$ x_1 = 2, \quad h = 3 $$

Note. The column leaving basis [2,3,4] is column 4, i.e. variable x₄, since the smallest positive ratio is found in the third constraint (h=3).

This also lets me update the objective function value:

$$ \min z(x)= 9 - 6.5 x_1 $$

$$ \min z(x)= 9 - 6.5(2) $$

$$ z(x)= -4 $$

Substituting x₁ = 2 back into the system yields the new basic solution for [2,3,1]:

$$ \begin{cases} x_2 = 1 + 0.5 x_1 \\ x_3 = 5 - 1.5 x_1 \\ x_4 = 2 - x_1 \end{cases} $$

$$ \begin{cases} x_2 = 1 + 0.5 (2) \\ x_3 = 5 - 1.5 (2) \\ x_4 = 2 - (2) \end{cases} $$

$$ \begin{cases} x_2 = 2 \\ x_3 = 2 \\ x_4 = 0 \end{cases} $$

So the updated vector of decision variables is:

$$ x = ( x_1, x_2, x_3, x_4) = ( 2, 2, 2, 0 ) $$

The new basis is [2,3,1].

Next, I bring the model into canonical form relative to this new basis, which requires a pivot operation on element a_h,k, here a_3,1.

First, I construct the augmented tableau:

$$ \begin{pmatrix} -d & c \\ b & A \end{pmatrix} $$

where d is the constant term of the objective function, b the right-hand side of the constraints, c the cost vector, and A the coefficient matrix.

$$ \begin{cases} \min 9 - 6.5 x_1 \\ \\ x_2 - 0.5 x_1 = 1 \\ x_3 + 1.5 x_1 = 5 \\ x_4 + x_1 = 2 \\ \\ x_1,x_2,x_3,x_4 \ge 0 \end{cases} $$

This yields:

$$ \begin{pmatrix} -9 & -6.5 & 0 & 0 & 0 \\ 1 & -0.5 & 1 & 0 & 0 \\ 5 & 1.5 & 0 & 1 & 0 \\ 2 & 1 & 0 & 0 & 1 \end{pmatrix} $$

Indices start at zero. The pivot element is a_3,1 = 1.

I normalize the pivot row (h=3) by dividing through by the pivot value:

$$ \begin{pmatrix} -9 & -6.5 & 0 & 0 & 0 \\ 1 & -0.5 & 1 & 0 & 0 \\ 5 & 1.5 & 0 & 1 & 0 \\ \frac{2}{1} & \frac{1}{1} & \frac{0}{1} & \frac{0}{1} & \frac{1}{1} \end{pmatrix} $$

$$ \begin{pmatrix} -9 & -6.5 & 0 & 0 & 0 \\ 1 & -0.5 & 1 & 0 & 0 \\ 5 & 1.5 & 0 & 1 & 0 \\ 2 & 1 & 0 & 0 & 1 \end{pmatrix} $$

I then update the other rows using:

$$ a_i \leftarrow a_i - a_{i,k} a_h $$

with h=3, k=1, and a_h = (2,1,0,0,1).

Updating the first row:

$$ ( -9 , -6.5 , 0 ,0 , 0 ) - (-6.5)(2,1,0,0,1) $$

$$ = ( -9 , -6.5 , 0 ,0 , 0 ) - ( -13 , -6.5 , 0 , 0 , -6.5 ) $$

$$ = ( 4 , 0 , 0 ,0 , 6.5 ) $$

Second row:

$$ ( 1 , -0.5 , 1 ,0 , 0 ) - (-0.5)(2,1,0,0,1) $$

$$ = ( 1 , -0.5 , 1 ,0 , 0 ) - ( -1 , -0.5 , 0 , 0 , -0.5 ) $$

$$ = ( 2 , 0 , 1 ,0 , 0.5 ) $$

Third row becomes:

$$ ( 5 , 1.5 , 0 , 1 , 0 ) - (1.5)(2,1,0,0,1) $$

$$ = ( 5 , 1.5 , 0 , 1 , 0 ) - ( 3 , 1.5 , 0 , 0 , 1.5 ) $$

$$ = ( 2 , 0 , 0 , 1 , -1.5 ) $$

The pivot row itself is already normalized.

The updated tableau is:

$$ \begin{pmatrix} 4 & 0 & 0 & 0 & 6.5\\ 2 & 0 & 1 & 0 & 0.5 \\ 2 & 0 & 0 & 1 & -1.5 \\ 2 & 1 & 0 & 0 & 1 \end{pmatrix} $$

Note. An equivalent (and often simpler) approach is to use the pivot matrix, which streamlines the update after a basis change.

This corresponds to the canonical form:

$$ \begin{cases} \min 4 + 6.5x_4 \\ \\ x_2+0.5x_4 = 2 \\ x_3-1.5x_4 = 2 \\ x_1+x_4 = 2 \\ \\ x_1,x_2,x_3,x_4 \ge 0 \end{cases} $$

This is the canonical system relative to the new basis [2,3,1].

The simplex cycle then repeats, continuing until one of two outcomes:

an optimal solution is reached (all reduced costs are nonnegative), or
the problem is found to be unbounded (the entering variable has only non-positive coefficients).

Note. In the next iteration, the solution (2,2,2,0) is already optimal, since the new objective function 4 + 6.5x₄ has no negative reduced costs. Thus, the minimum of the problem is z = -4.