Sensitivity Analysis & Post-Optimality in Linear Programming

What is Sensitivity Analysis?

Sensitivity analysis examines how changes in a linear programming (LP) model’s parameters affect the optimal solution.
Key questions:
- How robust is the optimal solution?
- What happens if coefficients or constraints change?
- How does uncertainty in parameters affect decisions?
Goal: Understand the stability and flexibility of the LP solution.
Also called post-optimality analysis.
Essential for real-world applications where parameters are uncertain.

Types of Sensitivity Analysis

Local sensitivity: Small changes around optimal solution
Global sensitivity: Large changes and structural variations
Deterministic vs. Stochastic:
- Deterministic: Exact parameter changes
- Stochastic: Parameter uncertainty with probability distributions
One-way vs. Multi-way: Changing one or multiple parameters simultaneously
Continuous vs. Discrete: Gradual changes vs. step changes

Mathematical Foundation

Consider the standard LP problem:
\[\begin{aligned} \max \quad & \mathbf{c}^T\mathbf{x} \\ \text{s.t.} \quad & \mathbf{A}\mathbf{x} = \mathbf{b} \\ & \mathbf{x} \geq \mathbf{0} \end{aligned}\]

Where sensitivity analysis examines changes in:
- Objective coefficients $\mathbf{c}$
- Right-hand side values $\mathbf{b}$
- Constraint matrix elements $\mathbf{A}$
- Adding/removing variables or constraints

Objective Function Sensitivity

Objective function: $\max \, c_1x_1 + c_2x_2 + \dots + c_nx_n$
Changing $c_j$ (coefficient of variable $x_j$) may:
- Keep the optimal solution unchanged (same basis).
- Alter the optimal value of the objective function.
- Change the optimal solution if $c_j$ exceeds allowable range.
Analyzed using the reduced cost of non-basic variables.
Graphical interpretation: Rotation of the objective function line.

Reduced Costs and Optimality Conditions

For a basic feasible solution with basis $\mathbf{B}$:
- Reduced cost vector: $\mathbf{\bar{c}} = \mathbf{c} - \mathbf{c}_B^T\mathbf{B}^{-1}\mathbf{A}$
- For maximization, optimality requires: $\bar{c}_j \leq 0$ for all $j$
- For basic variables: $\bar{c}_j = 0$
- For non-basic variables: $\bar{c}_j$ indicates improvement potential
Interpretation:
- $\bar{c}_j > 0$: Entering variable $x_j$ would improve objective
- $\bar{c}_j = 0$: Alternative optimal solution exists
- $\bar{c}_j < 0$: Variable $x_j$ should remain non-basic

Range of Optimality for Objective Coefficients

For basic variable $x_k$ with current coefficient $c_k^0$:
- Current solution remains optimal if reduced costs stay feasible
- Calculate allowable range: $c_k^0 + \Delta c_k^- \leq c_k \leq c_k^0 + \Delta c_k^+$
Algorithm:
1. Identify current basic variables
2. For each non-basic variable $j$, solve: $\bar{c}_j + y_{kj}\Delta c_k = 0$
3. Find tightest bounds: $\Delta c_k^- = \max\{-\bar{c}_j/y_{kj} : y_{kj} < 0\}$
4. $\Delta c_k^+ = \min\{-\bar{c}_j/y_{kj} : y_{kj} > 0\}$

Example: Objective Coefficient Changes

Consider the problem:
\[\begin{aligned} \max \quad & 3x_1 + 2x_2 \\ \text{s.t.} \quad & x_1 + x_2 \leq 4 \\ & 2x_1 + x_2 \leq 6 \\ & x_1, x_2 \geq 0 \end{aligned}\]
Optimal solution: $(x_1^*, x_2^*) = (2, 2)$ with $z^* = 10$
Analysis: What range of $c_1$ keeps this solution optimal?
- Current slope of objective: $-c_1/c_2 = -3/2$
- Constraint slopes: $-1$ and $-2$
- Range: $1 \leq c_1 \leq 4$ (when $c_2 = 2$)

RHS Sensitivity and Shadow Prices

