Special Cases By Looking At A Simplex

Question

Given the following simplex tableau

Find $\alpha, \beta, \gamma, \epsilon, \eta$ such that:

1. The current solution is optimal, but there are infinite optimal sloutions

2. The problem is unbounded

3. The current solution is feasible but not optimal

4. The current solution is not a sloution

So for 2 I take:

for 3:

for 4:

But for 1 I am not sure, how can I be sure that there are infinite solutions?

Answer 1

For 1 you need two ingredients: a) the solution should be optimal, and b) you should be able to let a different variable enter the basis without changing the optimal value.

The idea for the second ingredient is that if you have two optimal solution, a convex combination of them is also optimal.

For (a), you need $\delta \geq 0$ while for (b) you need $\delta \leq 0$ (since a variable should enter the basis), so $\delta=0$.

Note that due to due $-1$ in the second column, $x_3$ remains in the basis.

If $x_1$ enters the basis in lieu of $x_4$, you need $\alpha \geq 0$, and either $\gamma<0$ or $1/\alpha \leq \beta / \gamma$. An example of a solution is $\alpha=\beta=\gamma=1$, $\delta=\eta=0$.

If $x_1$ enters the basis in lieu of $x_5$, you need $\gamma \geq 0$, and either $\alpha<0$ or $1/\alpha \geq \beta / \gamma$. You also need $\beta>0$ since for $\beta=0$ the solution you get after pivoting is the same as the current solution. You could use the same example as before, or construct a different one.