A student asks… about the Simplex Algorithm

A student asks:

I'm struggling with the simplex algorithm. How do I read the tableau at the end? And how do I pick the right pivot?

The simplex algorithm - which is D2 for most students, but D1 if you're doing OCR - is frequently listed as one of the top ten algorithms of the 20th century. It's a way of solving a linear programming problem (a series of inequalities) while keeping all of the variables positive.

For example, if you want to maximise $P=2x + 3y$, subject to the constraints $x + 2y \le 6$ and $x + y \le 5$, you would translate that into a system of equations like this:

$P - 2x - 3y=0$ (just rearranging)
$x + 2y + s = 6$ (adding in a slack variable $s$)
$x + y + t = 5$ (adding in a second slack variable $t$).

Because the inequality sign means "this stuff adds up to less than this stuff", you can turn it into an equation by making up another 'slack' variable to add on. Saying $x ≤ 3$ is the same as saying "$x$ plus something positive equals three." You don't really care what the something is, though.

Now, let me show you the textbook approach first. Then I'll show you what's really going on. The textbook turns this into a tableau, which is like a table but more French.

$P$ $x$ $y$ $s$ $t$ $k$ label algebra
1 -2 -3 0 0 0 (1) $P-2x-3y=0$
0 1 2 1 0 6 (2) $x+2y+s=6$
0 1 1 0 1 5 (3) $x+y+t=5$

Now: we want the top row to say that $P$ plus other stuff equals some constant, which will be our maximum value. At the moment, it's minus, and we need to fix it using row operations. Everyone do the Gauss-Jordan shudder!

What that means is, we can add and subtract rows of the table to each other as much as we like. The simplex algorithm just gives us a specific order to do them in! We need to pick a pivot - which is a cell of the table that won't make any of the variables go negative when we add and subtract multiples of it.

Remember, we're trying to make the negatives in the top line become positive, so let's start with $y$ (it doesn't matter which one we do first). The pivot is the cell in the $y$ column such that the value in the $k$ column divided by the value in the $y$ column is smallest - in this case, it'd be the 2 (in equation (2)).

We're going to get rid of everything else in the $y$ column now. If you add three-halves of row (2) to row (1), you get rid of the -3; if you add subtract half of row (2) from row (3), you get rid of the 1 there as well. You end up with:

$P$ $x$ $y$ $s$ $t$ $k$ label algebra
1 $-\frac12$ 0 $\frac32$ 0 9 (4)=(1)+1.5(2) $P-\frac12 x + \frac32s=9$
0 $\frac12$ 1 $\frac12$ 0 3 (5) = 0.5(2) $\frac12 x+\frac12 s=3$
0 $\frac12$ 0 $-\frac12$ 1 2 (6) = (3) - 0.5(2) $\frac 12x-\frac12s + t=2$

Nearly there! We still have to get rid of the $-\frac12$ in the $x$ column. The pivot this time is in row (6), because $2 ÷ \frac12$ is smaller than $3 ÷ \frac12$. We'll need to add row (6) to row (4) and take it away from row (5) to clear out the $x$ columns, leaving us with:

$P$ $x$ $y$ $s$ $t$ $k$ label algebra
1 0 0 1 1 11 (7)=(4)+(6) $P+s + t=11$
0 0 1 1 -1 1 (8) = (5)-(6) $y+ s - t=1$
0 1 0 $-1$ 2 6 (9) = 2(6) $x -s +2t =4$

We can set the slack variables to 0 since they appear in equation (7), giving $P=11$, $y=1$ and $x=4$, the solution to the problem. In some cases, you may need to solve the equations below to get $x$ and $y$, but here we got lucky.

If you look at the last column of the tableau, you'll see what's going on algebraically - this is another way to solve the simultaneous equations, but you still need to be cautious of picking the correct pivot.

* Edited to fix typo. Thanks, @chrismaslanka!

Colin

Colin is a Weymouth maths tutor, author of several Maths For Dummies books and A-level maths guides. He started Flying Colours Maths in 2008. He lives with an espresso pot and nothing to prove.

Share

6 comments on “A student asks… about the Simplex Algorithm

  • Joshua Zucker

    Algebraically? With matrices? How about a little talk from the ninja about what the simplex method means geometrically about walking along edges of a polytope, choosing the one with the greatest rate of increase of your objective? At least then maybe we can understand what it means. Though maybe the geometry is too hard to visualize in an example like yours with so many variables.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Sign up for the Sum Comfort newsletter and get a free e-book of mathematical quotations.

No spam ever, obviously.

Where do you teach?

I teach in my home in Abbotsbury Road, Weymouth.

It's a 15-minute walk from Weymouth station, and it's on bus routes 3, 8 and X53. On-road parking is available nearby.

On twitter