Simplex Method

by Justin Skycak on March 09, 2021

A technique for maximizing linear expressions subject to linear constraints.

This post is a chapter in the book Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. Suggested citation: Skycak, J. (2021). Simplex Method. Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. https://justinmath.com/simplex-method/

The simplex method is a technique for maximizing linear expressions subject to linear constraints. Many applied problems can be framed like this – for example, a business may have a variety of raw materials and need to determine the most profitable inventory of products that they can produce from those materials. This would ultimately amount to maximizing a linear expression for profit, subject to a linear inequality for each type of raw material (the total amount of raw material used in the products produced must be less than or equal to the amount of raw material available).

At its core, the simplex method is just algebra that can be implemented elegantly using array manipulations. Let’s work through the algebra on an example:

$\begin{align*} \textrm{maximize } x_1 + 2x_2 + x_3 & \textrm{ such that} \\ 2x_1 + x_2 + x_3 &\leq 14 \\ 4x_1 + 2x_2 + 3x_3 &\leq 28 \\ 2x_1 + 5x_2 + 5x_3 &\leq 30 \\ x_1, \, x_2, \, x_3 &\geq 0 \end{align*}$

Step 1: Introduce Slack Variables

Math is generally easier when we work with equations (rather than inequalities). We can convert most of the system above into equations if we move everything to the RHS and then assign those RHS expressions to new variables called slack variables.

$\begin{align*} &\textrm{maximize } x_1 + 2x_2 + x_3 \\ &0 \leq 14 - 2x_1 - x_2 - x_3 \\ &0 \leq 28 - 4x_1 - 2x_2 - 3x_3 \\ &0 \leq 30 - 2x_1 - 5x_2 - 5x_3 \\ &0 \leq x_1, \, x_2, \, x_3 \end{align*}$

$\begin{align*} &\textrm{maximize } x_1 + 2x_2 + x_3 \\ &x_4 = 14 - 2x_1 - x_2 - x_3 \\ &x_5 = 28 - 4x_1 - 2x_2 - 3x_3 \\ &x_6 = 30 - 2x_1 - 5x_2 - 5x_3 \\ &0 \leq x_1, \, x_2, \, x_3, \, x_4, \, x_5, \, x_6 \end{align*}$

The slack variables that we created are $x_4, x_5, x_6.$ Note that the original system is entirely equivalent to the definition of the slack variables. The system involving slack variables is exactly the same as the original system, but written a little differently. (This is analogous to change of variables in integration.)

Step 2: Evaluate the Objective Quantity

Each system in the above form is associated with a “guess” that comes from setting all the basic variables equal to $0.$ The basic variables are the variables that appear in the expressions for other non-basic variables.

In our case, the basic variables are $x_1, x_2, x_3$ because they appear in the quantity we’re trying to maximize and also in the expressions for the non-basic variables $x_4, x_5, x_6.$ You can also remember that the basic variables are the RHS and the non-basic variables are the LHS.

When we set the basic variables equal to $0,$ we plug

$\begin{align*} x_1 &= 0 \\ x_2 &= 0 \\ x_3 &= 0 \end{align*}$

into the quantity that we’re trying to maximize (known as the objective quantity) and get

$\begin{align*} &x_1 + 2x_2 + x_3 \\ &\to 0 + 2(0) + 0 \\ &\to 0. \end{align*}$

So currently, we have a guess $x_1 = x_2 = x_3 = 0$ and this brings the objective quantity to $0.$ This is a pretty bad guess, but we’re going to repeatedly improve it until it’s optimal.

Step 3: Identify the Basic Variable with the Greatest Slope

We’re going to improve upon our guess by repeatedly increasing the basic variable that will most quickly improve our guess.

To improve our guess, we need to increase the objective quantity $x_1 + 2x_2 + x_3,$ which we write as a function below:

$\begin{align*} M(x_1, x_2, x_3) = x_1 + 2x_2 + x_3 \end{align*}$

The basic variable that will most quickly improve our guess is the one that will make the objective quantity increase the fastest (when we increase that variable). In other words, it is the one with the greatest slope.

$\begin{align*} \textrm{slope}(x_1) = 1, \quad \textrm{slope}(x_2) = 2, \quad \textrm{slope}(x_3) = 1 \end{align*}$

Here, the basic variable with the largest slope is $x_2.$ So this what we will increase.

Step 4: Identify which Non-Basic Variable to Trade for that Basic Variable

The basic variable with the largest slope is $x_2.$ We will now trade this for one of the non-basic variables ($x_4, x_5, x_6$).

