Sensitivity Analysis

Loukil Sana
Spring 2025

1
 Outline:

• Changes in the objective function coefficients

• Changes in the RHS of the constraints

• Addition /Deletion of a new constraint

• Addition /Deletion of a new activity/variable

2
Sensitivity Analysis:

• Is a post-optimality analysis

• Studies impact of parameter changes on optimal solution

• Defines range where optimality remains unchanged

• Useful for decision-making under uncertainty

3
VARIATION IN THE OBJECTIVE COEFFICIENTS

4
 Variation in the objective coefficients

• How much the objective-function coefficients can vary without

changing the values of the decision variables in the optimal solution?

5
 Range of the Coefficients (Sensitivity Range):
•For each coefficient ci, there is a range where the current optimal
solution remains unchanged.
•Within this range:
•The optimal solution stays the same
•The objective value changes proportionally with ci
•Outside this range:
•The optimal solution may change (a different solution can become
optimal)
•This interval is called the allowable range of the coefficient. 6
7
8
 Example1

Maxz = 10 x1 + 20 x2
The Optimal solution is given by:
x1 + x2  15 X1*= 2.5; X2* = 12.5;
4 x1 + 2 x2  40 Z* = 275

− x1 + x2  10
x1  20
We are interested in determining by how much we may
x1 , x2  0 change the coefficient c1 of X1 in the OF without affecting
optimality?

➔In order to answer, we need to carry out a sensitivity analysis to c1.

9
 Optimal Simplex tableau

CJ 10 20 0 0 0 0

Basis X1 X2 S1 S2 S3 S4 RHS

10 X1 1 0 1/2 0 -1/2 0 2.5

0 S2 0 0 -3 1 1 0 5
20 X2 0 1 1/2 0 1/2 0 12.5
0 S4 0 0 -1/2 0 1/2 1 17.5

ZJ 10 20 15 0 5 0 275

CJ -Zj 0 0 -15 0 -5 0

10
 C-bar values of all non-
Basic Variable basic variables are
impacted
Changes in the
Coefficients in the
Objective Function
Only its corresponding
Non-Basic Variable
c-bar changes

11
 By varying c1, the optimal tableau is modified as:

Cj 10 + c1 20 0 0 0 0
VB X1 X2 S1 S2 S3 S4 RHS
10 +c1 X1 1 0 1/2 0 -1/2 0 2.5
0 S2 0 0 -3 1 1 0 5
20 X2 0 1 1/2 0 1/2 0 12.5
0 S4 0 0 -1/2 0 1/2 1 17.5
Zj 10 +c1 20 15 +1/2c1 0 5 -1/2c1 0 275 +2.5c1
j 0 0 -15 -1/2c1 0 -5 +1/2c1 0

For the tableau to remain optimal, the c-bar values must remain <=0.

12
 -15 – ½ c1  0 Or -30  c1  10

-5 + ½ c1  0

Equivalently, 10-30  c1  10+10 ➔ -20  c1  20

Question: Determine the effect on Z if c’1 is equal to 25.

c1 = 10 c1 = 25 and hence c1 = 15

Note that c1[-20,20]. Thus Z and the basis solution [Link] optimal

simplex tableau becomes: 13

 Cj 10 +15 20 0 0 0 0

BV X1 X2 S1 S2 S3 S4 RHS

10 +15 X1 1 0 1/2 0 -1/2 0 2.5

0 S2 0 0 -3 1 1 0 5
20 X2 0 1 1/2 0 1/2 0 12.5
0 S4 0 0 -1/2 0 1/2 1 17.5

Zj 10 + 15 20 15 + 7.5 0 5 - 7.5 0 275 +37.5

j 0 0 -15 - 7.5 0 -5 + 7.5 0

14
By performing the next iteration, we obtain the following optimal
tableau:

