Introduction to Management Science (10th Edition)

In this section we will show how sensitivity ranges are mathematically determined using the simplex method. While this is not as efficient or quick as using the computer, close examination of the simplex method for performing sensitivity analysis can provide a more thorough understanding of the topic.

Changes in Objective Function Coefficients

To demonstrate sensitivity analysis for the coefficients in the objective function, we will use the Hickory Furniture Company example developed in the previous section. The model for this example was formulated as

where

x ₁ = number of tables produced

x ₂ = number of chairs produced

The coefficients in the objective function will be represented symbolically as c _j (the same notation used in the simplex tableau). Thus, c ₁ = 160 and c ₂ = 200. Now, let us consider a change in one of the c _j values by an amount D . For example, let us change c ₁ = 160 by D = 90. In other words, we are changing c ₁ from $160 to $250. The effect of this change on the solution of this model is shown graphically in Figure A-10.

Originally, the solution to this problem was located at point B in Figure A-10, where x ₁ = 4 and x ₂ = 8. However, increasing c ₁ from $160 to $250 shifts the slope of the objective function so that point C ( x ₁ = 8, x ₂ = 4) becomes the optimal solution. This demonstrates that a change in one of the coefficients of the objective function can change the optimal solution. Therefore, sensitivity analysis is performed to determine the range over which c _j can be changed without altering the optimal solution.

The sensitivity range for a c _j value is the range of values over which the current optimal solution will remain optimal.

The range of c _j that will maintain the optimal solution can be determined directly from the optimal simplex tableau. The optimal simplex tableau for our furniture company example is shown in Table A-33.

Table A-33. The Optimal Simplex Tableau

D is added to c _j in the optimal simplex tableau.

First, consider a D change for c ₁ . This will change the c ₁ value from c ₁ = 160 to c ₁ = 160 + D , as shown in Table A-34. Notice that when c ₁ is changed to 160 + D , the new value is included not only in the top c _j row but also in the left-hand c _j column. This is because x ₁ is a basic solution variable. Since 160 + D is in the left-hand column, it becomes a multiple of the column values when the new z _j row values and the subsequent c _j z _j row values, also shown in Table A-34, are computed.

Table A-34. The Optimal Simplex Tableau with c ₁ = 160 + D

For the solution to remain optimal all values in the c _j z _j row must be 0.

The solution shown in Table A-34 will remain optimal as long as the c _j z _j row values remain negative. (If c _j z _j becomes positive, the product mix will change, and if it becomes zero, there will be an alternative solution.) Thus, for the solution to remain optimal,

20 + D /2

and

20/3 D /9

Both of these inequalities must be solved for D .

and

Thus, D 40 and 60. Now recall that c ₁ = 160 + D ; therefore, D = c ₁ 160. Substituting the amount c ₁ 160 for D in these inequalities,

and

Therefore, the range of values for c ₁ over which the solution basis will remain optimal (although the value of the objective function may change) is

100 c ₁ 200

Next, consider a D change in c ₂ so that c ₂ = 200 + D . The effect of this change in the final simplex tableau is shown in Table A-35.

Table A-35. The Optimal Simplex Tableau with c ₂ = 200 + D

As before, the solution shown in Table A-35 will remain optimal as long as the c _j z _j row values remain negative or zero. Thus, for the solution to remain optimal, we must have

20 D /2

and

20/3 + D /18

Solving these inequalities for D gives

and

Thus, D 40 and 120. Since c ₂ = 200 + D , we have D = c ₂ 200. Substituting this value for D in the inequalities yields

and

Therefore, the range of values for c ₂ over which the solution will remain optimal is

160 c ₂ 320

The ranges for both objective function coefficients are as follows .

100 c ₁ 200

160 c ₂ 320

However, these ranges reflect a possible change in either c ₁ or c ₂ , not simultaneous changes in both c ₁ and c ₂ . Both of the objective function coefficients in this example were for basic solution variables. Determining the c _j sensitivity range for a decision variable that is not basic is much simpler. Because it is not in the basic variable column, the D change does not become a multiple of the z _j row. Thus, the D change will show up in only one column in the c _j z _j row.

Changes in Constraint Quantity Values

To demonstrate the effect of a change in the quantity values of the model constraints, we will again use the Hickory Furniture Company example.

The quantity values 40, 216, and 240 will be represented symbolically as q _i . Thus, q ₁ = 40, q ₂ = 216, and q ₃ = 240. Now consider a D change in q ₂ . For example, let us change q ₂ = 216 by D = 18. In other words, q ₂ is changed from 216 board feet to 234 board feet. The effect of this change is shown graphically in Figure A-11.

