Optimization- Primal and Dual Linear Programming
Introduction
Linear Programming (LP) is a mathematical optimization technique used to find the best solution from a set of feasible solutions in linear functions. The primary goal of LP is to maximize or minimize an objective function, subject to a set of linear constraints.
Primal Linear Programming (LP) Problem:
In LP, the Primal LP problem is the original optimization problem that we want to solve. It has the following standard form:
Maximize: c^T x
Subject to: Ax ≤ b
x ≥ 0
Where:
c is the vector of coefficients of the objective function to be maximized.
x is the vector of decision variables that we need to determine to maximize the objective function.
A is the matrix of constraint coefficients that defines the constraints on the decision variables.
b is the vector of constants representing the right-hand side of the inequality constraints.
The objective of the Primal LP problem is to find the values of x that maximize the linear objective function c^T x while satisfying the given inequality constraints Ax ≤ b and the non-negativity constraints x ≥ 0.
The solution to the Primal LP problem provides the optimal values of the decision variables x and the corresponding maximum value of the objective function. However, in some cases, the solution might be unbounded (no upper bound on the objective function) or infeasible (no feasible solution satisfying all constraints).
Dual Linear Programming (LP) Problem:
The Dual LP problem is derived from the Primal LP problem and provides an alternative representation of the optimization problem. For a Primal LP problem in standard form, the Dual LP problem can be formulated as follows:
Minimize: b^T y
Subject to: A^T y ≥ c
y ≥ 0
Where:
y is the vector of dual variables associated with the constraints of the Primal LP problem.
The objective of the Dual LP problem is to find the values of the dual variables y that minimize the linear objective function b^T y, subject to the given constraints A^T y ≥ c and the non-negativity constraints y ≥ 0.
Strong Duality:
Strong duality is an important property in linear programming that relates the optimal solutions of the Primal and Dual LP problems. If the Primal LP problem has an optimal solution and the Dual LP problem also has an optimal solution, then the optimal objective values of both problems are equal. Mathematically, it can be expressed as follows:
Primal Optimal Objective Value = Dual Optimal Objective Value
When strong duality holds, the Primal and Dual LP problems provide complementary information about the optimization problem. The dual variables y represent the "shadow prices" associated with the constraints in the Primal LP problem. They indicate how much the optimal objective value of the Primal problem will change with a small increase in the corresponding constraint right-hand side b. Similarly, the primal variables x represent the optimal values of the decision variables in the Primal LP problem.
Strong duality is a powerful property that has practical implications in optimization theory, economics, and various other fields. It allows us to study the Primal and Dual problems together to gain insights into the nature of the optimal solutions and identify the "dual" relationships between constraints and variables. Additionally, strong duality provides useful information in sensitivity analysis and understanding the effects of changes in the problem's parameters.
Steps to Derive Dual LP from Primal LP
To derive the Dual Linear Programming (LP) problem from the Primal LP problem, we use a mathematical transformation based on the concept of Lagrange multipliers. The derivation involves interchanging the roles of variables and constraints between the Primal and Dual problems. Let's go through the steps using a specific example.
Primal LP:
Maximize: 2x + y
Subject to: x + 2y ≤ 6
3x + y ≤ 9
x, y ≥ 0
Step 1: Write the Primal LP in standard form by introducing slack variables s1 and s2 for the inequality constraints:
Maximize: 2x + y
Subject to: x + 2y + s1 = 6
3x + y + s2 = 9
x, y, s1, s2 ≥ 0
Step 2: Form the Lagrangian by introducing Lagrange multipliers (λ1 and λ2) for the constraints:
L(x, y, s1, s2, λ1, λ2) = 2x + y + λ1(6 - x - 2y - s1) + λ2(9 - 3x - y - s2)
Step 3: Find the partial derivatives of the Lagrangian with respect to x, y, s1, and s2, and set them to zero to find the critical points:
∂L/∂x = 2 - λ1 - 3λ2 = 0
∂L/∂y = 1 - 2λ1 - λ2 = 0
∂L/∂s1 = -λ1 = 0
∂L/∂s2 = -λ2 = 0
Step 4: Solve the system of equations to find the values of x, y, s1, and s2 in terms of λ1 and λ2:
λ1 = 0
λ2 = 0
2 - λ1 - 3λ2 = 2
1 - 2λ1 - λ2 = 1
The critical points are x = 1, y = 3, s1 = 0, and s2 = 0.
Step 5: Substitute the critical points into the Primal LP to find the optimal objective value:
2x + y = 2(1) + 3 = 5
Thus, the optimal objective value of the Primal LP is 5.
Step 6: Substitute the critical points into the Lagrangian to find the Dual LP objective function in terms of λ1 and λ2:
L(1, 3, 0, 0, λ1, λ2) = 2(1) + 3 + λ1(6 - 1 - 2(3) - 0) + λ2(9 - 3(1) - 3 - 0)
L(1, 3, 0, 0, λ1, λ2) = 5 + 5λ1 - 3λ2
Step 7: Formulate the Dual LP by minimizing the objective function with respect to λ1 and λ2:
Minimize: 5λ1 - 3λ2
Subject to: λ1 ≥ 0
λ2 ≥ 0
The Dual LP is now derived from the Primal LP and is given by the above formulation.
In this example, we have shown the derivation of the Dual LP problem from the given Primal LP problem. The Dual LP provides valuable information about the "shadow prices" associated with the constraints in the Primal LP problem, which helps us gain insights into the optimal solutions and the trade-offs between different constraints. Additionally, the concept of strong duality allows us to relate the optimal solutions and objective values of the Primal and Dual LP problems, demonstrating their complementary nature in linear programming.