How to apply the simplex method to prove that the following problem is unbounded?

Question

$\max 6t_1 + 4t_2$

$-t_1 + t_2 \leq 6$

$t_1 - t_2 \leq 1$

$t_1 - 2t_2 \leq 8$

$t_1, t_2 \geq 0$

Anyone?

Answer 1

If you have been taught the relationship between the primal and dual forms of a linear program then you can take advantage of the fact that if the primal is unbounded then the dual is infeasible.

The dual constraints can be written as:

$-y_1 + y_2 +y_3 \ge 6$

$y_1-y_2-2y_3 \ge 4$

and

$y_1 \ge 0$, $y_2 \ge 0$ and $y_3 \ge 0$.

Adding up the first two inequalities we get:

$-y_3 \ge 10$ which is incompatible with the condition that $y_3 \ge 0$.

Thus, the dual constraints are infeasible which implies that the primal is unbounded.