Sensitivity Analysis I
73-220 Lecture 09
1
Agenda ● ●
Last two weeks – Typical linear programming applications Sensitivity Analysis – Objective function coefficient changes (Range of optimality) – Changes in RHS of constraints (Shadow or Dual Price and Range of Feasibility) » Non-binding Constraints » Binding Constraints
●
Interpretation of Excel sensitivity report – Excel Solver – Sensitivity Report
●
Next Class 2
Sensitivity Analysis
●
Sensitivity analysis (or postoptimality analysis) is used to determine how the optimal solution is affected by changes, within specified ranges, in: – the objective function coefficients – the right-hand side (RHS) values
●
Sensitivity analysis is important to the manager who must operate in a dynamic environment with imprecise estimates of the coefficients.
●
Sensitivity analysis allows the manager to ask certain what-if questions about the problem. 3
Impact of Possible Changes ●
Change objective function coefficient – May or may not change optimal solution (can be assessed by reading the Excel sensitivity report)
●
Change existing constraint – RHS change: shift a constraint line – LHS coefficient : change slope; may change size of feasible region
●
Add new constraint – may decrease feasible region (if binding)
●
Remove constraint – may increase feasible region (if binding)
4
LP Example ●
Kelson makes 2 different types of baseball gloves: a regular glove and a catcher’s mitt. The firm has 900 hours of production time available in its cutting and sewing department, 300 hours available in its finishing department, and 100 hours available in its packaging and shipping department. The production time requirements and the profit contribution for each product are shown below. Assume that the company is interested in maximizing the total profit contribution. Regular
Cutting& Sewing 1 (hr)
Catcher
1.5
Model
Profit/glove
0.5
Packaging& Shipping 0.125
0.333
0.25
$8
Finishing
$5
5
LP Formulation - Verbal 3 Components 1) Decision variables – number of regular gloves to be produced – number of catcher’s mitts to be produced 2) Objective function – maximize the total profit contribution. 3) Constraints – cutting&sewing: 900 hours available – finishing: 300 hours available – packaging&shipping: 100 hours available
6
LP Formulation - Mathematical 1) Let x1 = number of regular gloves x2 = number of catcher’s mitts 2) Max z = 5x1 + 8x2 3) s.t. 1x1 + 1.5x2 ≤ 900
(Cut&Sew)
0.5 x1 + 0.333x2 ≤ 300(Finishing) 0.125x1 + 0.25x2 ≤ 100
(Pack&Ship)
x1, x2 ≥ 0
(Nonnegativity)
7
Graphical Solution C 900
Finish
600 400 Pack&Ship
(500, 150) Cut&Sew
0
600
800 900
R 8
Computer Solution P ro b le m D a ta G love M itt P rofit 5 8 C ut& S ew 1 1.5 <= F inishing 0.5 0.33 <= P ack& S hip 0.125 0.25 <= D e cisio n va ria b le s # of 500
900 300 100
150
O b je ctive fu n ctio n M ax 3700 C o n stra in ts LH S C ut& S ew F inishing P ack& S hip
T ype 725 <= 300 <= 100 <=
RHS 900 300 100 9
Computer Sensitivity To obtain the sensitivity report, highlight Sensitivity on the right box when Solver Result pop-up window is available. M icro so ft E xce l 1 1 .0 S e n sitivity R e p o rt W o rksh e e t: [2 2 0 -L e ctu re 0 9 .xls]K e lso n R e p o rt C re a te d : 9 /2 3 /2 0 0 5 1 0 :5 7 :4 2 A M
A djustable C ells C e ll $B $9 $C $9
N am e # of G love # of M itt
F in a l V a lu e
R e d u ce d C o st
500 150
O b je ctive C o e fficie n t
0 0
A llo w a b le In cre a se 5 8
A llo w a b le D e cre a se 7 1 2 4.666666667
C onstraints C e ll $B $16 $B $17 $B $18
N am e C ut& S ew LH S F inishing LH S P ack& S hip LH S
F in a l V a lu e 725 300 100
S hadow P rice 0 3 28
C o n stra in t R .H . S id e 900 300 100
A llo w a b le In cre a se
A llo w a b le D e cre a se
1E +30 175 100 166.6666667 35 25 10
Obj. Func. Coeff. Change If an objective function coefficient changes, slope of objective function line changes. At some threshold, another corner point may become optimal. ● Question: How much can objective coefficient change without changing optimal corner point? ● This change is usually referred to as Range of Optimality ●
11
Range of Optimality A range of optimality of an objective function coefficient is found by determining an interval for the coefficient in which the original optimal solution remains optimal while keeping all other data of the problem constant. (The value of the objective function may change in this range.) ● This range of optimality can be found in the Solver sensitivity report. ●
12
Range of Optimality– Computer output M icro so ft E xce l 1 1 .0 S e n sitivity R e p o rt W o rksh e e t: [2 2 0 -L e ctu re 0 9 .xls]K e lso n R e p o rt C re a te d : 9 /2 3 /2 0 0 5 1 0 :5 7 :4 2 A M
A djustable C ells C e ll $B $9 $C $9
N am e # of G love # of M itt
F in a l V a lu e 500 150
R e d u ce d C o st 0 0
O b je ctive C o e fficie n t
A llo w a b le In cre a se 5 8
A llo w a b le D e cre a se 7 2
1 4.666666667
If the change in the objective function coefficients is within allowable limits, the current solution will remain optimal. The new OFV can be calculated by substituting the optimal solution in the new objective function.
13
Reduced Cost ●
●
●
The reduced cost for a decision variable whose value is 0 in the optimal solution is the amount the variable's objective function coefficient would have to improve (increase for maximization problems, decrease for minimization problems) before this variable could assume a positive value. The reduced cost for a decision variable with a positive value is 0. If reduced cost is zero for a variable which takes the value zero at optimality, this indicates that there are alternate optimal solutions.
14
Computer Output – Reduced Cost M icro so ft E xce l 1 1 .0 S e n sitivity R e p o rt W o rksh e e t: [2 2 0 -L e ctu re 0 9 .xls]K e lso n R e p o rt C re a te d : 9 /2 3 /2 0 0 5 1 0 :5 7 :4 2 A M
A djustable C ells C e ll $B $9 $C $9
N am e # of G love # of M itt
F in a l V a lu e 500 150
R e d u ce d C o st 0 0
O b je ctive C o e fficie n t
A llo w a b le In cre a se 5 8
A llo w a b le D e cre a se 7 2
1 4.666666667
Final value is non-zero for both variables, hence the reduced cost is zero. The objective function coefficient for either variable does not have to change before they assume non-zero values.
15
RHS Coefficient Changes ●
● ●
When a right-hand-side value changes, the constraint moves parallel to itself Question: How is the solution affected, if at all? Two cases: – constraint is binding or active – constraint is nonbinding or inactive
●
Common terms – Shadow price and dual price – Range of feasibility
16
Shadow Price (RHS coefficient) ●
●
●
A shadow price for a right hand side value (or resource limit) is the amount the objective function will change per unit increase in the right hand side value of a constraint. The shadow price is equal to the difference in the values of the objective functions between the new and original problems. The shadow price for a nonbinding constraint is 0.
17
Shadow vs Dual Prices Shadow Price: Amount objective function will change per unit increase in RHS value of constraint ● Some s/w pkgs calculate a dual price (defined differently) ●
– Amount objective function will improve per unit increase in constraint RHS value – so same for max, but opposite for min – Our text takes this approach, and uses it in all their examples 18
Shadow Price: Non-binding constraint Cutting Constraint: 1x1 + 1.5x2 ≤ 900 At optimality, LHS of the constraint is 725[x1=500 & x2=150]. This is not a binding constraint as LHS is not equal to RHS at optimality.Hence shadow price for this constraint is zero.
If cutting hours are reduced to 725 from 900, this constraint will still be satisfied. Hence allowable decrease is 900-725=175. Any further increase in cutting hours won’t change anything as we already have a surplus of cutting hours. Hence allowable increase is infinite. 19
Shadow Price –binding constraints
Finishing and Packing Constraints 0.5 x1 + 0.333x2 ≤ 300 Both these constraints are satisfied as equalities at optimality and hence they 0.125x1 + 0.25x2 ≤ 100 have non-zero shadow prices.
If we can get an extra hour of finishing, the profit would increase by 3 units. If we lose an hour of finishing, the profit would decrease by 3 units However, if we get an extra hour of packing, profit would increase by 28 units. Profit is more sensitive to changes in packing constraint than in finishing constraint. 20
Range of Feasibility ●
The range of feasibility for a change in the right hand side value is the range of values for this coefficient in which the original shadow price remains the same.
21
Range of Feasibility: Non-binding Constraints M icro so ft E xce l 1 1 .0 S e n sitivity R e p o rt W o rksh e e t: [2 2 0 -L e ctu re 0 9 .xls]K e lso n R e p o rt C re a te d : 9 /2 3 /2 0 0 5 1 0 :5 7 :4 2 A M
A djustable C ells C e ll $B $9 $C $9
N am e # of G love # of M itt
F in a l R e d u ce d V a lu e C o st 500 0 150 0
O b je ctive C o e fficie n t
F in a l V a lu e
C o n stra in t R .H . S id e
A llo w a b le In cre a se 5 8
A llo w a b le D e cre a se 7 1 2 4.666666667
C onstraints C e ll $B $16 $B $17 $B $18
N am e C ut& S ew LH S F inishing LH S P ack& S hip LH S
725 300 100
S hadow P rice 0 3 28
900 300 100
A llo w a b le In cre a se
A llo w a b le D e cre a se
1E +30 175 100 166.6666667 35 25
If the RHS of a non-binding constraint is changed within allowable limits, the optimal solution and OFV are unchanged. 22
Range of Feasibility: Binding (Computer Solution) M icro so ft E xce l 1 1 .0 S e n sitivity R e p o rt W o rksh e e t: [2 2 0 -L e ctu re 0 9 .xls]K e lso n R e p o rt C re a te d : 9 /2 3 /2 0 0 5 1 0 :5 7 :4 2 A M
A djustable C ells C e ll $B $9 $C $9
N am e # of G love # of M itt
F in a l V a lu e
R e d u ce d C o st
500 150
O b je ctive C o e fficie n t
A llo w a b le In cre a se
A llo w a b le D e cre a se
0 0
5 8
7 1 2 4.666666667
0 3 28
C o n stra in t R .H . S id e 900 300 100
A llo w a b le A llo w a b le In cre a se D e cre a se 1E +30 175 100 166.6666667 35 25
C onstraints C e ll $B $16 $B $17 $B $18
N am e C ut& S ew LH S F inishing LH S P ack& S hip LH S
F in a l V a lu e 725 300 100
S hadow P rice
As long as the change in RHS of the binding constraints is within the allowable limits, the current binding constraints will remain binding. The new OFV will change by an amount equal to shadow price multiplied by the change in RHS. The new optimal solution can be determined only by re-solving. 23
Tightening or Relaxing Constraints ●
Tightening a constraint means to make it more restrictive; i.e. decreasing the RHS of a ≤ constraint, or increasing the RHS of a ≥ constraint – compresses feasible region – may make solution worse
●
Relaxing a constraint means to make it less restrictive – expands feasible region – may make solution better 24
Multiple changes - 100% Rule ●
Simultaneous changes in coefficients (Obj. Func. OR RHS)will not change decision variables in optimal solution as long as sum of percentages of change divided by corresponding maximum allowable change in range of optimality for each coefficient does not exceed 100%
25
Kelson’s example re-visited
1. What if the profit contribution of a regular glove is $7 instead of $5? What if it is $4? • We can get 10 more hours in the Finishing Department. Does this increase our profit? If yes, by how much? If not, why not? • What is the maximum amount we should pay for obtaining an extra hour in Cutting and Sewing? • If we can get 3 more hours in Packing&Shipping or 20 hours in Finishing, which is better? • If the profit of a regular glove is increased to $6 and the profit of a catcher’s mitt is reduced to $7, what is the optimal solution and OFV? • If the available hours in cutting and sewing is reduced by 50 hours and the available hours in finishing is increased by 50 hours, what happens to the optimal solution and OFV? 26
Kelson’s example contd. 7. If management decides to impose a new constraint that at least a total of 600 gloves(includes both types of gloves) should be made, what is the new optimal solution and OFV? .
. 8. If there is a new constraint which says that number of regular gloves produced should be at least 4 times as many as catcher’s mitts, what is the new optimal solution and OFV? 9. If management wants to introduce a new product – baseball bats which yields a profit of $10 per bat, what is the new optimal solution and OFV? Each baseball bat requires 2 hours in cutting, 2 hours in finishing and 15 minutes in packing and finishing. 10. If we can have as many hours of finishing as we want at no extra cost, what is the new optimal solution and OFV?
27
Course Planning The dean of Western College of Business must plan the School’s course offerings for the fall semester. Student demands make it necessary to offer at least 30 undergraduate and 20 graduate courses in the term. Faculty contracts also dictate that at least 60 courses be offered in total. Each undergraduate course taught costs the college an average of $2500 in faculty wages and each graduate course costs $3000. How many undergraduate and graduate courses should be taught so that the total faculty salaries are kept to a minimum? • •
Model it as a linear programming model and solve graphically. The Excel sensitivity report for this problem is provided on the slide. Answer associated sensitivity questions on slide #30. 28
Sensitivity Report for the Course Planning Problem M icro so ft E xce l 1 0 .0 S e n sitivity R e p o rt W o rksh e e t: [2 2 0 -L e ctu re 0 9 .xls]C o u rse P la n n in g R e p o rt C re a te d : 1 0 /6 /2 0 0 5 1 1 :4 5 :5 4 A M
Adjustable Cells
C e ll $B$9 $C$9
N am e # of courses Undergrad # of courses Graduate
F in a l R e d u ce d V a lu e C o st 40 20
0 0
O b je ctive C o e fficie n t 2500 3000
A llo w a b le In cre a se 500 1E+30
A llo w a b le D e cre a se 2500 500
Constraints
C e ll $B$16 $B$17 $B$18
N am e Undergrad req LHS Graduate req LHS Total courses LHS
F in a l V a lu e 40 20 60
S hadow P rice 0 500 2500
C o n stra in t R .H . S id e 30 20 60
A llo w a b le In cre a se 10 10 1E+30
A llo w a b le D e cre a se 1E+30 20 10
29
Interpretation of Results 1. If the cost of an under-graduate course increases to $3000, what is the new optimal solution and OFV? 3. If the cost of undergraduate course decreases to $2000, what is the new optimal solution and OFV? 5. If the cost of undergraduate course increases by $250 and the cost of a graduate course increases by $500, what is the new optimal solution and OFV? 8. If there has to be at least 33 under graduate courses and 15 graduate courses, what is the new optimal solution and OFV? 11. If the total number of courses is at least 50, what is the new optimal solution and OFV?
30
Next Class ●
Homework: – Solve the course planning question given in this lecture note. » Graphically » Based on the sensitivity report on the slide, answer the sensitivity analysis questions
●
Sensitivity Analysis contd.
31