Chapter 5: Sensitivity Analysis

Chapter 5: Sensitivity Analysis

5.1 Introduction to Sensitivity Analysis

Real-world problems exist in a changing environment: prices of raw materials
change, product demands change, stock prices change, etc. We can expect some of
the coefficients in the model to change over time. Sensitivity analysis is the study of
how changes in the coefficients of a linear programming problem affect the optimal
solution. It is also known as post-optimality analysis since it is done after the optimal
solution to the original linear problem programming problem has been obtained.
Sensitivity analysis helps answer the following questions:
How will a change in an objective function coefficient affect the optimal solution?
How will a change in a right-hand-side value for a constraint affect the optimal
solution?

5.2 Objective Function Coefficients

We will first analyze how a change in an objective function coefficient affects the
optimal solution and the objective function value. Here, we use the RMC problem
as an example.
RMC, Inc., is a small firm that produces a variety of chemical-based products. In a
particular production process, three raw materials are used to produce two products:
a fuel additive and a solvent base. The three raw materials are blended to form the
fuel additive and solvent base as indicated in the table below:

Table 1: Material Requirements per Ton for the RMC Problem

Product
Fuel Additive Solvent Base
Material 1 0.4 0.5
Material 2 0 0.2
Material 3 0.6 0.3

Page 1 of 54
 Chapter 5: Sensitivity Analysis

RMC’s production is constrained by a limited availability of the three raw materials.

For the current production period, RMC has available the following quantities of
each raw material:

Because of spoilage and the nature of the production process, any materials not used
for current production are useless and must be discarded. The accounting department
analyzed the production figures, assigned all relevant costs, and arrived at prices for
both products that will result in a profit contribution of $40 for every ton of fuel
additive produced and $30 for every ton of solvent base produced.
The linear programming model to determine the number of tons of fuel additive and
the number of tons of solvent base to produce in order to maximize total profit
contribution is given below:

Max 40𝐹 + 30𝑆

s.t.
0.4𝐹 + 0.5𝑆 ≤ 20 Material 1
0.2𝑆 ≤ 5 Material 2
0.6𝐹 + 0.3𝑆 ≤ 21 Material 3
𝐹, 𝑆 ≥ 0
where
𝐹=tons of fuel additive to produce
and
𝑆=tons of solvent base to produce.

Page 2 of 54
 Chapter 5: Sensitivity Analysis

5.2.1 Changing the Objective Function Coefficient of One Variable

Example [Link]
Refer to the RMC problem. Suppose that a price reduction for the fuel additive
reduces the company’s profit contribution from $40 per ton to $30 per ton. In other
words, the objective function in the linear program changes from 40𝐹 + 30𝑆 to
30𝐹 + 30𝑆. Would there be any change in the optimal solution and the total profit
contribution?

Page 3 of 54
 Chapter 5: Sensitivity Analysis

Suppose that a further price reduction causes the profit contribution for the fuel
additive to be reduced to $20 per ton. That is, the objective function in the linear
program changes to 10𝐹 + 30𝑆. Would there be any change in the optimal solution
and the total profit contribution?

From this example, we observe that

1. Changing the objective function only affects the slope of the objective
function line, but leaves the feasible region unchanged.

2. If the change in the objective function coefficient is small, the optimal solution
may remain the same. If the change in the objective function coefficient is
large enough, the optimal solution will change.

Page 4 of 54
 Chapter 5: Sensitivity Analysis

5.2.2 Objective coefficient range

The objective coefficient range for a variable is the range within which its
coefficient in the objective function can change without altering the current
optimal solution. In practice, it provides us with a measure of how much we can
improve the profit contribution (in case of maximization) or cost (in case of
minimization) of a decision variable without losing the optimality we already have.
Managers should focus on those objective coefficients that have a narrow range of
optimality and coefficients near the endpoints of the range.

Referring to the graph for the

RMC problem in which the
objective is to maximize the total
profit contribution 40𝐹 + 30𝑆 ,
we see that the optimal solution is
the point 𝑃4 = (25,20).

Finding the objective coefficient range for the variable 𝐹 is the same as answering
the question:

Suppose the objective function changes to 𝑐1 𝐹 + 30𝑆. For what values of 𝑐1

will the current optimal solution (𝑃4 ) remain optimal?

Similarly, finding the objective coefficient range for the variable 𝑆 is the same as
answering the question:

Suppose the objective function changes to 40𝐹 + 𝑐2 𝑆. For what values of 𝑐2

will the current optimal solution (𝑃4 ) remain optimal?

Page 5 of 54
 Chapter 5: Sensitivity Analysis

To answer these, notice that 𝑃4 is the intersection point between the constraint lines
0.4𝑆 + 0.5𝑆 = 20 (𝑙1 ) and 0.6𝐹 + 0.3𝑆 = 21 (𝑙2 ). Hence, as long as the slope of
the objective function line is between the slopes of the two constraint lines 𝒍𝟏
and 𝒍𝟐 , the optimal solution will remain at 𝑷𝟒 (provided that the feasible region
remains the same).

Objective coefficient range for 𝐹

Page 6 of 54
 Chapter 5: Sensitivity Analysis

Objective coefficient range for 𝑆

Page 7 of 54
 Chapter 5: Sensitivity Analysis

The objective coefficient range can also be obtained from the sensitivity analysis
report generated by Excel’s solver.
The figure below shows the sensitivity analysis report for the RMC problem.

The “Allowable Increase” and “Allowable Decrease” indicate how much the
current value of the objective function coefficient can decrease or increase without
changing the optimal solution.
Allowable Decrease = Current Obj Coef – Lower Limit of Obj Coef Range
Allowable Increase = Upper Limit of Obj Coef Range - Current Obj Coef

Page 8 of 54
 Chapter 5: Sensitivity Analysis

