Duality in linear programming means that every linear programming problem (called the primal problem) has a related linear programming problem called the dual problem. These two problems are based on the same underlying data and offer valuable, related perspectives on the optimization problem.
Understanding the Primal and Dual
The primal problem typically seeks to maximize or minimize an objective function subject to a set of constraints. The dual problem, on the other hand, reverses the roles of the objective function and the constraints. If the primal problem is a maximization problem, the dual problem is a minimization problem, and vice versa. The constraints in the primal become the variables in the dual, and the variables in the primal become the constraints in the dual.
Key Relationships Between Primal and Dual
- Weak Duality: The objective function value of the primal (maximization) is always less than or equal to the objective function value of the dual (minimization).
- Strong Duality: At optimality, the objective function values of the primal and dual are equal. This is a very important property.
- Complementary Slackness: This relationship links the optimal primal and dual solutions. It provides conditions under which a primal constraint or dual constraint is binding (active).
Benefits of Duality
- Economic Interpretation: The dual variables often have important economic interpretations. They represent the shadow prices or marginal values of the resources represented by the primal constraints. Understanding these shadow prices helps in decision-making regarding resource allocation.
- Computational Efficiency: In some cases, solving the dual problem is computationally easier than solving the primal problem, especially for problems with a large number of constraints and fewer variables.
- Sensitivity Analysis: Duality provides a way to analyze how the optimal solution changes when the problem's parameters (e.g., constraint limits, objective function coefficients) change.
- Validation: Since the optimal values of the primal and dual problems are equal (strong duality), comparing solutions helps validate that the problem has been correctly formulated and solved.
Example
Let's say we have the following (simplified) primal problem:
Maximize: z = 3x₁ + 2x₂
Subject to:
x₁ + x₂ ≤ 42x₁ + x₂ ≤ 5x₁, x₂ ≥ 0
The dual problem would be:
Minimize: w = 4y₁ + 5y₂
Subject to:
y₁ + 2y₂ ≥ 3y₁ + y₂ ≥ 2y₁, y₂ ≥ 0
In this example:
- The objective function coefficients (3 and 2) in the primal became the constraint limits in the dual.
- The constraint limits (4 and 5) in the primal became the objective function coefficients in the dual.
- The constraint coefficients in the primal form the coefficients in the dual's constraints (transposed).
Solving both problems will result in the same optimal objective function value, demonstrating strong duality. The optimal values of y₁ and y₂ in the dual represent the shadow prices of the constraints in the primal problem.
Conclusion
Duality in linear programming is a fundamental concept that provides a different, yet related, perspective on an optimization problem. It not only offers valuable economic insights but can also be used to improve computational efficiency and perform sensitivity analysis.
