The Role of Sensitivity Analysis

of the Optimal Solution

• Is the optimal solution sensitive to changes in

input parameters?

• Possible reasons for asking this question:

– Parameter values used were only best estimates.
– Dynamic environment may cause changes.
– “What-if” analysis may provide economical and
operational information.
1
The Galaxy Linear Programming Model

Max 8X1 + 5X2 (Weekly profit)

subject to
2X1 + 1X2  1000 (Plastic)
3X1 + 4X2  2400 (Production Time)
X1 + X2  700 (Total production)
X1 - X2  350 (Mix)
Xj> = 0, j = 1,2 (Nonnegativity)
2
 Sensitivity Analysis of
Objective Function Coefficients.

• Range of Optimality
– The optimal solution will remain unchanged as long as
• An objective function coefficient lies within its range of
optimality
• There are no changes in any other input parameters.

– The value of the objective function will change if the

coefficient multiplies a variable whose value is nonzero.

3
 Sensitivity Analysis of
Objective Function Coefficients.
1000 X2

M
Ma ax 4
x3
.75 X1 +
X 5X
1 +
Ma

5X 2
x8

2
X1
+5

500
X2

Max
2X + 5X
1
2

X1

4
500 800
 Sensitivity Analysis of
Objective
X
Function Coefficients.
1000 2
Ma
x8
X1

Range of optimality: [3.75, 10]

+5
X2

(Coefficient of X1)
Ma
x1

500
0 X1

Ma
x3
+5

.75
X1
X2

+5
X2

400 600 800 X1 5

• Reduced cost
Assuming there are no other changes to the input parameters,
the reduced cost for a variable Xj that has a value of “0” at the
optimal solution is:
– The negative of the objective coefficient increase of the variable
Xj (-Cj) necessary for the variable to be positive in the optimal
solution
– Alternatively, it is the change in the objective value per unit
increase of Xj.
• Complementary slackness
At the optimal solution, either the value of a variable is zero, or
its reduced cost is 0.
6
 Sensitivity Analysis of
Right-Hand Side Values

• In sensitivity analysis of right-hand sides of constraints

we are interested in the following questions:
– Keeping all other factors the same, how much would the
optimal value of the objective function (for example, the profit)
change if the right-hand side of a constraint changed by one
unit?
– For how many additional or fewer units will this per unit
change be valid?

7
 Sensitivity Analysis of
Right-Hand Side Values
• Any change to the right hand side of a binding
constraint will change the optimal solution.

• Any change to the right-hand side of a non-

binding constraint that is less than its slack or
surplus, will cause no change in the optimal
solution.
8
 Shadow Prices

• Assuming there are no other changes to the

input parameters, the change to the objective
function value per unit increase to a right hand
side of a constraint is called the “Shadow Price”

9
 Shadow Price – graphical demonstration
The Plastic
constraint X2
When more plastic becomes available (the
plastic constraint is relaxed), the right hand
side of the plastic constraint increases.
1000
2X 1

Maximum profit = $4360

2X 1

+1
+1

x 2<
x 2<

=10

Maximum profit = $4363.4

=10

01

500
00

Shadow price =
4363.40 – 4360.00 = 3.40

Production time X1
constraint
500 10
 Range of Feasibility

• Assuming there are no other changes to the

input parameters, the range of feasibility is
– The range of values for a right hand side of a constraint, in
which the shadow prices for the constraints remain
unchanged.
– In the range of feasibility the objective function value changes
as follows:
Change in objective value =
[Shadow price][Change in the right hand side value]

11
The Plastic
Range of Feasibility
constraint X2

Increasing the amount of

2X 1

plastic is only effective until a

+1

1000
x 2<

new constraint becomes active.

=10

Production mix A new active

00

constraint constraint
X1 + X2 700
500
This is an infeasible solution
Production time
constraint

X1

500 12
The Plastic
Range of Feasibility
constraint 2X 1 X2

Note how the profit increases

+1

1000
as the amount of plastic
x 2

increases.
100
0

500

Production time
constraint

X1

500 13
 Range of Feasibility
X2

Less plastic becomes available (the

1000 plastic constraint is more restrictive).
Infeasible
solution The profit decreases

500
2X1 + 1X2  1100

A new active
constraint
X1

500 14
 Other Post - Optimality Changes

• Addition of a constraint.
• Deletion of a constraint.
• Addition of a variable.
• Deletion of a variable.
• Changes in the left - hand side coefficients.

15
 Using Excel Solver to Find an Optimal