Cj 25 20 0 0 0 0
VB X1 X2 S1 S2 S3 S4 bi
25 X1 1 0 -1 1/2 0 0 5
0 S3 0 0 -3 1 1 0 5
20 X2 0 1 2 -1/2 0 0 10
0 S4 0 0 1 -1/2 0 1 15
Zj 25 20 15 2,5 0 0 325
j 0 0 -15 -2,5 0 0 <=0

The new solution becomes: X1*= 5, X2* = 10 and Z* = 325.

15
Question: By how much we can modify the coefficient c2 of X2 in Z

without affecting the optimal solution?

To answer, we need to perform a sensitivity analysis to the variation of

c2 in the objective function.

c2 = 20 c2 = 20 + c2

16
 Cj 10 20 +c2 0 0 0 0
VB X1 X2 S1 S2 S3 S4 bi
10 X1 1 0 1/2 0 -1/2 0 2.5
0 S2 0 0 -3 1 1 0 5
20 +c2 X2 0 1 1/2 0 1/2 0 12.5
0 S4 0 0 -1/2 0 1/2 1 17.5
Zj 10 20 +c2 15 +1/2c2 0 5 +1/2c2 0 275 +12.5c2
j 0 0 -15 -1/2c2 0 -5 -1/2c2 0 <=0 !!!

For the tableau to remain optimal, row j must remain non-positive.

17
 -15 – ½ c2  0 Or just -30  c2

-5 – ½ c2  0 -10  c2

It follows that c2 ≥ 10 and hence optimality is preserved.

Question: What is the effect on optimality if the coefficient c2 takes the value 25?

c2= 20 c2 = 25 ≥ 10 ➔ c2 = c2 - c2 = 25 – 20 = 5

Therefore, optimality is preserved: X1*=2.5; X2*=12.5; Z*=337.5.

18
Changes in the RHS of a constraint

19
 Question1: By how many units can the availability of

resource 1 increase or decrease without affecting

Maxz = 10 x1 + 20 x2 feasibility or changing the optimal basis?
x1 + x2  15
4 x1 + 2 x2  40
✓ Constraint 1 is binding as the associated slack
− x1 + x2  10
x1  20 variable is non-basic (s1=0)

x1 , x2  0 ✓ Let b1 be the variation in RHS of the 1st constraint.

✓ The 1st constraint becomes X1 + X2  15 + b1

20
 Optimal Simplex tableau

CJ 10 20 0 0 0 0

Basis X1 X2 S1 S2 S3 S4 RHS

10 X1 1 0 1/2 0 -1/2 0 2.5

0 S2 0 0 -3 1 1 0 5
20 X2 0 1 1/2 0 1/2 0 12.5
0 S4 0 0 -1/2 0 1/2 1 17.5

ZJ 10 20 15 0 5 0 275

CJ -Zj 0 0 -15 0 -5 0

21
 The change in the RHS of the constraints would only affect the

corresponding column in the simplex tableau, the corresponding Slack

variable column.

• It suffices to take the coefficients of S1 in the last tableau as those of b1 in column bi .

22
CJ 10 20 0 0 0 0
Basis X1 X2 S1 S2 S3 S4 RHS
10 X1 1 0 1/2 0 -1/2 0 2.5 + 1/2 b1
0 S2 0 0 -3 1 1 0 5 – 3 b1
20 X2 0 1 1/2 0 1/2 0 12.5 + 1/2 b1
0 S4 0 0 -1/2 0 1/2 1 17.5 – 1/2 b1

ZJ 10 20 15 0 5 0 275 + 15 b1
J 0 0 -15 0 -5 0
23
 For the optimal basis to remain feasible and hence optimal, all the RHS values

must remain ≥ 0

2.5 + 1/2 b1  0 b1  -5

5 – 3 b1  0 b1  5/3

12.5 + 1/2 b1  0 ➔ b1  -25

17.5 – 1/2 b1  0 b1  35

➔ -5  b1  5/3 Or equivalently, 10  b1  50/3