Example [Link]
Compute the objective coefficient range for each variable in the LP below.
Max 5𝑥1 + 7𝑥2
s.t.
𝑥1 ≤ 6
2𝑥1 + 3𝑥2 ≤ 19
𝑥1 + 𝑥2 ≤ 8
𝑥1 , 𝑥2 ≥ 0

Then fill in the missing entries in the sensitivity analysis report.

The current optimal solution

remains optimal as long as the
slope of the objective function line
is between the slopes of the two
constraint lines that intersect with
the current optimal solution.
Current optimal solution:

Page 9 of 54
Chapter 5: Sensitivity Analysis

Page 10 of 54
 Chapter 5: Sensitivity Analysis

Example [Link]
Compute the objective coefficient range of the following LP.
Max 2𝐴 + 3𝐵
s.t.
𝐴 + 3𝐵 ≤ 6
5𝐴 + 3𝐵 ≤ 15
𝐴, 𝐵 ≥ 0

Then fill in the missing entries in the sensitivity analysis report.

The current optimal solution

remains optimal as long as
the slope of the objective
function line is between the
slopes of the two constraint
lines that intersect with the
current optimal solution.
Current optimal solution:

Page 11 of 54
Chapter 5: Sensitivity Analysis

Page 12 of 54
 Chapter 5: Sensitivity Analysis

Suppose that only one objective coefficient is changed and all other aspects of a
linear program remain the same.
What would happen to the optimal solution
and the optimal objective function value?
The new objective coefficient is Optimal solution would remain the same. The
within the objective coefficient new optimal objective function value can be
range. computed by substituting the current optimal
solution into the new objective function.
The new objective coefficient is Optimal solution would change. Need to solve
outside the objective coefficient the revised linear program to determine the
range. new optimal solution and the optimal
objective function value.

Example:

Analyze each of the following changes based on the sensitivity analysis report
for the RMC problem given above.

Page 13 of 54
 Chapter 5: Sensitivity Analysis

Change What would happen to the optimal solution and the

total profit contribution?
The profit contribution Since the new objective coefficient of 𝐹 is within
for fuel additive is the objective coefficient range [24,60], the optimal
increased to $55 per ton. solution would remain the same. The total profit
contribution would increase to 55𝐹 + 30𝑆 =
55(25) + 30(20) = $1975.
The profit contribution Since the new objective coefficient of 𝑆 is within the
for solvent base is objective coefficient range [20,50], the optimal
decreased to $20 per ton. solution would remain the same. The total profit
contribution would decrease to 40𝐹 + 20𝑆 =
40(25) + 20(20) = $1400.
The profit contribution Since the new objective coefficient of 𝐹 is outside
for fuel additive is the objective coefficient range [24,60], the optimal
decreased to $15 per ton. solution would change. The new optimal solution
and optimal objective function value cannot be
determined based on the report. We need to solve
the revised linear program to find out.
The profit contribution Since the new objective coefficient of 𝑆 is outside
for solvent base is the objective coefficient range [20,50], the optimal
increased to $55 per ton. solution would change. The new optimal solution
and optimal objective function value cannot be
determined based on the report. We need to solve
the revised linear program to find out.

Page 14 of 54
 Chapter 5: Sensitivity Analysis

5.2.3 Simultaneous Changes in Objective Coefficients

• The interpretations provided in the earlier sections were based on the assumption
that only one objective function coefficient changes at a time and that all other
aspects of the original problem remain unchanged.
• However, we may be interested in what happens if two or more objective function
coefficients change simultaneously.
• We can analyze such simultaneous changes using the 100 percent rule.
100 Percent Rule for Objective Function Coefficients
For each objective function coefficient that is changed, compute the
percentage of change relative to its allowable increase or decrease. If the
sum of these percentages is less than or equal to 100%, the optimal solution
will remain the same.
• IMPORTANT: Note that the 100 percent rule does not say that the optimal
solution will change if the sum of the percentages of the allowable increases and
allowable decreases is greater than 100%. All we can say is that if the sum of
percentages is greater than 100%, a different optimal solution may exist. Thus,
whenever the sum of the percentages is greater than 100%, the revised problem
must be solved in order to determine the new optimal solution.

Page 15 of 54
 Chapter 5: Sensitivity Analysis

Example [Link]
Again, consider the RMC problem in which the objective is to maximize the total
profit contribution 40F + 30S. Suppose that after the company reviews both the price
and cost data for the two products, the profit contribution for the fuel additive is
increased to $48 per ton and the profit contribution for the solvent base is decreased
to $27 per ton.
Determine whether the optimal solution would change, and compute the total profit
contribution if the optimal solution remains. (Answer based on the sensitivity
analysis report given below.)

Variable Original New Change Allowable Percentage of allowable

objective objective change change
coefficient coefficient
𝐹
𝑆

Page 16 of 54
 Chapter 5: Sensitivity Analysis

Example [Link]
Suppose that the profit contribution for the fuel additive decreases from $40 per ton
to $20 per ton, and the profit contribution for the solvent base decreases from $30
per ton to $27 per ton.
Determine whether the optimal solution would change, and compute the total profit
contribution if the optimal solution remains.

Variable Original New Change Allowable Percentage of allowable

objective objective change change
coefficient coefficient
𝐹
𝑆

Page 17 of 54
 Chapter 5: Sensitivity Analysis

Example [Link]
Suppose that the profit contribution for the fuel additive increases from $40 per ton
to $400 per ton, and the profit contribution for the solvent base increases from $30
per ton to $300 per ton.
Determine whether the optimal solution would change, and compute the total profit
contribution if the optimal solution remains.

Variable Original New Change Allowable Percentage of allowable

objective objective change change
coefficient coefficient
𝐹
𝑆

