By Yamal 
Duality in linear programming is a powerful concept that provides insights into the relationships between two optimization problems: the primal problem and the dual problem. Understanding duality can help in solving linear programming problems more effectively and provides strong economic interpretations. Here’s a detailed overview of duality in linear programming:
- Primal and Dual Problems
– Primal Problem: The original linear programming problem is called the primal problem. It typically involves maximizing or minimizing an objective function subject to linear constraints.
Standard Form of the Primal Problem:
\[
\text{Maximize } Z = c^T x
\]
Subject to:
\[
Ax \leq b
\]
\[
x \geq 0
\]
Where \(c\) is a vector of coefficients for the objective function, \(A\) is the matrix of coefficients for the constraints, \(x\) is the vector of decision variables, and \(b\) is the vector of resource limits.
– Dual Problem: The dual problem is derived from the primal problem and involves a different objective function and constraints. Each variable in the primal corresponds to a constraint in the dual, and each constraint in the primal corresponds to a variable in the dual.
Standard Form of the Dual Problem:
\[
\text{Minimize } W = b^T y
\]
Subject to:
\[
A^T y \geq c
\]
\[
y \geq 0
\]
Here, \(y\) is the vector of dual variables associated with the primal constraints.
- Relationship Between Primal and Dual
– Weak Duality: This principle states that the value of the objective function of the primal problem (for a feasible solution) is always less than or equal to the value of the objective function of the dual problem (for a feasible solution). Mathematically:
– For a feasible solution \(x\) of the primal and a feasible solution \(y\) of the dual:
\[
c^T x \leq b^T y
\]
– Strong Duality: This principle states that if both the primal and dual problems have feasible solutions, then their optimal solutions are equal. If one problem has an optimal solution, so does the other, and the values of the objective functions at the optimal solutions are the same:
\[
Z^* = W^*
\]
Where \(Z^*\) is the optimal value of the primal and \(W^*\) is the optimal value of the dual.
– Complementary Slackness: This condition provides further insight into the relationship between the primal and dual problems. It states that if \(x_i\) is a positive decision variable in the primal, then the corresponding dual constraint is tight (exactly satisfied), and vice versa:
– If \(x_i > 0\), then the corresponding dual constraint holds with equality.
– If \(y_j > 0\), then the corresponding primal constraint holds with equality.
- Economic Interpretation
– Value of Resources: The dual variables can be interpreted as the values of the resources in the primal problem. For example, if the primal problem represents maximizing profit subject to cost constraints, the dual variables can be viewed as the shadow prices, indicating how much the objective would improve if there were one additional unit of the resource.
– Resource Allocation: The primal problem reflects how to allocate resources to maximize the output, while the dual problem can provide insights into the cost of those resources and how they can be used efficiently.
- Application of Duality
– Solving Linear Programs: The dual problem provides an alternative method for solving the primal problem. Often, solving the dual can be more computationally efficient, especially for large-scale problems.
– Sensitivity Analysis: Duality is useful in sensitivity analysis since changes in the dual variables provide information on how the optimal solution will change in response to changes in the problem constraints.
– Formulation of Problems: Duality can help in reformulating problems to find the simplest or most efficient representation of a linear programming scenario.
- Example of Primal and Dual
Primal Problem Example:
\[
\text{Maximize } Z = 3x_1 + 5x_2
\]
Subject to:
\[
2x_1 + x_2 \leq 10
\]
\[
x_1 + 3x_2 \leq 15
\]
\[
x_1, x_2 \geq 0
\]
Dual Problem:
\[
\text{Minimize } W = 10y_1 + 15y_2
\]
Subject to:
\[
2y_1 + y_2 \geq 3
\]
\[
y_1 + 3y_2 \geq 5
\]
\[
y_1, y_2 \geq 0
\]
Conclusion
Understanding duality in linear programming is crucial as it not only enhances the efficiency of solving linear programs but also provides deep economic insights. The relationship between the primal and dual problems enriches the analysis of resource allocation, decision-making, and optimal value interpretation, making duality a fundamental principle in operations research and economic modeling.