Constraints: $a_{i1}x_1 + a_{i2}x_2 + \dots + a_{in}x_n \leq b_i$
Changing $b_i$ (RHS of constraint $i$) affects:
- Feasibility of the current solution.
- Optimal objective value via shadow prices.
- Shape of the feasible region.
Shadow price: Change in objective value per unit change in $b_i$.
Mathematically: Shadow price = $y_i^* = (\mathbf{c}_B^T\mathbf{B}^{-1})_i$
Graphical interpretation: Movement of constraint boundaries.

Range of Feasibility for RHS

For RHS value $b_i$, the current basis remains feasible when:
\[\mathbf{B}^{-1}(\mathbf{b} + \Delta b_i \mathbf{e}_i) \geq \mathbf{0}\]
Calculation:
- Let $\mathbf{d} = \mathbf{B}^{-1}\mathbf{e}_i$ (i-th unit vector)
- Current basic solution: $\mathbf{x}_B = \mathbf{B}^{-1}\mathbf{b}$
- New basic solution: $\mathbf{x}_B' = \mathbf{x}_B + \Delta b_i \mathbf{d}$
- Feasibility requires: $x_{B_k} + \Delta b_i d_k \geq 0$ for all $k$
Allowable range:
- $\Delta b_i^- = \max\{-x_{B_k}/d_k : d_k > 0\}$
- $\Delta b_i^+ = \min\{-x_{B_k}/d_k : d_k < 0\}$

Shadow Price Interpretation

Shadow price $y_i^*$: Marginal value of relaxing constraint $i$.
- For $\leq$ constraint: Increase in objective per unit increase in $b_i$.
- For $\geq$ constraint: Decrease in objective per unit increase in $b_i$.
- For $=$ constraint: Can be positive or negative depending on direction.
Only valid within the allowable range of $b_i$.
Zero shadow price indicates non-binding (slack) constraint.
Economic interpretation: Willingness to pay for additional resource.

Example: RHS Changes and Shadow Prices

Continuing previous example:
\[\begin{aligned} \max \quad & 3x_1 + 2x_2 \\ \text{s.t.} \quad & x_1 + x_2 \leq 4 \\ & 2x_1 + x_2 \leq 6 \\ & x_1, x_2 \geq 0 \end{aligned}\]
At optimal solution $(2, 2)$:
- Constraint 1: $2 + 2 = 4$ (binding, slack = 0)
- Constraint 2: $4 + 2 = 6$ (binding, slack = 0)
- Shadow prices: $y_1^* = 1$, $y_2^* = 1$
- If $b_1$ increases to 5: new optimal value = $10 + 1(1) = 11$

Constraint Coefficient Changes

Changing constraint matrix element $a_{ij}$ affects:
- Feasibility of current solution
- Optimality conditions
- Both primal and dual relationships
Two cases to consider:
1. $a_{ij}$ where $x_j$ is non-basic: Affects reduced costs
2. $a_{ij}$ where $x_j$ is basic: Affects feasibility and optimality
Analysis approach:
- Update the constraint matrix
- Recalculate basis inverse $\mathbf{B}^{-1}$
- Check feasibility: $\mathbf{B}^{-1}\mathbf{b} \geq \mathbf{0}$
- Check optimality: $\mathbf{c} - \mathbf{c}_B^T\mathbf{B}^{-1}\mathbf{A} \leq \mathbf{0}$

Adding New Variables

When adding new variable $x_{n+1}$ with:
- Objective coefficient $c_{n+1}$
- Constraint coefficients $\mathbf{a}_{n+1}$
Analysis:
1. Calculate reduced cost: $\bar{c}_{n+1} = c_{n+1} - \mathbf{c}_B^T\mathbf{B}^{-1}\mathbf{a}_{n+1}$
2. If $\bar{c}_{n+1} \leq 0$: Current solution remains optimal
3. If $\bar{c}_{n+1} > 0$: Variable should enter basis (re-optimize)
Applications:
- Introducing new products
- Evaluating investment opportunities
- Scenario analysis with additional options

Adding and Removing Constraints

