0
$\begingroup$

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.

1 Answers 1

1

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.