Sensitivity Analysis
Table of Contents
When using linear programming to model real world situations we often need to solve new linear programs obtained by making small changes to problems we’ve already solved. This can happen for various reasons, among many others:
- The coefficients might have been estimates of key quantities, later with more information we might have better estimates.
- Even if the coefficients were completely accurate they might change over time, for example, if we needed to take into account the price of some resource, as that price changes we’d want to update our model.
- We might realize we forgot a constraint, or suddenly have an extra variable we want to know about.
- We might want to replace any coefficients that were estimated with more pessimistic estimates to compute a worst case scenario.
We can handle this problem by simply solving the new LP from scratch using the Simplex Method, but we can often reuse the work done in solving the original LP to solve the new one faster than we could from scratch. This ability of the Simplex Method to “reuse work” gives it an advantage when solving many related LPs over other methods that might be faster for single LPs but need to start over for every change. (We won’t actually cover any other methods for solving LPs in this course, and you can take this as part of the justification for that.)
The study of how solutions of LPs change when you change the LP is called sensitivity analysis, and we’ve already seen some of it: the marginal values theorem tells us something about what happens in a standard form LP if you change the right-hand sides of the constraints. It gave us an upper bound for the new optimal solution and conditions under which that estimate was exactly right. Now we’ll complete this analysis, indicating what to do when those conditions don’t hold; as well as analyze various other changes we can make to an LP.
Consider an LP in standard form:
\((\mathsf{P})\) Maximize \( \mathbf{c} \cdot \mathbf{x} \)
subject to \(\left\{\begin{aligned} A \mathbf{x} & \le \mathbf{b} \\ \mathbf{x} & \ge 0 \\ \end{aligned}\right.\)
We can consider changes such as:
- Changing the objective function, \(\mathbf{c}\).
- Changing the right-hand sides of the constraints, \(\mathbf{b}\).1
- Changing (some entries of) the matrix of coefficients, \(A\).
- Adding or removing a constraint.
- Adding or removing a variable.
For each type of change we’d like to know:
- Conditions for which the solution of the new LP is easy to get from the old optimal solution, say, for when the old optimal solution is still optimal, or at least the old optimal basis is still optimal even if the values of the variables need recomputing (this is what happens in the marginal values theorem).
- What to do if those conditions don’t hold and we need to work more to solve the new LP. Ideally, this would be better than doing the Simplex Method from scratch on the new LP.
Each type of change needs separate analysis, and in each case we’ll start by looking at the matrix formulas for the final dictionary of the original LP to see what changes.
Changing the objective function
Let’s consider changing \(\mathbf{c}\) to \(\hat{\mathbf{c}}\) in the problem \((\mathsf{P})\) to get a problem \((\hat{\mathsf{P}})\). Say \(\mathbf{x}_B\) is an optimal basis for \((\mathsf{P})\). The matrix formulas say the dictionary is given by:
\[\begin{aligned} \mathbf{x}_B & = A_B^{-1} \mathbf{b} - A_B^{-1} A_N \mathbf{x}_N \\ z & = \mathbf{c}_B^\top A_B^{-1} \mathbf{b} + \left(\mathbf{c}_N^\top - \mathbf{c}_B^\top A_B^{-1} A_N \right) \mathbf{x}_N \end{aligned}\]
Let’s try to use the same basis for the new problem. The dictionary would be:
\[\begin{aligned} \mathbf{x}_B & = A_B^{-1} \mathbf{b} - A_B^{-1} A_N \mathbf{x}_N \\ z & = \hat{\mathbf{c}}_B^\top A_B^{-1} \mathbf{b} + \left(\hat{\mathbf{c}}_N^\top - \hat{\mathbf{c}}_B^\top A_B^{-1} A_N \right) \mathbf{x}_N \end{aligned}\]
Notice that the top part, the formulas for the basic variables, hasn’t changed at all. In particular, this dictionary is feasible! And if the new coefficients in the \(z\)-row are non-positive, that is, if \(\hat{\mathbf{c}}_N^\top - \hat{\mathbf{c}}_B^\top A_B^{-1} A_N \le 0\), then this dictionary is even optimal!
And if \(\hat{\mathbf{c}}_N^\top - \hat{\mathbf{c}}_B^\top A_B^{-1} A_N\) has some positive entries we can just use the above dictionary as the initial dictionary for the Simplex Method to solve \(\hat{\mathbf{P}}\).
Adding a variable
Now let’s consider adding a new variable \(x_{m+n+1}\) to an LP. The new variable should come, of course, with coefficients: we need a \(c_{m+n+1}\) for the objective functions and a new column \(A_{m+n+1}\) for the matrix of coefficients of the constraints.
Inspired by the initial dictionary (where we take the slack variables as basic and the non-slack variables as non-basic) we will make the guess that the new variable should be added as a non-basic variable to the final dictionary. Using the matrix formulas to compute the new column, we get this dictionary for the LP with the extra variable:
\[\begin{aligned} \mathbf{x}_B & = A_B^{-1} \mathbf{b} - A_B^{-1} A_N \mathbf{x}_N - A_B^{-1} A_{m+n+1} x_{m+n+1} \\ z & = \mathbf{c}_B^\top A_B^{-1} \mathbf{b} + \left(\mathbf{c}_N^\top - \mathbf{c}_B^\top A_B^{-1} A_N \right) \mathbf{x}_N + (c_{m+n+1} - \mathbf{c}_B^{\top} A_B^{-1} A_{m+n+1}) x_{m+n+1} \end{aligned}\]
This dictionary is feasible, because the first column hasn’t changed, but the new coefficient in the \(z\)-row may have any sign. If we’re lucky, \(c_{m+n+1} - \mathbf{c}_B^{-1} A_{m+n+1} \le 0\) and this dictionary is already optimal! If not, since it is at least feasible, we can just use it as the initial dictionary for the Simplex Method.
Other types of changes
If you attempt this sort of analysis for a change of \(\mathbf{b}\), or for adding a constraint (guessing the new slack variable is basic), you’ll see that, while we can easily formulate a criterion for when the modified dictionary is optimal, when it isn’t we won’t be left with a feasible dictionary! Instead we’d get a dictionary that is not feasible but “looks optimal”: all of the coefficients in the \(z\)-row are non-positive.
Such a dictionary can’t be used in the Simplex Method: the Simplex Method pivots from feasible dictionary to feasible dictionary working towards non-positive coefficients in the \(z\)-row. To take advantage of this infeasible dictionary that “looks optimal”, instead of the Simplex Method we’ll use a very similar pivoting technique called the Dual Simplex Method. That’s our next topic.
Notice that in a sense this is the same kind of change as the previous one: we can view this in the dual as changing the objective function. Here we’ll stick with the point of view of the primal and treat this as a different case.