Adding a constraint $\mathbf{a}^T\mathbf{x} \leq b_{new}$:
- Check if current solution satisfies new constraint
- If violated: Current solution becomes infeasible
- If satisfied with slack: Solution remains optimal
- If satisfied exactly: May create alternative optimal solutions
Removing a constraint:
- Expands the feasible region
- If constraint was non-binding: No change in optimal solution
- If constraint was binding: May improve objective value
- Requires re-optimization to find new optimum
Redundancy analysis: Identify constraints that can be removed without affecting the feasible region.

Production Planning Case Study

Problem: A company produces two products with limited resources.

\[\begin{aligned} \max \quad & 40x_1 + 30x_2 \quad \text{(profit)} \\ \text{s.t.} \quad & x_1 + 2x_2 \leq 100 \quad \text{(labor hours)} \\ & 3x_1 + x_2 \leq 120 \quad \text{(raw material)} \\ & x_1, x_2 \geq 0 \end{aligned}\]
Optimal solution: $(x_1^*, x_2^*) = (20, 40)$, $z^* = 2000$
Sensitivity insights:
- Shadow price of labor: $10/hour
- Shadow price of material: $10/unit
- Both constraints are binding (bottlenecks)

Managerial Decisions from Sensitivity Analysis

Resource acquisition decisions:

Pay up to $10 for additional labor hour
Pay up to $10 for additional material unit
Both resources equally valuable at current levels

Product mix decisions:

Current mix is optimal within coefficient ranges
If product 1 profit increases beyond $50: change mix
If product 2 profit decreases below $20: change mix

Capacity planning:

Identify which capacity expansion provides best ROI
Evaluate trade-offs between different resource investments
Plan for demand variability

Portfolio Optimization Example

Investment problem: Allocate funds among assets with risk constraints.

\[\begin{aligned} \max \quad & \sum_{i=1}^n r_i x_i \quad \text{(expected return)} \\ \text{s.t.} \quad & \sum_{i=1}^n x_i = 1 \quad \text{(budget)} \\ & \sum_{i=1}^n \sigma_i^2 x_i^2 \leq \sigma_{max}^2 \quad \text{(risk)} \\ & x_i \geq 0 \quad \forall i \end{aligned}\]

Sensitivity analysis reveals:

Shadow price of risk constraint: Cost of risk aversion
Range analysis: Stability of portfolio to return changes
Critical returns: Threshold values that change allocation

Software Tools for Sensitivity Analysis

Commercial solvers:
- Gurobi, CPLEX: Comprehensive sensitivity reports
- Xpress: Advanced parametric programming
- Excel Solver: Basic sensitivity for small problems
Open-source tools:
- COIN-OR: CBC, CLP with sensitivity analysis
- GLPK: GNU Linear Programming Kit
- LP_Solve: Lightweight solver with basic analysis
Programming interfaces:
- Python: PuLP, Pyomo, CVXPY
- R: lpSolve, ROI
- MATLAB: Optimization Toolbox

Interpreting Solver Output

Typical sensitivity report sections:

Variable	Value	Reduced Cost	Lower Bound	Upper Bound
$x_1$	20.0	0.0	30.0	60.0
$x_2$	40.0	0.0	20.0	$\infty$

Constraint	Shadow Price	Slack	Lower Bound	Upper Bound
Labor	10.0	0.0	80.0	150.0
Material	10.0	0.0	80.0	200.0

Key insights:

Both variables basic (zero reduced cost)
Both constraints binding (zero slack, positive shadow price)
Valid ranges for maintaining current basis

Python Implementation Example

PuLP Implementation

                import pulp
                
                # Create problem
                prob = pulp.LpProblem("Production", pulp.LpMaximize)
                
                # Variables
                x1 = pulp.LpVariable("x1", lowBound=0)
                x2 = pulp.LpVariable("x2", lowBound=0)
                
                # Objective
                prob += 40*x1 + 30*x2
                
                # Constraints
                prob += x1 + 2*x2 <= 100  # Labor
                prob += 3*x1 + x2 <= 120  # Material
                
                # Solve
                prob.solve()
                
                # Extract sensitivity information
                print(f"Optimal value: {pulp.value(prob.objective)}")
                for v in prob.variables():
                print(f"{v.name}: {v.varValue}, Reduced cost: {v.dj}")
                
                for name, constraint in prob.constraints.items():
                print(f"{name}: Shadow price: {constraint.pi}")

