Sensitivity Analysis

Sensitivity Analysis

▪ In LP models, the parameters are usually not exact. Often, in real

situations, these parameters can only be good estimates of the real
problem inputs

▪ The parameters of the model can change without causing the optimum
solution to change

▪ Sensitivity analysis refers to the process of determining the range of

parameter(s) for which optimality or the optimal basis remains
unchanged

135
Sensitivity Analysis

▪ Sensitive parameters are those for which a small change may affect
optimality
▪ Hence, sensitive parameters should be estimated with a lot of care.
▪ For example:
for an estimated unit profit of a product, if sensitivity analysis reveals that the
optimum remains the same for ±10% change in the unit profit, we can conclude
that the solution is more robust than in the case where the indifference range is
only ±1%,

136
Sensitivity Analysis

The basic idea is to be able to give answers to questions of the form:

▪ If the objective function changes in its parameter ci , how does the

solution change?

▪ If the resources available change, how does the solution change?

▪ If a new constraint is added to the problem, how does the solution

change?

137
Sensitivity Analysis
Change in the Objective Function Coefficients

▪ When one or more of the objective function coefficients change, two cases
may develop:

► The obtained optimal solution remains optimal (even though the objective
value would change)

► The obtained optimal solution is no longer optimal.

138
Sensitivity Analysis
Change in the Objective Function Coefficients

▪ For each coefficient, it is possible to determine the range for which optimality
is preserved: optimality interval

▪ When optimality is preserved, then the Z-value will change when changing the
coefficient corresponding to a basic variable

▪ Otherwise, the Z-value will remain unchanged

139
Sensitivity Analysis
Change in the Objective Function Coefficients
Example
Max Z = 10X1 + 20X2 ▪ The optimal solution is given by:

ST
X1 + X 2  15 X1*= 2.5; X2* = 12.5; et Z* = 275.
4X1 + 2X2  40
-X1 + X2  10 ▪ We are interested in determining by how much we may
change the coefficient c1 of X1 in the objective function
X1  20
without affecting optimality.

X1, X2  0
▪ In order to answer, we need to carry out a sensitivity
analysis to c1.
140
Sensitivity Analysis
Change in the Objective Function Coefficients

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
C J - ZJ 0 0 -15 0 -5 0
141
Sensitivity Analysis
Change in the Objective Function Coefficients

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

CJ 10 + ∆c1 20 0 0 0 0
Basis 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
CJ - ZJ 0 0 -15- 1/2∆c1 0 -5 + 1/2 ∆c1 0

142
Sensitivity Analysis
Change in the Objective Function Coefficients

▪ To remain optimal, the non-positivity of row Cj-Zj must be preserved. That is:
-15 – ½ ∆c1 ≤ 0
-5 + ½ ∆ c1 ≤ 0
Or -30 ≤ ∆c1 ≤ 10

Equivalently, -20 ≤ c1’ ≤ 20

▪ Question: Determine the effect on Z if c1 is equal to 25.

c1 = 10, c1’ = 25 and hence ∆c1 = 15
143
▪ Note that c1’ ∉ [-20,20]. Thus Z changes
Sensitivity Analysis
Change in the Objective Function Coefficients

▪ The optimal simplex tableau becomes :

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
144
Sensitivity Analysis
Change in the Objective Function Coefficients

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 The new solution becomes:
0 S3 0 0 -3 1 1 0 5
20 X2 0 1 2 -1/2 0 0 10 X1*= 5, X2* = 10 and Z* = 325.
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 145
Sensitivity Analysis
Change in the Objective Function Coefficients

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

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

of c2 in the objective function.
➢ c2 = 20 and then c2’ = 20 + ∆c2

-15 – ½ c2  0
It follows that c2 ≥ 10 and hence
optimality is preserved
-5 – ½ c2  0

146
Sensitivity Analysis
Change in the Objective Function Coefficients

Note that upon the change of the coefficient of a non-basic variable

only the corresponding ∆j will change.

147
Sensitivity Analysis
Change in the Right-Hand Side

Question: In what range it is possible to vary the RHS of the 1st constraint while
preserving the optimality of the basis?

