Graphical Sensitivity Analysis of LP

In summary, the student attempted to find a solution to a system of equations by using the simplex method. However, they ran into some confusion and eventually decided to drop the third constraint. They found that x = 1, y = 1.5, and z = 5.5 were the solution and that c1 = 3/2 and c2 = -2 were needed in order to remain optimal.
  • #1
USN2ENG
108
0

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!
 
Physics news on Phys.org
  • #2
USN2ENG said:

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.)
 
  • #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,

Chuck
 
  • #4
USN2ENG said:
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.
 
  • #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.
 

1. What is Graphical Sensitivity Analysis of LP?

Graphical Sensitivity Analysis of LP is a method used in linear programming (LP) to visually analyze the impact of changes in the parameters of a LP model on the optimal solution. It involves plotting the objective function and constraints on a graph to identify the range of values for the parameters that do not affect the optimal solution.

2. Why is Graphical Sensitivity Analysis important in LP?

Graphical Sensitivity Analysis is important in LP because it helps decision-makers understand how sensitive the optimal solution is to changes in the parameters of the model. This allows for a more informed decision-making process and can help identify potential risks and opportunities in the solution.

3. How is Graphical Sensitivity Analysis performed?

To perform Graphical Sensitivity Analysis, the objective function and constraints of the LP model are plotted on a graph. The slope of the objective function and the constraints are then analyzed to determine the range of values for the parameters that do not affect the optimal solution.

4. What are the limitations of Graphical Sensitivity Analysis?

Graphical Sensitivity Analysis has some limitations, such as being limited to models with two decision variables and two constraints. It also assumes that the objective function and constraints are linear and that the parameters can only take on a certain range of values.

5. How is Graphical Sensitivity Analysis different from other sensitivity analysis methods?

Graphical Sensitivity Analysis is a visual method, while other sensitivity analysis methods involve manipulating the parameters and observing the changes in the optimal solution. Graphical analysis is also limited to models with two decision variables, while other methods can be applied to models with multiple decision variables.

Similar threads

  • Calculus and Beyond Homework Help
Replies
24
Views
2K
  • Calculus and Beyond Homework Help
Replies
8
Views
857
  • Calculus and Beyond Homework Help
Replies
6
Views
787
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
523
  • Calculus and Beyond Homework Help
Replies
7
Views
473
  • Calculus and Beyond Homework Help
Replies
4
Views
926
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
26
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
Back
Top