Parametric Programming

Systematic analysis of parameter changes:

RHS Parametric Programming:

Consider $\mathbf{b}(t) = \mathbf{b}^0 + t\boldsymbol{\delta}$
Optimal value: $z(t) = z^0 + t(\mathbf{y}^*)^T\boldsymbol{\delta}$
Valid for $t \in [t^-, t^+]$ (feasibility range)
At breakpoints: Basis changes, slope changes

Cost Parametric Programming:

Consider $\mathbf{c}(t) = \mathbf{c}^0 + t\boldsymbol{\gamma}$
Optimal solution changes at breakpoints
Reduced costs become zero at breakpoints
Creates piecewise-linear objective function

Applications: Multi-objective optimization, trade-off analysis, scenario planning

100% Rule for Multiple Changes

When multiple parameters change simultaneously:

For objective coefficients:

\[\sum_{j} \frac{|\Delta c_j|}{\text{allowable change for } c_j} \leq 1\]

For RHS values:

\[\sum_{i} \frac{|\Delta b_i|}{\text{allowable change for } b_i} \leq 1\]

Interpretation:

If sum $\leq 1$: Current basis guaranteed to remain optimal/feasible
If sum $> 1$: Cannot guarantee basis stability
Conservative rule - actual stability region may be larger

Robust Optimization Connection

From sensitivity to robustness:

Uncertainty sets:

Box uncertainty: $\mathbf{c} \in [\mathbf{c} - \boldsymbol{\delta}, \mathbf{c} + \boldsymbol{\delta}]$
Ellipsoidal uncertainty: $\|\mathbf{c} - \mathbf{c}^0\|_2 \leq \rho$
Polyhedral uncertainty: $\mathbf{D}\mathbf{c} \leq \mathbf{d}$

Robust counterpart:

\[\begin{aligned} \max \quad & \min_{\mathbf{c} \in \mathcal{U}} \mathbf{c}^T\mathbf{x} \\ \text{s.t.} \quad & \mathbf{A}\mathbf{x} = \mathbf{b} \\ & \mathbf{x} \geq \mathbf{0} \end{aligned}\]

Provides solutions less sensitive to parameter variations.

Stochastic Programming Extension

When parameters are random variables:

Two-stage stochastic programming:

\[\begin{aligned} \min \quad & \mathbf{c}^T\mathbf{x} + \mathbb{E}_\xi[Q(\mathbf{x}, \boldsymbol{\xi})] \\ \text{s.t.} \quad & \mathbf{A}\mathbf{x} = \mathbf{b} \\ & \mathbf{x} \geq \mathbf{0} \end{aligned}\]

Where $Q(\mathbf{x}, \boldsymbol{\xi})$ is the second-stage problem:

\[\begin{aligned} Q(\mathbf{x}, \boldsymbol{\xi}) = \min \quad & \mathbf{q}^T\mathbf{y} \\ \text{s.t.} \quad & \mathbf{W}\mathbf{y} = \mathbf{h} - \mathbf{T}\mathbf{x} \\ & \mathbf{y} \geq \mathbf{0} \end{aligned}\]

Connects to sensitivity analysis through:

Value of stochastic solution (VSS)
Expected value of perfect information (EVPI)

Supply Chain Optimization

Multi-echelon supply chain problem:

Suppliers, plants, distribution centers, customers
Uncertain demand, supply disruptions, cost fluctuations

Sensitivity analysis applications:

Demand uncertainty: How robust is the distribution strategy?
Supplier reliability: Impact of supply disruptions
Transportation costs: Effects of fuel price changes
Capacity constraints: Value of additional warehouse space

Decision support:

Identify critical suppliers and routes
Evaluate backup supplier contracts
Optimize inventory positioning

Energy System Planning

Power generation and distribution:

\[\begin{aligned} \min \quad & \sum_{i} c_i x_i + \sum_{i,t} v_i y_{it} \\ \text{s.t.} \quad & \sum_{i} y_{it} = D_t \quad \forall t \quad \text{(demand)} \\ & y_{it} \leq x_i \quad \forall i,t \quad \text{(capacity)} \\ & \text{transmission and environmental constraints} \end{aligned}\]

