What happens when a small change in input parameters disrupts a carefully calculated optimal solution? Imagine you’re managing a supply chain for a major retailer. You’ve optimized the transportation routes to minimize costs using linear programming. Suddenly, fuel prices spike or a major supplier increases its rates. How does this impact your optimal routes and costs? Sensitivity analysis in linear optimization provides the tools to answer these questions!
What is Sensitivity Analysis?
Sensitivity analysis in linear optimization evaluates how changes in model parameters affect the optimal solution. It identifies influential variables or constraints, assessing the solution’s stability and reliability. This process shows how variations in inputs, such as cost coefficients or resource availability, impact the outcome. This helps businesses anticipate risks and make informed decisions.
Types of Sensitivity Analysis
Parameter Sensitivity
Parameter sensitivity focuses on how changes in the coefficients of the objective function and constraints influence the optimal solution. For instance, if a company is maximizing profit, it might analyze how variations in the cost of raw materials or selling prices affect its profit-maximizing production levels. This type of analysis helps identify which parameters are most influential and where the model is most sensitive to changes.
Right-Hand Side (RHS) Sensitivity
RHS sensitivity examines how changes in the constraint boundaries, or right-hand side values, impact the optimal solution. This analysis is vital for understanding the flexibility of constraints such as resource availability, labor hours, or budget limits. For example, a manufacturing plant might study how increasing the available labor hours affects its production schedule and overall efficiency.
Shadow Prices
Shadow prices explore the worth of relaxing constraints. These values indicate the marginal value of additional resources. For example, in a production model, the shadow price of a raw material constraint reveals how much the objective function (e.g., profit) would increase with one more unit of that material. This helps businesses prioritize resource allocation and investment decisions.
Conducting Sensitivity Analysis
Assume you have a store that sells chairs (I know… it sounds like a college book example… and it is😉). You handcraft three types of outdoor chairs: sling chairs, club chairs, and hammocks. Each type of chair requires different amounts of time for cutting, assembling, and finishing. You have limited hours available each month for these activities, and you want to maximize your revenue. You already built the linear optimization model using the Simplex LP method in Excel and determined the optimal number of each type of chair to produce: 41 sling chairs and 7 hammocks, taking home a nice revenue of roughly $2,100. Now you want to understand how changes in various parameters might affect your optimal production plan, which is where the sensitivity report comes into play. Let’s walk through the different aspects we discussed earlier. First, make sure you actually used the ‘Simplex LP’ as a solving method and have only linear constraints, then solve the problem and wait until the solver ‘finds a solution’. Don’t be too quick with clicking on ‘OK’; you will need to select the ‘Sensitivity’ Report first (see below). Understanding the content of that report is the whole idea of this article.
Range of Optimality
The range of optimality refers to the interval within which the coefficients of the objective function (i.e., the prices of the chairs) can vary without changing the current optimal solution. To determine the range of optimality, we analyze the allowable increase and decrease for each coefficient while keeping other coefficients constant.
Mathematically, if the optimal basis remains unchanged, the new objective function coefficient ci′ for a variable xi (number of Sling Chairs, Club Chairs, or Hammocks) must satisfy:
where Δci lies within the allowable interval determined by the sensitivity analysis.
In our example, if the objective function is:
Z = 35×Sling Chairs + 75×Club Chairs + 100×Hammocks
The optimal solution remains unchanged as long as the price of Sling Chairs, c1, lies between c1_min and c1_max, then [c1_min,c1_max] defines the range of optimality for c1.
As you can see in the sensitivity report above, the price of Sling Chairs can increase by up to $16.136 (from $35 to $51.136) or decrease by up to $5.363 (from $35 to $29.637) without changing the optimal production quantities. The price of Club Chairs can increase by up to $9.638 (from $75 to $84.638) before the optimal solution will be impacted in any way. The allowable decrease is extremely large, with 1E+30 — which is Excel’s way of indicating infinity. This pretty much means that the price can drop to zero without affecting the current solution. I believe we can all agree that this makes a lot of sense since the Club Chairs are not part of our current solution, and a price decrease (contribution to our sales revenue) will not make it more attractive.
Shadow Prices
Shadow prices represent the change in the objective function’s value per unit increase in the right-hand side of a constraint, assuming all other parameters remain constant. These values provide insights into the marginal worth of resources.
For example, in our chair production example, the shadow price can indicate how much additional revenue would be gained by acquiring one more unit of a scarce resource, such as labor hours for cutting, assembling, or finishing.
The shadow price for cutting hours is zero, indicating that increasing the available cutting hours will not increase the revenue, as the current cutting capacity is not a limiting factor in the optimal solution (non-binding constraint). The shadow prices for assembling hours and total hours are non-zero, therefore binding. For each additional hour available for assembling, the total revenue would increase by $20.580. This suggests that assembling is a bottleneck in the current production plan, and increasing assembling capacity would be valuable. For each additional total hour available, the total revenue would increase by $8.696. This indicates that overall available time is a constraint, and increasing total available hours would positively impact revenue.
Range of Feasibility
The range of feasibility pertains to the RHS values of the constraints. It determines the extent to which the RHS values can vary while keeping the current solution feasible. In other words, it identifies the allowable increase and decrease for the RHS values that do not violate the feasibility of the solution.
To find the range of feasibility for the j-th constraint, we solve the following inequalities:
where bj is the RHS value of the j-th constraint, and bj_min and bj_max are the lower and upper bounds within which the solution remains feasible. These bounds are derived from the shadow prices and the current solution’s basis matrix.
In our chair production example, the constraints include the available hours for cutting, assembling, finishing, and the total hours. The sensitivity report indicates that the cutting hours can increase infinitely without affecting feasibility (again 1E+30), but they can only decrease by up to 27.10 hours (from 50 to 22.90) without violating feasibility. The assembling hours, however, can increase by up to 31.82 hours (from 50 to 81.82) or decrease by up to 4.65 hours (from 50 to 45.35) while maintaining feasibility. This suggests that assembling is a critical constraint in the current solution.
We know that the shadow price for assembling hours is $20.580, so each additional hour available for assembling increases the total revenue by $20.580. However, this shadow price is only valid within the specified range of feasibility. If the assembling hours increase or decrease beyond this range, the shadow price may no longer be accurate, and a new sensitivity analysis must be conducted. For example, if the available assembling hours were increased by 30 hours, the expected revenue increase would be $617.4 (30 hours * shadow price). If we were to hire someone to work 40 hours in assembling, we would need to run the sensitivity report again to determine the new optimal solution and shadow price.
In practice, knowing the range of feasibility helps businesses understand how flexible their constraints are and prepare for changes in resource availability or demand. For instance, if a company knows that its optimal production plan remains feasible as long as the demand for a product stays within a certain range, it can better plan for fluctuations in market demand.
