1

I have the following question to tackle:

Maximize $x_1$ and $x_2$ for:

$$ x_1, x_2 \geq 0$$

$$ -x_1 + x_2 \leq 5$$

$$ x_1 + 4x_2 \leq 45$$

$$ 2x_1 + x_2 \leq 27$$

$$3x_1 - 4x_2 \leq 24$$

So I just wrote out these constraints as the following functions:

$$ y \leq -x+5$$

$$ y \leq \dfrac{1}{4}x+ \dfrac{45}{4}$$

$$ y \leq -2x + 27$$

$$ y \geq \dfrac {3}{4}x - 6$$

But then I realized; I have no idea what to do here. What do they mean with 'maximize $x_1$ and $x_2$?! From what I can see with my graphing calculator, $y\leq -x+5$ seems to be the only constraint which actually matter, and it has 2 vertices (namely the y-intercept and the x-intercept). Do they perhaps mean that you should maximize $x_1$ and $x_2$ seperately? (i.e. the maximum of $x_1$ is the x-intercept and the maximum of $x_2$ is the y-intercept?) I haven't got the faintest idea.

Also, I don't get how we can have the constraint $y \geq \dfrac{3}{4}x -6$. It seems to contradict the 3 above constraints!

Ylyk Coitus
  • 970
  • 2
  • 10
  • 18
  • "Do they perhaps mean that you should maximize x1 and x2 seperately? ... I haven't got the faintest idea." Neither do we. "Maximize $x_1$ and $x_2$" does not make sense. – leonbloy Apr 01 '13 at 21:04

1 Answers1

1

This is a linear programming problem. I suggest you reading about simplex method. Maximizing $x_1 + x_2$ is the same as minimizing $-x_1-x_2$.

I will present you a geometric solution. Draw all the conditions in the plane and if you do it right you should get an area bounded by 6 lines: $x=0$, $y=0$, $y=x+5$, $y=\frac{45}{4} - \frac{x}{4}$, $y=27-2x$, and $y=-6+\frac{3x}{4}$. The solution is then one of the vertices of this polygon. Its vertices are: $(0,0),(0,5),(5,10),(9,9),(12,3)$ and $(8,0)$. Choose the right one.

UrošSlovenija
  • 915
  • 2
    I think substituting $+$ for and is a reasonable guess. – Ross Millikan Apr 01 '13 at 21:27
  • Choose the right one. Really, you think that helps? – Ylyk Coitus Apr 01 '13 at 22:16
  • @RossMillikan What do you mean? – Ylyk Coitus Apr 01 '13 at 22:19
  • @YlykCoitus: This answer assumes we are being to maximize $x_1+x_2$ instead of $x_1$ "and" $x_2$. Sometimes people read a plus sign as "and". I was just saying that seemed a good way to translate the problem to one that could be understood and solved. – Ross Millikan Apr 01 '13 at 22:24
  • @RossMillikan Oh, that's what you meant. But I still don't get how to do this. Isn't this answer wrong? The constraint $-x_1 + x_2 \leq 5$ makes the other ones redundant, right? Also, I still don't know what he means by 'choose the right one'. Right doesn't sound too mathematical for me. – Ylyk Coitus Apr 01 '13 at 22:28
  • @YlykCoitus: The other constraints are not redundant. As UrošSlovenija says, each constraint gives a line in the plane with the allowed region on one side of the line. The intersection of these regions is a hexagon with the corners he gave. A fundamental theorem of linear programming is that the optimal solution will be at one of the corners of the feasible region. This region has few enough corners you can just evaluate the objective function $x_1+x_2$ at all the corners and the highest one is the winner. – Ross Millikan Apr 01 '13 at 22:40
  • @YlykCoitus: when there are many more variables and constraints there will be too many to try them all. The simplex method gives a systematic way of finding the best one. But as long as you can try them all, that is a fine approach. – Ross Millikan Apr 01 '13 at 22:41
  • @RossMillikan But this is what I don't understand: The feasible region in this case, why is it bounded by the polygon? If you graph it, you see that $y\leq -x+5$ So everything to the right of that (which includes all other constraints) should not matter. Why am I incorrect? Also, what do you mean evaluate the objective function $x_1 + x_2$? We don't have it in this question right? – Ylyk Coitus Apr 01 '13 at 22:50
  • @YlykCoitus: You should have $y \le x+5$. When you moved the $x$ to the right you forgot to flip the sign – Ross Millikan Apr 01 '13 at 23:13