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 - Feasible sets?

  1. Sep 14, 2011 #1
    1. The problem statement, all variables and given/known data

    Consider the following LOP K:

    Max [tex]z = 4x_1 + 3x_2[/tex]


    [tex]7x_1 + 6x_2 \leq 42[/tex]

    [tex]2x_1 - 3x_2 \geq -6[/tex]

    [tex]x_1 \geq 2, x_1 \leq 5, x_2 \geq \frac{1}{2}[/tex]

    (a) Decide whether the solution sets are feasible

    i) [tex]x = (3.5, 2.5)^t[/tex]
    ii) [tex]x = (2.1, 4)^t[/tex]
    iii) [tex]x = (5,1/2)^t[/tex]

    (b) Graph the system of constraints of K. Label the corner points

    (c) Draw the line z = 12 and z = 24 on the graph

    (d) Estimate where the optimum occurs

    3. The attempt at a solution

    (a) Does the t mean transpose? If not, I have no idea what to do. There's a lot of weird words in this course I am taking.

    (b) [PLAIN]http://img707.imageshack.us/img707/9267/unledwuj.png [Broken]

    (c) I don't know what this means, z(x_1, x_2), that's a plane

    (d) ONe of the corners? No computation? Confused
    Last edited by a moderator: May 5, 2017
  2. jcsd
  3. Sep 14, 2011 #2


    Staff: Mentor

    a) Yes, the t means transpose.

    Also, I'm not happy with the phrasing "Decide whether the solution sets are feasible"
    What you are given for i), ii), iii) are just points, and you should determine whether they are in the "feasible region" or "feasible set". This set is all of the points that satisfy your constraints.

    b) Your graph of the feasible region is not quite right. The inequality you have wrong is x2 >= 1/2. Your graph shows x2 <= 1/2

    c) z is a function of x1 and x2, so z(2, 5) for example, means the value you get if you put 2 in for x1 and 5 in for x2.
    This is NOT a plane - it's a line.
    They are asking you to draw the lines 4x1 + 3x2 = 12 and 4x1 + 3x2 = 24

    d) Draw the lines and see...
  4. Sep 14, 2011 #3
    a) Wouldn't the transpose (I know this isn't a matrix) make my solution set vertical? How would I plug that in? Why is that there?

    b) So it's the triangle above my pink region right? (the white triangle, yes i realize there are 4 triangles in my picture)

    c) Wow that's confusing!

    d) Will do
  5. Sep 14, 2011 #4
    [PLAIN]http://img607.imageshack.us/img607/8898/unledcz.png [Broken]

    I will draw the lines later
    Last edited by a moderator: May 5, 2017
  6. Sep 14, 2011 #5


    Staff: Mentor

    All they are doing is writing 2D points as column vectors. It's nothing more than that.
    Not quite. Your "triangle" has four sides.
    I know you can do it.
    Think of it like this:
    z = f(x1, x2) = 4x1 + 3x2.

    It's true that z = 4x1 + 3x2 is a plane in R3, but what we're looking at here is the intersection of this plane with the planes z = 12 and z = 24. These intersections are also called contour lines.
    What is the "locus of points in the plane" such that z = f(x1, x2) = 12? z = f(x1, x2) = 24?
    These are nothing more than straight lines.
  7. Sep 14, 2011 #6
    Mark, I hope you are here tomorrow and on the weekend LOL. The drawing takes some time, I will finish the lines tomorrow. Thanks
  8. Sep 15, 2011 #7
    a) All they are doing is writing 2D points as column vectors. It's nothing more than that.

    They are vectors?? They look like points. WHy would they do that? Actually why would my professor do that?

    b) Some quadrilateral -trapezoid thing.

    [PLAIN]http://img262.imageshack.us/img262/2933/unled.png [Broken]

    I still don't know where to guess
    Last edited by a moderator: May 5, 2017
  9. Sep 16, 2011 #8


    Staff: Mentor

    For a) are the three points in your feasible region or not? That's all you need to say. For some reason your instructor is writing points as vectors. Big deal.
    b) done
    c) You need to graph 4x1 + 3x2 = 24 and 4x1 + 3x2 = 12. These are parallel lines.
    d) The optimum point will be the point in the feasible region (yes, it will be a corner point) that is closest to the two lines of part c).
  10. Sep 16, 2011 #9
    Yeah my lines are on there in the picture.

    How do you know it will be inside the two lines? How did he even know what line to choose?
  11. Sep 16, 2011 #10


    Staff: Mentor

    I just did a more careful drawing of the feasible region, and have discovered a mistake in yours. The feasible region should have five sides, not four as you have drawn. The line 2x - 3y = -6 has an x-intercept at (-3, 0) and a y-intercept at (0, 2). Your drawing has these reversed. (I've switched to using x and y instead of using subscripts on x.)

    In my drawing, one of the lines passes through the feasible region, but the other one is completely outside it. The objective function, z = 4x + 3y, gets larger as both x and y increase. Assuming that your goal is to maximize the objective function, you want the line that is farthest from (0, 0), but still lies inside or just touches the feasible region.
  12. Sep 16, 2011 #11


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    The objective function, z = 4x + 3y, can be thought of as giving a family of parallel lines -- a different line for each different value of z. Solving z = 4x + 3y for y gives:
    [itex]\displaystyle y=-\frac{4}{3}x+\frac{z}{3}[/itex]​
    This represents a family of lines each with a y intercept of z/3 and all with slope of -4/3 . The maximum z occurs for the line in this family that has the largest y-intercept, but which also intersects the feasible region. This is consistent with what Mark has pointed out.
  13. Sep 16, 2011 #12
    1) How exactly do show that it is a feasible set? Like for (3.5, 2.5), do I just ue the inequalities?

    [tex]1/2 \leq 3.5 \leq 5[/tex]
  14. Sep 16, 2011 #13


    Staff: Mentor

    In part b you are asked to sketch the feasible region, which you did, but with the error noted in post #10. You should be able to tell from your sketch, whether a point is in the feasible region.
  15. Sep 16, 2011 #14
    [PLAIN]http://img600.imageshack.us/img600/4136/unledclp.png [Broken]
    Last edited by a moderator: May 5, 2017
  16. Sep 16, 2011 #15
    Yeah but how do I show that to the grader?
  17. Sep 16, 2011 #16


    Staff: Mentor

    How are you going to show the grader that you have sketched the feasible region? If the grader sees your sketch, he/she will also be able to see whether the point (3.5, 2.5) is in the feasible region.
  18. Sep 16, 2011 #17
    For d) it asked me to "guess", you said it would be the farthest point from the origin (which make sense), but I think they want us to give them a point and explain why?

    That sounds tedious seeing I might have to use the distance formula for each point?
  19. Sep 16, 2011 #18


    Staff: Mentor

    It says, "Estimate where the optimum occurs".
    USE THE SKETCH - you don't need to calculate any distances. Look to see which corner point of the feasible region is closest to whichever line is outside the feasible region.

    You are really overthinking this stuff...
  20. Sep 17, 2011 #19


    User Avatar
    Science Advisor

    By drawing the feasible region and marking the point.
  21. Sep 17, 2011 #20
    OKay I checked my prof's solution on another similar problem and I am suppose to put my points into all of the constraints and show that it satisfies the inequality.

    Kinda stupid but okay
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook