Linear Programming Sensitivity analysis

Math2208

Adugna Fita Gabissa

Departement of Applied Mathematice

College of Applied Natural Science
Adama Science and Technology University
email:[Link]@[Link]

December 5, 2024
 Sensitivity analysis

Outline

1 Sensitivity analysis
Shadow Prices

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 2 / 23

 Sensitivity analysis

Sensitivity analysis

Sensitivity analysis is a systematic study of how sensitive the LP’s

optimal solution is to (small) changes in the LPs parameters, i.e.
how changes in some parameters affect the optimal solution.
If a parameter changes, sensitivity analysis often makes it
unnecessary to solve the considered LP problem again.
A knowledge of sensitivity analysis often enables the analyst to
determine from the original optimal solution how the changes in an
LP’s parameters change the optimality.

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 3 / 23

 Sensitivity analysis

Sensitivity analysis

Sensitivity analysis in LP is presented to give answers to questions of the

following forms:
1. If the objective function changes, how does the optimal solution
change?
2. If the amount of resources available changes, how does the optimal
solution change?
3. If an additional constraint is added to the LP, how does the optimal
solution change?
Usually, sensitivity analysis is performed on ”individual” variables, i.e. in
each specific analysis only one parameter of the LP changes and all the
other parameters remain fixed at their original values.

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 4 / 23

 Sensitivity analysis

Sensitivity analysis
We will discuss how 6 types of changes on LP’s parameters change the
optimal solution:
1. Changing the objective function coefficient of a nonbasic
variable: If the objective function coefficient for a nonbasic variable
xj is changed, the current basis remains optimal if c̄j ≥ 0. If c̄j < 0,
then the current basis is no longer optimal, and xj will be a basic
variable in the new optimal solution.
2. Changing the objective function coefficient of a basic variable:
If the objective function coefficient of a basic variable xj is changed,
then the current basis remains optimal if the coefficient of every
variable in row 0 of the B tableau remains nonnegative. If any
variable in row 0 has a negative coefficient, then the current basis is
no longer optimal.
3. Changing the right-hand side of a constraint: If the right-hand
side of a constraint is changed, then the current basis remains
optimal if the right-hand side of each constraint in the tableau
remains nonnegative. If the right-hand side of any constraint is
negative, then the current basis is infeasible, and a new optimal
solution must be found.
Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 5 / 23
 Sensitivity analysis

Sensitivity analysis

4. Changing a column of a nonbasic variable: If the column of a

nonbasic variable xj is changed, then the current basis remains
optimal if c̄j ≥ 0. If c̄j < 0, then the current basis is no longer
optimal and xj will be a basic variable in the new optimal solution. If
the column of a basic variable is changed, then it is usually difficult
to determine whether the current basis remains optimal. This is
because the change may affect both B and cB and thus the entire
row 0 and the entire right-hand side of the optimal tableau. As
always, the current basis would remain optimal if and only if each
variable has a nonnegative coefficient in row 0 and each constraint
has a nonnegative right-hand side.
5. Adding a new variable: If a new column (corresponding to a
variable xj ) is added to an LP, then the current basis remains
optimal if c̄j ≥ 0. If c̄j < 0, then the current basis is no longer
optimal and xj will be a basic variable in the new optimal solution.
6. Adding a new constraint. (see dual-simplex)

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 6 / 23

 Sensitivity analysis

Sensitivity analysis

To learn how to perform sensitivity analysis on an arbitrary LP, we recall

the algebraic Simplex tableau. Assume that in an arbitrary LP in
standard form: So, the LP can be written as

max z = cB xB + cN xN
s.t. BxB + NxN = b (1.1)
xB , xN ≥ 0

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 7 / 23

 Sensitivity analysis

Sensitivity analysis

The initial tableau has the form

Basic B N RHS
z cB cN z value

xB Bm×m Nm×(n−m) b

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 8 / 23

 Sensitivity analysis

Formulas for Computing the Optimal Tableau

1. Right-hand side of optimal tableau’s constraints: b̄ = B −1 b.

2. Right-hand side of optimal row 0: z̄ = cB B −1 b = cB b̄

3. xj columns in optimal tableau’s constraints: āj = B −1 aj . In general,

xN columns in optimal tableau’s constraints: N̄ = B −1 N and xN
column in optimal tableau’s constraints = Im .
4. (a) c̄j = cB B −1 aj − cj .

