Sensitivity: Algebraic explanation¶
Changes in the coefficients of the objective function¶
Let us start with the Production Mix Problem example, which in the standard form is:
\(max Z = 300x_{1} + 250x_{2} + 0s_{1} + 0s_{2} + 0s_{3}\)
subject to:
The final Tableau is:
Basic |
z |
\(x_{1}\) |
\(x_{2}\) |
\(s_{1}\) |
\(s_{2}\) |
\(s_{3}\) |
RHS |
Ratio |
|---|---|---|---|---|---|---|---|---|
1 |
0 |
0 |
0 |
250/3 |
650/3 |
6350 |
||
\(s_{1}\) |
0 |
0 |
0 |
1 |
-1/3 |
-5/3 |
5 |
|
\(x_{2}\) |
0 |
0 |
1 |
0 |
1/3 |
-1/3 |
11 |
|
\(x_{1}\) |
0 |
1 |
0 |
0 |
0 |
1 |
12 |
Let us assume we want to make a change in coefficient \(c_{1}\) of \(\Delta c_{1}\). The objective function becomes:
\(max Z = (300 +\Delta c_{1})·x_{1} + 250x_{2}\)
It can be proved that the final Tableau now becomes:
Basic |
z |
\(x_{1}\) |
\(x_{2}\) |
\(s_{1}\) |
\(s_{2}\) |
\(s_{3}\) |
RHS |
Ratio |
|---|---|---|---|---|---|---|---|---|
1 |
\(-\Delta c_{1}\) |
0 |
0 |
250/3 |
650/3 |
6350 |
||
\(s_{1}\) |
0 |
0 |
0 |
1 |
-1/3 |
-5/3 |
5 |
|
\(x_{2}\) |
0 |
0 |
1 |
0 |
1/3 |
-1/3 |
11 |
|
\(x_{1}\) |
0 |
1 |
0 |
0 |
0 |
1 |
12 |
The Simplex method requires that the Tableau is in canonical form. Thus, we need to add the last row times \(\Delta c_{1}\) to the first row to fulfill this:
Basic |
z |
\(x_{1}\) |
\(x_{2}\) |
\(s_{1}\) |
\(s_{2}\) |
\(s_{3}\) |
RHS |
Ratio |
|---|---|---|---|---|---|---|---|---|
1 |
0 |
0 |
0 |
250/3 |
650/3 + \(\Delta c_{1}\) |
6350 + 12·\(\Delta c_{1}\) |
||
\(s_{1}\) |
0 |
0 |
0 |
1 |
-1/3 |
-5/3 |
5 |
|
\(x_{2}\) |
0 |
0 |
1 |
0 |
1/3 |
-1/3 |
11 |
|
\(x_{1}\) |
0 |
1 |
0 |
0 |
0 |
1 |
12 |
And taking into account that the coefficient of \(s_{3}\) needs to be positive for \(x_{1}\) to remain in the basis, \(\Delta c_{1}\) cannot be lower than -650/3 and can increase up to infinity.
Let us now assume we want to make a change in coefficient \(c_{2}\) of \(\Delta c_{2}\). The objective function becomes:
\(max Z = 300·x_{1} + (250 +\Delta c_{2})·x_{2}\)
The final Tableau now becomes:
Basic |
z |
\(x_{1}\) |
\(x_{2}\) |
\(s_{1}\) |
\(s_{2}\) |
\(s_{3}\) |
RHS |
Ratio |
|---|---|---|---|---|---|---|---|---|
1 |
0 |
\(-\Delta c_{2}\) |
0 |
250/3 |
650/3 |
6350 |
||
\(s_{1}\) |
0 |
0 |
0 |
1 |
-1/3 |
-5/3 |
5 |
|
\(x_{2}\) |
0 |
0 |
1 |
0 |
1/3 |
-1/3 |
11 |
|
\(x_{1}\) |
0 |
1 |
0 |
0 |
0 |
1 |
12 |
Again, the Simplex method requires that the Tableau is in canonical form. Thus, we need to add the second last row times \(\Delta c_{2}\) to the first row to fulfill this:
Basic |
z |
\(x_{1}\) |
\(x_{2}\) |
\(s_{1}\) |
\(s_{2}\) |
\(s_{3}\) |
RHS |
Ratio |
|---|---|---|---|---|---|---|---|---|
1 |
0 |
0 |
0 |
250/3 + \(\Delta c_{2}/3\) |
650/3 - \(\Delta c_{2}/3\) |
6350 + 11·\(\Delta c_{2}\) |
||
\(s_{1}\) |
0 |
0 |
0 |
1 |
-1/3 |
-5/3 |
5 |
|
\(x_{2}\) |
0 |
0 |
1 |
0 |
1/3 |
-1/3 |
11 |
|
\(x_{1}\) |
0 |
1 |
0 |
0 |
0 |
1 |
12 |
And taking into account that the coefficients of \(s_{2}\) and \(s_{3}\) need to be positive for \(x_{2}\) to remain in the basis, \(\Delta c_{2}\) cannot be lower than -250 nor higher than 650.
Changes in the constraint independent terms¶
Now let us see what is the effect of changing b, for instance decreasing \(b_{1}\) an amount equal to \(\Delta b_{1}\). In the original problem formulation, this means:
\(2x_{1} + x_{2} + s_{1} = 40 - \Delta b_{1}\)
\(x_{1} + 3x_{2} + s_{2} = 45\)
\(x_{1} + s_{3} = 12\)
Changing the Right Hand Side by \(\Delta b_{1}\) is equivalent to changing \(s_{1}\) an amount of \(\Delta b_{1}\). Note that \(s_{1}\) is in the basis, thus for it to remain in the basis, it must satisfy:
\(s_{1}=5 + \Delta b_{1} \geq 0\)
\(\Delta b_{1} \geq -5\)
Now, take the second constraint and let us apply the same change:
\(2x_{1} + x_{2} + s_{1} = 40\)
\(x_{1} + 3x_{2} + s_{2} = 45 - \Delta b_{2}\)
\(x_{1} + s_{3} = 12\)
Again, this is equivalent to:
\(2x_{1} + x_{2} + s_{1} = 40\)
\(x_{1} + 3x_{2} + s_{2} + \Delta b_{2} = 45\)
\(x_{1} + s_{3} = 12\)
Which can be regarded as a change of \(\Delta b_{2}\) in \(s_{2}\). Now, if we change \(s_{2}\) from \(s_{2}=0\) to \(s_{2} =\Delta b_{2}\) in the final Tableau:
Basic |
z |
\(x_{1}\) |
\(x_{2}\) |
\(s_{1}\) |
\(s_{2}\) |
\(s_{3}\) |
RHS |
Ratio |
|---|---|---|---|---|---|---|---|---|
1 |
0 |
0 |
0 |
250/3·\(\Delta b_{2}\) |
650/3 |
6350 |
||
\(s_{1}\) |
0 |
0 |
0 |
1 |
-1/3 ·\(\Delta b_{2}\) |
-5/3 |
5 |
|
\(x_{2}\) |
0 |
0 |
1 |
0 |
1/3 ·\(\Delta b_{2}\) |
-1/3 |
11 |
|
\(x_{1}\) |
0 |
1 |
0 |
0 |
0 ·\(\Delta b_{2}\) |
1 |
12 |
The basis remains unchanged as long as all the constraints are still met:
\(s_{1} - 1/3 · \Delta b_{2} = 5\)
\(x_{2} + 1/3· \Delta b_{2} = 11\)
\(x_{1} + 0 ·\Delta b_{2} = 12\)