The basis remains optimal as 10  b1  50/3

24
Question2: Determine the effect on Z if b1 takes the value 12?

b1’ = 15 + b1 = 12. Hence, b1 = -3.

The basis remains optimal as 10  b1’ 50/3

Feasibility interval

The range at which the RHS of a constraint may vary while preserving the optimal basis
of the last simplex tableau

25
Let: X1’* & X2’* form the new optimal solution

Y1*, Y2*, Y3* & Y4* constitute the dual optimal solution.

Then ZX’* = 10X1’* + 20X2’*

ZY’* = (15+b1)Y1* + 40Y2* + 10Y3* + 20Y4*

Given that ZX’* = ZY’*

It follows that ZX’* = (15+b1)Y1* + 40Y2* + 10Y3* + 20Y4*

ZX’* = ZY* + b1Y1*

ZX’* = ZX* + b1Y1* ➔ That is, ZX’* = 275 + 15 b1

26
 ZX’ = 275 + 15 b1

ZX’ = 275 + 15(-3) = 230

As a result, Z decreases by 45 units.

We may equivalently obtain the new optimal objective value. In fact, while keeping

a variation within the feasibility interval of the RHS, row j remains unchanged and

hence optimality is preserved.

27
Introducing a new constraint

28
 redundant and
Satisfied by the
optimality is
Optimal Solution
preserved
Introducing a
new constraint
Not satisfied by
optimality is not
the Optimal
preserved
Solution

New solution
will be worse

29
 ✓ Let consider an additional constraint: 2X1 + X2  15
Maxz = 10 x1 + 20 x2 ✓ Would the basis remain optimal after adding this new
x1 + x2  15 constraint? Without doing any calculations would the
4 x1 + 2 x2  40 total profit increase or decrease?
− x1 + x2  10
x1  20 The optimal Solution is: X1 = 2.5; X2 = 12.5; and Z = 275
x1 , x2  0 We plug in the Optimal Solution in the new constraint:
➔This constraint is not satisfied by the optimal
solution: 2 (2,5) + 12,5 = 17,5 > 15
30
Maxz = 10 x1 + 20 x2
If we solve the modified LP, we will find the following
x1 + x2  15 optimal solution:
4 x1 + 2 x2  40
− x1 + x2  10
X1* = 5/3, X2* = 35/3 & Z*= 250
x1  20
2 x1 + x2  15
x1 , x2  0 ➔New optimal solution is worse than the previous
one

31
 ✓ Suppose that the constraint is: 2X1 + X2  17,5
✓ Would the basis remain optimal after adding this new
Maxz = 10 x1 + 20 x2
x1 + x2  15 constraint?
4 x1 + 2 x2  40
The optimal Solution is: X1 = 2.5; X2 = 12.5; and Z = 275
− x1 + x2  10
x1  20 We plug in the Optimal Solution in the new constraint:
2 x1 + x2  17.5 ➔This constraint is satisfied by the optimal solution:
x1 , x2  0
2 (2,5) + 12,5 = 17,5
Then, it is considered redundant and will not impact
the optimal solution
32
Deleting a constraint

33
 Non-binding
No change in the
(Inactive)
Optimal Solution
constraint
Deleted
constraint

Binding (Active) Optimal Solution

constraint will change

34
 Deleting a Non-Binding Constraint
Maxz = 10 x1 + 20 x2 CJ 10 20 0 0 0 0
x1 + x2  15 Basis X1 X2 S1 S2 S3 S4 RHS
4 x1 + 2 x2  40 10 X1 1 0 1/2 0 -1/2 0 2.5
0 S2 0 0 -3 1 1 0 5
− x1 + x2  10 20 X2 0 1 1/2 0 1/2 0 12.5
x1  20 0 S4 0 0 -1/2 0 1/2 1 17.5
x1 , x2  0 ZJ 10 20 15 0 5 0 275
CJ -Zj 0 0 -15 0 -5 0
In order to delete the 2nd constraint (inactive), it suffices to delete row S2 & column S2.
CJ 10 20 0 0 0
Basis X1 X2 S1 S3 S4 RHS
10 X1 1 0 1/2 -1/2 0 2.5
20 X2 0 1 1/2 1/2 0 12.5
0 S4 0 0 -1/2 1/2 1 17.5
ZJ 10 20 15 5 0 275
CJ -Zj 0 0 -15 -5 0 35
 Deleting a Binding Constraint