Page 18 of 54
 Chapter 5: Sensitivity Analysis

5.3 Changes in Constraint Right-Hand Sides

5.3.1 Changing the Right-Hand Side of One Constraint
Now we will consider what would happen to the optimal solution and the optimal
objective function value when only one constraint is changed on the right-hand side
and all other aspects of the linear program remain unchanged.
The shadow price of a constraint is the change in the optimal objective function
value when the constraint RHS increases by 1. Shadow prices are useful in
providing economic information that helps make decisions about acquiring
additional resources.
The right-hand side (RHS) range of a constraint is the range within which the
shadow price of the constraint remains the same.

Example [Link]

(a) Suppose the RHS of constraint 3 is first increased to 22 and then to 23. Draw the
new feasible region. Determine whether the optimal solution and the optimal
objective function value remain the same after each change. What do you observe
about the changes in the optimal objective function value?
Page 19 of 54
 Chapter 5: Sensitivity Analysis

Solution:

RHS of Optimal solution Optimal objective function

constraint 3 value (40𝐹 + 30𝑆)
21 (original) 40(25) + 30(20) = 1600

22 40 (
250
) + 30 (
160
)=
14800
9 9 9
23 40 (
275
) + 30 (
140
)=
15200
9 9 9

For every 1 unit increase in the RHS of constraint 3, the optimal objective
function value increases by ________ . So, the shadow price of constraint 3
is _________.
The shadow price remains the same as long as the intersection point between
the lines of constraint 1 and constraint 3 remains feasible. So, the RHS
range of constraint 1 is _________.

Page 20 of 54
 Chapter 5: Sensitivity Analysis

(b) Consider the case in which the RHS of constraint 1 is increased by 1 and another
case in which the RHS of constraint 1 is decreased by 1. For each case, determine
whether the optimal solution and the optimal objective function value remain the
same after each change. What do you observe about the changes in the optimal
objective function value?

Solution:
RHS of constraint 1 increases by 1 RHS of constraint 1 decreases by 1

RHS of Optimal solution Optimal objective function

constraint 1 (𝐹, 𝑆) value (40𝐹 + 30𝑆)
21 70 70 4900
40 ( ) + 30 ( ) =
3 3 3
20 (original) 40(25) + 30(20) = 1600

19 80 50
40 ( ) + 30 ( ) =
4700
3 3 3

When the RHS of constraint 1 increases by 1, the optimal objective function

value increases by ______ . When the RHS of constraint 1 decreases by 1,

Page 21 of 54
 Chapter 5: Sensitivity Analysis

the optimal objective function value decreases by ______. So, the shadow
price of constraint 1 is ______.
The shadow price remains the same as long as the intersection point between
the lines of constraint 1 and constraint 3 remains feasible. So, the RHS
range of constraint 1 is _________.

(c) Consider the case in which the RHS of constraint 2 is increased to 6 and then to
7, and another case in which the RHS of constraint 2 is decreased to 4 and then
to 3. Determine whether the optimal solution and the optimal objective function
value remain the same after each change. What do you observe about the changes
in the optimal objective function value?
Solution:
RHS of constraint 2 increases to 6 and RHS of constraint 2 decreases to 4 and
then to 7. then to 3.

Page 22 of 54
 Chapter 5: Sensitivity Analysis

RHS of Optimal Optimal objective function

constraint 2 solution (𝐹, 𝑆) value (40𝐹 + 30𝑆)

7
6 𝑃4 =(25,20) 40(25) + 30(20) = 1600

5 (original)
4
3 𝑃 =(27.5,15) 40(27.5) + 30(15) = 1550

When the RHS of constraint 2 increases by 1, the optimal objective function value
_________________________. So, the shadow price of constraint 2 is ________.
The shadow price remains applicable as long as the current optimal solution
remains feasible. So, the RHS range of constraint 2 is _______________.

Page 23 of 54
 Chapter 5: Sensitivity Analysis

A constraint is binding if the optimal solution lies on the corresponding

constraint line. Hence, a change in the RHS of binding constraint would change
the optimal solution and thus affect the optimal objective function value. So, the
shadow price of a binding constraint is non-zero.
By contrast, a change in the RHS of a non-binding constraint would not affect the
optimal solution and hence the optimal objective function value would remain
unchanged, unless the change causes the constraint to become binding. So, the
shadow price of a non-binding constraint is zero.

Example:
Constraints 1 and 3 are binding,
because the lines corresponding to
the two constraints contain the
optimal solution 𝑃4 . Hence, a change
on the RHS of either of these
constraints would change the
optimal solution and thus affect the
optimal objective function value. So,
the shadow prices of these two
constraints are non-zero, as shown
in Example [Link] (a) and (b).

Constraint 2 is non-binding,
because the corresponding constraint
line does not contain the optimal
solution 𝑃4 . Hence, a change on the
RHS of constraint 2 would not
change the optimal solution and the
optimal objective function value,
unless the change causes the
constraint to become binding. So,
constraint 2 has zero shadow price,
as shown in Example [Link] (c).

Page 24 of 54
 Chapter 5: Sensitivity Analysis

5.3.2 Interpreting Sensitivity Analysis Reports

Suppose that only the RHS of one constraint is changed and all other aspects of a
linear program remain the same.
What would happen to the shadow price, the optimal
solution and the optimal objective function value?
The new constraint The current shadow price would remain valid.
RHS is within the
• If the shadow price is zero, then the optimal
RHS range.
solution and the optimal objective function value
would remain the same.
• If the shadow price is nonzero, then the optimal
solution and the optimal objective function value
would change. The new optimal objective
function value can be computed as follows:
New optimal objective function value
= original optimal objective function value
+ (new RHS – original RHS)*(shadow price)

The new optimal solution cannot be determined

