# Steps in the Simplex Method

I'm trying to look at how the Simplex method in standard form works. I understand the basics of how ti works, but I can't understand what happens between two steps.

I'm using the example from chapter 6 of Seymour Lipschutz's book Schaum's Outline of Finite Mathematics. The formulas I'm trying to maximize:

$$x+y+z+u=3$$ $$2x+2y+z+v=4$$ $$x-y+w=1$$ $$-4x+2y+z+f=0$$

I understand how to create the initial tableau, which is:

I can follow the steps to get the pivot entry (the $1$ in the $w$ row and $x$ column) and I can follow most of the steps to get the next tableau, however some entries seem to change with no explanation. The steps I'm following are:

1. Divide each entry in the row of the pivot by the pivot entry
2. In all other rows, introduce a zero in the column of the pivot entry
3. Replace the variable label to the left of the pivot by the variable label above the pivot

After following this you're meant to get:

The first and third steps I'm fine with. I think the problem I'm having is with the second step. I can't see why the other values in the $u$, $v$ and $f$ rows change. Any pointers on what I'm missing?

This is a repost from CS Theory

-
Minor comment: You forgot to implement step 3 in the second tableau. – Mike Spivey Dec 19 '12 at 18:32
The right-hand side in the second tableau is also incorrect. The entries should be 2, 2, 1, 4 rather than 3, 4, 1, 4. – Mike Spivey Dec 19 '12 at 18:42
Ah yes. They were correct in the book, but wrong my my lecturer's slides. I'll correct it now – matto1990 Dec 19 '12 at 18:45

To get the $0$'s in the other rows in the pivot column you're supposed to apply elementary matrix row operations. For instance, to get the $0$ in column $x$, row $u$, multiply row $w$ by $-1$ and add it to row $u$. Similarly, to get the $0$ in column $x$, row $v$, multiply row $w$ by $-2$ and add it to row $v$. Finally, to get the $0$ in column $x$, row $f$, multiply row $w$ by $4$ and add it to row $f$. This causes most of the other values in rows $u, v$, and $f$ to change as well.
What's going on under the hood here is that you're manipulating the original set of equations. At first the equations are in terms of $u$, $v$, and $w$ ($f$ is special because it is the objective function), in the sense that if you let $x$, $y$, and $z$ be $0$ you can just read off the current solution $u = 3, v = 4, w = 1$. We say that $u$, $v$, and $w$ are basic variables. The next step of pivoting on row $w$, column $x$, moves $x$ into the basis and $w$ out of the basis. Now, by letting $y$, $z$, and $w$ be $0$ you can read off the new solution $x = 1, u = 2, v = 2$. In fact, the whole point of doing this pivot thing is that you can read off the current solution like this.
(You may ignore the following if you're not sufficiently comfortable with linear algebra.) The pivot step is actually encoding the process of switching bases of the column space of the constraint matrix. At first the columns consisting of the coefficients of $u$, $v$, and $w$ comprise the basis. The pivot stop consists of the elementary matrix operations required to change the basis to the columns consisting of the coefficients of $x$, $u$, and $v$.