LINEAR PROGRAMMING UNDER UNCERTAINTY:THE ESSENCE OF SENSITIVITY ANALYSIS

THE ESSENCE OF SENSITIVITY ANALYSIS

The work of the operations research team usually is not even nearly done when the simplex method has been successfully applied to identify an optimal solution for the model. As we pointed out at the end of Sec. 3.3, one assumption of linear programming is that all the parameters of the model (aij, bi, and cj) are known constants. Actually, the parameter values used in the model normally are just estimates based on a prediction of future conditions. The data obtained to develop these estimates often are rather crude or non- existent, so that the parameters in the original formulation may represent little more than quick rules of thumb provided by busy line personnel. The data may even represent de- liberate overestimates or underestimates to protect the interests of the estimators.

Thus, the successful manager and operations research staff will maintain a healthy skepticism about the original numbers coming out of the computer and will view them in many cases as only a starting point for further analysis of the problem. An “optimal” so- lution is optimal only with respect to the specific model being used to represent the real problem, and such a solution becomes a reliable guide for action only after it has been verified as performing well for other reasonable representations of the problem. Fur- thermore, the model parameters (particularly bi) sometimes are set as a result of man- agerial policy decisions (e.g., the amount of certain resources to be made available to the activities), and these decisions should be reviewed after their potential consequences are recognized.

For these reasons it is important to perform sensitivity analysis to investigate the ef- fect on the optimal solution provided by the simplex method if the parameters take on other possible values. Usually there will be some parameters that can be assigned any rea- sonable value without the optimality of this solution being affected. However, there may also be parameters with likely alternative values that would yield a new optimal solution. This situation is particularly serious if the original solution would then have a substan- tially inferior value of the objective function, or perhaps even be infeasible!

Therefore, one main purpose of sensitivity analysis is to identify the sensitive parameters (i.e., the parameters whose values cannot be changed without changing the optimal solution). For coefficients in the objective function that are not categorized as sen- sitive, it is also very helpful to determine the range of values of the coefficient over which the optimal solution will remain unchanged. (We call this range of values the allowable range for that coefficient.) In some cases, changing the right-hand side of a functional con- straint can affect the feasibility of the optimal BF solution. For such parameters, it is use- ful to determine the range of values over which the optimal BF solution (with adjusted val- ues for the basic variables) will remain feasible. (We call this range of values the allowable range for the right-hand side involved.) This range of values also is the range over which the current shadow price for the corresponding constraint remains valid. In the next sec- tion, we will describe the specific procedures for obtaining this kind of information.

Such information is invaluable in two ways. First, it identifies the more important parameters, so that special care can be taken to estimate them closely and to select a solution that performs well for most of their likely values. Second, it identifies the para- meters that will need to be monitored particularly closely as the study is implemented. If it is discovered that the true value of a parameter lies outside its allowable range, this immediately signals a need to change the solution.

For small problems, it would be straightforward to check the effect of a variety of changes in parameter values simply by reapplying the simplex method each time to see if the optimal solution changes. This is particularly convenient when using a spreadsheet formulation. Once Solver has been set up to obtain an optimal solution, all you have to do is make any desired change on the spreadsheet and then click on the Solve button again.

However, for larger problems of the size typically encountered in practice, sensi- tivity analysis would require an exorbitant computational effort if it were necessary to reapply the simplex method from the beginning to investigate each new change in a pa- rameter value. Fortunately, the fundamental insight discussed in Sec. 5.3 virtually elim- inates computational effort. The basic idea is that the fundamental insight immediately reveals just how any changes in the original model would change the numbers in the fi- nal simplex tableau (assuming that the same sequence of algebraic operations originally performed by the simplex method were to be duplicated ). Therefore, after making a few simple calculations to revise this tableau, we can check easily whether the original op- timal BF solution is now nonoptimal (or infeasible). If so, this solution would be used as the initial basic solution to restart the simplex method (or dual simplex method) to find the new optimal solution, if desired. If the changes in the model are not major, only a very few iterations should be required to reach the new optimal solution from this “advanced” initial basic solution.

To describe this procedure more specifically, consider the following situation. The simplex method already has been used to obtain an optimal solution for a linear programming model with specified values for the bi, cj, and aij parameters. To initiate sensitivity analysis, at least one of the parameters is changed. After the changes are made, let b i, c j, and a ij denote the values of the various parameters. Thus, in matrix notation,

The first step is to revise the final simplex tableau to reflect these changes. In particular, we want to find the revised final tableau that would result if exactly the same algebraic operations (including the same multiples of rows being added to or subtracted from other rows) that led from the initial tableau to the final tableau were repeated when starting from the new initial tableau. (This isn’t necessarily the same as reapplying the simplex method since the changes in the initial tableau might cause the simplex method to change some of the algebraic operations being used.) Continuing to use the notation presented in Table 5.9, as well as the accompanying formulas for the fundamental insight [(1) t* = t + y*T and (2) T* = S*T], the revised final tableau is calculated from y* and S* (which have not changed) and the new initial tableau, as shown in Table 7.1. Note that y* and S* together are the coefficients of the slack variables in the final simplex tableau, where the vector y* (the dual variables) equals these coefficients in row 0 and the matrix S* gives these coefficients in the other rows of the tableau. Thus, simply by using y*, S*, and the revised numbers in the initial tableau, Table 7.1 reveals how the revised numbers in the rest of the final tableau are calculated immediately without having to repeat any al- gebraic operations.