from the sensitivity analysis report alone.
The new constraint The shadow price would change. Need to solve the
RHS is outside the revised linear program to determine the new shadow
RHS range. price, optimal solution and optimal objective function
value.

Page 25 of 54
 Chapter 5: Sensitivity Analysis

Example [Link]

The “Allowable Increase” and “Allowable Decrease” for each constraint indicate
how much the current value of the constraint RHS can decrease or increase without
changing the shadow price. These values are computed as follows:
Allowable Decrease = Current RHS – Lower Limit of RHS range
Allowable Increase = Upper Limit of RHS range - Current RHS

Analyze each of the following changes based on the sensitivity analysis report
for the RMC problem given above.
Change What would happen to the optimal solution and the
total profit contribution?
The amount of Material 3 Since the new RHS of Material 3 constraint is
available is increased to within the RHS range [18.75,30], the current
25 tons. shadow price 44.44 would remain valid. Since the
shadow price is nonzero, the optimal solution and
the total profit contribution would change. The
new total profit contribution would be 1600 +
(25 − 21)(44.44) = $1777.76. The new optimal
solution can
not be determined based on the report.

Page 26 of 54
 Chapter 5: Sensitivity Analysis

The amount of Material 1 Since the new RHS of Material 1 constraint is

available is decreased to within the RHS range [14,21.5], the current
15 tons. shadow price 33.33 would remain valid. Since the
shadow price is nonzero, the optimal solution and
the total profit contribution would change. The
new total profit contribution would be 1600 +
(15 − 20)(33.33) = $1433.35. The new optimal
solution cannot be determined based on the report.
The amount of Material 2 Since the new RHS of Material 2 constraint is
available is increased to within the RHS range [4, ∞), the current shadow
10 tons. price 0 would remain valid. Since the shadow price
is 0, the optimal solution and the total profit
contribution would remain the same.
The amount of Material 1 Since the new RHS of Material 1 constraint is
available is increased to outside the RHS range [14,21.5], the current
25 tons. shadow price would change. The new optimal
solution and total profit contribution cannot be
determined based on the report.
The amount of Material 2 Since the new RHS of Material 2 constraint is
available is decreased to outside the RHS range [4, ∞), the current shadow
2 tons. price would change. The new optimal solution and
total profit contribution cannot be determined based
on the report.

Page 27 of 54
 Chapter 5: Sensitivity Analysis

We can also determine the slack or surplus value for a constraint based on a
sensitivity analysis report.

The “Final Value” column in the “Constraints” section indicates the values
obtained by substituting the optimal solution into the constraints’ LHS.
Slack for a ≤ constraint: RHS-LHS Surplus for a ≥ constraint: LHS-RHS
A constraint with zero slack or zero surplus is a binding constraint.

For example, the constraints for the RMC problem are all ≤ constraints. Material 1
and Material 3 constraints have zero slack, whereas Material 2 constraint has a
slack of 1. This means that at the optimal solution, all the available amount of
Material 1 and Material 3 are used up, and there is 1 ton of Material 2 that is
unused.

Page 28 of 54
 Chapter 5: Sensitivity Analysis

Example [Link]
M&D Chemicals produces two products that are sold as raw materials to companies
manufacturing bath soaps and laundry detergents. Based on an analysis of current
inventory levels and potential demand for the coming month, M&D’s management
has specified that the combined production for products A and B must total at least
350 gallons. Separately, a major customer’s order for 125 gallons of product A must
also be satisfied. Product A requires 2 hours of processing time per gallons while
product B requires 1 hour of processing time per gallon, and for the coming month,
600 hours of processing time are available. M&D’s objective is to satisfy these
requirements at a minimum total production cost. Production costs are $2 per gallon
for product A and $3 per gallon for product B.

Let A = gallons of product A

B = gallons of product B
Formulate a linear programming model for the problem above.

Based on the sensitivity analysis report given above, answer the following questions.

Page 29 of 54
 Chapter 5: Sensitivity Analysis

(a) Find the optimal solution and the minimum total production cost.

Solution:
Optimal solution:
Minimum total production cost:

(b) What is the slack or surplus value for each constraint? Interpret the values.

Solution:
Constraint 1 has a surplus of 125. This means that at the optimal solution, the
major customer’s demand for product A is exceeded by 125 gallons.

Constraint 2 has zero surplus. This means that at the optimal solution, the
combined production of products A and B does not exceed the minimum
requirement of 350 gallons.

Constraint 3 has zero slack. This means that the optimal solution uses up all the
processing hours available.

(c) Which constraints are binding and which are non-binding?

Solution:

(d) Find and interpret the objective coefficient range for each variable.

Solution:
Objective coefficient range for variable 𝐴:
Interpretation:
In this problem, the objective coefficient of 𝐴 represents _________________
_______________________________________________________________.
Thus, the optimal solution will remain at 𝐴 = 250 and 𝐵 = 100, provided that
________________________________________________________________
and all other aspects of the problem remain unchanged.

Page 30 of 54
 Chapter 5: Sensitivity Analysis

Objective coefficient range for variable 𝐵:

Interpretation:
In this problem, the objective coefficient of 𝐵 represents ___________________
_______________________________________________________________.
Thus, the optimal solution will remain at 𝐴 = 250 and 𝐵 = 100, provided that
________________________________________________________________
and all other aspects of the problem remain unchanged.

(e) Find and interpret the shadow price and RHS range for each constraint.

Solution:
Constraint 1 has a shadow price of ____, with a RHS range of ____________.
This indicates that ________________________________________________
_______________________________________________________________,
provided that ____________________________________________________
________________________________________________________________
and all other aspects of the problem remain unchanged.

Constraint 2 has a shadow price of ____, with a RHS range of ____________.

This indicates that ________________________________________________
_______________________________________________________________,
provided that ____________________________________________________
________________________________________________________________
and all other aspects of the problem remain unchanged.

