Optimization Tutorial 2: Sensitivity Analysis

2-Dimensional Geometry and Sensitivity Analysis. An Online Tutorial It is often the case that data is not known accurately. One of the great strengths of modeling is the opportunity to rerun the model with different data or with different assumptions. When one checks the sensitivity of a model to changes in the data, it is usually referred to as “sensitivity analysis.” Sensitivity analysis is widely used throughout all of Management Science and Operations Research, and is common in other fields as well. Normally, when one wants to check the sensitivity of a model to changes in a single datum (singular of data), one reruns the model with the old datum replaced by the new one. In linear programming models, the number of variables (millions of variables), that one could not expect to check the sensitivity to very much data. But one would be wrong! 1 On Sensitivity Analysis in Linear Programming • When the simplex algorithm solves a linear program, it simultaneously generates detailed sensitivity analysis for changes in the RHS coefficients and changes in the cost coefficients. The purpose of this tutorial is to describe this type of sensitivity analysis in the case of linear programs with two variables. • We first review David’s Tool Company, which we will use as a running example. If you think that this tutorial is valuable to you, please send me two shekels, one for each variable. Just joking. 2 Data for the DTC Problem Pack of 10 Slingshot Kits Stone Gathering time 2 person days Stone Smoothing Pack of 10 Stone Shields Resources 3 person days 10 persondays 1 person-day 2 persondays 6 persondays Delivery time 1 person-day 1 persondays 5 persondays Demand 4 packs 3 packs 30 shekels 50 shekels Profit In the original DTC problem, the RHS was measured in hours, and the columns were the number of kits. We have changed the units here to better conform with the 2D geometry used in class. We assume here that each person-day corresponds to 10 hours. We first investigate changes to the optimal objective function, and to the optimal solution itself, as we change one of the right hand side coefficients. To motivate this, we first consider a managerial question that David wants to answer. Suppose that one of the children in town, say Beth, volunteered to do stone gathering. What would be the extra profit for David, assuming that he does not pay her? Alternatively, what is the maximum amount he could pay her while breaking 3 even? 2D Sensitivity Analysis, for 15.053 Tutorial: Modeling the managerial sensitivity analysis question • As is the case with all managerial models, one needs to transform the managerial situation into the mathematical model. Note that we omitted some information from the managerial situation. We did not say how efficient Beth is, or how many hours she is willing to work. So, there is no way that one can give a precise answer without making some additional assumptions. • But here is what we can do, and what we will do. We will assume that Beth is available for one person-day. We can measure the increase in profit if the number of stone gathering person-days increases by exactly one, and all other data stays the same. We will call this value the “shadow price” of the “gathering time constraint”. With a caveat to be explained later, the shadow price of a constraint is the increase in the optimal objective value if the RHS of the constraint increases by exactly one. (You can see here that the shadow price depends on the units used for the RHS as well as the units used for the objective function.) • We shall explain the caveat later and make the definition more precise. But the definition is adequate for now. 4 Sensitivity Analysis in 2D Suppose the gathering time is increased from 10 to 11. What is the impact on the optimal solution value? S When we investigated 2-variable linear programs, we learned that the optimal solution occurs at the intersection of two lines. Equivalently, it occurs at the solution of two equations in two unknowns. 5 4 2K + 3 S = 10 3 2 In this case, the optimal solution can be obtained by solving for the unique solution to: K+ 2S=6 1 1 2 3 4 5 6 K 2 K + 3 S = 10 K + 2 S = 6 Recall that the objective function is z = 30 K + 50 S 5 The Current Optimal Solution 2 K + 3 S = 10 K + 2 S = 6 S 5 4 After one pivot (or two EROs), we get K + 3/2 S = 5 1/2 S = 1 2K + 3 S = 10 After another pivot (or two EROs), we get 3 K 2 = 2 S = 2 And therefore, K+ 2S=6 1 z = 30 K + 50 S = 160 1 2 3 4 5 6 K 6 The Optimal Solution if we Increase Gathering Time to 11 2 K + 3 S = 10 11 K + 2 S = 6 S 5 After one pivot (or two EROs), we get 2K + 3 S = 11 K+2S = 6 K + 3/2 S = 11/2 5 1/2 S = 1/2 1 4 After another pivot (or two EROs), we get 3 K 2 K+ 2S=6 1 = 24 S = 21 And therefore, z = 30 K + 50 S = 160 170 1 2 3 4 5 6 K The optimal solution value increased from 160 to 170, that is, it increased by 10. So, the shadow price of the “gathering time constraint” is 10. 7 The Shadow Price is Valid in an Interval • If we increase the RHS of gathering time from 10 to 11, then the optimal objective value increased from 160 to 170. Suppose that instead we had increased the RHS from 10 to 10.5. Would it have been true that the optimal objective value would have increased from 160 to 165? The answer is yes. In fact, if we had increased the RHS from 10 to 10 + Δ, then the optimal objective value would increase from 160 to 160 + 10Δ, so long as Δ is at most 1. In other words, the change in the optimal objective function varies linearly with the change in the RHS coefficients. Ollie, the computationally wise owl. 8 The change in the optimal solution as a function of Δ 2 K + 3 S = 10 10 + Δ K + 2 S = 6 S 5 After one pivot (or two EROs), we get 2K + 3 S = 10+ Δ K+2S = 6 K + 3/2 S = 5 5 + Δ/2 1/2 S = 11 Δ/2 4 After another pivot (or two EROs), we get 3 K 2 K+ 2S=6 1 = 2 + 2Δ S = 22- Δ And therefore, z = 30 K + 50 S = 160 16 + 10Δ 1 2 3 4 5 6 K The optimal solution value increased from 160 to 160 + 10Δ, that is, it increased by 10Δ. So, the shadow price of the “gathering time constraint” is 10. 9 The interval for the Shadow Price Ollie, what does it mean for a shadow price to be valid in an interval? Tim, the shadow price of the gathering time constraint is 10. If one increases the RHS of gathering time by Δ units, then the optimal objective value increases by 10 Δ. But it is only true for Δ if it is within a certain interval. That’s what we mean when we say it is valid in an interval. So, how can you figure out what the interval is? Tim, the turkey We’’ll demonstrate it on the DTC example. Ollie, the computationally wise owl. 10 Computing the Interval for the Shadow Price Recall that the optimum solution is given by S 5 = 2 + 2Δ S = 22- Δ K 2K + 3 S = 10+ Δ K+2S = 6 And therefore, 4 z = 30 K + 50 S = 160 160 + 10Δ 3 2 K+ 2S=6 1 1 2 3 4 5 6 K So long as Δ is chosen so that the solution above remains feasible, then it will also be an optimal solution. Also recall, that there were additional constraints not listed above, including K≤4 The above solution becomes infeasible if Δ >1 or if Δ < -1. So, the interval is -1 ≤ Δ ≤111. More on the interval Maximize Profit Gathering time: Smoothing time: Delivery time: Slingshot demand: Shield demand: Non-negativity: K =2+2Δ; z = 30 K + 50 S 2 K + 3 S ≤ K + 2 S ≤ 10 + Δ 6 K + S ≤ 5 K ≤ S ≤ 4 3 K,S ≥ 0 S= 2-Δ z = 160 + 10Δ You can easily verify that the above solution is feasible whenever -1 ≤ Δ ≤ 1, and it becomes infeasible if Δ < -1 or Δ > 1. You can also see that the optimal solution value is z = 160 + 10Δ within the interval. So, the shadow price is 10, and it is valid when -1 ≤ Δ ≤ 1 12 Time to try an example yourself That’s not a hint. That’s the answer. You may wish to try it yourself. What is the smoothing time shadow price? I’ll give you a hint. It’s also 10. That’s pretty foxy of you. But I really want students to see how to do the work. By giving them the answer, they can verify that they did it correctly. Ollie Nooz, the most trusted name in fox. 13 An exercise 2 K + 3 S = 10 K + 2 S = 67 S 5 After one pivot (or two EROs), we get K + 3/2 S = ? 1/2 S = ? 4 2K + 3 S = 10 After another pivot (or two EROs), we get 3 K K+ 2S=7 2 = ? S = ? And therefore, 1 z = 30 K + 50 S = 160 + ? 1 2 3 4 5 6 K You will find that the corner point solution is no longer feasible. But use it anyway, and you’ll still determine the correct shadow price. The fact that the corner point solution is infeasible implies that the interval for the shadow price does not contain the value “1”.. 14 The Caveat on the Definition of Shadow Prices • Recall how we defined shadow prices . “With a caveat to be explained later, the shadow price of a constraint is the increase in the optimal objective value if the RHS of the constraint increases by exactly one.” • You can now see what why we needed the caveat. The shadow price is defined in an interval, and the shadow price may not be valid if the RHS is increased by one. More properly, the shadow price is the rate of change in the optimal objective function as the RHS increases. • In mathematical notation, let f(Δ) be the optimal objective value if the RHS of the constraint is increased by Δ. Then the shadow price is the derivative of f( ) at Δ = 0. • It’s possible that there is no derivative, in which case, there are two shadow prices. One is One is Lim [f(Δ)- f(0)]/ Δ as Δ Î 0 from the positive side. The other is Lim [f(Δ)- f(0)]/ Δ as Δ Î 0 from the negative side. 15 Summary for changes in RHS coefficients • Determine the binding constraints • Determine the change in the “corner point solution” as a function of Δ. • Compute the largest and smallest values of Δ so that the solution stays feasible. • The shadow price is valid so long as the “corner point solution” remains optimal, which is so long as it is feasible. • If there are three binding constraints, then choose two of these to get the two equations to solve, and the technique still works. (But the shadow prices and ranges depends on which two constraints are chosen.) And here is a shortcut. Determine the binding constraints, and determine the solution to the constraints if the RHS is increased by 1. (Don’t worry about feasibility). The shadow price is the increase in the objective value. Nooz 16 Cost Coefficients Sensitivity Analysis • The simplex algorithm also gives sensitivity analysis information on the cost coefficients. • A natural first question is: how much does the optimal solution value change if a cost coefficient increases by 1. It turns out that this is very easy to answer (with a caveat). We illustrate it with the DTC example. • Recall that the optimum solution is a corner point, – in 2D: 2 binding equations in 2 variables – in 2D: it has two neighboring corner points • Cost sensitivity: how much can you change the cost coefficient of a variable so that the current corner point solution stays optimal? 17 More on Cost Sensitivity Analysis Suppose the objective function is changed to z = 30 K + 51 S S 5 4 If the same solution K = 2, S = 2, stays optimal, then the optimal objective value increases from 160 to 162. (Note that the increase is the optimal value for S). K + 2 S If the cost coefficient of S is increased by Δ, then the revised objective function is z = 30 K + (50 + Δ) S = 6 3 2 K + 3 S = 10 2 1 1 2 3 4 5 6 K Assuming that the current optimal solution stays optimal, then the objective increases to z = 160 + 2Δ The key issue is the following: how large and small can Δ be so that 2D theSensitivity optimalAnalysis, solutionforremains optimal? Tutorial: 15.053 18 Determining Bounds on Cost Coefficients Suppose the objective function is changed to z = 30 K + (50 + Δ) S As Δ increases or decreases, the slope of the objective line changes. For example, if we set Δ = -40, then the objective function is z = 30 K + 10 S and the point K = 4, S = 2/3 would be optimal. S 5 4 K + 2 S If we set Δ = 40, then the objective function is z = 30 K + 90 S , and the point K = 0, S = 3 would be optimal. = 6 3 2 K + 3 S = 10 2 1 1 2 3 4 5 6 K To see that these solutions are optimal, it helps to recall the “geometric solution method”, where one shifts the isoprofit lines to the maximum level that touches the feasible region. 19 Determining Bounds on Cost Coefficients Suppose the objective function is changed to z = 30 K + (50 + Δ) S If Δ = 10, the objective is parallel to K + 2 S = 6 If Δ = -5, the objective is parallel to 2 K + 3 S = 10 S So (2, 2) remains optimal if -5 ≤ Δ ≤ 10. 5 4 K + 2 S = 6 3 2 K + 3 S = 10 2 1 1 2 3 4 5 6 K 20 Summary for Changes in the Cost Coefficients Suppose that we want to modify the cost coefficient for a variable xj. We want to increase it from cj to cj + Δ. • Determine the binding constraints and the current corner point solution, say x*. • Compute the largest and smallest values of Δ so that the x* remains optimal. In two dimensions, this will occur when the revised objective function is parallel to one of the constraints. 21 Last Slide By the way, 2-D LPs are not so important in and of themselves. But by knowing how to do sensitivity analysis in 2-D, it’s easier to understand what happens with problems with more variables. That concludes this tutorial of sensitivity analysis for Linear Programming in two dimensions. I hope it was helpful. So long! Cleaver Ollie 22