Actually, we can substantially streamline these calculations for obtaining the revised final tableau. Because none of the coefficients of x2 changed in the original model (tableau), none of them can change in the final tableau, so we can delete their calculation. Several other original parameters (a11, a21, b1, b3) also were not changed, so another shortcut is to calculate only the incremental changes in the final tableau in terms of the incremental changes in the initial tableau, ignoring those terms in the vector or matrix multiplication that involve zero change in the initial tableau. In particular, the only incremental changes in the initial tableau are 8c1 = 1, 8a31 = -1, and 8b2 = 12, so these are the only terms that need be considered. This streamlined approach is shown below, where a zero or dash appears in each spot where no calculation is needed.

Adding these increments to the original quantities in the final tableau (middle of Table 7.3) then yields the revised final tableau (bottom of Table 7.3).

This incremental analysis also provides a useful general insight, namely, that changes in the final tableau must be proportional to each change in the initial tableau. We illustrate in the next section how this property enables us to use linear interpolation or extrapolation to determine the range of values for a given parameter over which the final basic solution remains both feasible and optimal.

After obtaining the revised final simplex tableau, we next convert the tableau to proper form from Gaussian elimination (as needed). In particular, the basic variable for row i must have a coefficient of 1 in that row and a coefficient of 0 in every other row (in- cluding row 0) for the tableau to be in the proper form for identifying and evaluating the current basic solution. Therefore, if the changes have violated this requirement (which can occur only if the original constraint coefficients of a basic variable have been changed), further changes must be made to restore this form. This restoration is done by using Gauss- ian elimination, i.e., by successively applying step 3 of an iteration for the simplex method (see Chap. 4) as if each violating basic variable were an entering basic variable. Note that these algebraic operations may also cause further changes in the right-side column, so that the current basic solution can be read from this column only when the proper form from Gaussian elimination has been fully restored.

For the example, the revised final simplex tableau shown in the top half of Table 7.4 is not in proper form from Gaussian elimination because of the column for the basic vari- able x . Specifically, the coefficient of x in its row (row 3) is 2 instead of 1, and it has nonzero coefficients (-2 and 1) in rows 0 and 1. To restore proper form, row 3 is multiplied by --; then 2 times this new row 3 is added to row 0 and -- times new row 3 is subtracted from row 1. This yields the proper form from Gaussian elimination shown in the bottom half of Table 7.4, which now can be used to identify the new values for the cur- rent (previously optimal) basic solution:

Because x1 is negative, this basic solution no longer is feasible. However, it is superoptimal (as defined in Table 6.10), and so dual feasible, because all the coefficients in row 0 still are non- negative. Therefore, the dual simplex method (presented in Sec. 8.1) can be used to reoptimize (if desired), by starting from this basic solution. (The sensitivity analysis procedure in IOR

Tutorial includes this option.) Referring to Fig. 7.1 (and ignoring slack variables), the dual sim- plex method uses just one iteration to move from the corner-point solution (-3, 12) to the opti- mal CPF solution (0, 9). (It is often useful in sensitivity analysis to identify the solutions that are optimal for some set of likely values of the model parameters and then to determine which of these solutions most consistently performs well for the various likely parameter values.)

If the basic solution (-3, 12, 7, 0, 0) had been neither primal feasible nor dual fea-

sible (i.e., if the tableau had negative entries in both the right-side column and row 0), ar- tificial variables could have been introduced to convert the tableau to the proper form for an initial simplex tableau.1

The General Procedure. When one is testing to see how sensitive the original optimal solution is to the various parameters of the model, the common approach is to check each parameter (or at least cj and bi) individually. In addition to finding allowable ranges as de- scribed in the next section, this check might include changing the value of the parameter from its initial estimate to other possibilities in the range of likely values (including the end- points of this range). Then some combinations of simultaneous changes of parameter val- ues (such as changing an entire functional constraint) may be investigated. Each time one (or more) of the parameters is changed, the procedure described and illustrated here would be applied. Let us now summarize this procedure.

Summary of Procedure for Sensitivity Analysis

1. Revision of model: Make the desired change or changes in the model to be investigated next.

2. Revision of final tableau: Use the fundamental insight (as summarized by the formu- las on the bottom of Table 7.1) to determine the resulting changes in the final simplex tableau. (See Table 7.3 for an illustration.)

3. Conversion to proper form from Gaussian elimination: Convert this tableau to the proper form for identifying and evaluating the current basic solution by applying (as necessary) Gaussian elimination. (See Table 7.4 for an illustration.)

1There also exists a primal-dual algorithm that can be directly applied to such a simplex tableau without any conversion.

4. Feasibility test: Test this solution for feasibility by checking whether all its basic vari- able values in the right-side column of the tableau still are nonnegative.

5. Optimality test: Test this solution for optimality (if feasible) by checking whether all its nonbasic variable coefficients in row 0 of the tableau still are nonnegative.

6. Reoptimization: If this solution fails either test, the new optimal solution can be ob- tained (if desired) by using the current tableau as the initial simplex tableau (and mak- ing any necessary conversions) for the simplex method or dual simplex method.

The interactive routine entitled sensitivity analysis in IOR Tutorial will enable you to efficiently practice applying this procedure. In addition, a demonstration in OR Tutor (also entitled sensitivity analysis) provides you with another example.

For problems with only two decision variables, graphical analysis provides an alter- native to the above algebraic procedure for performing sensitivity analysis. IOR Tutorial includes a procedure called Graphical Method and Sensitivity Analysis for performing such graphical analysis efficiently.

In the next section, we shall discuss and illustrate the application of the above algebraic procedure to each of the major categories of revisions in the original model. We also will use graphical analysis to illuminate what is being accomplished algebraically. This discussion will involve, in part, expanding upon the example introduced in this section for investigating changes in the Wyndor Glass Co. model. In fact, we shall begin by individually checking each of the preceding changes. At the same time, we shall integrate some of the applications of duality theory to sensitivity analysis discussed in Sec. 6.5.