Sensitivity Analysis: An Example
Consider the linear program:
Maximize z=−5x1+5x2+13x3
Subject to:
−x1+x2+3x3≤20 (1)
12x1+4x2+10x3≤90 (2)
x1,x2,x3≥0 .
After introducing two slack variables s1and s2and executing the Simplex algorithm to
optimality, we obtain the following final set of equations:
z+2x3+5s1= 100 , (0)
−x1+x2+3x3+s1= 20 , (1)
16x1−2x3−4s1+s2= 10 . (2)
Our task is to conduct sensitivity analysis by independently investigating each of a set of
nine changes (detailed below) in the original problem. For each change, we will use the
fundamental insight to revise the final set of equations (in tableau form) to identify a new
solution and to test the new solution for feasibility and (if applicable) optimality.
We will first recast the above equation systems into the following pair of initial and final
tableaus.
Initial Tableau: Basic z x1x2x3s1s2
Variable 1 5 −5−13 0 0 0
s10−1 1 3 1 0 20
s20 12 4 10 0 1 90
Final Tableau: Basic z x1x2x3s1s2
Variable 1 0 0 2 5 0 100
x20−1 1 3 1 0 20
s20 16 0 −2−4 1 10
The basic variables associated with this final tableau are x2and s2; therefore, the current
basic feasible solution is (x1, x2, x3, s1, s2) = (0,20,0,0,10), which has an objective-
function value of 100.
An inspection of the initial tableau shows that the columns associated with z,s1, and s2
form a 3 ×3 identity matrix. Therefore, the Pmatrix will come from the corresponding
columns in the final tableau. That is, we have
P=
1 5 0
0 1 0
0−4 1
;
1
and the final tableau equals the matrix product of this Pand the initial tableau, i.e.,
TF=P×TI.
Our basic approach for dealing with parameter changes in the original problem is in two
steps. In the first step, we will revise the final tableau by multiplying the same Pto the
new initial tableau; in other words, despite a revision in TI, we intend to follow the original
sequence of pivots. After producing a revised TF, we will, in the second step, take the
revised TFas the starting point and initiate any necessary further analysis of the revised
problem.
We now begin a detailed sensitivity analysis of this problem.
(a) Change the right-hand side of constraint (1) to 30.
Denote the right-hand-side constants in the original constraints as b1and b2. Then, the
proposed change is to revise b1from 20 to 30, while retaining the original value of b2at 90.
With this change, the RHS column in the initial tableau becomes
0
30
90
.
Since the rest of the columns in the initial tableau stays the same, the only necessary revision
in TFwill be in the RHS column. To determine this new RHS column, we multiply Pto
the above new column to obtain:
1 5 0
0 1 0
0−4 1
×
0
30
90
=
150
30
−30
.
Since the basic variables in the final tableau are x2and s2, the solution associated with the
revised TFis (x1, x2, x3, s1, s2) = (0,30,0,0,−30). With a negative value for s2, this
(basic) solution is not feasible.
Geometrically speaking, increasing the value of b1from 20 to 30 means that we are relaxing
the first inequality constraint. Relaxing a constraint is tantamount to enlarging the feasible
set; therefore, one would expect an improved optimal objective-function value. The fact
that the revised solution above is not feasible is not a contradiction to this statement. It
only means that additional work is necessary to determine the new optimal solution.
What causes the infeasibility of the new solution? Recall that the original optimal solution is
(x1, x2, x3, s1, s2) = (0,20,0,0,10). Since x1,x3, and s1are serving as nonbasic variables,
the defining equations for this solution are: x1= 0, x3= 0, and −x1+x2+ 3x3= 20. Now,
2
imagine an attempt to increase the RHS constant of the last equation from 20 to 20 + δ
(say) while maintaining these three equalities. As we increase δ(from 0), we will trace out
a family of solutions. That the new solution is infeasible simply means that if δis made
sufficiently large (in this case, δ= 10), then this family of solutions will eventually exit the
feasible set.
More formally, suppose the original RHS column is revised to
0
20 + δ
90
; or alternatively, to
0
20
90
+
0
δ
0
.
Then, after premultiplying this new column by P, we obtain
1 5 0
0 1 0
0−4 1
×
0
20 + δ
90
=
1 5 0
0 1 0
0−4 1
×
0
20
90
+
0
δ
0
=
1 5 0
0 1 0
×
0
20
+
1 5 0
0 1 0
×
0
δ
