0
$\begingroup$

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

  • 0
    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.2011-12-15

1 Answers 1

4

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.

  • 0
    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. A$n$d then your argument goes through from there.2011-12-17