Sensitivity Analysis for LP



Sensitivity Analysis for LP

Q: Why do we need to do a sensitivity analysis for LP?

A: Anytime you have the assumption of Determinism, you need to consider a sensitivity analysis.

Q: Will it be just like the sensitivity analysis for Payoff Tables?

A: Yes and no. The allowable variation is given to you (with payoff tables, you had to work that out for yourself), but you must still work out the expected variation on your own. We will also do more with the allowable variation than we did before.

Q: When does LP give us the allowable variation?

A: After Solver finds the optimal solution, it will give you a dialogue box asking whether or not you want to keep the new-found solution. To the right side of that box will be a list of reports. The second item on that list is the sensitivity analysis report. Click on it to highlight the words “Sensitivity Analysis” and then click OK. A new sheet, labeled “Sensitivity Analysis” will be added to your spreadsheet.

Q: How does LP calculate the allowable variation?

A: For the objective function coefficients (the cost or profit of each variable, usually) the computer can calculate the how far the coefficient can increase or decrease before the current optimal solution (graphically, the current optimal corner point) changes significantly.

Q: What do you mean by “changes significantly?”

A: Any change in the objective coefficients will change the total profit (or total cost), but until the variable values themselves change the solution is still pretty much the same. This is similar to the situation in the Transportation model, where you change the number of units shipped on a route, but still use the same routes.

Q: Why does changing the objective coefficients change the variable values?

A: The optimal solution is based on finding the best value (highest profit or lowest cost) for the given objective. For the computer, the objective is expressed as a series of coefficients (the costs or profits of each variable). Graphically, the coefficients determine the slope of the objective line. Changing the coefficients changes the slope of the objective line. If the slope of the objective changes too much, then the objective line will no longer to tangent to the solution space. Instead, it will pass through the center of the solution space, as it did when we first tried graphing the objective (see lecture notes on “Graphing an LP Problem”). When that happens, we must move the objective line out (if maximizing) or in (if minimizing) until it is once again tangent to the solution space. This will move us to a new corner point, with different objective values.

Q: Is LP a robust solution, like the Transportation solutions?

A: Unfortunately, no. Quite often, LP problems have a very narrow allowable variation range.

Q: How do we read the Sensitivity Analysis report?

A: The report comes as two tables, one for “Adjustable Cells,” which we call variables, and one for “Constraints,” which we call constraints as well.

Q: Have you talked about the sensitivity analysis for the constraints yet?

A: No, but I will. Let’s just look at the variables for now.

Q: What are the column headings for the Adjustable Cells table?

A: They are “Cell,” “Name,” “Final Value,” “Reduced Cost,” “Objective Coefficient,” “Allowable Increase,” and “Allowable Decrease.”

Q: What does the “Cell” tell us?

A: Simply the location on the spreadsheet where the variable is located.

Q: What does the “Name” tell us?

A: Whatever labels you may have entered above or next to the cell containing the variable value.

Q: What does the “Final Value” tell us?

A: The optimal value of the variable.

Q: What does the “Reduced Cost” tell us?

A: The reduced cost tells us how much the objective value would change if the variable value were to increase by one unit.

Q: Is that part of sensitivity analysis also?

A: Yes, but I’ll deal with it in a minute.

Q: What does the “Objective Coefficient” tell us?

A: It simply repeats the coefficient you typed into the spreadsheet as the profit (or cost) of the variable.

Q: Why do we need that in the sensitivity analysis?

A: We may need it to apply the sensitivity analysis later on, so it is convenient to have it available.

Q: What does the “Allowable Increase” tell us?

A: How much the objective coefficient can increase before the solution will change.

Q: Is the Allowable Increase the upper limit for the objective coefficient?

A: Not exactly. You find the upper limit by adding the Allowable Increase to the Objective Coefficient, if that is what you need to do.

Q: What else would you need to do?

A: Suppose you knew the profit on bowls would be going up by $0.50. You do not need to know the upper limit for the objective coefficient; you can simply compare the amount of the increase ($0.50) to the allowable increase ($0.925) and provided the actual increase is less than the allowable increase, you know the solution will not change significantly.

Q: Does it work the same way for the Allowable Decrease?

A: Yes, except that you have a negative change instead of a positive one.

Q: Is it the same for the Constraints?

A: Pretty much. First you have to realize which parts of the constraints are being analyzed.

Q: Aren’t the coefficients being analyzed?

A: Yes, but there are two sets of coefficients, the ones in the left-hand side of the constraints (the variable coefficients) or the ones in the right-hand side of the constraints (the constraint limits).

Q: Do both sets have allowable increases and decreases?

A: No, just the constraint limits.

Q: Why don’t the variable coefficients have allowable increases and decreases?

A: We could calculate allowable increases or decrease for the variable coefficients (they are called “technical coefficients”), but we don’t bother to because those coefficients don’t have much random variation.

Q: Why don’t the technical coefficients have much random variation?

A: Think about what the technical coefficients represent. They basically give you the recipe for making the product. That recipe is not subject to change, unless you make a change to the product, in which case you have a new product, with a new variable, and so you would know to make a change to the formulation.

Q: Do we expect the constraint limits to change?

A: Sometimes. If a constraint is dealing with supply or demand, then changes to the constraint limit are likely. If a constraint deals with production ratios, then the changes tend to be under the control of the production planner. This is a question of expected variation, which you still have to do on your own.

Q: So, how do we use the sensitivity analysis?

A: We’ve already gone over two ways: one is to check to see if a specific change will change the solution, and the second is for the assumption of determinism, where you compare expected variation to allowable variation.

