# Linear Programming

1. Aug 25, 2009

### songoku

1. The problem statement, all variables and given/known data

Sketch the area that fulfills :
x + y ≥ 1
3y ≥ 2x - 1
2y ≤ 3x

and find the range of x and y that are restricted.
Find the maximum value of y – 2x that satisfies the area above and find also the value of x

2. Relevant equations
Line equation

3. The attempt at a solution

I've drawn the graph and got :

I'm not sure about finding the range of x and y that are restricted. Do I have to find the value of x and y that are allowed or not allowed ?

And I don't think that the answer can stated in specific range for x and y. If I want to find the range of x that is allowed, I can't state that $$x\geq 0.4$$ satisfies the inequalities because there are values of $$x\geq 0.4$$ where (x,y) lie outside the shaded area.

I can state that $$x\leq 0.4$$ is not allowed, but there are some values of $$x\geq 0.4$$ that are also not allowed...

For maximum value of y - 2x, I substitute (0.4 , 0.6) to get maximum value -0.2
But I don't know how to give an argument that this is the maximum value..

Thanks

Last edited: Aug 25, 2009
2. Aug 25, 2009

### symbolipoint

My not-very-smart question is, did you mistreat the condition equations and then pick the wrong region to analyze? Are you really interested in the triangular region?

3. Aug 25, 2009

### songoku

Hi symbolipoint
Sorry, I don't really understand what your point is. My solution, based on the graph I posted, is the shaded area (infinite area) and not triangular region. I've checked it once again and I think the shaded area satisfies the three inequalities.

Thanks

4. Aug 25, 2009

### symbolipoint

Usually my common exercises and tasks did not directly use linear programming. What I should have said was, "mishandled", and not "mistreated". I should also have actually tried to determine the shaded ("feasable") region myself. Linear programming was hardly emphasised in my own courses, only having a brief mention and examples in one course so very long ago.

5. Aug 25, 2009

### Staff: Mentor

I can't offer much help on how to describe the range of x and y values, but your minimum value at (.4, .6) looks to be correct. Here's how you can justify this result. You want to find the maximum value of y - 2x, so consider the equation y - 2x = k. For each value of k, the graph of y - 2x = k is a straight line with slope 2 and y-intercept (0, k). If k = -.2, the line y - 2x = -.2 just touches the point (.4, .6). moving the line upward but keeping the same slope (i.e., using a larger value of k) causes the line to not intersect the feasible region. Moving the line downward (using smaller values of k) causes the line to intersect the feasible region but results in smaller value of y - 2x.

Does that make sense?

6. Aug 25, 2009

### songoku

Hi symbolipoint and Mark44

Your explanation is very good, Mark. I understand it ^^
And now the last problem is to find the restricted range for x and y. The best answer I can come up now is that I interpret the question is asking to find the range of x and y that are not allowed. So, the answer :

$$x\leq 0.4$$

$$y\leq 0.2$$

But I am definitely not sure of my answer..

Thanks

Last edited: Aug 25, 2009
7. Aug 26, 2009

### Дьявол

Hello songoku!

And why do you believe that for $x \geq 0.4$, there are values which are allowed and non-allowed. Could you possibly provide one which is not-allowed?

Regards.

8. Aug 26, 2009

### songoku

Hi Дьявол

One example is (0.4, 1). And other coordinates that don't lie in the shaded area.

Thanks

9. Aug 26, 2009

### HallsofIvy

Staff Emeritus
To find "the range of x and y that are restricted" (very awkward wording) means to find the "feasible region" and that is the shaded area on your graph.

To show that -0.2 is, in fact, the maximum, draw a few graphs of y-2x= a or y= 2x+ a for different values of a. You should see that, as a increases, the linear graphs move "up and to the left" and that one of the lines, y= 2x- 0.2, passes through the vertex (0.4, 0.6). The key concept in linear programming is that a linear function takes on its maximum or minimum on a convex polygonal reason at a vertex.

10. Aug 26, 2009

### songoku

Hi Mr. HallsofIvy

Oh so I have to find the range of x and y that lie on the shaded area. How to answer the question appropriately ? I think the best answer is just the same as the question :

x + y ≥ 1
3y ≥ 2x - 1
2y ≤ 3x

But it's so weird to have the answer exactly the same as the question...

Thanks

11. Aug 26, 2009

### Staff: Mentor

I believe that what HallsOfIvy is saying is that your graph of the feasible region is the description the problem is asking for.

12. Aug 26, 2009

### HallsofIvy

Staff Emeritus
Yes, the graph you show is the answer to that question!

13. Aug 26, 2009

### songoku

Hi Mark44 and Mr. HallsofIvy

Oh my god. I answered the question without even realizing it...

Thank you so much for your help !