Constraint 3 has a shadow price of ____, with a RHS range of ____________.

This indicates that ________________________________________________
_______________________________________________________________,
provided that ____________________________________________________
________________________________________________________________
and all other aspects of the problem remain unchanged.

Page 31 of 54
 Chapter 5: Sensitivity Analysis

5.3.3 Simultaneous Changes in Constraint RHS

The previous discussion on sensitivity analysis for the right-hand side of constraints
is based on the assumption that only one constraint changes on the right-hand side.
We may be interested in what happens if two or more constraints change on their
right-hand sides simultaneously.

100 Percent Rule for Right-Hand Sides

For each constraint RHS that is changed, compute the percentage of change
relative to its allowable increase or decrease. If the sum of these percentages is
less than or equal to 100%, the shadow prices remain valid.
The new optimal objective function value can be computed as follows:
New optimal objective function value
= Original optimal objective function value
+ ∑(New RHS – Original RHS)*Shadow Price
If the optimal objective function value changes, then the optimal solution will
also change.

IMPORTANT: Note that the 100 percent rule does not say that the shadow prices
will change if the sum of the percentages is greater than 100%. All we can say is that
if the sum of the percentages is greater than 100%, different shadow prices may exist.
Thus whenever the sum of the percentage changes is greater than 100%, a revised
problem must be solved in order to determine the new shadow prices, optimal
solution and optimal objective function value.

Page 32 of 54
 Chapter 5: Sensitivity Analysis

Example [Link]
Refer to the M&D Chemicals problem in Example [Link]. Suppose that the company
decides to purchase an additional 0.5 tons of material 1, an additional 7 tons of
material 2, and an additional 4.5 tons for material 3. Determine whether the optimal
solution and the total profit contribution would change.

Solution:
Constraint Original New RHS Change Allowable Percentage of allowable
RHS change change
1
2
3

Change in total profit contribution:

Page 33 of 54
 Chapter 5: Sensitivity Analysis

Example [Link]
Refer to the M&D Chemicals problem in Example [Link]. Suppose the major
customer’s demand for Product A decreases by 50 gallons, the minimum required
total production of Products A and B increases by 10 gallons, and the available
processing time increases by 40 hours. Determine whether the optimal solution and
the minimum total cost would change.

Solution:
Constraint Original New RHS Change Allowable Percentage of allowable
RHS change change
1
2
3

Change in minimum total cost:

Page 34 of 54
 Chapter 5: Sensitivity Analysis

5.4 Reduced Costs

The reduced cost for a decision variable 𝑥 indicates how much the objective
function coefficient for 𝑥 would have to be reduced before that variable could have
a positive value in the optimal solution.
• If 𝑥 > 0 in the optimal solution, then the reduced cost for 𝑥 is 0.
• If 𝑥 = 0 in the optimal solution for a MAX problem, then the reduced cost for
𝑥 is negative.
• If 𝑥 = 0 in the optimal solution for a MIN problem, then the reduced cost for
𝑥 is positive.
The reduced cost for 𝑥 can also be thought of as the shadow price of the non-
negativity constraint 𝑥 ≥ 0.

Let’s consider the RMC problem with 3 variables to illustrate this concept.

Example 5.5.1
Say we have another variable C (cleaning fluid) added to the original RMC problem.
The linear program for the modified problem is as follows:

Max 40𝐹 + 30𝑆 + 50𝐶

s.t.
0.4𝐹 + 0.5𝑆 + 0.6𝐶 ≤ 20 Material 1
0.2𝑆 + 0.1𝐶 ≤ 5 Material 2
0.6𝐹 + 0.3𝑆 + 0.3𝐶 ≤ 21 Material 3
𝐹, 𝑆, 𝐶 ≥ 0

The sensitivity analysis report for this problem is given in the following figure.

Page 35 of 54
 Chapter 5: Sensitivity Analysis

(a) What is the optimal solution and the maximum total profit contribution?

Solution:
Optimal solution:
Total profit contribution:

(b) Find and interpret the reduced cost for each decision variable.

Solution:
The reduced costs for variables 𝐹 and 𝐶 are zero. This is because these
variables already have positive values in the optimal solution.

The reduced cost for 𝑆 is -12.5. This is the same as the shadow price of the
non-negativity constraint 𝑆 ≥ 0. So, for every ton of solvent base produced,
the total profit contribution will decrease by $12.5. Hence, the profit
contribution for the solvent base would have to increase by at least $12.5
before the variable 𝑆 could take a positive value in the optimal solution. In
other words, unless the profit contribution for solvent base increases to at least
$30-(-$12.5)=$42.5, the value of 𝑆 will remain at zero in the optimal solution.

Remark: If the profit contribution for solvent base increases by exactly $12.5,
then there are alternative optimal solutions.
• The current optimal solution (𝐹 = 27.5, 𝑆 = 0, 𝐶 = 15) is still optimal
(since the increase of 12.5 in the objective coefficient for 𝑆 is within the
allowable increase). The maximum profit attained by this solution is
27.5(40) + 0(30 + 12.5) + 15(50) = $1850.
Page 36 of 54
 Chapter 5: Sensitivity Analysis

• Another optimal solution is 𝐹 = 25, 𝑆 = 20, 𝐶 = 0 . The maximum

profit attained by this solution is 25(40) + 20(30 + 12.5) + 0(50) =
$1850.

(c) The figure below shows the sensitivity analysis report obtained when the
profit contribution of solvent base is increased by $12.501. What is the new
optimal solution? What is the new total profit contribution? Compare to the
original optimal solution and total profit contribution.

Page 37 of 54
 Chapter 5: Sensitivity Analysis

