LINEAR PROGRAMMING UNDER UNCERTAINTY:PERFORMING SENSITIVITY ANALYSIS ON A SPREADSHEET

PERFORMING SENSITIVITY ANALYSIS ON A SPREADSHEET

With the help of Solver, spreadsheets provide an alternative, relatively straightforward way of performing much of the sensitivity analysis described in Secs. 7.1 and 7.2. The spread- sheet approach is basically the same for each of the cases considered in Sec. 7.2 for the types of changes made in the original model. Therefore, we will focus on only the effect of changes in the coefficients of the variables in the objective function (Cases 2a and 3 in Sec. 7.2). We will illustrate this effect by making changes in the original Wyndor model formulated in Sec. 3.1, where the coefficients of x1 (number of batches of the new door produced per week) and x2 (number of batches of the new window produced per week) in the objective function are

c1 = 3 = profit (in thousands of dollars) per batch of the new type of door, c2 = 5 = profit (in thousands of dollars) per batch of the new type of window.

4We have written this section in a way that can be understood without first reading either of the preceding sec- tions in this chapter. However, Sec. 4.7 is important background for the latter part of this section.

For your convenience, the spreadsheet formulation of this model (Fig. 3.22) is repeated here as Fig. 7.7. Note that the cells containing the quantities to be changed are Profit- PerBatch (C4:D4).

Spreadsheets actually provide three methods of performing sensitivity analysis. One is to check the effect of an individual change in the model by simply making the change on the spreadsheet and re-solving. A second is to systematically generate a table on a single spreadsheet that shows the effect of a series of changes in one or two parameters of the model. A third is to obtain and apply Excel’s sensitivity report. We describe each of these methods in turn below.

Checking Individual Changes in the Model

One of the great strengths of a spreadsheet is the ease with which it can be used interactively to perform various kinds of sensitivity analysis. Once Solver has been set up to obtain an optimal solution, you can immediately find out what would happen if one of the parameters of the model were changed to some other value. All you have to do is make this change on the spreadsheet and then click on the Solve button again.

To illustrate, suppose that Wyndor management is quite uncertain about what the profit per batch of doors (c1) will turn out to be. Although the figure of 3 given in Fig.

7.7 is considered to be a reasonable initial estimate, management feels that the true profit could end up deviating substantially from this figure in either direction. However, the range between c1 = 2 and c1 = 5 is considered fairly likely.

The revised Wyndor problem where the estimate of the profit per batch of doors has been decreased from

c1 = 3 to c2 = 2, but no change occurs in the optimal solution for the product mix.

Figure 7.8 shows what would happen if the profit per batch of doors were to drop from c1 = 3 to c1 = 2. Comparing with Fig. 7.7, there is no change at all in the optimal solution for the product mix. In fact, the only changes in the new spreadsheet are the new value of c1 in cell C4 and a decrease of 2(in thousands of dollars) in the total profit shown in cell G12 (because each of the two batches of doors produced per week provides 1 thousand dollars less profit). Because the optimal solution does not change, we now know that the original estimate of c1 = 3 can be considerably too high without invalidating the model’s optimal solution.

But what happens if this estimate is too low instead? Figure 7.9 shows what would

happen if c1 were increased to c1 = 5. Again, there is no change in the optimal solution. Therefore, we now know that the range of values of c1 over which the current optimal solution remains optimal (i.e., the allowable range discussed in Sec. 7.2) includes the range from 2 to 5 and may extend further.

Because the original value of c1 = 3 can be changed considerably in either direction without changing the optimal solution, c1 is a relatively insensitive parameter. It is not necessary to pin down this estimate with great accuracy in order to have confidence that the model is providing the correct optimal solution.

This may be all the information that is needed about c1. However, if there is a good possibility that the true value of c1 will turn out to be even outside this broad range from 2 to 5, further investigation would be desirable. How much higher or lower can c1 be be- fore the optimal solution would change?

Figure 7.10 demonstrates that the optimal solution would indeed change if c1 is in- creased all the way up to c1 = 10. Thus, we now know that this change occurs somewhere between 5 and 10 during the process of increasing c1.

The revised Wyndor problem where the estimate of the profit per batch of doors has been increased from C1 = 3 to C1 = 10, which results in a change in the optimal solution for the product mix.

Using a Parameter Analysis Report to Do Sensitivity Analysis Systematically To pin down just when the optimal solution will change, we could continue selecting new values of c1 at random. However, a better approach is to systematically consider a range of values of c1. The Analytic Solver Platform for Education (ASPE), first introduced in Sec. 3.5, can generate a parameter analysis report that is designed to do just this sort of analysis. Instructions for installing ASPE are on a supplementary insert included with the book and also on the bookís website, www.mhhe.com/hillier.

The data cell containing a parameter that will be systematically varied (ProfitPer- BatchOfDoors in cell C4 in this case) is referred to as a parameter cell. A parameter analysis report is used to show the results in the changing cells and/or the objective cell for various trial values in the parameter cell. For each trial value, these results are ob- tained by using Solver to re-solve the problem.

To generate a parameter analysis report, the first step is to define the parameter cell. In this case, select cell C4 (the profit per batch of doors) and choose Optimization under the Parameters menu on the ASPE ribbon.In the parameter cell dialog box, shown in Fig.7.11,enter the range of trial values for the parameter cell.The entries shown specify

that c1 will be systematically varied from 1 to 10. If desired, additional parameter cells could be defined in this same way, but we will not do so at this point.

Next choose Optimization>Parameter Analysis under the Reports menu on the ASPE ribbon. This brings up the dialog box shown in Fig. 7.12 that allows you to specify which parameter cells to vary and which results to show. The choice of which parameter cells to vary is made under Parameters in the bottom half of the dialog box. Clicking on (>>) will select all of the parameter cells defined so far (moving them to the box on the right). In the Wyndor example, only one parameter has been defined, so this causes the single parameter cell (ProfitPerBatchOfDoors or cell C4) to appear on the right. If more para- meter cells had been defined, particular parameter cells can be chosen for immediate analy- sis by clicking on the + next to Wyndor to reveal the list of parameter cells that have been defined in the Wyndor spreadsheet. Clicking on (>) then moves individual parameter cells to the list on the right.

The choice of which results to show as the parameter cell is varied is made in the upper half of the dialog box. Clicking on (>)will cause all of the changing cells (DoorBatchesProduced or C12, and WindowBatchesProduced or D12) and the objective cell (Total Profit or G12) to appear in the list on the right. To instead choose a subset of these cells, click on the small + next to Variables (or Objective) to reveal a list of all the changing cells (or objective cell) and then click on > to move that changing cell (or ob- jective cell) to the right.

Finally, enter the number of Major Axis Points to specify how many different values of the parameter cell will be shown in the parameter analysis report. The values will be spread evenly between the lower and upper values specified in the parameters cell dialog box in Fig. 7.11. With 10 major axis points, a lower value of 1, and an upper value of 10, the parameter analysis report will show results for c1 of 1, 2, 3,...10.

Clicking on the OK button generates the parameter analysis report shown in Fig. 7.13.

One at a time, the trial values listed in the first column of the table are put into the para- meter cell (ProfitPerBatchOfDoors or C4) and then Solver is called on to re-solve the problem. The optimal results for that particular trial value of the parameter cell are then shown in the remaining columns—DoorBatchesProduced (C4), WindowsBatchesProduced (D4), and TotalProfit (G12). This is repeated automatically for each remaining trial value of the parameter cell. The end result (which happens very quickly for small problems) is the completely-filled-in parameter analysis report shown in Fig. 7.13.

The parameter analysis report reveals that the optimal solution remains the same all the way from c1 = 1 (and perhaps lower) to c1 = 7, but that a change occurs somewhere be- tween 7 and 8. We next could systematically consider values of c1 between 7 and 8 to de- termine more closely where the optimal solution changes. However, this is not necessary since, as discussed a little later, a shortcut is to use the Excel sensitivity report to determine exactly where the optimal solution changes.

Thus far, we have illustrated how to systematically investigate the effect of changing only c1 (cell C4 in Fig. 7.7). The approach is the same for c2 (cell D4). In fact, a parameter analysis report can be used in this way to investigate the effect of changing any single data cell in the model, including any cell in HoursAvailable (G7:G9) or HoursUsedPerBatchPro- duced (C7:D9).

We next will illustrate how to investigate simultaneous changes in two data cells with a spreadsheet, first by itself and then with the help of the a parameter analysis report.

Checking Two-Way Changes in the Model

When using the original estimates for c1 (3) and c2 (5), the optimal solution indicated by the model (Fig. 7.7) is heavily weighted toward producing the windows (6 batches per week) rather than the doors (only 2 batches per week). Suppose that Wyndor management is concerned about this imbalance and feels that the problem may be that the estimate for c1 is too low and the estimate for c2 is too high. This raises the question: If the estimates are indeed off in these directions, would this lead to a more balanced product mix being the most profitable one? (Keep in mind that it is the ratio of c1 to c2 that is relevant for determining the optimal product mix, so having their estimates be off in the same direc- tion with little change in this ratio is unlikely to change the optimal product mix.)

This question can be answered in a matter of seconds simply by substituting new estimates of the profits per batch in the original spreadsheet in Fig. 7.7 and clicking on the Solve button. Figure 7.14 shows that new estimates of 4.5 for doors and 4 for windows causes no change at all in the solution for the optimal product mix. (The total profit does change, but this occurs only because of the changes in the profits per batch.) Would even larger changes in the estimates of profits per batch finally lead to a change in the optimal product mix? Figure 7.15 shows that this does happen, yielding a relatively balanced product mix of (x1, x2) = (4, 3), when estimates of 6 for doors and 3 for windows are used.

Figures 7.14 and 7.15 don’t reveal where the optimal product mix changes as the profit estimates increase from 4.5 to 6 for doors and decrease from 4 to 3 for windows. We next describe how a parameter analysis report can systematically help to pin this down better.

Using a Two-Way Parameter Analysis Report (ASPE) for This Analysis Using APSE, a two-way parameter analysis report, provides a way of systematically investigating the effect if the estimates of both profits per batch are inaccurate. This kind of parameter analysis report shows the results in a single output cell for various trial values in two parameter cells. Therefore, for example, it can be used to show how TotalProfit (G12) in Fig. 5.1 varies over a range of trial values in the two parameter cells, ProfitPer- BatchOfDoors (C4) and ProfitPerBatchOfWindows (D4). For each pair of trial values in these data cells, Solver is called on to re-solve the problem.

To create such a two-way parameter analysis report for the Wyndor problem, both ProfitPerBatchOfDoors (C4) and ProfitPerBatchOfWindows (D4) need to be defined as parameter cells. In turn, select cell C4 and D4, then choose Optimization under the Parameters menu on the ASPE ribbon, and then enter the range of trial values for each parameter cell (as was done in Fig. 7.11 in the previous section). For this example, Prof- itPerBatchOfDoors (C4) will be varied from 3 to 6 while ProfitPerBatchOfWindows (D4) will be varied from 1 to 5.

Next, choose Optimization>Parameter Analysis under the reports menu on the ASPE ribbon to bring up the dialog box shown in Fig. 7.16. For a two-way parameter analysis report, two parameter cells are chosen, but only a single result can be shown. Under Para- meters, clicking on (>>) chooses both of the defined parameter cells, ProfitPerBatchOf- Doors (C4) and ProfitPerBatchOfWindows (D4). Under Results, click on (<<) to clear out the list of cells on the right, click on the + next to Objective to reveal the objective cell (TotalProfit or G12), select TotalProfit, and then click on > to move this cell to the right.

The next step is to choose the option in the menu at the bottom to Vary Two Selected Parameters Independently. This will allow both parameter cells to be varied independently over their entire ranges. The number of different values of the first parameter cell and the second parameter cell to be shown in the parameter analysis report are entered in Major Axis Points and Minor Axis Points, respectively. These values will be spread evenly over the range of values specified in the parameter dialog box for each parameter cell.

Clicking on the OK button generates the parameter analysis report shown in Fig.

7.17. The trial values for the respective parameter cells are listed in the first column and first row of the table. For each combination of a trial value from the first column and from the first row, Solver has solved for the value of the output cell of interest (the ob- jective cell for this example) and entered it into the corresponding column and row of the table.

It also is possible to choose either DoorBatchesProduced (C12) or WindowBatches- Produced (D12) instead of TotalProfit (G12), as the Result to show in the dialog box of Fig. 7.16. A similar parameter analysis report then could have been generated to show ei- ther the optimal number of doors to produce or the optimal number of windows to pro- duce for each combination of values for the unit profits. These two parameter analysis re- ports are shown in Fig. 7.18. The upper right-hand corner (cell F3) of both reports, taken together, gives the optimal solution of (x1, x2) = (2, 6) when using the original profit estimates of 3 per batch of doors and 5 per batch of windows. Moving down from this cell corresponds to increasing this estimate for doors while moving to the left amounts to decreasing the estimate for windows. (The cells when moving up or to the right of H26 are not shown because these changes would only increase the attractiveness of (x1, x2) = (2, 6) as the optimal solution.) Note that (x1, x2) = (2, 6) continues to be the optimal solution for all the cells near H26. This indicates that the original estimates of profit per batch would need to be very inaccurate indeed before the optimal product mix would change.

