Readings Readings Chapter 3 Linear Programming: Sensitivity Analysis and Interpretation of Solution BA 452 Lesson A.6 Sensitivity Analysis Theory 1 Overview Overview BA 452 Lesson A.6 Sensitivity Analysis Theory 2 Overview Sensitivity Analysis (or post-optimality analysis) determines how an optimal solution is affected by changes in the objective function coefficients or in the right-hand side constants. Sensitivity to Coefficients measures how changes in the objective function coefficients change optimal solutions. The range of optimality are those values keeping the current solution optimal. Sensitivity to Constants measures how changes in the right-hand-side

constants of constraints change optimal solutions. The dual price is the rate of improvement in the objective function. Computer Analysis computes the range of optimality of each decision variable, the dual price of each constraint, and range of feasibility for each dual price. Resource Allocation Problems with Sensitivity Analysis help production managers compute the value to them of buying additional resources to produce goods. That value guides mutually-beneficial trade. BA 452 Lesson A.6 Sensitivity Analysis Theory 3 Sensitivity Analysis Sensitivity Analysis BA 452 Lesson A.6 Sensitivity Analysis Theory 4 Sensitivity Analysis Overview Sensitivity Analysis (or post-optimality analysis) determines how an optimal solution is affected by changes, within specified ranges, in:

the objective function coefficients the right-hand side (RHS) constants That helps managers operate with imprecise estimates of the coefficients and constants of their optimization problems, helps managers ask hypothetical questions about optimization problems, such as: How much more profit could be earned if 10 more hours of labor were available?. BA 452 Lesson A.6 Sensitivity Analysis Theory 5 Sensitivity to Coefficients Sensitivity to Coefficients BA 452 Lesson A.6 Sensitivity Analysis Theory 6 Sensitivity to Coefficients Overview Sensitivity to Coefficients measures how changes in the objective function coefficients change optimal solutions. The range of optimality are those values keeping the current solution optimal.

BA 452 Lesson A.6 Sensitivity Analysis Theory 7 Sensitivity to Coefficients To begin, consider how changes in the objective function coefficients might affect the optimal solution. The range of optimality for each coefficient is the range of values over which the current solution remains optimal. Managers should be aware of those objective coefficients that have a narrow range of optimality, and of coefficients near the endpoints of the range. In those cases, the predicted optimal solutions are sensitive to any errors in the estimates of the objective coefficients . BA 452 Lesson A.6 Sensitivity Analysis Theory 8

Sensitivity to Coefficients Recall a previous Example and its graphical solution. x1 + x2 < 8 Example: Max 5x1 + 7x2 s.t. x1 < 6 2x1 + 3x2 < 19 x1 + x2 < 8 Max 5x1 + 7x2 x1 > 0 and x2 > 0 x1 < 6 Optimal solution: x1 = 5, x2 = 3

Feasible region 2x1 + 3x2 < 19 BA 452 Lesson A.6 Sensitivity Analysis Theory 9 Sensitivity to Coefficients Graph objective-function lines for alternative coefficients. An objective-function line coinciding . with the binding edge of the third constraint x1 + x2 < 8 Example: Max 5x1 + 7x2 s.t. x1 < 6

2x1 + 3x2 < 19 x1 + x2 < 8 x1 > 0 and x2 > 0 The objective-function line for the original function 5x1 + 7x2 Optimum Feasible region An objective-function line coinciding with the binding edge of the second constraint 2x1 + 3x2 < 19 BA 452 Lesson A.6 Sensitivity Analysis Theory 10 Sensitivity to Coefficients Example: Max 5x1 + 7x2 Generally, the limits of a range of optimality are

found by changing the slope of the objective function line within the limits of the slopes of the binding constraint lines. Compute the range of optimality for c1 in Example 1. The slope of an objective function line, Max c1x1 + c2x2, is -c1/c2. The slope of the binding third constraint, x1 + x2 = 8, is -1. The slope of the binding second constraint, 2x1 + 3x2 = 19, is -2/3. Find the range of values for c1 (with c2 staying 7) such that the objective-function line slope lies between that of the two binding constraints: -1 < -c1/7 < -2/3 Multiplying by -1, 1 > c1/7 > 2/3

