Results 1 to 6 of 6

Math Help - LP help

  1. #1
    Senior Member Danneedshelp's Avatar
    Joined
    Apr 2009
    Posts
    303

    LP help

    Q1: Suppose that the following constraints have been provided for a linear programming model.

    -x_{1}+2x_{2}\leq\\50 (1)
    -2x_{1}+x_{2}\leq\\50 (2)

    and

    x_{1}\geq\\0, x_{2}\geq\\0.

    a) Demonstrate that the feasible region is unbounded.
    b) If the objective is to maximize Z=-x_{1}+x_{2}, does that model have an optimal soultion? If so, find it. If now, explain why not.
    c) Repeat part (b) when the objective is to maximize Z=x_{1}-x_{2}.


    Does "unbounded" mean something specific when dealing with LP problems? When, I graph the above lines, I am not sure where the feasible region is, since the inequality tells me to shade below both lines in the first quadrant. Furthermore, since line (2) is above line (1) I have to shade over line (1) down to the horizontal axis, which doesn't seem right, as that would mean the constraints are not being satisfied. Does this mean the the feasible region is unbouned? Also,

    Moreover, if the feasible region is unbouned and the gradiants of both objective functions from parts (b) and (c) are in directions away from the first quadrant, how can there be optimal solutions?


    Q2: Minimize Z=15x_{1}+20x_{2}

    subject to:

    x_{1}+2x_{2}\geq\\10 (1)
    2x_{1}-3x_{2}\leq\\6 (2)
    x_{1}+x_{2}\leq\\6 (3)

    and x_{1}\geq\\0,x_{2}\geq\\0.

    For this question, I am also not sure where my feasible region is (or if one even exists). I have graphed all the lines and drawn arrows in the direction of the inequality signs, but I am not sure where to shade. I am assuming this means there is no feasible region.

    Should I be checking to makie sure the inequalities hold or do I just assume they do and and shade above or below the lines accordingly?

    Thanks in advanced for your time



    disclaimer: My entire second week of class has been cancled due to snow days, so I only have one example of how to solve an LP in my notes and have yet to recieve my text book. Thats my excuse for these elementary questions....
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Linear Programming

    Hello Danneedshelp
    Quote Originally Posted by Danneedshelp View Post
    Q1: Suppose that the following constraints have been provided for a linear programming model.

    -x_{1}+2x_{2}\leq\\50 (1)
    -2x_{1}+x_{2}\leq\\50 (2)

    and

    x_{1}\geq\\0, x_{2}\geq\\0.

    a) Demonstrate that the feasible region is unbounded.
    b) If the objective is to maximize Z=-x_{1}+x_{2}, does that model have an optimal soultion? If so, find it. If now, explain why not.
    c) Repeat part (b) when the objective is to maximize Z=x_{1}-x_{2}.


    Does "unbounded" mean something specific when dealing with LP problems? When, I graph the above lines, I am not sure where the feasible region is, since the inequality tells me to shade below both lines in the first quadrant. Furthermore, since line (2) is above line (1) I have to shade over line (1) down to the horizontal axis, which doesn't seem right, as that would mean the constraints are not being satisfied. Does this mean the the feasible region is unbouned? Also,

    Moreover, if the feasible region is unbouned and the gradiants of both objective functions from parts (b) and (c) are in directions away from the first quadrant, how can there be optimal solutions?
    (a) You're right in saying that the shading for line (2) goes over all the shading for line (1), leaving the feasible region just the same as that obtained by line (1) together with x_1\ge0, x_2\ge0.

    This region extends infinitely far to the right and upwards, and so is unbounded. In other words, you can find values of x_1 and x_2 as large as you like and both inequalities will be satisfied. For example, if you want to make x_2 = 1\,000\,000, just take x_1 = 2\,000\,000, and both inequalities are satisfied.

    It's very easy to decide which side of the line to shade. Choose a point not on the line (if the line doesn't pass through the origin, then choose the origin), and check to see whether the condition is satisfied at this point. If it is, shade that side; if not, shade the other side.


    So for both (1) and (2), the values x_1 = 0 = x_2 satisfy both inequalities. Therefore the origin is on the side to be shaded in each case.

    (b) To maximise Z = -x_1+x_2, draw the line -x_1+x_2 = 0 (in other words, the line x_1 = x_2) and then try to find the line parallel to that whose intercept with the x_2 axis is as large as possible, subject to at least one point on the line lying within the shaded region. This intercept is at (0,25) giving a maximum value Z = 25.


    (c) We draw the same line again ( x_1=x_2), but this time, since x_2 = x_1-Z, we need to make the intercept as far down as possible, to make Z a maximum. Since the region is unbounded to the right, there is no limit to the lowest intercept possible. Hence Z can be made as large as you like. (In the example that I gave above, Z = 2\,000\,000-1\,000\,000 = 1\,000\,000, for instance.)

    Q2: Minimize Z=15x_{1}+20x_{2}

    subject to:

    x_{1}+2x_{2}\geq\\10 (1)
    2x_{1}-3x_{2}\leq\\6 (2)
    x_{1}+x_{2}\leq\\6 (3)

    and x_{1}\geq\\0,x_{2}\geq\\0.

    For this question, I am also not sure where my feasible region is (or if one even exists). I have graphed all the lines and drawn arrows in the direction of the inequality signs, but I am not sure where to shade. I am assuming this means there is no feasible region.

    Should I be checking to makie sure the inequalities hold or do I just assume they do and and shade above or below the lines accordingly?

    Thanks in advanced for your time

    disclaimer: My entire second week of class has been cancled due to snow days, so I only have one example of how to solve an LP in my notes and have yet to recieve my text book. Thats my excuse for these elementary questions....
    Look at the diagram I've attached.

    Using the technique I outlined above, choosing the origin as my test point, I found the origin is on the 'wrong' side of line (1), but it's on the 'right' side of lines (2) and (3). Hence the only feasible area is the triangle I've shaded.

    I've drawn in the optimum ' Z line' to make Z a minimum. This is the line that passes through (0,5), giving the minimum value of Z = 100.

    Grandad
    Attached Thumbnails Attached Thumbnails LP help-untitled.jpg  
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Danneedshelp's Avatar
    Joined
    Apr 2009
    Posts
    303
    Quote Originally Posted by Grandad View Post


    Look at the diagram I've attached.

    Using the technique I outlined above, choosing the origin as my test point, I found the origin is on the 'wrong' side of line (1), but it's on the 'right' side of lines (2) and (3). Hence the only feasible area is the triangle I've shaded.

    I've drawn in the optimum ' Z line' to make Z a minimum. This is the line that passes through (0,5), giving the minimum value of Z = 100.

    Grandad
    Thank you very much for all your help and time.

    I do have one last question though. I am not seeing how you got the feasible region illustrated in the above attachment, since we are concerend with the region below line (2). In you illustration, the afore mentioned constraint isn't accounted for, correct?

    Nevertheless, I used the solver tool in excel to do this problem and got the same solution you posted. So, I am clearly seeing this problem incorrectly. Some clarification would be much appreciated.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hello Danneedshelp
    Quote Originally Posted by Danneedshelp View Post
    Thank you very much for all your help and time.

    I do have one last question though. I am not seeing how you got the feasible region illustrated in the above attachment, since we are concerend with the region below line (2). In you illustration, the afore mentioned constraint isn't accounted for, correct?

    Nevertheless, I used the solver tool in excel to do this problem and got the same solution you posted. So, I am clearly seeing this problem incorrectly. Some clarification would be much appreciated.
    We want the side of line (2) that contains the origin - which is the region above the line.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Danneedshelp's Avatar
    Joined
    Apr 2009
    Posts
    303
    Quote Originally Posted by Grandad View Post
    Hello DanneedshelpWe want the side of line (2) that contains the origin - which is the region above the line.

    Grandad
    Due to the non-negativity constraint?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hello Danneedshelp
    Quote Originally Posted by Danneedshelp View Post
    Due to the non-negativity constraint?
    No - it has nothing to do with that. Condition (2) is:
    2x_1-3x_2\le6
    At the origin:
    2x_1-3x_2= 0, and 0\le6
    So the origin lies on the side of the line where values of x_1 and x_2 satisfy condition (2); i.e. the region 'above' the line.

    The points representing the possible solutions to the problem lie in the region that is the intersection of the five regions that satisfy each individual inequality (including the non-negativity ones). If you study these five regions, you'll see that it's only the triangle I have shaded light blue that satisfies them all.

    Grandad
    Attached Thumbnails Attached Thumbnails LP help-untitled.jpg  
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum