Exercise 3.17

We follow the procedure from page 113.

Phase I. In order to find a feasible solution, we form the auxiliary problem

A basic feasible solution to the auxiliary problem is obtained by letting $(x_6,x_7,x_8):=b=(2,2,1)$. The corresponding basis matrix is the identity. We build the following tableau:

For the auxiliary problem, we have $c_B^{\prime }=(1,1,1)$, while the costs for the rest of variables are $c_i=0$, $i=1,\dots ,n$. Evaluating the reduced costs for each one of the original variables $x_i$, we obtain $c_i-c_B^{\prime }{A}_i=-(1,1,1)A_i$. Thus, the initial auxiliary tableau is:

We choose $x_3$ to enter the basis and $x_8$ to exit the basis. To get the pivot element to become one and all other entries of the pivot column to become zero, we add the pivot row to the zeroth row and divide the pivot row by the pivot element $3$.

Now let $x_1$ enter the basis and $x_6$ exit the basis. Repeating the procedure, we add double the pivot row to the zeroth row and one-third of the pivot row to the third row:

Now let $x_2$ enter and $x_7$ exit. Again, to get the pivot element to become one and all other entries of the pivot column to become zero, add the pivot row to the zeroth row; add the three times of the pivot row to the first row; subtract one-third of the pivot row from the third row; finally, multiply the pivot row by $-1$. The resulting tableau is:

Note that the cost of the auxiliary problem has dropped to zero, indicating that we have a feasible solution to the original problem. Since we have removed all of the artificial variables as well, we can move on to the second phase.

Phase II. From the previous part we deduce the following initial tableau for the original problem:

We start the simplex search. Choose $x_5$ to exit the basis and $x_1$ to enter. To do so, add five times the pivot row to the zeroth row and subtract one-third of the pivot row from the third row:

Now $x_2$ exits and $x_4$ enters. We add $\frac{82}{7}$ times pivot row to the zeroth row, $\frac{17}{7}$ times pivot row to the first row, and subtract $\frac{4}{3}$ of the pivot row from the third row:

We have now reached the point $x^{\text{∗}}=\left(0,0,\frac{1}{3},0,2\right)$ and its optimality is confirmed by observing that all reduced costs at this point are nonnegative. The optimal cost is thus $3$.