Seminar 2: Linear Programming – Sensitivity Analysis
Sensitivity analysis (or post-optimality analysis) is the study of how changes in a linear programming model’s coefficients affect the optimal solution.
It helps us answer “what-if” questions like:
This is crucial for managers who work in a dynamic environment where estimates are not always perfect.
When we solve an LP problem using software like Excel Solver, it gives us the optimal solution and a “Sensitivity Report”. This report is our main tool for this analysis.
Variables Section This part tells us about our decision variables (e.g., how much of a product to make).
Constraints Section This part tells us about our limitations (e.g., resources, demand).
Olympic Bike Co. is making two new bike frames: Deluxe and Professional.
| Frame | Aluminum (lbs) | Steel (lbs) |
|---|---|---|
| Deluxe | 2 | 3 |
| Professional | 4 | 2 |
LP Solution: Produce 15 Deluxe and 17.5 Professional frames for a max profit of $412.50.
The Range of Optimality is the range a profit or cost coefficient can change without changing the optimal production plan (the Final Values).
Let’s look at the report for Olympic Bike:
| Variable | Final Value | Objective Coeff | Allowable Increase | Allowable Decrease |
|---|---|---|---|---|
| Deluxe (D) | 15 | 10 | 12.5 | 2.5 |
| Professional (P) | 17.5 | 15 | 5 | 8.33 |
For the Deluxe frame, the profit is $10. The allowable increase is $12.5 and decrease is $2.5.
So, the Range of Optimality for Deluxe profit is:
[$10 - $2.5, $10 + $12.5] ⇒ [$7.5, $22.5]
Question 1: The profit on Deluxe frames increases to $20. Is the solution (15 Deluxe, 17.5 Professional) still optimal?
Answer: Yes. $20 is within the range [$7.5, $22.5].
The production plan does not change.
However, the total profit will increase: \[ \text{New Profit} = (\mathbf{\$20} \times 15) + (\$15 \times 17.5) = \$300 + \$262.50 = \mathbf{\$562.50} \]
Question 2: The profit on Deluxe frames drops to $6. Does the solution change?
Answer: Yes, it might. $6 is outside the range [$7.5, $22.5]. The current production plan is no longer guaranteed to be optimal. We would need to re-solve the LP to find the new best plan.
Reduced Cost applies to variables whose optimal value is zero.
It tells you how much the variable’s profit/cost coefficient must improve (increase for profit, decrease for cost) before it becomes a good idea to include it in the solution.
The Shadow Price (or Dual Value) of a constraint is one of the most powerful concepts in LP.
It is the amount the objective function value will improve for every one-unit increase in the Right-Hand Side (RHS) of that constraint.
The Range of Feasibility is the range the RHS of a constraint can change while the shadow price remains valid.
Let’s look at the constraints report for Olympic Bike:
| Constraint | Final Value (LHS) | Shadow Price | Constraint R.H. Side | Allowable Increase | Allowable Decrease |
|---|---|---|---|---|---|
| Aluminum | 100 | 3.125 | 100 | 60 | 46.67 |
| Steel | 80 | 1.25 | 80 | 70 | 30 |
For Aluminum, the shadow price is $3.125. This means for every extra pound of aluminum we get, our total profit will increase by $3.125.
This is only true within the Range of Feasibility: [100 - 46.67, 100 + 60] ⇒ [53.33, 160].
To understand binding vs. non-binding constraints, it helps to know about slack and surplus variables. Software uses them behind the scenes to convert inequalities into standard equations.
Slack Variables (for ≤ constraints): Represents the amount of an unused resource. 2x + 3y ≤ 100 becomes 2x + 3y + s₁ = 100. If s₁ > 0, the constraint is non-binding (there is slack).
Surplus Variables (for ≥ constraints): Represents the amount produced above a minimum requirement. A + B ≥ 350 becomes A + B - s₂ = 350. If s₂ > 0, the constraint is non-binding (we produced more than the minimum).
Key idea: if slack or surplus is 0, the constraint is binding.
What if multiple things change at once? We can use the 100% Rule.
The 100% Rule states that the solution (and shadow prices) will remain valid as long as the sum of the percentages of the changes (relative to their maximum allowable changes) does not exceed 100%.
Formula: \[ \sum_{i} \frac{|\text{Actual Change}_i|}{\text{Allowable Change}_i} \le 1 \]
This rule applies separately to Objective Coefficients (testing the Range of Optimality) and RHS values (testing the Range of Feasibility).
Question: At Olympic Bike, what if the profit on Deluxe frames rises to $16 and the profit on Professional frames rises to $17 at the same time? Will the solution (15 D, 17.5 P) still be optimal?
Conclusion: Since 88% is less than 100%, the optimal solution will not change. The production plan remains 15 Deluxe and 17.5 Professional frames.
Question: For M&D Chemicals (our minimization problem from last time), what if the minimum total production (Constraint 2) is decreased by 25 gallons, and the available processing time (Constraint 3) is increased by 30 hours?
Sensitivity Report Snippet:
| Constraint | Change | Allowable Change | Shadow Price |
|---|---|---|---|
| Total Prod. | ↓ 25 | ↓ 50 | 4 |
| Proc. Time | ↑ 30 | ↑ 100 | -1 |
Conclusion: Since 80% < 100%, the shadow prices are still valid. We can calculate the change in total cost: \[ \begin{aligned} \text{Change in Cost} &= (-25 \times \text{ShadowPrice}_2) + (30 \times \text{ShadowPrice}_3) \\ &= (-25 \times 4) + (30 \times -1) \\ &= -100 - 30 = -\mathbf{\$130} \end{aligned} \] The total cost will decrease by $130. New Cost = $800 - $130 = $670.