Simplex method - multiple optimal solutions?

Question

I have to solve this optimization problem:

$$\begin{array}{ll}\text{minimize} & z= x_1 - x_2 + 3x_3\\\\ \text{subject to} &x_1-x_2+x_3-x_4=2\\ & 2x_1-2x_2-x_3+x_5=0\\ & x_1, x_2, x_3, x_4, x_5 \geq 0\end{array}$$

I used the two-phase simplex method and this is the final tableau:

The current solution $(x_1,x_2,x_3,x_4,x_5) = (2/3,0,4/3,0,0)$ is optimal.
As you can see the reduced cost of $x_2$ is $0$ but $x_2$ is a non-basic variable; this implies that if we attempt to let $x_2$ enter the basis, then the objective-function value will not change. So we should have multiple optimal solutions. But I'm not able to let $x_2$ to enter the basis since there is $-1$ and $0$ in $x_2$ column.

Answer 1

This answer is not correct as it does not take into account unbounded sets that besides extreme points may additionally have extreme directions. I cannot delete it as it has been accepted, so it will stay for history.

---

The reduced cost for a non-basic variable is not enough to conclude that we have multiple optimal solutions. For that to be the case it is necessary also that this non-basic variable can enter the basis, in other words, it should have a proper pivot element in the column to be picked. The variable $x_2$ has no candidate for the pivot (no positive elements at all), so it cannot be made basic. Conclusion: the optimal solution is unique.

Answer 2

The proposed answer is not right.

The tableau has a reduced cost for a non-basic variable equal to $0$. This means that there are alternative optimal solutions. As it is not possible to go to another extreme point (the column $y_2$ is $\le 0$), there are optimal solutions which are obtained as: $x^* + \lambda(-y_2,e_2)$, where $(-y_2,e_2)$ is an extreme direction, so the multiple solutions are:

$\left(\frac 23,0,\frac43\right)' + \lambda(1,1,0)' = \left(\frac23+\lambda, \lambda, \frac43\right)'$ for $\lambda \ge 0$.

So, as an example, you can observe that when $\lambda=1$ you obtain the solution $\left(\frac 53,1,\frac 43\right)$ which is feasible and also optimal.

Answer 3

The answer that @mathematician provided is correct. Consider this image with an unbounded feasible region. By considering an objective function similar to $f(x)$ and $g(x)$ in the image, the black point is the optimal solution. Now here, we have multiple optimal solutions and the red line is the extreme direction and the solutions on that are also optimal.

The simplex tableau in the question is similar to this case. If there is a non-basic variable and all the values in its column are non-positive, the feasible region is unbounded under that direction (which again, is the case in the simplex tableau of this question)