ISL 323E Operations Research
Fall 2024
Assoc. Prof. Dr. Fuat Kosanoğlu
ISL 323E Operations Research
Week VII
26 November 2024
Sensitivity Analysis
Sensitivity analysis is concerned with how
changes in an LP’s parameters affect the optimal
solution.
We will first look into geometric interpretation of
sensitivity analysis.
2/68
Shadow price
Shadow price: In LP, if the right-hand side of
the ith constraint is increased by 1, the amount of
change in the optimal z-value is called shadow
price.
◼ Increase in a max problem
◼ And decrease in a min problem
◼ If inequality is “≥” , the shadow price ≤ 0
◼ If inequality is “≤” , the shadow price ≥ 0
3/68
Graphical Introduction to Sensitivity Analysis
Ex: Giapetto produces two types of toy.
◼ 𝑥1 : number of soldiers produced per week
◼ 𝑥2 : number of trains produced per week
Max Z= 3𝑥1 + 2𝑥2
Subject to
2𝑥1 + 𝑥2 ≤ 100 (Finishing constraint)
𝑥1 + 𝑥2 ≤ 80 (carpentry constraint)
𝑥1 ≤ 40 (Demand constraint)
𝑥1 ≥0
𝑥2 ≥0
The optimal solution: z=180, 𝑥1 = 20, 𝑥2 = 60
What are the values of slack variables?
4/68
X2
The optimal solution for this LP
100
was z = 180, x1=20, x2= 60 (point finishing constraint
Slope = -2
B) and it has x1, x2, and s3 (the A Feasible Region
80
slack variable for the demand demand constraint
constraint) as basic variables. Isoprofit line z = 120
60
B Slope = -3/2
How would changes in the
problem’s objective function D
40
carpentry constraint
Slope = -1
coefficients or right-hand side
values change this optimal
20
C
solution?
10 20 40 50 60 80 X1
5/68
Graphical analysis of the effect of a change in an
objective function value for the Giapetto LP shows:
◼ By inspection, we can see that making the slope of the
isoprofit line more negative than the finishing
constraint (slope = -2) will cause the optimal point to
switch from point B to point C.
◼ Likewise, making the slope of the isoprofit line less
negative than the carpentry constraint (slope = -1) will
cause the optimal point to switch from point B to point
A.
◼ Clearly, the slope of the isoprofit line must be between
-2 and -1 for the current basis to remain optimal.
6/68
A graphical analysis can also be used to determine
whether a change in the rhs of a constraint will
make the current basis no longer optimal.
For example, let b1 = number of available finishing
hours.
The current optimal solution (point B) is where the
carpentry and finishing constraints are binding.
If the value of b1 is changed, then as long as where
the carpentry and finishing constraints are binding,
the optimal solution will still occur where the
carpentry and finishing constraints intersect.
7/68
In the Giapetto problem to the X2
finishing constraint, b1 = 120
100
right, we see that if b1 > 120, finishing constraint, b1 = 100
x1 will be greater than 40 and A
Isoprofit line z = 120
80
will violate the demand demand constraint
constraint. Also, if b1 < 80, x1 finishing constraint, b1 = 80
60
will be less than 0 and the B
nonnegativity constraint for x1 D
40
carpentry constraint
will be violated.
Therefore: 80 ≤b1≤ 120 Feasible Region
20
C
The current basis remains
optimal for 80 ≤b1≤ 120, but 20 40 50 60 80 X1
the decision variable values
and z-value will change.
8/68
It is often important to determine how a change in a constraint’s rhs
changes the LP’s optimal z-value.
The shadow price for the ith constraint of an LP is the amount by
which the optimal z-value is improved if the rhs of the ith
constraint is increased by one.
◼ This definition applies only if the change in the rhs of constraint i leaves the
current basis optimal.
For the finishing constraint, 100 + finishing hours are available.
◼ The LP’s optimal solution is then
x1 = 20 + and x2 = 60 – with z = 3x1 + 2x2 = 3(20 + ) + 2(60 - ) = 180
+ .
◼ Thus, as long as the current basis remains optimal, a one-unit increase in the
number of finishing hours will increase the optimal z-value by $1. So, the
shadow price for the first (finishing hours) constraint is $1.
9/68
Sensitivity analysis is important for several reasons:
◼ Values of LP parameters might change. If a parameter
changes, sensitivity analysis shows it is unnecessary to
solve the problem again.
For example in the Giapetto problem, if the profit
contribution of a soldier changes to $3.50, sensitivity
analysis shows the current solution remains optimal.
◼ Uncertainty about LP parameters.
In the Giapetto problem for example, if the weekly demand
for soldiers is at least 20, the optimal solution remains 20
soldiers and 60 trains. Thus, even if demand for soldiers is
uncertain, the company can be fairly confident that it is still
optimal to produce 20 soldiers and 60 trains.
10/68
Computer and Sensitivity Analysis
If an LP has more than two decision variables,
the range of values for a rhs (or objective
function coefficient) for which the basis remains
optimal cannot be determined graphically.
These ranges can be computed by hand but this is
often tedious, so they are usually determined by a
packaged computer program.
GAMS or EXCEL solver will be used and the
interpretation of its sensitivity analysis discussed.
11/68
Example : Winco Products 1
Winco sells four types of products. The resources
needed to produce one unit of each are known.
Product 1 Product 2 Product 3 Product 4
Raw material 2 3 4 7
Hours of labor 3 4 5 6
Sales price $4 $6 $7 $8
To meet customer demand, exactly 950 total units
must be produced.
Customers demand that at least 400 units of
product 4 be produced.
Formulate an LP to maximize profit.
12/68
Example 1: Solution
Let xi = number of units of product i produced
by Winco.
The Winco LP formulation:
max z = 4x1 + 6x2 +7x3 + 8x4
s.t. x1 + x2 + x3 + x4 = 950
x4 ≥ 400
2x1 + 3x2 + 4x3 + 7x4 ≤ 4600
3x1 + 4x2 + 5x3 + 6x4 ≤ 5000
x1,x2,x3,x4 ≥ 0
13/68
Ex. 1 – Solution continued
Lets look at GAMS output.
Reduced cost is the amount the objective
function coefficient for variable i would
have to be increased for there to be an
alternative optimal solution.
14/68
Ex. 1 – Solution continued
GAMS sensitivity analysis output
Allowable range (w/o changing basis) for the x2
coefficient (c2) is: 5.50 ≤ c2 ≤ 6.667
Allowable range (w/o changing basis) for the rhs (b1) of
the first constraint is:
850 ≤ b1 ≤ 1000
Shadow prices are shown in the Marginal value section of
GAMS output.
Shadow prices are the amount the optimal z-value
improves if the rhs of a constraint is increased by one unit
(assuming no change in basis).
15/68
Shadow price signs
1. Constraints with ≥ symbols will always have
nonpositive shadow prices.
2. Constraints with ≤ will always have
nonnegative shadow prices.
3. Equality constraints may have a positive, a
negative, or a zero shadow price.
16/68
For any inequality constraint, the product of the values of
the constraint’s slack/excess variable and the constraint’s
shadow price must equal zero.
◼ This implies that any constraint whose slack or excess variable >
0 will have a zero shadow price.
◼ Similarly, any constraint with a nonzero shadow price must be
binding (have slack or excess equaling zero).
◼ For constraints with nonzero slack or excess, relationships are
detailed in the table below:
Type of Constraint Allowable Increase for rhs Allowable Decrease for rhs
≤ ∞ = value of slack
≥ = value of excess ∞
17/68
When the optimal solution is degenerate (a bfs is
degenerate if at least one basic variable in the optimal
solution equals 0), caution must be used when interpreting
the GAMS output.
For an LP with m constraints, if the optimal GAMS output
indicates less than m variables are positive, then the
optimal solution is degenerate bfs.
MAX 6 X1 + 4 X2 + 3 X3 + 2 X4
SUBJECT TO
2) 2 X1 + 3 X2 + X3 + 2 X4 <= 400
3) X1 + X2 + 2 X3 + X4 <= 150
4) 2 X1 + X2 + X3 + 0.5 X4 <= 200
5) 3 X1 + X2 + X4 <= 250
18/68
Since the LP has four constraints and in the optimal
solution only two variables are positive, the optimal
solution is a degenerate bfs.
19/68
GAMS Output
20/68
Managerial Use of Shadow Prices
The managerial significance of shadow prices
is that they can often be used to determine the
maximum amount a manager should be
willing to pay for an additional unit of a
resource.
21/68
Example : Winco Products 2
Reconsider the Winco to the right.
What is the most Winco should be willing to
pay for additional units of raw material or
labor?
22/68
Example : Solution
The shadow price for raw MAX 4 X1 + 6 X2 + 7 X3 + 8 X4
SUBJECT TO
2) X1 + X2 + X3 + X4 = 950
material constraint (row 4) 3) X4 >= 400
4) 2 X1 + 3 X2 + 4 X3 + 7 X4 <= 4600
5) 3 X1 + 4 X2 + 5 X3 + 6 X4 <= 5000
shows an extra unit of raw END
LP OPTIMUM FOUND AT STEP 4
material would increase OBJECTIVE FUNCTION VALUE
1) 6650.000
revenue $1. VARIABLE VALUE REDUCED COST
X1 0.000000 1.000000
◼ Winco could pay up to $1 for an X2
X3
400.000000
150.000000
0.000000
0.000000
X4 400.000000 0.000000
extra unit of raw material and be
ROW SLACK OR SURPLUS DUAL PRICES
as well off as it is now. 2)
3)
0.000000
0.000000
3.000000
-2.000000
4) 0.000000 1.000000
Labor constraint’s (row 5) 5)
NO. ITERATIONS=
250.000000
4
0.000000
shadow price is 0 meaning that
an extra hour of labor will not
increase revenue.
◼ So, Winco should not be willing
to pay anything for an extra hour
of labor.
23/68
Glass Example
x1 = # of cases of 200 ml juice glasses (*100)
x2 = # of cases of 300 ml juice glasses (*100)
x3 = # of cases of champagne glasses (*100)
max 5 x1 + 4.5 x2 + 6 x3 (*$100)
s.t 6 x1 + 5 x2 + 8 x3 60 (prod. cap. in hrs)
10 x1 + 20 x2 + 10 x3 150 (warehose capacity 𝑚2 )
x1 8 (200 ml glass demand)
x1 0, x2 0, x3 0
24/68
Increasing Production Capacity
Let’s look at the objective function if we change the production
time from 60 and keep all other values the same.
Production Optimal Difference
hours obj. value
60 51.43
61 52.21 0.78
The shadow Price is
62 53 0.78 =0.78
63 53.78 0.78
25/68
Increase Production Hours More
Production Optimal Difference
hours obj. value
64 54.57 0.78
The shadow Price is
65 55.36 0.78 0.78 until
66 56.1 0.73 production = 65.5
67 57.77 0.68
26
26/68
How do we interpret the intervals?
If we change one coefficient in the RHS, say
production capacity, by the “basis” remains
optimal, that is, the same equations remain
binding.
So long as the basis remains optimal, the shadow
prices are unchanged.
The basic feasible solution varies linearly with
. If is big enough or small enough the basis
will change.
27/68
Sign of Shadow Prices
max 5 x1 + 4.5 x2 + 6 x3 (*$100)
s.t 6 x1 + 5 x2 + 8 x3 60 (prod. cap. in hrs)
10 x1 + 20 x2 + 10 x3 150 (warehose capacity 𝑚2 )
x1 8 (200 ml glass demand)
x1 0, x2 0, x3 0
The shadow price is the “increase” in the optimal value per unit
increase in the RHS.
If an increase in RHS coefficient leads to an increase in optimal
objective value, then the shadow price is positive.
If an increase in RHS coefficient leads to a decrease in optimal
objective value, then the shadow price is negative 29
29/68
Sign of Shadow Prices
max 5 x1 + 4.5 x2 + 6 x3 (*$100)
s.t 6 x1 + 5 x2 + 8 x3 60 (prod. cap. in hrs)
10 x1 + 20 x2 + 10 x3 150 (warehose capacity 𝑚2 )
x1 8 (200 ml glass demand)
x1 0, x2 0, x3 0
The shadow price of the production capacity constraint cannot be
negative.
Because any feasible solution for this problem remains feasible after
the production capacity increases. So, the increase in production
capacity cannot cause the optimum objective value to go down.
30
30/68
Signs of Shadow Prices
max 5 x1 + 4.5 x2 + 6 x3 (*$100)
s.t 6 x1 + 5 x2 + 8 x3 60 (prod. cap. in hrs)
10 x1 + 20 x2 + 10 x3 150 (warehose capacity 𝑚2 )
x1 8 (200 ml glass demand)
x1 0, x2 0, x3 0
The shadow price of the “x1 0” constraint cannot be positive.
Reason: Let x* be the solution if we replace the constraint “x1 0” with
the constraint “x1 1”. Then x* is feasible for the original problem,
and thus the original problem has at least as high an objective value.
31
31/68
Signs of Shadow Prices for minimization problems
“ constraint” . The shadow price is … ?
“ constraint” . The shadow price is … ?
“ = constraint”. The shadow price could be ...?
32
32/68
Signs of Shadow Prices
“ constraint” . The shadow price is non-
negative.
“ constraint” . The shadow price is non-positive.
“ = constraint”. The shadow price could be zero
or positive or negative.
33
33/68
Signs of Shadow Prices for minimization problems
“ constraint” . The shadow price is non-
negative ?
“ constraint” . The shadow price is non-
positive ?
“ = constraint”. The shadow price could be
zero or positive or negative.
34
34/68
Dual-Shadow Price in Minimization
For maximization problems dual variable and
shadow prices are the same.
For minimization problems, shadow prices are
the negative of dual variable.
35/68
The shadow price of a non-binding constraint is 0
max 5 x1 + 4.5 x2 + 6 x3 (*$100)
s.t 6 x1 + 5 x2 + 8 x3 60 (prod. cap. in hrs)
10 x1 + 20 x2 + 10 x3 150 (warehose capacity 𝑚2 )
x1 8 (200 ml glass demand)
x1 0, x2 0, x3 0
In the optimal solution x1 = 6 + 3/7.
Is shadow price for the constraint “x1 8” is zero ?
Yes: Because if optimum solution has x1 < 8, one does not get
a better solution by permitting x1 > 8. 36
36/68
Do the non-negativity constraints have shadow prices?
Yes. They are very special and are called reduced
costs
Look at the reduced costs for
◼ 200 ml glasses : reduced cost = 0
◼ 300 ml glasses : reduced cost = 0
◼ Champagne glasses : reduced cost = -4/7
37
37/68
What is the managerial interpretation of a reduced cost?
Reduced cost is an important value for the decision
maker.
We are currently not producing champagne glasses.
How much would the profit of champagne glasses need
to go up for us to produce champagne glasses in an
optimum solution?
The reduced cost for champagne classes is –4/7. If we
increase the revenue for these glasses by 4/7 (from 6 to
6 + 4/7), then there will be an alternative optimum in
which champagne glasses are produced.
38/68
Reduced costs can be derived from shadow
prices (Pricing Out)
Shadow Price
max 5 x1 + 4.5 x2 + 6 x3 (*$100)
s.t 6 x1 + 5 x2 + 8 x3 60 ……11/14
10 x1 + 20 x2 + 10 x3 150 ……1/35
1 x1 8 …….0
x1 0, x2 0, x3 0
❑ Pricing out treats shadow prices as though they are real
prices. The result is the “reduced costs.”
❑ How ?
39
39/68
Pricing Out of x1
Shadow Price
max 5 x1 + 4.5 x2 + 6 x3 (*$100)
s.t 6 x1 + 5 x2 + 8 x3 60 ……11/14
10 x1 + 20 x2 + 10 x3 150 ……1/35
1 x1 8 …….0
x1 0, x2 0, x3 0
5
Reduced Cost of x1 = - 6 x 11/14
- 10 x 1/35
- 1 x0
= 5 – 33/7 – 2/7 = 0 40
40/68
Pricing Out of x2
Shadow Price
max 5 x1 + 4.5 x2 + 6 x3 (*$100)
……11/14
s.t 6 x1 + 5 x2 + 8 x3 60
……1/35
10 x1 + 20 x2 + 10 x3 150
1 x1 8 …….0
x1 0, x2 0, x3 0
4.5
Reduced cost of x2 = - 5 x 11/14
- 20 x 1/35
- 0 x0
= 4.5 – 55/14 – 4/7 = 0 41
41/68
Pricing Out of x3
Shadow price
max 5 x1 + 4.5 x2 + 6 x3 (*$100)
……11/14
s.t 6 x1 + 5 x2 + 8 x3 60
……1/35
10 x1 + 20 x2 + 10 x3 150
1 x1 8 …….0
x1 0, x2 0, x3 0
6
Reduced cost of x3 = - 8 x 11/14
- 10 x 1/35
- 0 x0
= 6 – 44/7 – 2/7 = -4/7 42
42/68
Can we use pricing out to figure out whether
a new type of glass should be produced?
Shadow price
max 5 x1 + 4.5 x2 + 7 x4 (*$100)
s.t 6 x1 + 5 x2 + 8 x4 60 ……11/14
10 x1 + 20 x2 + 20 x4 150 ……1/35
1 x1 8 …….0
x1 0, x2 0, x4 0
7
Reduced cost of x4 = - 8 x 11/14
- 20 x 1/35
- 0 x0
= 7 – 44/7 – 4/7 = 1/7 43
43/68
Pricing Out of xj
Shadow price
max 5 x1 + 4.5 x2 + cj xj (*$100)
s.t 6 x1 + 5 x2 + a1j xj 60 ……y1
10 x1 + 20 x2 + a2j xj 150 ……y2
……….. ………
………. + amjxj = bm ……ym
x1 0, x2 0, x3 0
Reduced cost of xj = ?
44
44/68