(b) c̄si = i th element in cB B −1 .

(c) c̄ei = −i th element in cB B −1 .
(d) In maximization LP, c̄ai = i th element in cB B −1 + M.
(e) In minimization LP, c̄ai = i
th element in cB B −1 − M.
(f) In general,c̄N = cB B −1 N − cN = cB N̄ − cN .

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 9 / 23

 Sensitivity analysis

Sensitivity analysis

the Optimal Tableau

Basic B N RHS
cB B −1 N − cN cB B −1 b


z 0

xB Im×m B −1 Nm×(n−m) B −1 b

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 10 / 23

 Sensitivity analysis

Sensitivity analysis
Example 1
Consider the following LP:

max z = 60x1 + 30x2 + 20x3 (1.2)

s.t. 8x1 + 6x2 + x3 ≤ 48 (1.3)
3
4x1 + 2x2 + x3 ≤ 20 (1.4)
2
3 1
4x1 + x2 + x3 ≤ 8 (1.5)
2 2
x1 , x2 , x3 ≥ 0 (1.6)

After adding slack variables s1 ; s2 , and s3 , the optimal tableau is:

Basic x1 x2 x3 s1 s2 s3 RHS
z 0 5 0 0 10 10 280
s1 0 −2 0 1 2 −8 24
x3 0 −2 1 0 2 −4 8
5
x1 1 4 0 0 − 12 3
2 2
Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 11 / 23
 Sensitivity analysis

Sensitivity analysis

1. Suppose we change the objective function coefficient of x2 from 30

to 30 + 4. For what values of 4 will the current set of basic
variables remain optimal ?
Solution: From the optimal tableau we know that B = {s1 , x3 , x1 }
and N = {x2 , s2 , s3 } , then
 
h i h i 48
cB = 0 20 60 , cN = 30 0 0 , and b = 20 ,
 

     
1 1 8 1 2 −8 6 0 0
B = 0 3
4 , B −1 = 0 2 −4 , and N =  2 1 0 ,
     
2
1
0 2 2 0 − 12 3
2
3
2 0 1

Because x2 is a nonbasic variable, cB has not changed.

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 12 / 23

 Sensitivity analysis

Change in the Objective Coefficient

Change in the Objective Coefficient
How we approach a change in coefficient of the objective function
depends on whether the coefficient is associated with a basic or a
nonbasic variable in the optimal bfs.
1. Suppose we change the objective function coefficient of x2 from 30
to 30 + 4. For what values of 4 will the current set of basic
variables remain optimal ?
Thus, B will remain optimal if

c̄N = cB B −1 N − cN
  
h i 1 2 −8 6 0 0 h i
= 0
20 60 0 2 −4  2 1 0 − 30 + 4 0 0
  

0 − 12 3
2
3
2 0 1
h i
= 5 − 4 10 10 ≥ 0
∴ 4 ≤ 5

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 13 / 23

 Sensitivity analysis

Sensitivity analysis

2. Suppose we change the objective function coefficient of x1 from 60

to 60 + 4. For what values of 4 will the current set of basic
variables remain optimal ? Solution: The B will remain optimal if

c̄N = cB B −1 N − cN
  
h i 1 2 −8 6 0 0 h i
= 0 20 60 + 4 0 2 −4  2 1 0 − 30 0 0
  

0 − 21 3 3
0 1
h i2 2

= 5 + 54 4 10 − 12 4 10 + 23 4 ≥ 0
h i
∴ 4 ∈ −4 20

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 14 / 23

 Sensitivity analysis

Change in the Right Hand Side

Suppose now that there is a change in the rhs of a constraint. This will
affect the values of the basic variables, and hence also the optimal
objective value. That is, the rhs column in the Simplex tableau is
affected. Hence, the feasibility rather than optimality is affected
3. Suppose we change the right-hand-side of the second constraint from
20 to 20 + 4. For what values of 4 will the current set of basic
variables remain optimal ? Solution: The B will remain optimal if

= B −1
b̄ b    
1 2 −8 48 24 + 24
= 0 2 −4 20 + 4 =  8 + 24  ≥ 0
    

0 − 12 3
2 8 2 − 12 4
h i
∴ 4 ∈ −4 4

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 15 / 23

 Sensitivity analysis

Sensitivity analysis
4. Suppose we change the elements of the column for x2 from
   
30 43
6 5
   
  to  .