Maxz = 10 x1 + 20 x2
x1 + x2  15
4 x1 + 2 x2  40
− x1 + x2  10
x1  20
2 x1 + x2  15
x1 , x2  0

In order to delete the 5th constraint (binding), we first introduce variable S5 in the
tableau, then we delete both the row and the column of S5. Finally, we continue
all required iterations till optimality is reached.

36
 First, we have to force S5 to enter the basis

CJ 10 20 0 0 0 0 0
Basis X1 X2 S1 S2 S3 S4 S5 RHS
10 X1 1 0 0 0 -1/3 0 1/3 5/3
0 S2 0 0 0 1 0 0 -2 10
20 X2 0 1 0 0 2/3 0 1/3 35/3
0 S4 0 0 0 0 1/3 1 -1/3 55/3
0 S1 0 0 1 0 -1/3 0 -2/3 5/3
J 0 0 0 0 -10 0 -10 250

37
 CJ 10 20 0 0 0 0 0
Basis X1 X2 S1 S2 S3 S4 S5 RHS
0 S5 3 0 0 0 -1 0 1 5
0 S2 6 0 0 1 -2 0 0 20
20 X2 -1 1 0 0 1 0 0 10
0 S4 1 0 0 0 0 1 0 20
0 S1 2 0 1 0 -1 0 0 5

J 30 0 0 0 -20 0 0 200

Now, we delete the row and column of S5, and continue until optimality

38
After deleting the row and the column of S5 and performing one iteration,
we obtain the following optimal tableau:

CJ 10 20 0 0 0 0
Basis X1 X2 S1 S2 S3 S4 RHS
0 S2 0 0 -3 1 1 0 5
20 X2 0 1 1/2 0 1/2 0 12.5
0 S4 0 0 -1/2 0 1/2 1 17.5
10 X1 1 0 1/2 0 -1/2 0 2.5

J 0 0 -15 0 -10 0 275

39
Introducing a new Variable

40
 The new LP is then:

Max Z = 10X1 + 20X2 + 10X3

Reconsider the last example and suppose X1+X2+X3  15

that a 3rd variable is introduced with a 4X1+2X2+2X3  40

coefficient of 10 in Z and coefficients of 1, 2,
-X1+X2  10
0 & 0 in 1st, 2nd, 3rd & 4th constraints,
X1  20
respectively.
X1, X2, X3  0
41
 Dual objective value
Constraint not satisfied
worsen = primal
by the dual Optimal
objective value
Introducing a variable Solution
improves
in the primal
=
adding a new
constraint in the dual Constraint satisfied by
the dual Optimal optimality is unchanged
Solution

42
variable X3 corresponds in the dual to adding the following constraint

Y1 + 2Y2 ≥ 10

This constraint is satisfied by the obtained optimal solution:

Y1 + 2Y2 = 1x15 + 2x0 = 15 ≥ 10.

The optimal solution remains unchanged

43
Introducing a new variable is We are usually interested in

particularly interesting when a assessing whether it is

new activity is under beneficial to go for such an

consideration such as a new activity by examining if the

product profit would increase

44
Deleting a new Variable

45
 The deleted variable
Optimality is
was non-basic (=0) at
preserved
the Optimal tableau
Deleting a variable X
=
adding a new constraint:
X = 0 in the primal The deleted variable Optimality will
was basic at the
Optimal tableau change

46