Solution:
The new optimal solution is 𝐹 = 25, 𝑆 = 20, 𝐶 = 0.
Before the change, no solvent base is produced at the optimal solution (𝑆 = 0).
After the change, 20 tons of solvent base are produced at the optimal solution
(𝑆 = 20).

The new total profit contribution is 40(25) + 42.501(20) + 50(0) = $1850.02.

Since the profit contribution of solvent base increases by $0.001 per ton and there
are 20 tons of solvent base produced at the new optimal solution, the original total
profit contribution ($1850) increases by 20(0.001)=$0.02.

(d) Refer to the problem described in the beginning of this example. Suppose that
the management decides to add the requirement that S must be at least 25% of
F. The sensitivity analysis report for this revised problem is given in the figure
below. Write down the new constraint, and interpret its shadow price.

Figure 5.10: Computer solution with added constraint.

Solution:
New constraint:

The shadow price for the new constraint is _________. This indicates that
_____________________________________________________________
_____________________________________________________________,
provided that __________________________________________________
__________________ and all other aspects of the problem remain unchanged.
Page 38 of 54
 Chapter 5: Sensitivity Analysis

(e) Suppose that another new constraint is added: the management states that the
amount of cleaning fluid produced must not exceed 20% of total production.
This type of constraint is known as a percentage or ratio constraint which
frequently occurs in linear programming models. The sensitivity analysis
report for this revised problem is given in the figure below. Write down the
new constraint, and interpret its shadow price.

Solution:
New constraint:

The shadow price for the new constraint is _________. This indicates that
________________________________________________________________
__________________________________________________________,
provided that ___________________________________________________
________________________________________________________________
and all other aspects of the problem remain unchanged.

Page 39 of 54
 Chapter 5: Sensitivity Analysis

5.6 The Dual Problem

• Every LP has a dual LP.

• Knowing the relation between an LP and its dual is important because it gives
us interesting economic insights and additional insights into sensitivity
analysis.
• When taking the dual of a given LP, we refer to the given LP as the primal.
If the primal is a max problem, the dual will be a min problem, and vice versa.

5.6.1 Finding the Dual of a Normal Max or Min Problem

Normal MAX problem Normal MIN problem

All constraints are ≤ constraints and all All constraints are ≥ constraints and
variables are non-negative. all variables are non-negative.

Dual of each other

Page 40 of 54
 Chapter 5: Sensitivity Analysis

Example [Link]
Find the dual of the following LP.

Example [Link]
Find the dual of the following LP.

Max 𝑧 = 6𝑥1 + 10𝑥2

s.t.
2𝑥1 + 8𝑥2 ≤ 60
3𝑥1 + 5𝑥2 ≤ 45
5𝑥1 − 6𝑥2 ≤ 10
𝑥2 ≤ 40
𝑥1 , 𝑥2 ≥ 0

Example [Link]
Find the dual of the following LP.

Max 𝑧 = 3𝑥1 + 2𝑥2

s.t.
2𝑥1 + 𝑥2 ≤ 100
𝑥1 + 𝑥2 ≤ 80
𝑥1 ≤ 40
𝑥1 , 𝑥2 ≥ 0

Page 41 of 54
 Chapter 5: Sensitivity Analysis

Example [Link]
Find the dual of the following LP.

Example [Link]
Find the dual of the following LP.

Min 𝑤 = 2𝑦1 − 8𝑦2 + 6𝑦3

s.t.
2𝑦1 + 3𝑦3 ≥ 25
−5𝑦2 + 2𝑦3 ≥ 70
𝑦1 + 3𝑦2 + 9𝑦3 ≥ 100
𝑦1 , 𝑦2 , 𝑦3 ≥ 0

Page 42 of 54
 Chapter 5: Sensitivity Analysis

5.6.2 Finding the Dual of a Nonnormal LP

In reality many LPs are not normal max or min problems. To find the dual of such
LP, follow the steps below.

Step 1: Determine whether the dual is a MAX or MIN problem.

Primal constraints → Dual variables
Step 2: Assign a dual variable to each primal constraint. The RHS of each primal
constraint is the objective coefficient of the corresponding dual variable.
Step 3: Determine the sign restriction of each dual variable based on the type of the
corresponding primal constraint.

Primal variables → Dual constraints

Step 4: Associate each primal variable to a dual constraint. The coefficients for
each primal variable are the coefficients for the corresponding dual constraint.
Step 5: Determine the type of dual constraint based on the sign restriction of the
corresponding primal variable.

Page 43 of 54
 Chapter 5: Sensitivity Analysis

Example [Link]
Find the dual of the following LP.

Example [Link]
Find the dual of the following LP.

Page 44 of 54
 Chapter 5: Sensitivity Analysis

Example [Link]
Find the dual of the following LP.

Example [Link]
Find the dual of the following LP.

Min 𝑧 = 𝑥1 − 3𝑥2 − 2𝑥3

s.t.
3𝑥1 − 𝑥2 + 2𝑥3 ≤ 7
2𝑥1 − 4𝑥2 ≥ 12
−4𝑥1 + 3𝑥2 + 8𝑥3 = 10
𝑥1 , 𝑥2 ≥ 0, 𝑥3 urs

Page 45 of 54
 Chapter 5: Sensitivity Analysis

5.6.3 Economic Interpretation of the Dual Problem

Example [Link] Interpreting the Dual of a Max Problem
The Dakota Furniture Company manufactures desks, tables, and chairs. The
manufacture of each type of furniture requires lumber and two types of skilled labor:
finishing and carpentry. The amount of each resource needed to make each type of
furniture is given in the table below. Currently, 48 board feet of lumber, 20 finishing
hours, and 8 carpentry hours are available. A desk sells for $60, a table for $30, and
a chair for $20.