Using the Sensitivity Report to Perform Sensitivity Analysis

You now have seen how some sensitivity analysis can be performed readily on a spread- sheet either by interactively making changes in data cells and re-solving or by using a parameter analysis report to generate similar information systematically. However, there is a shortcut. Some of the same information (and more) can be obtained more quickly and precisely by simply using the sensitivity report provided by Solver. (Essentially the same sensitivity report is a standard part of the output available from other linear programming software packages as well, including MPL/Solvers, LINDO, and LINGO.)

Section 4.7 already has discussed the sensitivity report and how it is used to perform sensitivity analysis. Figure 4.10 in that section shows the sensitivity report for the Wyndor problem. Part of this report is shown here in Fig. 7.19. Rather than repeating Sec. 4.7, we will focus here on illustrating how the sensitivity report can efficiently address the spe- cific questions raised in the preceding subsections for the Wyndor problem.

The question considered in the first two subsections was how far the initial estimate of 3 for c1 could be off before the current optimal solution, (x1, x2) = (2, 6), would change. Figures 7.9 and 7.10 showed that the optimal solution would not change until c1 is raised to somewhere between 5 and 10. Figure 7.13 then narrowed down the gap for where the optimal solution changes to somewhere between 7 and 8. This figure also showed that if the initial estimate of 3 for c1 is too high rather than too low, c1 would need to be dropped to somewhere below 1 before the optimal solution would change.

Now look at how the portion of the sensitivity report in Figure 7.19 addresses this same question. The DoorBatchesProduced row in this report provides the following information about c1:

Therefore, if c1 is changed from its current value (without making any other change in the model), the current solution (x1, x2) = (2, 6) will remain optimal so long as the new value of c1 is within this allowable range, 0 c1 7.5.

Figure 7.20 provides graphical insight into this allowable range. For the original value of c1 = 3, the solid line in the figure shows the slope of the objective function line pass- ing through (2, 6). At the lower end of the allowable range, where c1 = 0, the objective function line that passes through (2, 6) now is line B in the figure, so every point on the line segment between (0, 6) and (2, 6) is an optimal solution. For any value of c1 < 0, the ob- jective function line will have rotated even further so that (0, 6) becomes the only optimal solution. At the upper end of the allowable range, when c1 = 7.5, the objective function line that passes through (2, 6) becomes line C, so every point on the line segment between (2, 6) and (4, 3) becomes an optimal solution. For any value of c1 > 7.5, the objective

function line is even steeper than line C, so (4, 3) becomes the only optimal solution. Con- sequently, the original optimal solution, (x1, x2) = (2, 6) remains optimal only as long as 0 c1 7.5.

The procedure called Graphical Method and Sensitivity Analysis in IOR Tutorial is designed to help you perform this kind of graphical analysis. After you enter the model for the original Wyndor problem, the module provides you with the graph shown in Fig. 7.20 (without the dashed lines). You then can simply drag one end of the objective line up or down to see how far you can increase or decrease c1 before (x1, x2) = (2, 6) will no longer be optimal.

Conclusion: The allowable range for c1 is 0 c1 7.5, because (x1, x2) = (2, 6) remains optimal over this range but not beyond. (When c1 = 0 or c1 = 7.5, there are multiple optimal solutions, but (x1, x2) = (2, 6) still is one of them.) With the range this wide around the original estimate of 3 (c1 = 3) for the profit per batch of doors, we can be quite confident of obtaining the correct optimal solution for the true profit.

Now let us turn to the question considered in the preceding two subsections. What would happen if the estimate of c1 (3) were too low and the estimate of c2 (5) were too high simultaneously? Specifically, how far can the estimates be off in these directions be- fore the current optimal solution, (x1, x2) = (2, 6), would change?

Figure 7.14 showed that if c1 were increased by 1.5 (from 3 to 4.5) and C2 were decreased by 1 (from 5 to 4), the optimal solution would remain the same. Figure 7.15 then indicated that doubling these changes would result in a change in the optimal solution. How- ever, it is unclear where the change in the optimal solution occurs. Figure 7.18 provided fur- ther information, but not a definitive answer to this question.

Fortunately, additional information can be gleaned from the sensitivity report (Fig. 7.19) by using its allowable increases and allowable decreases in c1 and c2. The key is to apply the following rule (as first stated in Sec. 7.2):

