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

$\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?

-
Do you know how the simplex method works? Starting with $t_1 = t_2 = 0$, it shouldn't take more than a few iterations. – Mike Spivey Dec 15 '11 at 21:00
draw a picture of the inequalities to see they define an unbounded region – yoyo Dec 15 '11 at 21:21
In particular, note that if $t_1-t_2\leq 1$ and $t_2\geq 0$, then $t_1-2t_2\leq 1< 8$ so the condition $t_1-2t_2\leq 8$ is redundant. – Thomas Andrews Dec 15 '11 at 22:22

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.

-
Your argument is missing one small piece. Infeasibility of the dual implies that either the primal is unbounded or the primal is infeasible. It's easy to show the latter isn't the case, though; $t_1 = t_2 = 0$ is feasible for the primal. And then your argument goes through from there. – Mike Spivey Dec 17 '11 at 21:13