In linear programming, the dual problem is a mathematical formulation associated with the primal linear programming problem. It is derived from the primal problem and provides valuable insights into the original problem’s structure, particularly regarding resource availability and the objective function’s sensitivity to changes in the constraints.
The general steps to formulate the dual problem are as follows:
Primal Problem:
Consider the standard primal linear programming problem in maximization form:
Maximize: c^T * x
Subject to: Ax <= b
x >= 0
Where:
c^T is the transpose of the vector of objective function coefficients.
x is the vector of decision variables to be determined.
A is the matrix of constraint coefficients.
b is the vector of right-hand side values of the constraints.
Dual Variables:
Introduce a new vector of dual variables (also called Lagrange multipliers or shadow prices) y corresponding to each constraint in the primal problem. The vector y has the same dimension as the number of constraints.
Dual Problem:
The dual problem is formulated in minimization form and is derived by minimizing the Lagrangian function with respect to the dual variables y. The Lagrangian function for the primal problem is:
L(x, y) = c^T * x + y^T * (b – Ax)
The dual problem is then expressed as:
Minimize: d^T * y
Subject to: A^T * y >= c
y >= 0
Where:
d is the vector of right-hand side values of the primal constraints (the vector b in the primal problem).
Interpretation:
The dual problem has its own objective function and constraints. The objective function of the dual problem represents the lower bound (minimum value) of the primal objective function subject to the given constraints. The dual constraints provide bounds on the resources’ values and how much the primal objective function will change for unit changes in those resources.
The strong duality theorem in linear programming states that if both the primal and dual problems have feasible solutions, their optimal objective function values are equal, and the optimal solutions for both problems can be attained simultaneously. This is known as the duality property.
Solving the dual problem can provide valuable information, such as shadow prices (dual variables) that indicate the marginal value of resources and constraints’ tightness in the primal problem.
Formulating and solving the dual problem is particularly useful for understanding the primal problem’s characteristics and making informed decisions in real-world applications.
Relationship between Primal and Dual LPP
The relationship between the primal and dual linear programming problems is a fundamental aspect of linear programming known as duality. The duality theory establishes a strong relationship between these two problems, providing valuable insights and optimization information.
Here are the key points regarding the relationship between the primal and dual linear programming problems:
Objective Function Value:
The optimal objective function value of the primal linear programming problem is always greater than or equal to the optimal objective function value of the dual linear programming problem. Mathematically, it can be expressed as:
Primal Optimal Objective ≥ Dual Optimal Objective
This relationship is known as weak duality or the duality gap.
Optimal Solutions:
If both the primal and dual linear programming problems have feasible solutions, their optimal objective function values are equal, and the optimal solutions for both problems can be attained simultaneously. This is known as the strong duality theorem.
Primal Optimal Objective = Dual Optimal Objective
Complementary Slackness:
The optimal solution vectors of the primal and dual problems satisfy complementary slackness. It means that at the optimal solution, the product of each primal constraint’s slack variable and the corresponding dual variable is zero. Mathematically, it can be expressed as:
x_i * y_i = 0 for all i
where x_i is the slack variable for the ith primal constraint, and y_i is the ith dual variable.
Shadow Prices:
The dual variables (also known as shadow prices or prices of resources) provide information about the marginal value of the constraints in the primal problem. They represent the rate of change of the primal objective function value for a one-unit increase in the corresponding right-hand side (RHS) of the constraints.
Interpretation:
The dual problem can have economic interpretations related to resource values, opportunity costs, and sensitivity analysis. The primal problem represents the maximization or minimization of a certain objective subject to constraints, while the dual problem represents the minimization of resource costs to satisfy the constraints.
The duality relationship is a powerful tool in linear programming as it allows us to analyze and interpret the primal problem from different perspectives, providing additional information about the problem’s solution and sensitivity to changes in the constraints. Moreover, the optimal dual solution can be used to obtain bounds on the optimal primal solution and vice versa, enhancing the efficiency of solving and analyzing linear programming problems.