The 100 Percent Rule for Simultaneous Changes in Objective Function Coefficients: If simultaneous changes are made in the coefficients of the ob- jective function, calculate for each change the percentage of the allowable change (increase or decrease) for that coefficient to remain within its allow- able range. If the sum of the percentage changes does not exceed 100 percent, the original optimal solution definitely will still be optimal. (If the sum does exceed 100 percent, then we cannot be sure.)

This rule does not spell out what happens if the sum of the percentage changes does exceed 100 percent. The consequence depends on the directions of the changes in the coefficients. Remember that it is the ratios of the coefficients that are relevant for deter- mining the optimal solution, so the original optimal solution might indeed remain opti- mal even when the sum of the percentage changes greatly exceeds 100 percent if the changes in the coefficients are in the same direction. Thus, exceeding 100 percent may or may not change the optimal solution, but so long as 100 percent is not exceeded, the original optimal solution definitely will still be optimal.

Keep in mind that we can safely use the entire allowable increase or decrease in a single objective function coefficient only if none of the other coefficients have changed at all. With simultaneous changes in the coefficients, we focus on the percentage of the allowable increase or decrease that is being used for each coefficient.

To illustrate, consider the Wyndor problem again, along with the information provided by the sensitivity report in Fig. 7.19. Suppose now that the estimate of c1 has increased from 3 to 4.5 while the estimate of c2 has decreased from 5 to 4. The calcula- tions for the 100 percent rule now are

Since the sum of the percentages now exceeds 100 percent, the 100 percent rule says that we can no longer guarantee that (x1, x2) = (2, 6) is still optimal. In fact, we found earlier in both Figs. 7.15 and 7.18 that the optimal solution has changed to (x1, x2) = (4, 3).

These results suggest how to find just where the optimal solution changes while c1 is being increased and c2 is being decreased by these relative amounts. Since 100 percent is midway between 66-- percent and 133-- percent, the sum of the percentage changes will equal 100 percent when the values of c1 and c2 are midway between their values in the above cases. In particular, c1 = 5.25 is midway between 4.5 and 6 and c2 = 3.5 is mid-

way between 4 and 3. The corresponding calculations for the 100 percent rule are

Although the sum of the percentages equals 100 percent, the fact that it does not exceed 100 percent guarantees that (x1, x2) = (2, 6) is still optimal. Figure 7.21 shows graphically that both (2, 6) and (4, 3) are now optimal, as well as all the points on the line segment connecting these two points. However. If c1 and c2 were to be changed any further from their original values (so that the sum of the percentages exceeds 100 percent), the objec- tive function line would be rotated so far toward the vertical that (x1, x2) = (4, 3) would become the only optimal solution.

At the same time, keep in mind that having the sum of the percentages of allowable changes exceed 100 percent does not automatically mean that the optimal solution will change. For example, suppose that the estimates of both unit profits are halved. The resulting calculations for the 100 percent rule are

Even though this sum exceeds 100 percent, Fig. 7.22 shows that the original optimal solution is still optimal. In fact, the objective function line has the same slope as the original objective function line (the solid line in Fig. 7.20). This happens whenever pro- portional changes are made to all the profit estimates, which will automatically lead to the same optimal solution.

This section has focused on how to use a spreadsheet to investigate the effect of changes in only the coefficients of the variables in the objective function. One often is interested in investigating the effect of changes in the right-hand sides of the functional constraints as well. Occasionally you might even want to check whether the optimal solution would change if changes need to be made in some coefficients in the functional constraints.

The spreadsheet approach for investigating these other kinds of changes in the model is virtually the same as for the coefficients in the objective function. Once again, you can try out any changes in the data cells by simply making these changes on the spreadsheet and using Solver to re-solve the model. And once again, you can systematically check the effect of a series of changes in any one or two data cells by using a parameter analysis report. As already described in Sec. 4.7, the sensitivity report generated by Solver (or any other linear programming software package) also provides some valuable information, including the shadow prices, regarding the effect of changing the right-hand side of any single functional constraint. When changing a number of right-hand sides simultaneously, there also is a “100 percent rule” for this case that is analogous to the 100 percent rule for simultaneous changes in objective function constraints. (See the Case 1 portion of Sec.

7.2 for details about how to investigate the effect of changes in right-hand sides, including the application of the 100 percent rule for simultaneous changes in right-hand sides.) The Solved Examples section of the book’s website includes another example of using a spreadsheet to investigate the effect of changing individual right-hand sides.