Multiplying by 7, 7 > c1 s.t. x1 < 6 2x1 + 3x2 < 19 x1 + x2 < 8 x1 > 0 and x2 > 0 > 14/3 BA 452 Lesson A.6 Sensitivity Analysis Theory 11 Sensitivity to Coefficients Likewise, compute the range of optimality

for c2 in Example 1. Example: Max 5x1 + 7x2 s.t. x1 < 6 2x1 + 3x2 < 19 x + x < 8 The slope of the binding third constraint is -1. x > 0 and x > 0 The slope of the binding second constraint is -2/3. Find the range of values for c (with c staying 5) such 2 1 that the objective-function line slope lies between that of the two binding constraints: -1 < -5/c2 < -2/3 Multiplying by -1, 1 > 5/c2 > 2/3 Inverting,

1 < c2/5 < 3/2 1 1 Multiplying by 5, 5 < c2 2 2 < 15/2 BA 452 Lesson A.6 Sensitivity Analysis Theory 12 Sensitivity to Coefficients

Another measure of sensitivity to coefficients is available when the optimal solution of a particular decision variable is zero. The reduced cost for any variable is the amount the variable's objective function coefficient would have to improve (increase for maximization problems, decrease for minimization problems) before that variable could have a positive value at an optimal solution. On the one hand, the reduced cost for a decision variable whose value is zero in an optimal solution is a measure of sensitivity to coefficients for that solution. On the other hand, the reduced cost equals 0 for a decision variable whose value is already positive in an optimal solution. BA 452 Lesson A.6 Sensitivity Analysis Theory 13 Sensitivity to Constants

Sensitivity to Constants BA 452 Lesson A.6 Sensitivity Analysis Theory 14 Sensitivity to Constants Overview Sensitivity to Constants measures how changes in the right-hand-side constants of constraints change optimal solutions. The dual price is the rate of improvement in the objective function. BA 452 Lesson A.6 Sensitivity Analysis Theory 15 Sensitivity to Constants

Now consider how a change in the right-hand-side constant of a constraint might affect the feasible region and perhaps cause a change in the optimal solution. The dual price is the rate of improvement in the value of the optimal solution per unit increase in the righthand-side constant. The range of feasibility is the range over which the dual price applies. As the RHS increases beyond the range of feasibility, other constraints eventually become binding and lessen the change in the value of the objective function. BA 452 Lesson A.6 Sensitivity Analysis Theory 16 Sensitivity to Constants One way to compute a dual price by hand is to add a constant k to the right hand side value in question, and then resolve for the optimal solution by solving the same binding constraints.

The difference in the values of the objective functions between the new and original problems is always a linear function of k. The dual price equals the coefficient of k. The dual price can be negative. That happens when the objective function worsens if the RHS is increased. The dual price for a nonbinding (slack or surplus) constraint is 0. BA 452 Lesson A.6 Sensitivity Analysis Theory 17 Sensitivity to Constants Constraint 1: Since x1 < 6 is slack, its dual price is 0. Example: Max 5x1 + 7x2 Constraint 2: Change the RHS value of the second constraint to 19+k and resolve for the optimal point by binding the second and third constraints:

2x1 + 3x2 = 19+k and x1 + x2 = 8. s.t. The solution is x1 = 5-k, x2 = 3+k, z = 46+2k. x1 < 6 2x1 + 3x2 < 19 x1 + x2 < 8 x1 > 0 and x2 > 0 Optimal solution x1 = 5 and x2 = 3 binds second and third constraints, z = 46. znew - zold = 2k, so the dual price = 2. 2x1 + 3x2 = 19+k x1 + x2 = 8 2

1 3 1 x1 x2 = 19+k 8 x1 = det 19+k 3 8 1 / det 2 1 3 1 = (19+k-3x8)/(2x1-3x1) = 5-k

