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!

* Edited 2021-01-27 and again 2022-12-29 to fix tables.