In linear programming, the primal and dual solutions refer to the optimal solutions obtained for the primal and dual linear programming problems, respectively. The primal problem is a maximization or minimization problem subject to certain constraints, while the dual problem is the corresponding minimization or maximization problem derived from the original problem.
Characteristics of the primal and dual solutions:
Primal Solution:
The primal solution refers to the optimal values of the decision variables that maximize (in maximization problems) or minimize (in minimization problems) the objective function while satisfying all the constraints in the primal linear programming problem. These solutions are expressed as specific values for each decision variable that lead to the optimal objective function value.
For example, in a standard maximization problem:
Maximize: c^T * x
Subject to: Ax ≤ b
x ≥ 0
The primal solution would provide specific values for each variable in the vector x that maximize the objective function c^T * x while adhering to the constraint equations Ax ≤ b and the non-negativity constraint x ≥ 0.
Dual Solution:
The dual solution refers to the optimal values of the dual variables (also known as shadow prices or prices of resources) that minimize (in the dual minimization problem) or maximize (in the dual maximization problem) the dual objective function while satisfying the dual constraints derived from the primal problem.
For example, for the primal problem above, the dual problem would be formulated as:
Minimize: d^T * y
Subject to: A^T * y ≥ c
y ≥ 0
The dual solution would provide specific values for each dual variable in the vector y that minimize the dual objective function d^T * y while adhering to the dual constraints A^T * y ≥ c and the non-negativity constraint y ≥ 0.
Note: The mention of “excluding mixed constraints LPPs” is not directly relevant to the distinction between primal and dual solutions. Primal and dual solutions apply to both pure linear programming problems (only containing linear constraints) and mixed-integer linear programming problems (containing some integer variables). The distinction between pure and mixed-integer linear programming lies in the nature of the decision variables (whether they can take continuous or discrete values), and it doesn’t affect the concept of primal and dual solutions.
Primal and Dual solutions excluding mixed constraints LPPs) example
Primal Linear Programming Problem:
Maximize: 3x + 4y
Subject to:
2x + y ≤ 8
x + 2y ≤ 6
x, y ≥ 0
Step 1: Primal Solution:
We will find the optimal values for the decision variables x and y that maximize the objective function 3x + 4y while satisfying all the constraints.
The feasible region of this problem is bounded by the lines 2x + y = 8 and x + 2y = 6, and the non-negativity constraints x ≥ 0 and y ≥ 0. The feasible region is a convex polygon with vertices at (0, 0), (0, 3), (2, 2), and (4, 0).
Graphically, the feasible region looks like this:
(4,0)———————-(2,2)
| |
| |
| |
| |
| |
| |
| |
(0,3)———————-(0,0)
The optimal solution is at the vertex (2, 2), where the objective function value is 3(2) + 4(2) = 14.
Step 2: Dual Solution:
Now, we will formulate the dual problem and find its optimal solution.
Dual Linear Programming Problem:
Minimize: 8u + 6v
Subject to:
2u + v ≥ 3
u + 2v ≥ 4
u, v ≥ 0
The dual problem has its own objective function and constraints, which are derived from the primal problem. In this example, the dual objective function is 8u + 6v, and the dual constraints correspond to the original primal constraints.
The dual problem’s feasible region is also bounded, defined by the lines 2u + v = 3 and u + 2v = 4, and the non-negativity constraints u ≥ 0 and v ≥ 0. The feasible region is a convex polygon with vertices at (0, 4/3), (1, 1), and (2, 0).
Graphically, the feasible region looks like this:
(2,0)————–(1,1)
| |
| |
| |
| |
| |
(0,4/3)————–+
The optimal solution for the dual problem is at the vertex (1, 1), where the objective function value is 8(1) + 6(1) = 14.
Observations:
In this example, both the primal and dual problems have optimal solutions, and their optimal objective function values are equal at 14. This satisfies the strong duality theorem.
Furthermore, the complementary slackness condition holds, as the product of each primal constraint’s slack variable and the corresponding dual variable is zero at the optimal solution:
(2)(0) = 0
(1)(0) = 0
(0)(0) = 0
(0)(0) = 0