x1 = det 2 19+k 1 8 / det 2 1 3 1 = (2x8-19-k)/(2x1-3x1) = 3+k BA 452 Lesson A.6 Sensitivity Analysis Theory 18 Sensitivity to Constants Constraint 3: Change the RHS value of the third constraint to 8+k and resolve for the optimal point by binding the second and third constraints:

2x1 + 3x2 = 19 and x1 + x2 = 8+k. The solution is x1 = 5+3k, x2 = 3-2k, z = 46+k. 2 1 3 1 x1 x2 s.t. x1 < 6 2x1 + 3x2 < 19 x1 + x2 < 8 x1 > 0 and x2 > 0 Optimal solution x1 = 5 and x2 = 3 binds second

and third constraints, z = 46. znew - zold = k, so the dual price = 1. 2x1 + 3x2 = 19 x1 + x2 = 8+k Example: Max 5x1 + 7x2 = 19 8+k x1 = det 19 3 8+k 1 / det 2 1

3 1 = (19-24-3k)/(2x1-3x1) = 5+3k x1 = det 2 19 1 8+k / det 2 1 3 1 = (16+2k-19)/(2x1-3x1) = 3-2k BA 452 Lesson A.6 Sensitivity Analysis Theory 19 Computer Analysis Computer Analysis

BA 452 Lesson A.6 Sensitivity Analysis Theory 20 Sensitivity to Constants Overview Computer Analysis computes the range of optimality of each decision variable, the dual price of each constraint, and range of feasibility for each dual price. BA 452 Lesson A.6 Sensitivity Analysis Theory 21 Computer Analysis Optimal x1 = 5 and x2 = 3 Reduced costs are zero. (Variables are positive.)

Max s.t. 5x1 + 7x2 x1 < 6 2x1 + 3x2 < 19 x1 + x2 < 8 x1 > 0 and x2 > 0 Range of optimality for x1 is 4.667 to 7.000. Range of optimality for x2 is 5.000 to 7.500. Constraint #1 is slack, dual price = 0 with range of feasibility = 5 to infinity.

Constraint #2 is binding, dual price 2 with range of feasibility = 18 to 24. Constraint #3 is binding, dual price 1 with range of feasibility = 6.333 to 8.333. BA 452 Lesson A.6 Sensitivity Analysis Theory 22 Resource Allocation with Sensitivity Analysis Resource Allocation with Sensitivity Analysis BA 452 Lesson A.6 Sensitivity Analysis Theory 23 Resource Allocation with Sensitivity Analysis Overview Resource Allocation Problems with Sensitivity Analysis help production managers compute the value to them of buying additional resources to produce goods. That value is the most they would be willing to pay for additional resources.

Thus there are mutual gains from trade if some sellers are willing to sell at a price less than the managers willingness to pay. BA 452 Lesson A.6 Sensitivity Analysis Theory 24 Resource Allocation with Sensitivity Analysis A resource cost is relevant if it depends upon the amount of the resource used by the decision variables. Relevant resource costs influence objective-function coefficients. The dual price of a resource constraint is then the maximum premium over the normal cost that you should be willing to pay for one more unit of the resource. A resource cost is sunk if it must be paid regardless of the amount of the resource actually used. Sunk resource costs do not influence objectivefunction coefficients. The dual price of a resource constraint is then the maximum amount you should be willing to pay for one additional unit of the resource.

BA 452 Lesson A.6 Sensitivity Analysis Theory 25 Resource Allocation with Sensitivity Analysis Question: Blue Ridge Hot Tubs produces two types of hot tubs: Aqua-Spas and Hydro-Luxes. There are 200 pumps, 1566 hours of labor, and 2880 feet of tubing available to make the tubs. Here are the input requirements, and unit profits: Pumps Labor Tubing Unit Profit Aqua-Spa 1 9 hours 12 feet $350 Hydro-Lux 1 6 hours