For our next guess, we want to increase $x_2$ as much as possible (since doing so will increase our objective quantity the fastest). But we can’t increase it too much – remember that the system has constraints, and we can’t invalidate those constraints.

Each of the constraints of the original system was converted into a non-basic variable. So, we need to identify the non-basic variable that places the strictest constraint on $x_2,$ and then trade it with $x_2$ (i.e. make that variable basic in exchange for making $x_2$ non-basic).

Here is where we are so far:

Since $0 \leq x_4, x_5, x_6,$ we have the following constraints:

$\begin{align*} &0 \leq x_4 = 14 - 2x_1 - x_2 - x_3 \\ &0 \leq x_5 = 28 - 4x_1 - 2x_2 - 3x_3 \\ &0 \leq x_6 = 30 - 2x_1 - 5x_2 - 5x_3 \end{align*}$

Let’s simplify a bit:

$\begin{align*} &0 \leq 14 - 2x_1 - x_2 - x_3 \\ &0 \leq 28 - 4x_1 - 2x_2 - 3x_3 \\ &0 \leq 30 - 2x_1 - 5x_2 - 5x_3 \end{align*}$

Now, let’s set move $x_2$ to the LHS of each constraint and set the other basic variables ($x_1,x_3$) equal to zero so that we can see which constraint is strictest:

$\begin{align*} &x_2 \leq 14 \\ &x_2 \leq 14 \\ &x_2 \leq 6 \end{align*}$

The strictest constraint is the constraint that places the lowest non-negative upper bound on $x_2.$ Here, the third constraint is the strictest, and if you look at the work backwards, you’ll see that it came from the non-basic variable $x_6{:}$

$\begin{align*} &x_6 = 30 - 2x_1 - 5x_2 - 5x_3 \\[5pt] &\hspace{0.3cm} \updownarrow \\[5pt] &0 \leq 30 - 2x_1 - 5x_2 - 5x_3 \\[5pt] &\hspace{0.3cm} \updownarrow \\[5pt] &x_2 \leq 6 \end{align*}$

So, we need to trade the non-basic variable $x_6$ for the basic variable $x_2.$

Step 5: Execute the Trade

This step will feel more familiar than the earlier steps. We have an equation relating $x_6$ and $x_2{:}$

$\begin{align*} x_6 = 30 - 2x_1 - 5x_2 - 5x_3 \end{align*}$

All we need to do is solve this equation for $x_2$ and then substitute that into our system.

Solving for $x_2,$ we get

$\begin{align*} x_2 = 6 - \dfrac{2}{5}x_1 - x_3 - \dfrac{1}{5}x_6. \end{align*}$

Then, we substitute into our system. The only catch is that we need to fully replace the $x_6 = $ equation with the $x_2 = $ equation. (This equation is supposed to capture the relationship between $x_2$ and $x_6$, and if we just substituted $x_2$ in the RHS, then it would simplify to a useless equation $x_6 = x_6$).

$\begin{align*} &\textrm{maximize } x_1 + 2\color{blue}{x_2} + x_3 \\ &x_4 = 14 - 2x_1 - \color{blue}{x_2} - x_3 \\ &x_5 = 28 - 4x_1 - 2\color{blue}{x_2} - 3x_3 \\ &\color{red}{x_6 = 30 - 2x_1 - 5x_2 - 5x_3} \\ &0 \leq x_1, \, x_2, \, x_3, \, x_4, \, x_5, \, x_6 \end{align*}$

$\begin{align*} &\textrm{maximize } x_1 + 2\color{blue}{\left( 6 - \dfrac{2}{5}x_1 - x_3 - \dfrac{1}{5}x_6 \right)} + x_3 \\ &x_4 = 14 - 2x_1 - \color{blue}{\left( 6 - \dfrac{2}{5}x_1 - x_3 - \dfrac{1}{5}x_6 \right)} - x_3 \\ &x_5 = 28 - 4x_1 - 2\color{blue}{\left( 6 - \dfrac{2}{5}x_1 - x_3 - \dfrac{1}{5}x_6 \right)} - 3x_3 \\ &\color{red}{x_2 = 6 - \dfrac{2}{5}x_1 - x_3 - \dfrac{1}{5}x_6} \\ &0 \leq x_1, \, x_2, \, x_3, \, x_4, \, x_5, \, x_6 \end{align*}$

