4.2 Complementary slackness conditions

Linear programming's complementary slackness conditions link primal and dual solutions. These conditions reveal relationships between decision variables and resource values, helping identify binding constraints and optimal resource allocation in optimization problems.

Understanding these conditions is crucial for verifying solution optimality and conducting sensitivity analysis. They provide valuable insights into resource utilization, product profitability, and guide decision-making in various applications like manufacturing and investment portfolios.

Complementary Slackness Conditions in Linear Programming

Complementary slackness conditions

• Primal problem complementary slackness formulated as $x_j(c_j - \sum_{i=1}^m a_{ij}y_i) = 0$ applies to all decision variables $x_j$ (production quantities)
• Dual problem complementary slackness expressed as $y_i(b_i - \sum_{j=1}^n a_{ij}x_j) = 0$ applies to all dual variables $y_i$ (resource values)
• Interpretation reveals either primal variable zero or dual constraint binding and vice versa establishing relationship between solutions (resource utilization, product profitability)

Optimality in primal-dual solutions

1. Verify feasibility of primal and dual solutions ensuring constraints satisfied
2. Check complementary slackness conditions met for all variable pairs
3. Confirm both primal and dual solutions feasible and conditions satisfied

• Practical application enables optimality confirmation without objective function calculation useful for multiple feasible solutions (manufacturing processes, investment portfolios)

Binding constraints identification

• Binding constraints in primal problem recognized when corresponding dual variable non-zero indicating constraint satisfied with equality at optimality (production capacity limits)
• Non-binding constraints have zero corresponding dual variable may have slack at optimality (excess inventory)
• Implications for sensitivity analysis highlight binding constraints critical in determining optimal solution changes may affect outcome (resource availability, demand fluctuations)

Primal-dual variable relationships

• Economic interpretation links primal variables to resource or product quantities dual variables represent shadow prices or marginal values (labor hours, material costs)
• Relationship between variables shows non-zero primal variable implies binding dual constraint and vice versa (fully utilized resources, profitable products)
• Insights from complementary slackness help identify fully utilized resources and profitable activities (production bottlenecks, market opportunities)
• Applications in decision-making guide resource allocation based on shadow prices and identify improvement opportunities in processes (supply chain optimization, product mix decisions)