Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

enter image description here

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:

enter image description here

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

share|improve this question
    
Minor comment: You forgot to implement step 3 in the second tableau. –  Mike Spivey Dec 19 '12 at 18:32
3  
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

1 Answer 1

up vote 2 down vote accepted

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$.

share|improve this answer
    
Thanks that makes a lot more sense now! –  matto1990 Dec 19 '12 at 18:42
    
@matto1990: You're welcome. I'm glad it was helpful! As a side comment, I'm not really a big fan of the tableau form of the simplex method. I think it obscures why the simplex method actually works. If you continue to work with the simplex method in the future you might want to learn one of the other implementations. –  Mike Spivey Dec 19 '12 at 19:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.