Dual Formulation: Linear Programming

In this section, we will introduce the concept of Dual Formulation in Linear Programming (LP). Now lets concentrate on the following example:

Example: Dual Formulation in Linear Programming

Minimize z = 3x₁ + 3x₂

subject to

2x₁ + 4x₂ ≥ 40
3x₁ + 2x₂ ≥ 50

x₁, x₂ ≥ 0

Solution.

Maximize z = 40w₁ + 50w₂

subject to

2w₁ + 3w₂ ≤ 3
4w₁ + 2w₂ ≤ 3

w₁, w₂ ≥ 0

Primal Dual Relationship in Linear Programming (LP)

Primal Dual Relationship

• The number of constraints in the primal problem is equal to the number of dual variables, and vice versa.
• If the primal problem is a maximization problem, then the dual problem is a minimization problem and vice versa.
• If the primal problem has greater than or equal to type constraints, then the dual problem has less than or equal to type constraints and vice versa.
• The profit coefficients of the primal problem appear on the right-hand side of the dual problem.
• The rows in the primal become columns in the dual and vice versa.