Graphical Sensitivity Analysis of LP

[USN2ENG]

Homework Statement

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.

Homework Equations

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!

 

[Ray Vickson]

Homework Statement

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.

Homework Equations

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!

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.)

 

[USN2ENG]

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,

Chuck

 

[Ray Vickson]

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,

Chuck

Yes, the true feasible region is a segment of the line 4x + 2y = 7, pointing southeast from the y-axis.

 

[USN2ENG]

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.