SENSITIVITY ANALYSIS: COMPUTER SOLUTION

In Section 2.4 we showed how to interpret the output of a linear programming solver. In this section we
continue that discussion and show how to interpret the sensitivity analysis output. We use the Par, Inc.,
problem restated below.

Max 10S + 9D

s.t.

⁷/¹⁰ S + 1D < 630 Cutting and dyeing

½S + ⅚D < 600 Sewing

1S + ⅔ D < 708 Finishing

¹/¹⁰S + ¼D < 135 Inspection and packaging

S, D > 0

Let us demonstrate interpreting the sensitivity analysis by considering the solution to the Par, Inc.,
linear program shown in Figure 3.4.

Interpretation of Computer Output

In Section 2.4 we discussed the output in the top portion of Figure 3.4. We see that the optimal solution
is S = 540 standard bags and D = 252 deluxe bags; the value of the optimal solution is $7668. Associated
with each decision variable is reduced cost. We will interpret the reduced cost after our discussion on
dual values.

Immediately following the optimal S and D values and the reduced cost information, the computer
output provides information about the constraints. Recall that the Par, Inc., problem had four less-than-
or-equal-to constraints corresponding to the hours available in each of four production departments.
The information shown in the Slack/Surplus column provides the value of the slack variable for each of
the departments. This information is summarized here:

Constraint Number Constraint Name Slack

1 Cutting and dyeing 0

2 Sewing 120

3 Finishing 0

4 Inspection and packaging 18

Chapter 3: Linear programming: Sensitivity Analysis and Interpretation of Solution

FIGURE 3.4 THE SOLUTION FOR THE PAR, INC., PROBLEM

Optimal Objective Value = 7668.00000

Variable Value Reduced Cost

S 540 . 00000 0 . 00000

D 252 . 00000 0 . 00000

Constraints Slack/Surplus Dual Value

1 0 . 00000 4 . 37500

2 120 . 00000 0 . 00000

3 0 . 00000 6 . 93750

4 18 . 00000 0 . 00000

Objective Allowable Allowable

Variable Coefficient Increase Decrease
S 10 . 00000 3 . 50000 3 . 70000

D 9 . 00000 5 . 28571 2 . 33333

RHS Allowable Allowable

Constraints Value Increase Decrease
1 630 . 00000 52 . 36364 134 . 40000

2 600 . 00000 Infinite 120 . 00000

3 708 . 00000 192 . 00000 128 . 00000

4 135 . 00000 Infinite 18 . 00000

From this information, we see that the binding constraints (the cutting and dyeing and the finishing
constraints) have zero slack at the optimal solution. The sewing department has 120 hours of slack, or
unused capacity, and the inspection and packaging department has 18 hours of slack, or unused
capacity.

The Dual Value column contains information about the marginal value of each of the four resources
at the optimal solution. In this Section 3.2 we defined the dual value as follows:

The dual value associated with a constraint is the change in optimal value of the solution per unit
increase in the right-hand side of the constraint.
Thus, the nonzero dual values of 4.37500 for constraint 1 (cutting and dyeing constraint) and 6.93750
for constraint 3 (finishing constraint) tell us that an additional hour of cutting and dyeing time increases
the value of the optimal solution by $4.37, and an additional hour of finishing time increases the value of
the optimal solutions by $6.94. Thus, if the cutting and dyeing time were increased from 630 to 631
hours, with all other coefficients in the problem remaining the same, Par’s profit would be increased by
$4.37, from $7668 to $7668 + $4.37 = $7672.37. A similar interpretation for the finishing constraint
implies that an increase from 708 to 709 hours of available finishing time, with all other coefficients in
the problem remaining the same, would increase Par’s profit to $7668 + $6.94 = $7674.94. Because the
sewing and the inspection and packaging constraints both have slack, or unused capacity, available, the
dual values of zero show that additional hours of these two resources will not improve the value of the
objective function.

Now that the concept of a dual value has been explained, we define the reduced cost associated
with each variable. The reduced cost associated with a variable is equal to the dual value for the
nonnegativity constraint associated with the variable. From Figure 3.4, we see that the reduced cost on
variable S is zero and on variable D is zero. This makes sense. Consider variable S. The nonnegativity
constraint to S > 0. The current value of S is 540, so changing the nonnegativity constraints to S > 1 has
no effect on the optimal solution value. Because increasing the right-hand side by one unit has no effect
on the optimal objective function value, the dual value (i.e., reduced cost) of this nonnegativity
constraint is zero. A similar argument applies to variable D. In general, if a variable has a nonzero value
in the optimal solution, then it will have a reduced cost equal to zero. Later in this section we give an
example where the reduced cost of a variable is nonzero, and this example provides more insight on
why the term reduced cost is used for the nonnegativity constraint dual value.

Referring again to the computer output in Figure 3.4, we see that after providing the constraint
information on slack/surplus variables and dual values, the solution output provides ranges for the
objective function coefficients and the right-hand sides of the constraints.

Considering the objective function coefficient range analysis, we see that variable S, which has a
current profit coefficient of 10, has an allowable increase of 3.5 and an allowable decrease of 3.7.
Therefore, as long as the profit contribution associated with the standard bag is between $10 - $3.7 =
$6.30 and $10 + $3.5 = $13.50, the production of S = 540 standard bags and D = 252 deluxe bags will
remain the optimal solution. Therefore, the range of optimality for the objective function coefficient on
variable S is from 6.3 to 13.5. Note that the range of optimality is the same as obtained by performing
graphical sensitivity analysis for Cs in Section 3.2

Using the objective function coefficient range information for deluxe bags, we see the following
range of optimality (after rounding to two decimal places):

9 – 2.33 = 6.67 < Cp < 9 + 5.29 = 14.29

This result tells us that as long as the profit contribution associated with the deluxe bag is between
$6.67 and $14.29, the production of S = 540 standard bags and D = 252 deluxe bags will remain the
optimal solution.

The final section of the computer output provides the allowable increase and allowable decrease in
the right-hand sides of the constraints relative to the dual values holding. As long as the constraint right-
hand side is not increased (decreased) by more than the allowable increase (decrease), the associated
dual value gives the exact change in the value of the optimal solution per unit increase in the right-hand
side. For example, let us consider the cutting and dyeing constraint with a current right-hand side value
of 630. Because the dual value for this constraint is $4.37, we can conclude that additional hours will
increase the objective function by $4.37 per hour. It is also true that a reduction in the hours available
will reduce the value of the objective function by $4.37 per hour. From the range information given, we
see that the dual value of $4.37 has an allowable increase of 52.36364 and is therefore valid for right-
hand side values up to 630 + 52.36364 = 682.36364. The allowable decrease is 134.4, so the dual value
of $4.37 is valid for right-hand side values down to 630 – 134.4 = 495.6. A similar interpretation for the
finishing constraint’s right-hand side (constraint 3) shows that the dual value of $6.94 is applicable for
increases up to 900 hours and decreases down to 580 hours.

As mentioned, the right-hand side ranges provide limits within which the dual values give the exact
change in the optimal objective function value. For changes outside the range, the problem must be re-
solved to find the new optimal solution and the new dual value. We shall call the range over which the
dual value is applicable the range of feasibility. The ranges of feasibility for the Par, Inc., problem are
summarized here:

Constraint Min RHS Max RHS

Cutting and dyeing 495.6 682.4

Sewing 480.0 No upper limit

Finishing 580.0 900.0

Inspection and packaging 117.0 No upper limit

As long as the values of right-hand side are within these ranges, the dual values shown on the computer
output will not change. Right-hand side values outside these limits will result in changes in the dual
value information.

Cautionary Note on the Interpretation of Dual Values

As stated previously, the dual value is the change in the value of the optimal solution per unit increase in
the right-hand side of a constraint. When the right-hand side of the constraints represents the amount
of a resource available, the associated dual value is often interpreted as the maximum amount one
should be willing to pay for one additional unit of the resource. However, such an interpretation is not
always correct. To see why, we need to understand the difference between sunk and relevant costs. A
sunk cost is one that is not affected by the decision made. It will be incurred no matter what values the
decision variables assume. A relevant cost is one that depends on the decision made. The amount of a
relevant cost will vary depending on the values of the decision variables.

Let us reconsider the Par, Inc., problem. The amount of cutting and dyeing time available is 630
hours. The cost of the time available is a sunk cost if it must be paid regardless of the number of
standard and deluxe golf bags produced. It would be a relevant cost if Par only had to pay for the
number of hours of cutting and dyeing time actually used to produce golf bags. All relevant costs should
be reflected in the objective function of a linear program. Sunk costs should not be reflected in the
objective function. For Par, Inc., we have been assuming that the company must pay its employees’
wages regardless of whether their time on the job is completely utilized. Therefore, the cost of the
labor-hours resource for Par, Inc., is a sunk cost and has not been reflected in the objective function.

When the cost of a resource is sunk, the dual value can be interpreted as the maximum amount that
the company should be willing to pay for one additional unit of the resource. When the cost of a
resource used is relevant, the dual value can be interpreted as the amount by which the value of the
resource exceeds its cost. Thus, when the resource is relevant, the dual value can be interpreted as the
maximum premium over the normal cost that the company should be willing to pay for one unit of the
resource.

