1
$\begingroup$

So I and 2 colleagues are arguing over a solution to an exam question and would like some clarification. It's an MCQ

Q: Consider the following tableau for a maximisation LP Problem:

\begin{array}{r|rrrr|r} & x_1 & x_2 & x_3 & x_4 & \text{b} \\ \hline x_3 & 1 & 1 & 1 & 0 & 15\\ x_4 & 1 & 2 & 0 & 1 & 20\\ \hline z & -3 & 0 & 0 & -6 & -75 \end{array}

Which of the following tableau will be reached after performing one step of the Simplex Method?

a)\begin{array}{r|rrrr|r} & x_1 & x_2 & x_3 & x_4 & \text{b} \\ \hline x_1 & 1 & 1 & 1 & 0 & 15\\ x_4 & 0 & 1 & -1 & 1 & 5\\ \hline z & 0 & 3 & 3 & 0 & -30 \end{array}

b)\begin{array}{r|rrrr|r} & x_1 & x_2 & x_3 & x_4 & \text{b} \\ \hline x_3 & 1 & 1 & 1 & 0 & 15\\ x_4 & 1 & 2 & 0 & 1 & 20\\ \hline z & 3 & 12 & 0 & 0 & 45 \end{array}

c)\begin{array}{r|rrrr|r} & x_1 & x_2 & x_3 & x_4 & \text{b} \\ \hline x_3 & 0 & -1 & 1 & -1 & -5\\ x_1 & 1 & 2 & 0 & 1 & 20\\ \hline z & 0 & 6 & 0 & -3 & -15 \end{array}

d)\begin{array}{r|rrrr|r} & x_1 & x_2 & x_3 & x_4 & \text{b} \\ \hline x_2 & -3 & 1 & 0 & 1 & 6\\ x_3 & -1 & 0 & 1 & -2 & 2\\ \hline z & -2 & 0 & 0 & 1 & 20 \end{array}

e) We cannot perform an update on this tableau.

My one colleague says the answer is b) As your Pivot column is $x_4$ as it has the largest negative element. Most texts state that the pivot column is determined by the largest negative value.

The other colleague says it's e) as $x_2$ is nonbasic yet has a coefficient of 0 in the z row.

Now, I think there is a mistake in the actual question, since $x_4$ is in the basis, but does not have a 0 coefficient in the z row... which means this tableau is already wrong and should actually be something like

\begin{array}{r|rrrr|r} & x_1 & x_2 & x_3 & x_4 & \text{b} \\ \hline x_3 & 1 & 1 & 1 & 0 & 15\\ x_4 & 1 & 2 & 0 & 1 & 20\\ \hline z & -3 & -6 & 0 & 0 & -75 \end{array}

So which is it? Is the question wrong from the start like I suggested.. or is someone actually right.. or are we all wrong and the solution is one of the other options?

$\endgroup$
1
$\begingroup$

The first colleague's answer is right, but the argument is not. We have to observe the coefficients from a tableau with the $z$-row fixed. The $-6$ tells you nothing about the LP's optimality since it's in the $x_4$-column representing the current basis.

Since $x_4$ is in the basis, you have to clear the entry $-6$ at the $z$-row. To do so, multiply the $x_4$-row by $6$ and add the result to the $z$-row. This gives the tableau in (b).

\begin{array}{r|rrrr|r} & x_1 & x_2 & x_3 & x_4 & \text{b} \\ \hline z_0 & -3 & 0 & 0 & -6 & -75\\ +\; 6x_4 & 6 & 12 & 0 & 6 & 120\\ \hline z_1 & 3 & 12 & 0 & 0 & 45 \end{array}

$\endgroup$
  • $\begingroup$ I know that was the operation used. So you're saying that although $x_4$ is in the basis with a nonzero coefficient, you can still perform the simplex method? It looks more like a row operation. I would consider a simplex method iteration as being a new variable entering the basis and an old one leaving. Here, you're just doing a row operation to make $x_4$ "correct" $\endgroup$ – KennyB Mar 24 '18 at 14:29
  • $\begingroup$ I.e. I'm saying that row operation is just fixing the objective function to match the basis. It's not an actual step of the simplex method where your pivot column element is entering the basis and pivot row is leaving, and you're making the remaining column elements zero. $\endgroup$ – KennyB Mar 24 '18 at 14:36
  • $\begingroup$ @KennyB There's no consensus whether such row operation can be called a step. For example, in HEC Montréal's notes, the setup of a proper tableau is called "step A". In your question, you ask for a single tableau (as you use the singular form "tableau" instead of the plural form "tableaux"). $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Mar 24 '18 at 15:34
  • $\begingroup$ @KennyB Since this is a maximasation problem, the objective function value should not decrease after one iteration. With the initial solution $(x_3,x_4) = (15, 20)$, you reach tableau (b) "after zero iteration". Observe that it's the unique optimal BFS to the problem in (b), and that the objective values in other tableaux (a), (c) and (d) are smaller than the one in (b). $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Mar 24 '18 at 15:39
  • 1
    $\begingroup$ Thanks for the feedback. I agree with you that such a row operation can perhaps be called a step. I think the question is then just poorly stated, but when compared to the other answers, b) makes the most sense. $\endgroup$ – KennyB Mar 25 '18 at 21:34

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.