$\begin{align*} &\textrm{maximize } 12 + \dfrac{1}{5}x_1 - x_3 - \dfrac{2}{5}x_6 \\ &x_4 = 8 - \dfrac{8}{5} x_1 + \dfrac{1}{5}x_6 \\ &x_5 = 16 - \dfrac{16}{5} x_1 - x_3 + \dfrac{2}{5} x_6 \\ &x_2 = 6 - \dfrac{2}{5}x_1 - x_3 - \dfrac{1}{5}x_6 \\ &0 \leq x_1, \, x_2, \, x_3, \, x_4, \, x_5, \, x_6 \end{align*}$

Just to keep things tidy, we’ll re-order the equations so that the LHS variables are sorted:

$\begin{align*} &\textrm{maximize } 12 + \dfrac{1}{5}x_1 - x_3 - \dfrac{2}{5}x_6 \\ &x_2 = 6 - \dfrac{2}{5}x_1 - x_3 - \dfrac{1}{5}x_6 \\ &x_4 = 8 - \dfrac{8}{5} x_1 + \dfrac{1}{5}x_6 \\ &x_5 = 16 - \dfrac{16}{5} x_1 - x_3 + \dfrac{2}{5} x_6 \\ &0 \leq x_1, \, x_2, \, x_3, \, x_4, \, x_5, \, x_6 \end{align*}$

Step 6: Repeat Steps 2-5 Until No Slopes Are Positive

Evaluate the objective quantity. We will evaluate the objective quantity for our new guess. Remember that our guess is obtained by setting the basic variables equal to $0.$ The basic variables are now $x_1, x_3, x_6.$ Setting these variables equal to $0,$ our objective quantity becomes

$\begin{align*} &12 + \dfrac{1}{5}x_1 - x_3 - \dfrac{2}{5}x_6 \\ &\to 12 + \dfrac{1}{5}(0) - 2(0) - \dfrac{2}{5}(0) \\ &\to 12. \end{align*}$

So our guess has improved! Our previous guess gave us an objective quantity of $0,$ and our new guess gave us an objective quantity of $12.$

Sanity Checks

In this example, if you ever get a new guess that does not appear to increase the objective quantity, then something went wrong. The new guess should always increase the objective quantity. (In rare cases, it’s possible for the simplex algorithm to “cycle” around suboptimal minima that yield the same value of the objective function, but this example is not one of those cases.)

Additionally, you should always verify that your guess satisfies the constraints of the original problem statement. Below is an explanation of how to do that. As a reminder, the original problem statement was to maximize $x_1 + 2x_2 + x_3$ subject to the following constraints:

$\begin{align*} 2x_1 + x_2 + x_3 &\leq 14 \\ 4x_1 + 2x_2 + 3x_3 &\leq 28 \\ 2x_1 + 5x_2 + 5x_3 &\leq 30 \\ x_1, \, x_2, \, x_3 &\geq 0 \end{align*}$

The original problem statement is framed in terms of variables $x_1,x_2,x_3.$ The slack variables $x_4,x_5,x_6$ are artificial things that we made up. Here, our guess is $x_1 = x_3 = x_6 = 0.$ Although $x_2$ is not explicit in our guess, we can find it by substituting our guess into our system. Doing so, we find

$\begin{align*} x_2 = 6, \quad x_4 = 8, \quad x_5 = 16. \end{align*}$

So in terms of the original variables of our system, our guess is

$\begin{align*} x_1=0, \quad x_2 = 6, \quad x_3 = 0. \end{align*}$

Indeed, if we evaluate the objective quantity shown in the problem statement, we get

$\begin{align*} &x_1 + 2x_2 + x_3 \\ &\to 0 + 2(6) + 0 \\ &\to 12. \end{align*}$

Additionally, the guess $x_1=0, \, x_2 = 6, \, x_3 = 0$ satisfies all constraints in the original problem statement.

Another Iteration

Identify the basic variable with the largest slope. Our objective function is now

$\begin{align*} M(x_1, x_3, x_6) = 12 + \dfrac{1}{5}x_1 - x_3 - \dfrac{2}{5}x_6, \end{align*}$

and the basic variable with the largest slope is $x_1.$

Identify which non-basic variable to trade for that basic variable. With a bit of algebra work (which you should do on your own), we have the following constraints:

$\begin{align*} &x_1 \leq 15 \\ &x_1 \leq 5 \\ &x_1 \leq 5 \end{align*}$

The second and third constraints are the strictest. They are equally strict, so we can choose to proceed with either one. Referring back to our system (shown below), these two constraints come from $x_4$ and $x_5.$

Let’s proceed with the $x_4$ constraint since it’s simpler (it contains fewer variables).

