In maximization simplex, the pivot is the smallest element in the column divided by the rightmost corresponding number. I am stumbling with the Example 3 here with solution that choose the pivot with the largest element. Please, explain how to choose the pivot in different cases and why the latter document can choose the largest element, intstead of the smallest?

In the paper, I am puzzled how it can move from this phase: \begin{equation*} \begin{array}{rrrrr|r} x & y & u & v & P & \\ \hline 1 & 2 & 1 & 0 & 0 & 6 \\ 3 & 2 & 0 & 1 & 0 & 12 \\ \hline -2 & 1 & 0 & 0 & 1 & 0 \\ \hline \end{array} \end{equation*}

to this phase: \begin{equation*} \begin{array}{rrrrr|r} x & y & u & v & P & \\ \hline 0 & \frac{4}{3} & 1 & -\frac{1}{3} & 0 & 2 \\ 1 & \frac{2}{3} & 0 & \frac{1}{3} & 0 & 4 \\ \hline 0 & \frac{5}{3} & 0 & \frac{1}{3} & 1 & 8 \\ \hline \end{array} \end{equation*}

I would have choosen 1 as pivot because $\frac{1}{6}<\frac{3}{12}=\frac{1}{4}$. When I plug my solutions back to the original restrictions, I notice that they do not satisfy the results while the paper solution does. It may have something to do with the fact that this problem is a minimization problem, changed to maximization problem with $P=-C$.


The pivot row is found by dividing the numbers in the rightmost column by the numbers in the pivot column (so you have it backwards, even from the beginning). So the proper comparison is $\frac{6}{1}$ vs. $\frac{12}{3} = 4$. The latter is the smaller one, and so the pivot number is the 3. Look at Example 1 in the notes, and you'll see they're also dividing the numbers in the rightmost column by the numbers in the pivot column.

Once the original minimization problem has been transformed into a maximization problem, it's treated like any other maximization problem from there on.

In general, it may help to remember that the simplex tableau is encoding a solution to a set of linear equations. Your equations are $$x + 2y + u = 6,$$ $$3x + 2y + v = 12.$$ Initially, $u$ and $v$ are in the basis, so the nonbasic variables $x$ and $y$ are both $0$, leaving $u = 6$, $v = 12$. The choice to have $x$ enter the basis (because of the $-2$ in the $x$ column) means that you are letting $x$ increase from $0$ until one of the current basic variables decreases to $0$ (since your variables can't be negative). This means that $x$ will have to stop increasing when the first of $u$ and $v$ reach $0$ . Rewriting the equations to emphasize this process we have $$u = 6 - x - 2y,$$ $$v = 12 - 3x - 2y.$$ So, as $x$ increases, which of $u$ and $v$ reaches $0$ first? Well, $u$ reaches $0$ when $x$ reaches $\frac{6}{1} = 6$, and $v$ reaches $0$ when $x$ reaches $\frac{12}{3} = 4$. Thus we increase $x$ until $v$ hits $0$, the pivot row is the row for variable $v$, and $v$ leaves the basis as $x$ enters. This is the reason for the comparison of $\frac{6}{1}$ vs. $\frac{12}{3}$ and for why you take the smaller of the two numbers when determining the pivot row.

  • $\begingroup$ Sorry for this slight derail, but: what textbook do you use when you're teaching LP? $\endgroup$ – J. M. is a poor mathematician Sep 4 '11 at 0:11
  • 2
    $\begingroup$ @J.M.: I've used the first half of Hillier and Lieberman in the past, but I recently switched over to David Rader's new Deterministic Operations Research. It's funny that you ask as a comment on this question, as part of the reason I switched to Rader is that I don't like teaching the simplex tableau (Rader doesn't discuss it at all). I think it emphasizes rote manipulations while partially obscuring what's really going on - i.e., changes of basis in the solution space. $\endgroup$ – Mike Spivey Sep 4 '11 at 2:51
  • $\begingroup$ @J.M. (continued): For more on this, see my answer here. $\endgroup$ – Mike Spivey Sep 4 '11 at 2:52
  • $\begingroup$ Thanks! (I was the one who upvoted the answer you linked to.) I haven't gotten around to looking at Rader, but since you've recommended it and I need to brush up on my LP, I'll check the nearest library tomorrow. :) (P.S. I don't like the tableau either.) $\endgroup$ – J. M. is a poor mathematician Sep 4 '11 at 5:15
  • 1
    $\begingroup$ @J.M.: One funny thing about that answer I linked to is that I had upvoted all the other answers to that question shortly after it was asked, but nobody else had upvoted any of the answers. So for a long time the only answer that had not been upvoted was mine! Thanks for the upvote - back whenever you did so. :) $\endgroup$ – Mike Spivey Sep 4 '11 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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