1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linear Programming

  1. Aug 25, 2009 #1
    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 :
    pic-2.jpg

    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 [tex]x\geq 0.4[/tex] satisfies the inequalities because there are values of [tex]x\geq 0.4[/tex] where (x,y) lie outside the shaded area.

    I can state that [tex]x\leq 0.4[/tex] is not allowed, but there are some values of [tex]x\geq 0.4[/tex] 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. jcsd
  3. Aug 25, 2009 #2

    symbolipoint

    User Avatar
    Homework Helper
    Education Advisor
    Gold Member

    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?
     
  4. Aug 25, 2009 #3
    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 :smile:
     
  5. Aug 25, 2009 #4

    symbolipoint

    User Avatar
    Homework Helper
    Education Advisor
    Gold Member

    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.
     
  6. Aug 25, 2009 #5

    Mark44

    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?
     
  7. Aug 25, 2009 #6
    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 :

    [tex]x\leq 0.4[/tex]

    [tex]y\leq 0.2[/tex]

    But I am definitely not sure of my answer..

    Thanks
     
    Last edited: Aug 25, 2009
  8. Aug 26, 2009 #7
    Hello songoku!

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

    Regards.
     
  9. Aug 26, 2009 #8
    Hi Дьявол

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

    Thanks
     
  10. Aug 26, 2009 #9

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  11. Aug 26, 2009 #10
    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
     
  12. Aug 26, 2009 #11

    Mark44

    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.
     
  13. Aug 26, 2009 #12

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Yes, the graph you show is the answer to that question!
     
  14. Aug 26, 2009 #13
    Hi Mark44 and Mr. HallsofIvy

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

    Thank you so much for your help !
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Linear Programming
  1. Linear Programming (Replies: 9)

  2. Linear programming (Replies: 5)

Loading...