Scenario You are the owner of the Dakota You are an entrepreneur who
Furniture Company. You need to wants to purchase all of the
determine the number of each type resources of Dakota company.
of furniture to make in order to You need to determine the
maximize the total revenue. price to pay for buying each
unit of resources listed by
Dakota Company to minimize
the total purchase cost.
Decision
variables

Objective
function

Page 46 of 54
 Chapter 5: Sensitivity Analysis

Constraints Limited availability of each The total price to pay for the
resource. resources required for each
type of furniture must be no
less than Dakota’s selling
price of the furniture in order
to induce Dakota to sell.

Page 47 of 54
 Chapter 5: Sensitivity Analysis

Example [Link] - Interpreting the Dual of a Min Problem

Lisa’s diet requires that all the food she eats come from one of the four “basic food
groups” (chocolate cake, ice cream, soda, and cheesecake). At present, the following
four foods are available for consumption: brownies, chocolate ice cream, cola, and
pineapple cheesecake.
Each brownie costs 50¢, each scoop of chocolate ice cream costs 20¢, each bottle of
cola costs 30¢, and each piece of pineapple cheesecake costs 80¢. Each day, Lisa
must have at least 500 calories, 6 oz of chocolate, 10 oz of sugar, and 8 oz of fat. The
nutritional content per unit of each food is shown below:

Scenario You are a friend of Lisa who wants You are a salesperson who
to help her minimize the total cost wants to sell nutrients
of purchasing the food while still (calories, chocolate, sugar, fat)
meeting her nutritional to Gina. You want to determine
requirements. the price to charge for each
nutrient to maximize the
revenue.
Decision
variables

Objective
function

Page 48 of 54
 Chapter 5: Sensitivity Analysis

Constraints Gina’s nutritional requirements The total price to charge for

must be fulfilled. the nutrition in each food must
be no higher than the cost of
the food in order to induce
Gina to buy.

Page 49 of 54
 Chapter 5: Sensitivity Analysis

5.7 Duality and Sensitivity Analysis

An important result in linear programming is called the Dual Theorem. As the proof
of this theorem is beyond the scope of this course, we will only state the applications
from this theorem.
Assuming that the primal LP has an optimal solution, then the following hold:
Primal Dual
Optimal objective function value = Optimal objective function value
Objective coefficients (with allowable = Constraint RHS (with allowable
ranges) ranges)
Constraint RHS (with allowable = Objective coefficients (with
ranges) allowable ranges)
Optimal solution = Shadow prices
Shadow prices = Optimal solution
|Reduced costs| = Slack or surplus of constraints
Slack or surplus of constraint = -Reduced cost if dual is max
= Reduced cost if dual is min

Page 50 of 54
 Chapter 5: Sensitivity Analysis

Example 5.7.1
Recall the Dakota furniture problem in Example [Link]. From the perspective of the
entrepreneur interested in purchasing all of Dakota’s resources, the linear program
and its sensitivity analysis report is as follows.

where y1 = price to pay for 1 board feet of lumber, y2 = price to pay for 1 finishing
hour, y3 = price to pay for 1 carpentry hour.

The dual of this problem represents the perspective of the Dakota company’s
owner who seeks to determine the optimal production quantities of each type of
furniture in order to maximize the total revenue.

where 𝑥1 =number of desks to produce, 𝑥2 =number of tables to produce,

𝑥3 =number of chairs to produce.
Complete the sensitivity analysis report for this dual problem.

Page 51 of 54
 Chapter 5: Sensitivity Analysis

Answer the following questions about the dual problem.

(a) Optimal production quantities of each type of furniture:
2 desks, 0 table, 8 chairs

Maximum total revenue: 60x1 + 30x2 + 20x3 = 60(2) + 30(0) + 20(8) = $280

(b) Suppose the company requires tables to be produced in a positive quantity in

the optimal solution. What changes can be made to achieve this?

Ans: Since the reduced cost of x_2 is -5, this means that every table produced will decrease
the original total revenue by $5. So, to cover the reduced cost, we should increase the selling price
of each table by at least $5 (or increase the selling price of each table to $35 or above).
(c) Find and interpret the shadow price and RHS range for each constraint.

The lumber constraint has a shadow price of ____, 0 with a RHS range of
____________.
[24, ∞) This indicates that _________________________________
the total revenue and optimal solution
would remain the same
_____________________________________________________________,
the total amount of lumber available is at least 24 board feet
provided that __________________________________________________
_____________________________________________________________
and all other aspects of the problem remain unchanged.

Page 52 of 54
 Chapter 5: Sensitivity Analysis

The finishing hour constraint has a shadow price of ____,10 with a RHS range
[16,24]
of ____________. every additional finishing hour available
This indicates that _______________________________
will increase the total revenue by $10
_____________________________________________________________,
provided that __________________________________________________
the total finishing time available is within 16 to 24 hours
_____________________________________________________________
and all other aspects of the problem remain unchanged.

10 with a RHS range

The carpentry hour constraint has a shadow price of ____,
every additional carpentry hour
[6 2/3, 10] This indicates that _______________________________
of ____________.
available will increase the total revenue by $10
_____________________________________________________________,
provided that __________________________________________________
the total carpentry time available is within 6 2/3 to 10 hours
_____________________________________________________________
and all other aspects of the problem remain unchanged.

(d) If 18 finishing hours were available, what would happen to the optimal
solution and the total revenue?

RHS of the finishing constraint

The __________________________________ 20 to ____.
is changed from ____ 18
Since ________________________________________________________,
18 is within the RHS range [16,24] of the finishing constraint
the current shadow price _____
10 is valid / no longer valid. Since the shadow
price is zero / nonzero, the optimal solution and the total revenue would
remain the same / change. The new total revenue would be
280+10(-2)=$260
______________________________. The new optimal solution
cannot be determined based on the report
_____________________________________________________________.