In Figure A-11 a change in q ₂ is shown to have the effect of changing the feasible solution area from 0 ABCD to 0 AB'C'D . Originally, the optimal solution point was B ; however, the change in q ₂ causes 'B to be the new optimal solution point. At point B the optimal solution is

At point B' the new optimal solution is

Thus, a change in a q _i value can change the values of the optimal solution. At some point an increase or decrease in q _i will change the variables in the optimal solution mix, including the slack variables. For example, if q ₂ increases to 240 board feet, then the optimal solution point will be at

Notice that s ₃ has left the solution; thus, the optimal solution mix has changed. At this point, where q ₂ = 240, which is the upper limit of the sensitivity range for q ₂ , the shadow price will also change. Therefore, the purpose of sensitivity analysis is to determine the range for q _i over which the optimal variable mix will remain the same and the shadow price will remain the same.

The sensitivity range for a q _i , value is the range of values over which the right-hand-side values can vary without changing the solution variable mix, including slack variables and the shadow prices.

As in the case of the c _j values, the range for q _i can be determined directly from the optimal simplex tableau. As an example, consider a D increase in the number of labor hours. The model constraints become

Notice in the initial simplex tableau for our example (Table A-36) that the changes in the quantity column are the same as the coefficients in the s ₁ column.

Table A-36. The Initial Simplex Tableau

A D in a q _i value is duplicated in the s _i column in the final tableau.

This duplication will carry through each subsequent tableau, so the s ₁ column values will duplicate the D changes in the quantity column in the final tableau (Table A-37).

Table A-37. The Final Simplex Tableau

In effect, the D changes form a separate column identical to the s ₁ column. Therefore, to determine the D change, we need only observe the slack ( s _i ) column corresponding to the model constraint quantity ( q _i ) being changed.

Recall that a requirement of the simplex method is that the quantity values not be negative. If any q _i value becomes negative, the current solution will no longer be feasible and a new variable will enter the solution. Thus, the inequalities

are solved for D :

and

and

Since

q ₁ = 40 + D

then

D = q ₁ 40

These values are substituted into the inequalities D 16, 8, and 8 as follows.

Summarizing these inequalities, we have

24 32 q ₁ 48

The value of 24 can be eliminated, since q ₁ must be greater than 32; thus,

32 q ₁ 48

As long as q ₁ remains in this range, the present basic solution variables will remain the same and feasible. However, the quantity values of those basic variables may change. In other words, although the variables in the basis remain the same, their values can change.

To determine the range for q ₂ (where q ₂ = 216 + D ), the s ₂ column values are used to develop the D inequalities.

The inequalities are solved as follows.

Since

q ₂ = 216 + D

we have

D = q ₂ 216

Substituting this value into the inequalities D 144, 36, and 24 gives a range of possible values for q ₂ :

That is,

180 q ₂ 240 360

The value 360 can be eliminated, because q ₂ cannot exceed 240. Thus, the range over which the basic solution variables will remain the same is

180 q ₂ 240

The range for q ₃ is

192 q ₃

The upper limit of means that q ₃ can increase indefinitely (without limit) without changing the optimal variable solution mix in the shadow price.

Sensitivity analysis of constraint quantity values can be used in conjunction with the dual solution to make decisions regarding model resources. Recall from our analysis of the dual solution of the Hickory Furniture Company example that

y ₁ = $20, marginal value of labor

y ₂ = $6.67, marginal value of wood

y ₃ = $0, marginal value of storage space

The shadow prices are only valid with the sensitivity range for the right-hand-side values.

Because the resource with the greatest marginal value is labor, the manager might desire to secure some additional hours of labor. How many hours should the manager get? Given that the range for q ₁ is 32 q ₁ 48, the manager could secure up to an additional 8 hours of labor (i.e., 48 total hours) before the solution basis changes and the shadow price also changes. If the manager did purchase 8 more hours, the solution values could be found by observing the quantity values in Table A-37.

Since D = 8,

Total profit will be increased by $20 for each extra hour of labor.

In this example for the Hickory Furniture Company, we considered only constraints in determining the sensitivity ranges for q _i values. To compute the q _i sensitivity range, we observed the slack column, s _i , since a D change in q _i was reflected in the s _i column. However, recall that with a constraint we subtract a surplus variable rather than adding a slack variable to form an equality (in addition to adding an artificial variable). Thus, for a constraint we must consider a D would be used instead of q _i + D when computing the sensitivity range for q _i .