In LP, the parameters (input data) of the model can change within certain limits with-out causing the optimum solution to change. This is referred to as sensitivity analysis, and will be the subject matter of this section. Later, in Chapter 4, we will study post-optimal analysis which deals with determining the new optimum solution resulting from making targeted changes in the input data.
In LP models, the parameters are usually not exact. With sensitivity analysis, we can ascertain the impact of this uncertainty on the quality of the optimum solution. For example, for an estimated unit profit of a product, if sensitivity analysis reveals that the optimum remains the same for a ±10% change in the unit profit, we can conclude that the solution is more robust than in the case where the indifference range is only ±1 %.
We will start with the more concrete graphical solution to explain the basics of sensitivity analysis. These basics will then be extended to the general LP problem using the simplex tableau results.
1. Graphical Sensitivity Analysis
This section demonstrates the general idea of sensitivity analysis. Two cases will be considered:
1. Sensitivity of the optimum solution to changes in the availability of the resources (right-hand side of the constraints).
2. Sensitivity of the optimum solution to changes in unit profit or unit cost (coefficients of the objective function).
We will consider the two cases separately, using examples of two-variable graphical LPs.
Example 3.6-1 (Changes in the Right-Hand Side)
JOBCO produces two products on two machines. A unit of product 1 requires 2 hours on machine 1 and 1 hour on machine 2. For product 2, a unit requires 1 hour on machine 1 and 3 hours on ma-chine 2. The revenues per unit of products 1 and 2 are $30 and $20, respectively. The total daily processing time available for each machine is 8 hours.
Letting xl and x2 represent the daily number of units of products 1 and 2, respectively, the LP model is given as
Figure 3.12 illustrates the change in the optimum solution when changes are made in the capaci-ty of machine 1. If the daily capacity is increased from 8 hours to 9 hours, the new optimum will occur at point G. The rate of change in optimum z resulting from changing machine 1 capacity from 8 hours to 9 hours can be computed as follows:
The computed rate provides a direct link between the model input (resources) and its output (total revenue) that represents the unit worth of a resource (in $/hr)-that is, the change in the optimal objective value per unit change in the availability of the resource (machine capacity). This means that a unit increase (decrease) in machine 1 capacity will increase (decrease) revenue by $14.00. Although unit worth of a resource is an apt description of the rate of change of the objective function, the technical name dual or shadow price is now standard in the LP literature and all software packages and, hence, will be used throughout the book.
Graphical sensitivity of optimal solurion to changes in the availability of resources (right-hand side of the constraints)
Looking at Figure 3.12, we can see that the dual price of $14.00/hr remains valid for changes (increases or decreases) in machine 1 capacity that move its constraint parallel to itself to any point on the line segment BF. This means that the range of applicability of the given dual price can be computed as follows:
Minimum machine 1 capacity [at B = (0,2.67)] = 2 x 0 + 1 x 2.67 = 2.67 hr
Maximum machine 1 capacity [at F =(8,0)] = 2 x 8 + 1 x 0 = 16 hr
We can thus conclude that the dual price of $14.00/hr will remain valid for the range
2.67 hrs ≤ Machine 1 capacity ≤ 16 hrs
Changes outside this range will produce a different dual price (worth per unit).
Using similar computations, you can verify that the dual price for machine 2 capacity is $2.00/hr and it remains valid for changes (increases or decreases) that move its constraint parallel to itself to any point on the line segment DE, which yields the following limits:
Minimum machine 2 capacity [at D = (4,0)] = 1 x 4 + 3 x a = 4 hr
Maximum machine 2 capacity [at E = (8, 0)] = 1 x a + 3 x 8 = 24 hr
The conclusion is that the dual price of $2.00/hr for machine 2 will remain applicable for the range
4 hr ≤ Machine 2 capacity ≤ 24 hr
The computed limits for machine 1 and 2 are referred to as the feasibility ranges. All software packages provide information about the dual prices and their feasibility ranges. Section 3.6.4 shows how AMPL, Solver, and TORA generate this information.
The dual prices allow making economic decisions about the LP problem, as the following questions demonstrate:
Question 1. If JOBCO can increase the capacity of both machines, which machine should receive higher priority?
The dual prices for machines 1 and 2 are $14.00/hr and $2.00/hr. TIlis means that each addi-tional hour of machine 1 will increase revenue by $14.00, as opposed to only $2.00 for machine 2. Thus, priority should be given to machine 1.
Question 2. A suggestion is made to increase the capacities of machines 1 and 2 at the addi-tional cost of $10/hr. Is this advisable?
For machine 1, the additional net revenue per hour is 14.00 - 10.00 = $4.00 and for ma-chine 2, the net is $2.00 - $10.00 = -$8.00. Hence, only the capacity of machine 1 should be increased.
Question 3. If the capacity of machine 1 is increased from the present 8 hours to 13 hours, how will this increase impact the optimum revenue?
The dual price for machine 1 is $14.00 and is applicable in the range (2.67,16) hr. The pro-posed increase to 13 hours falls within the feasibility range. Hence, the increase in revenue is $14.00(13 - 8) = $70.00, which means that the total revenue will be increased to (current revenue + change in revenue) = 128 + 70 = $198.00.
Question 4. Suppose that the capacity of machine 1 is increased to 20 hours, how will this in-crease impact the optimum revenue?
The proposed change is outside the range (2.67, 16) hr for which the dual price of $14.00 re-mains applicable. Thus, we can only make an immediate conclusion regarding an increase up to 16 hours. Beyond that, further calculations are needed to find the answer (see Chapter 4). Re-member that falling outside the feasibility range does not mean that the problem has no solution. It only means that we do not have sufficient information to make an immediate decision.
Question 5. We know that the change in the optimum objective value equals (dual price X change in resource) so long as the change in the resource is within the feasibility range. What about the associated optimum values of the variables?
The optimum values of the variables will definitely change. However, the level of informa-tion we have from the graphical solution is not sufficient to determine the new values. Section 3.6.2, which treats the sensitivity problem algebraically, provides this detail.
PROBLEM SET 3.6A
1. A company produces two products, A and B. The unit revenues are $2 and $3, respective-ly. Two raw materials, M1 and M2, used in the manufacture of the two products have re-spective daily availabilities of 8 and 18 units. One unit of A uses 2 units of Ml and 2 units of M2, and 1 unit of Buses 3 units of Ml and 6 units of M2.
a. Determine the dual prices of Ml and M2 and their feasibility ranges.
b. Suppose that 4 additional units of Ml can be acquired at the cost of 30 cents per unit. Would you recommend the additional purchase?
c. What is the most the company should pay per unit of M2?
d. If M2 availability is increased by 5 units, determine the associated optimum revenue.
*2. Wild West produces two types of cowboy hats. A Type 1 hat requires twice as much labor time as a Type 2. If all the available labor time is dedicated to Type 2 alone, the company can produce a total of 400 Type 2 hats a day. The respective market limits for the two types are 150 and 200 hats per day. The revenue is $8 per Type 1 hat and $5 per Type 2 hat.
a. Use the graphical solution to determine the number of hats of each type that maxi-mizes revenue.
b. Determine the dual price of the production capacity (in terms of the Type 2 hat) and the range for which it is applicable.
c. If the daily demand limit on the Type 1 hat is decreased to 120, use the dual price to determine the corresponding effect on the optimal revenue.
d. What is the dual price of the market share of the Type 2 hat? By how much can the market share be increased while yielding the computed worth per unit?
Example 3.6-2 (Changes in the Objective Coefficients)
Figure 3.13 shows the graphical solution space of the JOBCO problem presented in Example 3.6-1. The optimum occurs at point C (xl == 3.2, x2 = 1.6, z == 128). Changes in revenue units (i.e., objective-function coefficients) will change the slope of z. However, as can be seen from the figure, the optimum solution will remain at point C so long as the objective function lies between lines BF and DE, the two constraints that define the optimum point. This means that there is a range for the coefficients of the objective function that will keep the optimum solution un-changed at C.
We can write the objective function in the general format
Maximize z = c1xl + c2x2
Imagine now that the line z is pivoted at C and that it can rotate clockwise and counterclockwise. The optimum solution will remain at point C so long as z = c1x1 + c2x2 lies between the two lines xl + 3x2 = 8 and 2xl + x2 = 8. This means that the ratio c1/c2 can vary between 1/3 and 2/1, which yields the following condition:
This information can provide immediate answers regarding the optimum solution as the follow-ing questions demonstrate:
Question 1. Suppose that the unit revenues for products 1 and 2 are changed to $35 and $25, respectively. Will the current optimum remain the same?
The new objective function is
Question 2. Suppose that the unit revenue of product 2 is fixed at its current value of c2 = $20.00. What is the associated range for Cj, the unit revenue for product 1 that will keep the optimum unchanged?
This range is referred to as the optimality range for c1 and it implicitly assumes that c2 is fixed at $20.00.
We can similarly determine the optimality range for c2 by fixing the value of c1 at $30.00. Thus,
As in the case of the right-hand side, all software packages provide the optimality ranges. Section 3.6.4 shows how AMPL, Solver, and TORA generate these results.
Remark. Although the material in this section has dealt only with two variables, the results lay the foundation for the development of sensitivity analysis for the general LP problem in Sections 3.6.2 and 3.6.3.
PROBLEM SET 3.6B
1. Consider Problem 1, Set 3.6a.
a. Determine the optimality condition for cA/cB that will keep the optimum unchanged.
b. Determine the optimality ranges for cA and c8, assuming that the other coefficient is kept constant at its present value.
c. If the unit revenues cA and cB are changed simultaneously to $5 and $4, respectively, determine the new optimum solution.
d. If the changes in (c) are made one at a time, what can be said about the optimum solution?
2. In the Reddy Mikks model of Example 2.2-1;
a. Determine the range for the ratio of the unit revenue of exterior paint to the unit revenue of interior paint.
b. If the revenue per ton of exterior paint remains constant at $5000 per ton, determine the maximum unit revenue of interior paint that will keep the present optimum solu-tion unchanged.
d. If for marketing reasons the unit revenue of interior paint must be reduced to $3000, will the current optimum production mix change?
*3. In Problem 2, Set 3.6a:
a. Determine the optimality range for the unit revenue ratio of the two types of hats that will keep the current optimum unchanged.
b. Using the information in (b), will the optimal solution change if the revenue per unit is the same for both types?