Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.