After the problem is solved and an optimal solution is obtained, a set of analysis is often conducted to determine the sensitivity of the optimal solution to changes in problem data, most commonly the objective function coefficients of variables and the right hand sides of constraints. These analyses are generally conducted by changing one dataelement at a time holding all other data constant.

• Clearly understand the difference between a problem datum and a problem variable. In sensitivity, we are allowing one of the problem data to vary, to see what happens to the optimality of the current solution (a set of values assigned to decision variables).
• Example

     Max 5000E + 4000F
     st      E + F       >= 5
             E - 3F      <= 0
           20E + 10F     <= 160
           10E + 15F     <= 150    
           30E + 10F     >= 135

---




---

[Objective Function] [Right Hand Sides]
• Optimality of point C is preserved for certain changes in the objective function coefficients of the variables (like in the case of the red contour) while the optimality shifts to point B, for a more drastic change in the objective function (as in the case of the green contour).
• The critical question of sensitivity analysis is how drastically a coefficient (data) has to change, before the current solution is no longer optimal --or before the optimal point shifts to another point.

Sensitivity of the optimal solution (point C) to changes in the coefficient of F

1. Increases in the coefficient of F.
• As F becomes more profitable every contour will become flatter since for any given level of total profit we will now need fewer Fs than before. If the contours do not become as flat as the line segment BC, point C will continue being optimal. When, however ,the contour is as flat as line BC, there will be two optimal corners -- points C and B. Any further increase in F's coefficient will make the contour too flat to be tangent at C making point B the unique optimal.
• We therefore want to calculate the increase in F's coefficient which makes points C and B optimal at the same time (or equivalently, it makes the slopes of the contours equal to the slope of line BC).
• Using the first argument (namely at the allowable maximum of F's coefficient points B and C are alternative optima) we can calculate this maximum allowable value. Let ? stand for the coefficient of F.
OV at point C (E=4.5, F=7) equals OV at B (E=1.5, F=9) or
5000*4.5 + ? * 7 = 5000*1.5 + ?*9 solving for "? " we find $7500.
• So, as long as the coefficient of F does not increase beyond $7500 point C will remain optimal; at $7500, both point C and point B will be optimal; and for values more than $7500, point B will be the unique optimal.
• We can reach the same conclusion by searching for the coefficient of F that will make the contours as flat as the line segment BC. We can calculate the slope of a linear line as minus the coefficient of the first variable (X axis)/the coefficient of the second (Y axis). Thus, we want
slope of a contour = slope of BC
-5000/? = -10/15 solving for ? we obtain $7500 as before.
• Notice that when F becomes sufficiently profitable the solution shifts counter-clock wise to take advantage of the more favorable price for F. At the new optimum more F's are made (9 now) at the expense of E's (only 1.5 now).
2. Decreases in the coefficient of F.
• As F becomes less profitable, the contours will become steeper. If they become steep enough, the optimal solution will move in the clock wise direction-- to point D (E= 6.86, F= 2.29). Hence:
5000*6.86 + ?*2.29 = 5000*4.5+?*7 Solving for ? we find $2,500. Also, from the equality of the slopes of the contours and line CD: -?/5000 = - 10/20 we find as before the critical value to be $2500.
• We can conclude that as long as the coefficient of F stays within the interval from $2500 to $7500, the current optimal values 4.5 for E and 7 for F (point C) will remain optimal. Notice however, that although the solution is not changing, the objective function value is changing . In fact, within this range, the objective function value changes at a rate equal to the optimal value of the variable whose coefficient is varying. In the example this is variable F and its optimal value is 7. Thus every dollar increase in the coefficient of F will produce a $7 increase in the OV as we are making and selling 7 units of F.




Sensitivity of the Optimal Solution to Changes in the Right Hand Sides of Constraints

---




---

• When the right hand side of a constraint changes, the constraint boundary will move parallel to itself. This will generally change the feasible region having no effect on the slopes of the objective function contours.
• When the RHS of a "<=" type constraint increases , the constraint moves in a direction making the feasible region larger. This is called loosening the constraint. Decreases in the RHS of a "<=" constraints will tighten the constraint. For a ">=" type constraint the tightening and loosening directions are reversed.
• In the graph if the RHS of 30E + 10F >=135 ( BA) increases, the constraint moves in the North-East direction shrinking the feasible region, while if the RHS of 20E + 10F <= 160 (CD) increases, the feasible region will grow.
1. Changing the RHS of an Inactive Constraint .
Consider 30E + 10F >= 135. This is an inactive constraint with a surplus of 70 units at the point of optimality. If the RHS, decreases line BA moves away from point C, preserving its optimality; the OV stays the same; only the surplus of the constraint increases by an amount equal to the decrease in the RHS.
• If the RHS increases the constraint moves towards point C. As long as point C remains on the feasible side of the constraint, its optimality is unaffected; OV stays the same; only the amount of surplus decreases. When the constraint shifts sufficiently (by the amount of the surplus) to pass through point C the constraint becomes active. Any further decrease forces the optimal point, C  to slide down toward point D along line CD.
• Thus we can conclude that RHS of an inactive constraint can change without any bound in the loosening direction, and can change by the amount of the slack/surplus in the tightening direction. In this example the RHS can vary from minus infinity to 205 without altering the optimality of point C.
2. Active Constraint 

   ---

   



---

• Consider 10E + 15F <=150, an active constraint passing through point C. When the RHS of this constraint decreases, the coordinates of C changes as it slides down along the line CD towards D. However, point C will remain optimal (albeit with different E and F values) until point D is reached.

This happens when the RHS is equal to: 10*(6.86) + 15*(2.29) = 102.95.

where 6.86 and 2.29 are the E and F coolrdinates at point C.


• If, on the other hand, the RHS increases, the constraint moves up, making the feasible region larger and moving the point of optimality upwards. This pattern will continue as long as the constraint remains active. Verify that the constraint remains active until point (0,16) is reached and that this happens for a rhs of 240whic is the value for which the constraint passes at point (E=0 and F=16) or  10E + 15F = b, plugging E=0 and F=16 we find  b=240.

• Thus as the RHS of the constraint changes from 240 to 102.95, point C (the intersection of CD and BC) stays optimal; the values of the variables change; the OV changes (increases as the constraint becomes looser, decreases if as it becomes tighter). This rate at which the OV changes is referred to as the shadow price of the constraint.

• The shadow price can be obtained by calculating the OV at the original optimum point C (4.5, 7). This is is $50,500. And the OV at point D  (6.86, 2.29) -- the optimum solution for a rhs of 102.5. The OV at point D is $43,460. Thus when the rhs goes down by 150-102.5 = 47.5 units, the OV goes down by $50,500- $43,460 = $7040. The per unit change in the OV then is $7,040 / 47.5 = $148.21 (the shadow price). Each unit of decrease in the rhs of the constraint causes a $148.21 decrease in the OV.
Main Sensitivity Principles