The Modified Par, Inc., Problem

The graphical solution procedure is useful only for linear programs involving two decision variables. In
practice, the problems solved using the linear programming usually involve a large number of variables
and constraints. For instance, the Management Science in Action, Determining Optimal Production
Quantities at GE Plastics, describes how a linear programming model with 3100 variables and 1100
constraints was solved in less than 10 seconds to determine the optimal production quantities at GE
Plastics. In this section, we discuss the formulation and computer solution for two linear programs with
three decision variables. In doing so, we will show how to interpret the reduced-cost portion of the
computer output.

The original Par, Inc., problem is restated as follows:

Max 10S + 9D

s.t.

⁷/¹⁰S + 1D < 630 Cutting and dyeing

½S + ⅚D < 600 Sewing

1S + ⅔ D < 708 Finishing

¹/¹⁰S + ¼D < 135 Inspection and packaging

S, D > 0

Recall that S is the number of standard golf bags produced and D is the number of deluxe golf bags
produced. Suppose that management is also considering producing a lightweight model designed
specifically for golfers who prefer to carry their bags. The design department estimates that each new
lightweight model will require 0.8 hours for cutting and dyeing, I hour for sewing, I hour for finishing,
and 0.25 hours for inspection and packaging. Because of the unique capabilities designed into the new
model, Par's management feels they will realize a profit contribution of $12.85 for each lightweight
model produced during the current production period.
 Let us consider the modifications in the original linear programming model that are needed to
incorporate the effect of this additional decision variable. We will let L denote the number of lightweight
bags produced. After adding L to the objective function and to each of the four constraints, we obtain
the following linear program for the modified problem:

Max 10S + 9D + 12.85L

s.t.

⁷/¹⁰S + 1D + 0.8L < 630 Cutting and dyeing

½S + ⅚D + 1L < 600 Sewing

1S + ⅔ D + 1L < 708 Finishing

¹/¹⁰S + ¼D + ¼L < 135 Inspection and packaging

S, D > 0

Figure 3.5 shows the solution to the modified problem. We see that the optimal solution calls for the
production of 280 standard bags, 0 deluxe bags, and 428 of the new lightweight bags; the value of the
optimal solution is $8299.80.

Let us now look at the information contained in the Reduced Cost column. Recall that the reduced costs
are the dual values of the corresponding nonnegativity constraints. As the computer output shows, the
reduced costs for S and L are zero because these decision variables already have positive values in the
optimal solution. However, the reduced cost for decision variable D is -1.15. The interpretation of this
number is that if the production of deluxe bags is increased from the current level of 0 to 1, then the
optimal objective function value will decrease by 1.15. Another interpretation is that if we "reduce the
cost” of deluxe bags by 1.15 (i.e., increase the contribution margin by 1.15), then there is an optimal
solution where we produce a nonzero number of deluxe bags.
FIGURE 3.5 SOLUTION FOR THE MODIFIED PAR, INC., PROBLEM

Optimal Objective Value = 8299 . 80000

Variable Value Reduced Cost

S 280 . 00000 0 . 00000

D 0 . 00000 -1 . 15000

L 428 . 00000 0 . 00000

Constraints Slack/Surplus Dual Value

1 91 . 60000 0 . 00000

2 32 . 00000 0 . 00000

3 0 . 00000 6 . 10000

4 0 . 00000 19 . 00000

Objective Allowable Allowable

Variable Coefficient Increase Decrease
S 10 . 00000 2 . 07000 4 . 86000

D 9 . 00000 1 . 15000 Infinite

L 12 . 85000 12 . 15000 0 . 94091

RHS Allowable Allowable

Constraints Value Increase Decrease
1 630 . 00000 Infinite 91 . 60000

2 600 . 00000 Infinite 32 . 00000

3 708 . 00000 144 . 63158 168 . 00000

4 135 . 00000 9 . 60000 64 . 20000

Suppose we increase the coefficient of D by exactly $1.15 so that the new value is $9 + $1.15 = $10.15
and then re-solve. Figure 3.6 shows the new solution. Note that although D assumes a positive value in
the new solution, the value of the optimal solution has not changed. In other words, increasing the
profit contribution of D by exactly the amount of the reduced cost has resulted in alternative optimal
solutions. Depending on the computer software package used to optimize this model, you may or may
not see D assume a positive value if you re-solve the problem with an objective function coefficient of
exactly 10.15 for D--that is, the software package may show a different alternative optimal solution.
However, if the profit contribution of D is increased by more than $1.15, then D will not remain at zero
in the optimal solution.