Solution and Analyze Results
• To see the input screen in Excel click [Link]
• Click Solver to obtain the following dialog box.
This cell contains Set Target cell $D$6
the value of the Equal To:
objective function By Changing cells
These cells contain $B$4:$C$4
the decision variables

To enter constraints click…

All the constraints
have the same direction,
thus are included in $D$7:$D$10 $F$7:$F$10
one “Excel constraint”.
16
 Using Excel Solver
• To see the input screen in Excel click [Link]
• Click Solver to obtain the following dialog box.
This cell contains Set Target cell $D$6
the value of the Equal To:
objective function By Changing cells
These cells contain $B$4:$C$4
the decision variables

$D$7:$D$10<=$F$7:$F$10
Click on ‘Options’
and check ‘Linear
Programming’ and
‘Non-negative’.
17
 Using Excel Solver
• To see the input screen in Excel click [Link]
• Click Solver to obtain the following dialog box.
Set Target cell $D$6
Equal To:
By Changing cells
$B$4:$C$4

$D$7:$D$10<=$F$7:$F$10

18
Using Excel Solver – Optimal Solution

GALAXY INDUSTRIES
Space Rays Zappers
Dozens 320 360
Total Limit
Profit 8 5 4360
Plastic 2 1 1000 <= 1000
Prod. Time 3 4 2400 <= 2400
Total 1 1 680 <= 700
Mix 1 -1 -40 <= 350

19
 Using Excel Solver – Optimal Solution

GALAXY INDUSTRIES
Space Rays Zappers
Dozens 320 360
Total Limit
Profit 8 5 4360
Plastic 2 1 1000 <= 1000
Prod. Time 3 4 2400 <= 2400
Total 1 1 680 <= 700
Mix 1 -1 -40 <= 350

Solver is ready to provide

reports to analyze the
optimal solution.
20
Using Excel Solver –Answer Report
Microsoft Excel 9.0 Answer Report
Worksheet: [[Link]]Galaxy
Report Created: 11/12/2001 8:02:06 PM

Target Cell (Max)

Cell Name Original Value Final Value
$D$6 Profit Total 4360 4360

Adjustable Cells
Cell Name Original Value Final Value
$B$4 Dozens Space Rays 320 320
$C$4 Dozens Zappers 360 360

Constraints
Cell Name Cell Value Formula Status Slack
$D$7 Plastic Total 1000 $D$7<=$F$7 Binding 0
$D$8 Prod. Time Total 2400 $D$8<=$F$8 Binding 0
$D$9 Total Total 680 $D$9<=$F$9 Not Binding 20
$D$10 Mix Total -40 $D$10<=$F$10 Not Binding 390
21
Using Excel Solver –Sensitivity
Report
Microsoft Excel Sensitivity Report
Worksheet: [[Link]]Sheet1
Report Created:

Adjustable Cells
Final Reduced Objective Allowable Allowable
Cell Name Value Cost Coefficient Increase Decrease
$B$4 Dozens Space Rays 320 0 8 2 4.25
$C$4 Dozens Zappers 360 0 5 5.666666667 1

Constraints
Final Shadow Constraint Allowable Allowable
Cell Name Value Price R.H. Side Increase Decrease
$D$7 Plastic Total 1000 3.4 1000 100 400
$D$8 Prod. Time Total 2400 0.4 2400 100 650
$D$9 Total Total 680 0 700 1E+30 20
$D$10 Mix Total -40 0 350 1E+30 390

22
Another Example:
Cost Minimization Diet Problem
• Mix two sea ration products: Texfoods, Calration.
• Minimize the total cost of the mix.
• Meet the minimum requirements of Vitamin A,
Vitamin D, and Iron.

23
 Cost Minimization Diet Problem
• Decision variables
– X1 (X2) -- The number of two-ounce portions of
Texfoods (Calration) product used in a serving.
• The Model
Minimize 0.60X1 + 0.50X2 Cost per 2 oz.
Subject to
20X1 + 50X2  100 Vitamin A
% Vitamin A 25X1 + 25X2  100 Vitamin D
provided per 2 oz. 50X1 + 10X2  100 Iron
% required
X1, X2  0
24
The Diet Problem - Graphical solution
10
The Iron constraint

Feasible Region

Vitamin “D” constraint

Vitamin “A” constraint

2 4 5 25
 Cost Minimization Diet Problem
• Summary of the optimal solution

– Texfood product = 1.5 portions (= 3 ounces)

Calration product = 2.5 portions (= 5 ounces)

– Cost =$ 2.15 per serving.

– The minimum requirement for Vitamin D and iron are met with
no surplus.

– The mixture provides 155% of the requirement for Vitamin A.

26