16 feet $300 How would Blue Ridge Hot Tubs maximize profit? BA 452 Lesson A.6 Sensitivity Analysis Theory 26 Resource Allocation with Sensitivity Analysis Objective: maximize profit from producing x1 AquaSpas and x2 Hydro-Luxes. Max 350x1 + 300x2 s.t. x1 + x2 < 200 9x1 + 6x2 < 1566 12x1 +16x2 < 2880 x 1, x 2 > 0 Constraint 1: Pumps available Constraint 2: Labor available Constraint 3: Tubing available Non-negativity constraints BA 452 Lesson A.6 Sensitivity Analysis Theory 27

Resource Allocation with Sensitivity Analysis Max 350x1 + 300x2 s.t. x1 + x2 < 200 (pumps) 9x1 + 6x2 < 1566 (labor) 12x1 +16x2 < 2880 (tubing) x 1, x 2 > 0 Produce x1 = 122 Aqua-Spas and x2 = 78 Hydro-Luxes. BA 452 Lesson A.6 Sensitivity Analysis Theory 28 Resource Allocation with Sensitivity Analysis Max 350x1 + 300x2 s.t. x1 + x2 < 200 (pumps) 9x1 + 6x2 < 1566 (labor) 12x1 +16x2 < 2880 (tubing) x 1, x 2 > 0

Hence, consider this further information: Aqua-Spas sell for $552 each, Hydro-Luxes sell for $476 each, pumps sell for $100 each, labor rents for $10 each hour, and tubing sells for $1 per foot. Compute the unit profit on Aqua-Spas. Unit profit = unit revenue unit cost = $552 - $100 - $10x9 - $1x12 = $350. Compute the unit profit on Hydro-Luxes. Unit profit = unit revenue unit cost = $476 - $100 - $10x6 - $1x16 = $300. Compute optimal output. Since the unit profits are the same as in Example 2, the previous calculation applies: Produce x1 = 122 AquaSpas and x2 = 78 Hydro-Luxes. BA 452 Lesson A.6 Sensitivity Analysis Theory 29 Resource Allocation with Sensitivity Analysis Max 350x1 + 300x2 s.t.

x1 + x2 < 200 (pumps) 9x1 + 6x2 < 1566 (labor) 12x1 +16x2 < 2880 (tubing) x 1, x 2 > 0 How much should Blue Ridge Hot Tubs be willing to pay for another pump? The range of feasibility for the pump constraint is 174 to 207. Hence, increasing the number of pumps from 200 to 201 stays in that range, and the dual price of $200 remains valid. Since the $100 pump price is already included in the unit profits, it is a relevant cost.

Therefore, Blue Ridge Hot Tubs should be willing to pay up to $100+$200 = $300 for another pump. BA 452 Lesson A.6 Sensitivity Analysis Theory 30 Resource Allocation with Sensitivity Analysis Max 350x1 + 300x2 s.t. x1 + x2 < 200 (pumps) 9x1 + 6x2 < 1566 (labor) 12x1 +16x2 < 2880 (tubing) x 1, x 2 > 0 How much should Blue Ridge Hot Tubs be willing to pay for

another 10 pumps? The range of feasibility for the pump constraint is 174 to 207. Hence, increasing the number of pumps from 200 to 210 is outside that range, and the dual price of $200 is now invalid. Hence, re-compute the optimum for 210 pumps available, and find the increase in profit. BA 452 Lesson A.6 Sensitivity Analysis Theory 31 Resource Allocation with Sensitivity Analysis Profit from 200 pumps is $66,100. Profit from 210 pumps is $67,500, which is an increase of $1,400.

Since the $100 pump price a relevant cost, Blue Ridge Hot Tubs should be willing to pay up to $100x10+$1,400 = $2,400 for another 10 pumps. BA 452 Lesson A.6 Sensitivity Analysis Theory 32 BA 452 Quantitative Analysis End of Lesson A.6 BA 452 Lesson A.6 Sensitivity Analysis Theory 33