▪ Let ∆b1 be the variation in RHS of the 1st constraint.

▪ Then, the 1st constraint becomes:

X1 + X2 ≤15 + ∆ b1

148
Sensitivity Analysis
Change in the Right-Hand Side

▪ See that the change in the RHS of the constraints would only affect the
corresponding column in the simplex tableau.
▪ Note that the parameter ∆b1 and the variable S1 have the same coefficients
in the standard form and will preserve identical coefficients for all simplex
tableaus, particularly for the optimal one.
▪ Hence, it suffices to take the coefficients of S1 in the last tableau as those
of ∆b1 in column bi.

149
Sensitivity Analysis
Change in the Right-Hand Side

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
J 0 0 -15 0 -5 0
150
Sensitivity Analysis
Change in the Right-Hand Side
For the basis to remain optimal, the corresponding solution must be feasible. That is:

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

5 – 3 b1  0
b1  5/3
12.5 + 1/2 b1  0 Or equivalently, 10  b1 50/3
b1  -25
17.5 – 1/2 b1  0
-5  b1  5/3 b1  35

Question: Determine the effect on Z if b1 takes the value 12.

151
Sensitivity Analysis
Introducing a new constraint

▪ Two outcomes are possible :

► This new constraint is satisfied by the optimal solution; hence it is

redundant and optimality is preserved.

► If the optimal solution does not satisfy the new constraint, then
optimality is not preserved and the new solution will be worse.

152
Sensitivity Analysis
Introducing a new constraint

▪ In the previous example, consider the additional constraint:

2X1 + X2 ≤ 15

▪ This constraint is not satisfied by the optimal solution

(X1 = 2.5; X2 = 12.5; et Z = 275).

▪ We can show that the new solution is

X1* = 5/3, X2* = 35/3 & Z*= 250.

▪ Consequently, Z decreases by 25 units.

153
Sensitivity Analysis
Deleting a constraint

▪ Two cases are possible:

► If the deleted constraint was inactive, then no change in the optimal

solution occurs

► If the deleted constraint however was binding, then the optimal solution
will change

154
Sensitivity Analysis
Deleting a constraint

▪ Reconsider the last example after introducing the 5th constraint.

▪ In order to find the optimal tableau after deleting a constraint, we proceed
as follows:
➢ In order to delete the 2nd constraint (inactive), it suffices to delete row
S2 & column S2.
➢ 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.

155
Sensitivity Analysis
Deleting a constraint

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

156
Sensitivity Analysis
Deleting a constraint

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

157
Sensitivity Analysis
Deleting a constraint

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
158
Sensitivity Analysis
Introducing a new variable

▪ Reconsider the last example and suppose that a 3rd variable is introduced with
a coefficient of 10 in Z and coefficients of 1, 2, 0 & 0 in 1st, 2nd, 3rd & 4th
constraints, respectively.
▪ The new LP is then:
Max Z = 10X1 + 20X2 + 10X3
X1+X2+X3 ≤ 15
4X1+2X2+2X3 ≤ 40
-X1+X2 ≤ 10
X1 ≤ 20
X1, X2, X3 ≤ 0
159
Sensitivity Analysis
Introducing a new variable

▪ Note that introducing a variable in the primal LP corresponds to adding a

new constraint in the dual LP.
▪ If the dual constraint is satisfied by the obtained optimal solution, then
optimality is unchanged.
▪ Else, optimality will be degraded with respect to the dual and hence
improved with respect to the primal. Hence, it is worthwhile introducing
this variable in this case.

160
Sensitivity Analysis
Introducing a new variable

▪ In the previous example, 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.
▪ Consequently, the optimal solution remains unchanged.

161
Sensitivity Analysis
Introducing a new variable

▪ Note that introducing a new variable is particularly interesting when a

new activity is under consideration such as a new product.
▪ We are usually interested in assessing whether it is beneficial to go for
such an activity by examining if the profit would increase

162
Sensitivity Analysis
Deleting a variable

▪ Deleting a variable X is equivalent to introducing a new constraint: X = 0.

▪ If the deleted variable was non-basic variable at the optimal solution, then
optimality is preserved.
▪ Else, optimality will change.

163