2 2
3
2 2

Would this change the optimal solution to the problem ?

Solution: Thus, B will remain optimal if c̄N ≥ 0. But

c̄N = cB B −1 N − cN
  
h i 1 2 −8 5 0 0 h i
= 0 20 60 0 2 −4 2 1 0 − 43 0 0
  

0 − 12 3
2 2 0 1
h i
= −3 10 10  0

∴ The current basis is no longer optimal.

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 16 / 23
 Sensitivity analysis

Sensitivity analysis

5. Suppose we add new activity or new variable x4 to the problem, and

we add the column  
15
1
 
 
1
1
for x4 to the problem. How will the addition of the new activity
change the optimal tableau? Solution:Because

c̄x4 = cB B −1 a4 − cx4
  
h i 1 2 −8 1 h i
= 0 20 60 0 2 −4 1 − 15
  

0 − 12 3
2 1
= 5≥0

∴ The current basis is still optimal.

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 17 / 23

 Sensitivity analysis

Shadow Prices

It is often important for managers to determine how a change in a

constraint’s right-hand side changes the LP’s optimal z−value.
Definition 2
The shadow price of the i th constraint is the amount by which the
optimal value of the objective function is improved (improved means
increased in max LP and decreased in min LP) if we increase bi (the RHS
of that constraint) by 1 (from bi to bi + 1).

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 18 / 23

 Sensitivity analysis

Shadow Prices

1. The previous definition assumes that after the RHS of constraint i

has been changed to bi + 1, the current basis remains optimal.
2. The shadow price of the i th constraint of a max LP is the optimal
value of the i th dual variable yi . Also, the shadow price of the i th
constraint of a min LP is −1×the optimal value of the i th dual
variable yi

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 19 / 23

 Sensitivity analysis

Shadow Prices

 
b1
 . 
 . 
h i . 
z̄new = yb = ȳ1 · · · ȳi · · · ȳm bi + 1
 
 . 
 . 
 . 
bm
= ȳ1 b1 + · · · + ȳi (bi + 1) + · · · + ȳm bm
= ȳ1 b1 + · · · + ȳi bi + · · · + ȳm bm + ȳi
= z̄old + ȳi
∴ z̄new − z̄old = ȳi

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 20 / 23

 Sensitivity analysis

Shadow Prices

3. In max LP, the shadow price for a (≤) constraint is nonnegative, for
a (≥) is nonpositive, and for (=) is urs. Also, in min LP, the shadow
price for a (≤) constraint is nonpositive, for a (≥) is nonnegative,
and for (=) is urs.
4. In general, if the RHS of the i th constraint is increased by an
amount 4bi , then

z̄new = z̄old + (4bi )ȳi if the LP is max

z̄new = z̄old − (4bi )ȳi if the LP is min

Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 21 / 23

 Sensitivity analysis

Shadow Prices
Example 3
Consider the following LP.

max z = 15x1 + 25x2

s.t. 3x1 + 4x2 ≤ 100
2x1 + 3x2 ≤ 70
x1 + 2x2 ≤ 30
x2 ≥ 3
x1 , x2 ≥ 0

The optimal solution of the problem is z = 435, when x1 = 24 and

x2 = 3, where the Row 0 in the optimal tableau (after adding slack
variables s1 , s2 , s3 to the first three constraints respectively and
subtracting excess variable e4 from the last constraint then adding to it
an artificial variable a4 ) is
z + 15s3 + 5e4 + (M − 5)a4 = 435.
Adugna F Gabissa Linear optimization, Sensitivity analysis December 5, 2024 22 / 23
 Sensitivity analysis

Shadow Prices
1. Find the shadow price of each constraint.
Solution: The shadow price of each constraint is the optimal value
of the corresponding dual variable of each constraint. So,
y1 = 0, y2 = 0, y3 = 15, y4 = −5
2. Assuming the current basis remains optimal, what would the change
on the z−value be if the RHS of the
(a) 3rd constraint were changed from 30 to 35 ?
Solution:
 
100
h i  70 
z̄new = ȳ b = 0 0 15 −5   = 510
 
 35 
3
(b) 4th constraint were changed from 3 to 2 ?
Solution:
 
100
h i  70 
z̄new = ȳ b = 0 −5   = 440
 
0 15
 30 
Adugna F Gabissa 2
Linear optimization, Sensitivity analysis December 5, 2024 23 / 23