Q: Checking specific changes is easy and we’ve done expected variation vs. allowable variation before, so are we done?

A: Not quite. There are a couple of catches to checking on specific changes and we haven’t covered reduced costs.

Q: I knew it couldn’t be that simple. What are the catches to checking specific changes?

A: The first catch is that you can check a specific change for only one variable at a time.

Q: If we have ranges for all the variables, why can’t we check more than one change at a time?

A: The ranges were calculated by allowing only one variable’s coefficient at a time to change. This gives you the maximum range for each variable’s coefficient, but means that if two or more coefficients change at the same time, the ranges are no longer accurate.

Q: So what if two coefficients change just a little bit at the same time? Can we make any judgment about the solution?

A: The correct question is, “Is the current solution still acceptable?” and the answer is “I don’t know.”

Q: Do you mean that if we were taking a quiz and you gave us a problem where two coefficients changed at the same time, asking whether the current solution is still OK, we should write “I don’t know?”

A: Exactly. Kind of a student’s dream come true, isn’t it? You write “I don’t know” as the answer to a question and you get full credit for it. Think how often that would have been the true answer (even if not correct) in some of your other (unimportant) classes. Oddly enough, putting “Yes” or “No” in answer to that question would have been wrong.

Q: Why don’t we know?

A: As stated above, the allowable variation ranges are determined one coefficient at a time. If two coefficients change, then the current solution might be optimal, but then again, it might not. You simply don’t know.

Q: So what do we do in the real world, when several coefficients could be expected to change simultaneously all the time?

A: Re-run the problem after inputting all the new values for the coefficients. This usually doesn’t take all that long a time, since the computer can start its calculations from the existing optimal solution, rather than starting all the way back at the beginning.

Q: Are there any more catches in looking at changes to the coefficient values?

A: One more, and it is related to the first. Let me phrase it as a question for you:

Q: What is the correct answer if an objective coefficient change by a small amount (within the allowable range) and a constraint limit changes by a small amount (within the allowable range). Is the current solution still acceptable?

A: I don’t know.

Q: Are you saying “I don’t know” meaning there were two changes or “I don’t know” meaning you didn’t understand the question?

A: “I don’t know” because there were two changes.

A: Wrong.

Q: How can that be wrong?

A: That’s the last catch. There are two tables in the sensitivity analysis report, one for the objective coefficients and one for the constraints. Those two tables are independent, so if you get one change in each, then you can use the ranges. You have a problem only when you get two (or more) changes in either table.

Q: What do we do with reduced costs?

A: First, notice that the reduced cost is called the “Shadow Price” for constraints. I tend to refer to them both as reduced costs (since they are used in much the same way) but there is a distinction (that you probably don’t care about, and by-the-way, a third phrase is “dual value,” but they all mean pretty much the same thing). Anyway, the definition is the change in the objective function value for a one unit change in a variable’s value.

Q: How can constraints have a change in a variable’s value?

A: Remember that every constraint has a variable associated with it, either slack or surplus. Increasing or decreasing the slack or surplus has an effect, just as increasing or decreasing a decision variable’s value.

Q: How do we interpret the reduced cost (or shadow price or dual value)?

A: First of all, the RC/SP for any basic variable is always zero.

Q: Why would a basic variable have an RC/SP of zero?

A: If the variable is a decision variable, then basic decision variables always have the highest possible value they can, so there is no possible change to the objective. If the variable is a slack or surplus variable, then a basic value indicates excess amounts around the constraint limit. Changes to the slack or surplus value would simply increase or decrease the excess, without affecting the objective.

Q: Since both of our decision variables are basic, what does that tell us?

A: That you don’t have to worry about interpreting the reduced cost for them.

Q: What if we had a third variable, say Vases, which was non-basic and had a reduced cost of 2? What would that tell us?

A: If a variable is non-basic, it has a value of zero. For a decision variable, that would mean the product is not being made. The only reason a product would not be made would be because it did not make enough profit. Therefore, there are two interpretations for the reduced cost of 2. First, if we insisted on making a vase, total profit would go down by $2. Second, if we want to make vases, we should raise the price, and thus the profit, by $2. The first interpretation is literally in line with the definition of reduced cost. The second turns the definition around, telling you that if you force the objective to change by the amount of the reduced cost, then the variable’s value would change too.

Q: Does this work the same way for the constraints?

A: Yes and no. For a decision variable, there is only one possible direction for change, an increase. For a constraint, the slack/surplus variable gets its value from the constraint limit, which can go up or down. In our problem, we had supply limits, so if we got more time (decided to work longer on the wheel), then we could make more products and our profits would go up by the shadow price for the wheel constraint ($0.03/minute). Conversely, should we choose to work less, we lose three cents in profits for every minute we leave early.

Q: What about turning the definition around?

A: You can do that too. The shadow price tells you how much you would be willing to pay to buy more resources. Since we know how much our profit would change (the shadow price) and we should have (in our records somewhere) how much we paid for the resource before, we can add those two together and get an upper limit on what it would be worth to us to pay for more of a resource. Let’s pretend clay had a shadow price of $0.05 (it doesn’t, but let’s pretend). If we normally pay $0.30 per gram for clay, then we would be willing to pay $0.35 per gram to get more clay.

Q: Are there any catches to this?

A: Only one. When deciding how much you are willing to pay for more of a resource, you must also consider how much you are buying. If you buy too much, you will exceed the allowable increase for the constraint, and your solution will be wrong.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download