Execute the trade. Solving for $x_1$ in terms of $x_4$ (which you should do on your own), we get

$\begin{align*} x_1 &= 5 - \dfrac{5}{8}x_4 + \dfrac{1}{8}x_6 \end{align*}$

I’ll leave it to you to finish the trade execution by substituting into your system.

In the next round, you should find that your guess has improved, but that no slopes are positive, which means you’re done and have found the optimal solution.

Array Manipulations

The algebra above can be implemented more elegantly as array manipulations. Let’s start by taking the system that we obtained after introducing slack variables, and converting it to an array:

$\begin{align*} &\textrm{maximize } x_1 + 2x_2 + x_3 \\ &2x_1 + x_2 + x_3 + x_4 = 14 \\ &4x_1 + 2x_2 + 3x_3 + x_5 = 28 \\ &2x_1 + 5x_2 + 5x_3 + x_6 = 30 \\ \end{align*}$

$\begin{align*} \begin{matrix} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & \textrm{constant} \\ \textrm{ maximize } & 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ \textrm{constraint } & 2 & 1 & 1 & 1 & 0 & 0 & 14 \\ \textrm{constraint } & 4 & 2 & 3 & 0 & 1 & 0 & 28 \\ \textrm{constraint } & 2 & 5 & 5 & 0 & 0 & 1 & 30 \end{matrix} \end{align*}$

From the array, we can tell that $x_2$ has the largest slope since it has the largest entry in the top row. To find the row that places the strictest constraint on $x_2,$ we just divide the constant column by the $x_2$ column:

$\begin{align*} \begin{matrix} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & \textrm{constant} & \textrm{constraint} \\ \textrm{ maximize } & 1 & 2 & 1 & 0 & 0 & 0 & 0 & - \\ \textrm{constraint } & 2 & 1 & 1 & 1 & 0 & 0 & 14 & 14/1 = 14 \\ \textrm{constraint } & 4 & 2 & 3 & 0 & 1 & 0 & 28 & 28/2 = 14 \\ \textrm{constraint } & 2 & 5 & 5 & 0 & 0 & 1 & 30 & 30/5 = 6 \end{matrix} \end{align*}$

The bottom row places the strictest constraint. To execute the trade, we perform elementary row operations using the bottom row to kill off the rest of the $x_2$ column. (That is, we divide the bottom row so that the entry in the $x_2$ column becomes $1,$ and then we subtract multiples of the bottom row from the other rows.)

$\begin{align*} \begin{matrix} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & \textrm{constant} \\ \textrm{ maximize } & 0.2 & 0 & -1 & 0 & 0 & -0.4 & -12 & \leftarrow \textrm{ max is } 12 \\ \textrm{constraint } & 1.6 & 0 & 0 & 1 & 0 & -0.2 & 8 \\ \textrm{constraint } & 3.2 & 0 & 1 & 0 & 1 & -0.4 & 16 \\ \textrm{constraint } & 0.4 & 1 & 1 & 0 & 0 & 0.2 & 6 \end{matrix} \end{align*}$

This matches up with the system that we got after the first iteration when we worked out the algebra (shown below). The only catch is that the $-12$ in the “constant” column really means that we’ve reached a maximum of positive $12.$ (This happens because the constant column usually represents the constant once it’s been moved to the other side of the equality sign, but there is no equality sign in the expression that we’re trying to maximize.)

Remember that the array manipulations are just implementing algebra that we’ve already worked through, so if you get confused or stuck when implementing the simplex method, it will help to go back to the algebra and make sure that every array manipulation you do matches up against the algebra.

Exercises

Work out the example that was covered, using algebra, on paper.
Write all the relevant array manipulations next to the algebra.
Implement the simplex method in code. The input should be the first array that you write down, and the output should be the last array that you wrote down.
Work out the array manipulations manually for the new system shown below, and then ensure that your implementation gives the same result. Note that when you are identifying the strictest constraint, if you ever get a constraint of that involves a comparison to a negative number, then you can discard it (since we already know the variables are non-negative). This should only require you to work out $3$ iterations (i.e. your $4$th guess will be the final one).

$\begin{align*} \textrm{maximize } 20x_1 + 10x_2 + 15x_3 & \textrm{ such that} \\ 3x_1 + 2x_2 + 5x_3 &\leq 55 \\ 2x_1 + x_2 + x_3 &\leq 26 \\ x_1 + x_2 + 3x_3 &\leq 30 \\ 5x_1 + 2x_2 + 4x_3 &\leq 57 \\ x_1, \, x_2, \, x_3 &\geq 0. \end{align*}$