Sensitivity insights:

Shadow prices reveal marginal cost of electricity
Transmission congestion shadow prices
Impact of renewable energy variability
Value of demand response programs

Manufacturing System Design

Production line optimization:

Machine capacities, setup times, inventory costs
Product mix decisions under demand uncertainty

Key sensitivity questions:

Bottleneck identification: Which machines limit throughput?
Capacity expansion: ROI of additional equipment
Product profitability: Reduced costs reveal marginal products
Quality constraints: Cost of meeting tighter specifications

Implementation benefits:

Prioritize equipment investments
Optimize maintenance scheduling
Design flexible production systems

Transportation and Logistics

Vehicle routing and scheduling:

\[\begin{aligned} \min \quad & \sum_{(i,j)} c_{ij} x_{ij} \\ \text{s.t.} \quad & \sum_{j} x_{ij} = 1 \quad \forall i \quad \text{(visit each customer)} \\ & \sum_{i} x_{ij} = 1 \quad \forall j \quad \text{(leave each customer)} \\ & \text{capacity and time window constraints} \end{aligned}\]

Sensitivity applications:

Fuel cost variations: Impact on route selection
Delivery time windows: Cost of flexibility
Vehicle capacity: Value of larger trucks
Customer demand changes: Route stability

Degeneracy and Multiple Optimal Solutions

Degeneracy issues:

Multiple basic feasible solutions with same objective value
Shadow prices may not be unique
Sensitivity ranges may be misleading

Detection methods:

Check for zero basic variables
Analyze basis matrix rank
Use perturbation techniques

Handling strategies:

Lexicographic pivoting rules
Bland’s anti-cycling rule
Regularization techniques
Report ranges of possible shadow prices

Numerical Stability Issues

Common problems:

Ill-conditioned basis matrices
Floating-point precision errors
Scaling issues with large coefficient ranges

Mitigation strategies:

Scaling: Normalize coefficients to similar magnitudes
Pivoting: Choose numerically stable pivot elements
Regularization: Add small perturbations to degenerate problems
Iterative refinement: Improve solution accuracy

Validation approaches:

Cross-verification with multiple solvers
Sensitivity to solver tolerances
Analytical verification for small problems

Large-Scale Problem Considerations

Challenges for large problems:

Computing and storing basis inverse $\mathbf{B}^{-1}$
Memory requirements for sensitivity information
Computational complexity of range calculations

Efficient approaches:

Sparse matrix techniques: Exploit problem structure
Incremental updates: Update sensitivity without full recomputation
Sampling methods: Approximate sensitivity for subset of parameters
Decomposition: Analyze subsystems independently

Practical considerations:

Focus on most critical parameters
Use screening methods to identify important variables
Parallel computation for independent analyses

Multi-Criteria Decision Making

Combining LP with MCDM:

Multiple conflicting objectives
Stakeholder preferences and priorities
Uncertainty in objective weights

Approaches:

Weighted sum method: $\max \sum_{k} w_k f_k(\mathbf{x})$
Goal programming: Minimize deviations from targets
Compromise programming: Minimize distance to ideal solution

Sensitivity analysis role:

Analyze stability to weight changes
Identify trade-off regions
Support interactive decision making

Risk Management Integration

Risk-aware optimization:

\[\begin{aligned} \max \quad & \mathbb{E}[f(\mathbf{x}, \boldsymbol{\xi})] - \lambda \text{Risk}[f(\mathbf{x}, \boldsymbol{\xi})] \\ \text{s.t.} \quad & \mathbf{g}(\mathbf{x}, \boldsymbol{\xi}) \leq \mathbf{0} \text{ with probability } \geq 1-\alpha \end{aligned}\]

Risk measures:

Variance: $\text{Var}[f(\mathbf{x}, \boldsymbol{\xi})]$
Value-at-Risk: $\text{VaR}_\alpha[f(\mathbf{x}, \boldsymbol{\xi})]$
Conditional VaR: $\text{CVaR}_\alpha[f(\mathbf{x}, \boldsymbol{\xi})]$

Sensitivity insights:

Risk-return trade-offs
Robustness to risk aversion parameters
Critical probability thresholds

Real-Time Decision Support

Dynamic environments:

Parameters change over time
Decisions must be made quickly
Limited computational resources

Sensitivity-based approaches:

Warm-start methods: Use previous solution as starting point
Parametric solutions: Pre-compute solutions for parameter ranges
Approximation methods: Use sensitivity information for quick estimates

Applications:

Supply chain disruption response
Energy market bidding
Traffic management systems
Financial portfolio rebalancing

Machine Learning Integration

Learning-augmented optimization:

Predict parameter values using historical data
Learn optimal solutions for parameter patterns
Adaptive sensitivity analysis

Approaches:

Predict-then-optimize: ML for parameter prediction
Integrated learning: End-to-end optimization with ML
Reinforcement learning: Adaptive decision making

Benefits:

Reduced computational burden
Improved parameter estimates
Online adaptation to changing environments

Distributed and Parallel Computing

Scalability challenges:

Large-scale optimization problems
Multiple scenario analysis
Real-time requirements

Parallel approaches:

Decomposition methods: Divide problem into subproblems
Scenario parallelization: Analyze scenarios independently
GPU acceleration: Parallel matrix operations

Cloud computing integration:

On-demand computational resources
Distributed optimization frameworks
Collaborative decision making platforms

Emerging Applications

Smart city optimization:

Traffic flow optimization with real-time data
Energy grid management with renewable integration
Waste collection route optimization

Sustainability and circular economy:

Multi-objective optimization with environmental constraints
Life-cycle assessment integration
Circular supply chain design

Industry 4.0 applications:

IoT-enabled real-time optimization
Digital twin-based sensitivity analysis
Predictive maintenance optimization

Modeling Best Practices

Problem formulation:

Clearly define uncertain parameters
Identify critical constraints and objectives
Consider parameter correlations
Validate model assumptions

Sensitivity analysis design:

Prioritize parameters by importance and uncertainty
Design systematic parameter variation studies
Consider multiple scenarios and stress tests
Document assumptions and limitations

Interpretation guidelines:

Understand validity ranges for sensitivity information
Consider practical constraints on parameter changes
Validate results with domain experts
Communicate uncertainty in recommendations

Implementation Checklist

Before analysis:

Verify optimal solution validity
Check for degeneracy and multiple optima
Validate input data quality
Assess numerical stability

During analysis:

Systematic parameter variation
Document all assumptions
Cross-validate with alternative methods
Test boundary conditions

After analysis:

Interpret results in business context
Identify actionable insights
Communicate uncertainty and limitations
Plan for model updates and maintenance

Common Pitfalls and How to Avoid Them

Interpretation errors:

Using shadow prices outside valid ranges
Always check allowable ranges first
Ignoring degeneracy effects
Test for alternative optimal solutions

Computational mistakes:

Trusting solver output without verification
Validate results with manual calculations
Ignoring numerical precision issues
Use appropriate solver tolerances

Application errors:

Applying 100% rule incorrectly
Understand rule limitations and assumptions
Overlooking constraint dependencies
Consider system-wide effects of changes

Summary and Key Takeaways

Core concepts mastered:

Sensitivity analysis fundamentals and mathematical foundation
Changes in objective coefficients, RHS values, and constraint matrix
Shadow prices, reduced costs, and allowable ranges
Computational tools and software implementation

Advanced techniques covered:

Parametric programming and 100% rule
Integration with robust optimization and stochastic programming
Multi-criteria decision making and risk management

Practical applications:

Production planning, supply chain, energy systems
Real-time decision support and risk management
Emerging applications in smart cities and Industry 4.0

Learning Objectives Achieved

Upon completion, you can:

Formulate and solve sensitivity analysis problems
Interpret solver sensitivity reports correctly
Apply sensitivity analysis to real engineering problems
Implement computational tools for sensitivity analysis
Integrate sensitivity analysis with decision-making processes
Recognize limitations and avoid common pitfalls
Design robust optimization strategies using sensitivity insights

Next steps:

Practice with real-world case studies
Explore advanced topics like stochastic programming
Develop domain-specific applications
Stay updated with computational advances

Understanding Sensitivity Analysis