(e) If 30 board feet of lumber were available, what would happen to the optimal
solution and the total revenue?

RHS of the lumber constraint

The __________________________________ is changed from ____ 30
48 to ____.
30 is within the RHS range [24, ∞) of the lumber constraint
Since ________________________________________________________,
the current shadow price _____
0 is valid / no longer valid. Since the shadow
price is zero / nonzero, the optimal solution and the total revenue would
remain the same / change. The new total revenue would be
______________________________. The new optimal solution
_____________________________________________________________.

Page 53 of 54
 Chapter 5: Sensitivity Analysis

(f) If 9 carpentry hours were available, what would happen to the optimal solution
and the total revenue?

RHS of the carpentry constraint

The __________________________________ 8 to ____.
is changed from ____ 9
9 is within the RHS range [6 2/3, 10] of the carpentry constraint
Since ________________________________________________________,
10 is valid / no longer valid. Since the shadow
the current shadow price _____
price is zero / nonzero, the optimal solution and the total revenue would
remain the same / change. The new total revenue would be
280+10(1)=$290
______________________________. The new optimal solution
_____________________________________________________________.
cannot be determined based on the report

(g) If 30 carpentry hours were available, what would happen to the optimal
solution and the total revenue?

RHS of the carpentry constraint

The __________________________________ is changed from ____ 30
8 to ____.
Since ________________________________________________________,
30 is outside the RHS range [6 2/3, 10] of the carpentry constraint
10 is valid / no longer valid. Since the shadow
the current shadow price _____
price is zero / nonzero, the optimal solution and the total revenue would
remain the same / change. The new total revenue would be
______________________________. The new optimal solution
cannot be determined based on the report.
_____________________________________________________________.

Page 54 of 54
Extra questions
h) Which constraints are binding, and which are nonbinding?
Interpret them in the context of the dual problem.

i) If the selling price of each desk were increased to $70, what would happen to the
optimal solution and the total revenue?

j) Suppose the selling price of each piece of furniture is revised as follows:

each desk now sells for $68, each table for $10, each chair for $18.
What would happen to the optimal solution and the total revenue?

k) Suppose that 1 hour of finishing is used for carpentry instead.

What would happen to the optimal solution and the total revenue?

l) Would you recommend that the company buy additional amount of lumber?

m) Suppose that overtime can be scheduled for finishing or carpentry at a cost of $20 per hour.
Would you recommend that the company schedule overtime?

n) Suppose that overtime can be scheduled for finishing or carpentry at a cost of $8 per hour.
Would you recommend that the company schedule overtime?
Answers to extra questions

h) Which constraints are binding, and which are nonbinding?

Interpret them in the context of the dual problem.

The finishing constraint and the carpentry constraint are binding because they have zero slack.
The lumber constraint is nonbinding because it has a slack of 24.
This means that, at the optimal solution, all the available finishing hours and carpentry hours
are used up, but there are 24 board feet of lumber not used.

i) If the selling price of each desk were increased to $70, what would happen to the
optimal solution and the total revenue?

Since 70 is within the objective coefficient range [56,80] of x_1

(or the increase of 70-60=10 in the objective coefficient of x_1 is within the
allowable increase of 20), the optimal solution would remain the same.
The total revenue would increase to
70x1 + 30x2 + 20x3 = 70(2) + 30(0) + 20(8) = $300
j) Suppose the selling price of each piece of furniture is revised as follows:
each desk now sells for $68, each table for $10, each chair for $18.
What would happen to the optimal solution and the total revenue?

8
The increase of 68-60=8 in the objective coefficient of x_1 is 20 × 100% = 40%
of the allowable increase.
The decrease of 30-10=20 in the objective coefficient of x_2 is 20 × 100% = 0%
∞
of the allowable decrease.
The decrease of 20-18=2 in the objective coefficient of x_3 is 2 × 100% = 40%
5
of the allowable decrease.
Since the sum of the percentages (40%+0%+40%=80%) is less than 100%,
the optimal solution would remain the same.
After the change, the total revenue would be 68(2)+10(0)+18(8)=$280,
which is same as the original total revenue.

k) Suppose that 1 hour of finishing is used for carpentry instead.

What would happen to the optimal solution and the total revenue?

If 1 hour of finishing is used for carpentry instead, then the available finishing hour
would decrease by 1 and the available carpentry hour would increase by 1.
The decrease of 1 in the RHS of the finishing constraint is 1 × 100% = 25%
4
of the allowable decrease.
The increase of 1 in the RHS of the carpentry constraint is 1 × 100% = 50%
2
of the allowable increase.
Since the sum of the percentages (25%+50%=75%) is less than 100%,
the shadow price of each constraint would remain valid.
The change in total revenue would be 10(-1)+10(1)=0.
Since the total revenue would remain the same, the optimal solution would also
remain the same.
l) Would you recommend that the company buy additional amount of lumber?

Since the lumber constraint has zero shadow price and the allowable increase for the
constraint RHS is infinity, this means that no matter how much the amount of lumber
available is increased, the optimal solution and total revenue would remain the same.
Hence, not recommended (in the sense that additional amount of lumber will not
increase the total revenue).

m) Suppose that overtime can be scheduled for finishing or carpentry at a cost of $20 per hour.
Would you recommend that the company schedule overtime?

Every additional hour available for finishing or carpentry will increase the total revenue
by $10. Since the cost of an additional hour is higher than the increase of revenue the
additional hour can bring, it is not recommended.

n) Suppose that overtime can be scheduled for finishing or carpentry at a cost of $8 per hour.
Would you recommend that the company schedule overtime?

Every additional hour available for finishing or carpentry will increase the total revenue
by $10. Since the cost of an additional hour is lower than the increase of revenue the
additional hour can bring, it is recommended.