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
    Do you know how the simplex method works? Starting with $t_1 = t_2 = 0$, it shouldn't take more than a few iterations.2011-12-15
  • 0
    draw a picture of the inequalities to see they define an unbounded region2011-12-15
  • 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. And then your argument goes through from there.2011-12-17