4
$\begingroup$

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

1 Answers 1

3

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.

  • 1
    @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. :)2011-09-04