We also note from Figure 3.6 that the dual values for constraints 3 and 4 are 8.1 and 19. respectively,
indicating that these two constraints are binding in the optimal solution. Thus, each additional hour in
the finishing department would increase the value of the optimal solution by $8.10, and each additional
hour in the inspection and packaging department would increase the value of the optimal solution by
$19.00. Because of a slack of 91.6 hours in the cutting and dyeing department and 32 hours in the
sewing department (see Figure 3.6), management might want to consider the possibility of utilizing
these unused labor-hours in the finishing or inspection and packaging departments. For example, some
of the employees

Optimal Objective Value = 8299 . 80000

Variable Value Reduced Cost

S 403 . 78378 0 . 00000

D 222 . 81081 0 . 00000

L 155 . 67568 0 . 00000

Constraints Slack/Surplus Dual Value

1 0 . 00000 0 . 00000

2 56 . 75676 0 . 00000

3 0 . 00000 8 . 10000

4 0 . 00000 19 . 00000

Objective Allowable Allowable

Variable Coefficient Increase Decrease
S 10 . 00000 2 . 51071 0 . 00000

D 10 . 15000 5.25790 0 . 00000

L 12 . 85000 0 . 00000 2 . 19688

RHS Allowable Allowable

Constraints Value Increase Decrease
1 630 . 00000 52 . 36364 91 . 60000

2 600 . 00000 Infinite 56 . 75676

3 708 . 00000 144 . 63158 128 . 00000

4 135 . 00000 16 . 15385 18 . 00000

in the cutting and dyeing department could be used to perform certain operations in either the finishing
department or the inspection and packaging department. In the future, Par's management may want to
explore the possibility of cross-training employees so that unused capacity in one department could be

NOTES AND COMMENTS

shifted to other departments. In the next chapter we will consider similar modeling situations.

1. Computer software packages for solving linear programs are readily available. Most of these provide
the optimal solution, dual or shadow price information, the range of optimality for the objective
function coefficients, and the range of feasibility for the right hand sides. The labels used for the ranges
of optimality and feasibility may vary, but the meaning is the same as what we have described here.

2. Whenever one of the right hand sides is at an end point of its range of feasibility, the dual and shadow
prices only provide one-sided in formation. In this case, they only predict the change in the optimal
value of the objective function for changes toward the interior of the range.

3. A condition called degeneracy can cause a sub- the difference in how we interpret changes in the
objective function coefficients beyond the end points of the range of optimality. Degeneracy occurs
when the dual value equals zero for one of the binding constraints. Degeneracy does not affect the
interpretation of changes toward the interior of the range of optimality. However, when degeneracy is
present, changes beyond the end points of the range do not necessarily mean a different solution will be
optimal. From a practical point of view, changes beyond the end points of the range of optimality
necessitate re-solving the problem.

4. Managers are frequently called on to provide an economic justification for new technology. Often the
new technology is developed, or purchased, in order to conserve resources. The dual value can be
helpful in such cases because it can be used to determine the savings attributable to the new technology
by showing the savings per unit of resource conserved.

MANAGEMENT SCIENCE IN ACTION

DETERMINING OPTIMAL PRODUCTION QUANTITIES AT GE PLASTICS

General Electric Plastics (GEP) is a $5 billion global materials supplier of plastics and raw materials to
many industries (e.g., automotive, computer, and medical equipment). GEP has plants all over the globe.
In the past, GEP followed a pole-centric manufacturing approach wherein each product was
manufactured in the geographic area (Americas, Europe, or Pacific) where it was to be delivered. When
many of GEP's customers started shifting their manufacturing operations to the Pacific, a geographic
imbalance was created between GEP's capacity and demand in the form of overcapacity in the Americas
and under capacity in the Pacific. Recognizing that a pole-centric approach was no longer effective, GEP
adopted a global approach to its manufacturing operations. Initial work focused on the high-
performance polymers (HPP) division. Using a linear programming model, GEP was able to determine
the optimal production quantities at each HPP plant to maximize the total contribution margin for the
division. The model included demand constraints, manufacturing capacity constraints, and constraints
that modeled the flow of materials produced at resin plants to the finishing plants and on to warehouses
in three geographical regions (Americas, Europe, and Pacific). The mathematical model for a one-year
problem has 3100 variables and 1 100 constraints, and can be solved in less than 10 seconds. The new
system proved successful at the HPP division, and other GE Plastics divisions are adapting it for their
supply chain planning.