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.

Minimize $-2x_1-x_2+2x_3$ subject to $x_1 +x_3 = 4$, $-2x_1 +x_2 = 8$ s.t. $x_1,x_2,x_3\geq 0$.

In my book, the augmented matrix is defined as $[A : 0 : b; -c^T : 1 :0]$ (where : separates columns and ; separates rows).

Since the matrix of coefficients $A = [1: 0: 1; -2: 1: 0]$ and $b=[4: 8]$ while $c^T=[2: 1: -2]$, I get the augmented matrix
$[A : 0 : b; -c^T : 1 :0]$ = $[1: 0: 1: 0: 4; -2: 1: 0: 0: 8; 2: 1: -2: 1: 0]$.
I am not sure how to get to the tableau matrix from here -- the book has it that it equals $[1: 0: 1: 0: 4; -2: 1: 0: 0: 8; 6: 0: 0: 1: 0]$ but it doesn't show the steps to how it got there.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Writing your formulation in a slightly more consumable format

$$ \begin{array}{|l|r|rrr|r|} \hline & z & x_1 & x_2 & x_3 & \text{RHS}\\ \hline z & 1 & 2 & 1 & -2 & 0\\ \hline x_2 & 0 & 1 & 0 & 1 & 4\\ x_3 & 0 & -2 & 1 & 0 & 8\\ \hline \end{array} $$

we observe that $x_2$ and $x_3$ form a feasible (unit-)basis.

What remained to be done is bringing this to a canonical tableau format. For this, we need to ensure that the objective function row (the first row in the above) contains nonzero elements only in columns corresponding to nonbasic variables (i.e., $x_1$), while the values corresponding to the basic variables ($x_2$ and $x_3$) are zero.

To achieve this, you must do some transformations on the table. In particular, you need to subtract the third row from the first one (this will make the element corresponding to $x_2$ zero in the first row), plus you need to add twice the second row to the first row (this will take care of the element for $x_3$ in the first row).

Here is what you get:

$$ \begin{array}{|l|r|rrr|r|} \hline & z & x_1 & x_2 & x_3 & \text{RHS}\\ \hline z & 1 & 6 & 0 & 0 & 0\\ \hline x_2 & 0 & 1 & 0 & 1 & 4\\ x_3 & 0 & -2 & 1 & 0 & 8\\ \hline \end{array} $$

As you can see, this corresponds to the tableau in your book.

share|improve this answer

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.