1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Graphical Sensitivity Analysis of LP

  1. Sep 27, 2013 #1
    1. The problem statement, all variables and given/known data

    This was from a test I took today:

    Maximize z = 4x + y subject to:

    4x + 2y = 7
    3x + 2y >= 6
    4x + 2y <= 8

    1.Graphically solve and find x y and z
    2.What are the range of values for c1 (Coefficients of x) so that the solution remains optimal.

    2. Relevant equations

    3. The attempt at a solution

    I graphically solved and found x = 1, y = 1.5, and z = 5.5. The optimal solution is the intersection of these two constraints:
    4x + 2y = 7
    3x + 2y >= 6

    For the c1 & c2 I am running into some confusion and I am not sure why. I am assuming, because he didn't specify, that the c1 and c2 are referring to the objective function coefficients and I am finding the range of values where the solution is still optimal.

    Normally to do this you find the slope of the isoprofit line which is -c1/c2 and say that it needs to be bound between the slope of the two intersecting lines.
    Slope of (4x + 2y = 7) is -2
    Slope of (3x + 2y >= 6) is -3/2

    For c1: -2<= -c1/1 <= -3/2

    Therefore: 3/2<= c1 <= 2

    This answer makes no sense at all since the solution is already optimal and the coefficient is 4...
    Any advice on where I am messed up would be great!
  2. jcsd
  3. Sep 27, 2013 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    This case is not a 'normal' one; you have the wrong picture in mind for the feasible region! I cannot conveniently include a drawing here, but instead I can give you the final form of the equations from the simplex method.

    Note that if there is no typo in the problem, the third constraint is redundant, since the first one says that 4x+2y must = 7 and the third one says that this same quantity 4x+2y must be <= 8, which is already true because 7 < 8.

    So, assuming no typo, drop the third constraint and write the system of equations as
    z = c1*x + y, 4x + 2y = 7, 3x + 2y - s = 6, where s ≥ 0 is a surplus variable.

    Choosing x and y as basic variables we have
    z = c1 + 3/2 + (2-c1)*s, x = 1-s, y = 3/2 + 2*s.

    When c= = 4 (the original problem) we have z = 11/2 - 2*s, so it is optimal to take s = 0. This solution remains optimal as long as 2-c1 ≤ 0, or c1 ≥ 2. (Note that there is no upper bound on c1: the solution x = 1, y = 3/2 would remain optimal even if c1 = 100,000,000, for example.)

    BTW: I assume you also want x, y ≥ 0, but you did not say so explicitly. (However, even if you do allow x < 0 and/or y < 0, the above solution x = 1, y = 3/2 is still optimal whenever c1 ≥ 2.)
  4. Sep 27, 2013 #3
    Thanks a lot Dr. Vickson. This was driving me crazy trying to figure it out today. And yes, there is a non negativity constraint and the third constraint is redundant as it parallels the equality constraint. I have no clue why we did not cover this material/method, but I guess it is not the normal case like you said. I assume the only true feasible region is along the 4x +2y = 7 line, on or above its intersection with the inequality. I am going to work this out a few times to make sure I have it down. Thanks again,

  5. Sep 27, 2013 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Yes, the true feasible region is a segment of the line 4x + 2y = 7, pointing southeast from the y-axis.
  6. Sep 27, 2013 #5
    One last thing Dr. Vickson. Off the top of your head do you know anywhere where I can see more examples of this case? I have been looking through the sensitivity analysis section of my Text (OR applications and algorithms, Winston, 4th edition) and do not seem to find any with equalities (that are not done with lindo). My tests are of the non-computer, non-calculator, pencil and paper only type, so I just was hoping to get this down.

    Thanks again.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted