Duality

Note: this lesson is optional.

An important concept in linear programming is duality. Every linear programming problem (referred to as the primal problem) has a corresponding dual problem. The dual problem provides insights into the original problem and can sometimes be easier to solve.

The relationship between the primal and dual problems is such that the optimal solution to one provides information about the optimal solution to the other. Specifically, the value of the objective function in the primal problem at the optimal solution equals the value of the objective function in the dual problem at the optimal solution. This principle is known as the Strong Duality Theorem.

Primal Problem Example

Suppose a company produces two types of products, $$x_1$$ and $$x_2$$. The company wants to maximize its profit, with profits of $3 per unit of $$x_1$$ and $5 per unit of $$x_2$$. The production is subject to the following constraints:

  1. The production of $$x_1$$ and $$x_2$$ requires different amounts of two resources, $$R1$$ and $$R2$$.
  2. Resource $$R1$$ has a maximum availability of 4 units.
  3. Resource $$R2$$ has a maximum availability of 12 units.
  4. Each unit of $$x_1$$ requires 1 unit of $$R1$$ and 3 units of $$R2$$.
  5. Each unit of $$x_2$$ requires 2 units of $$R1$$ and 2 units of $$R2$$.

The primal linear programming problem can be formulated as follows:

Primal Problem:

Maximize $$z = 3x_1 + 5x_2$$

subject to:

$$ \begin{align*} x_1 + 2x_2 & \leq 4 & \text{(Resource R1 constraint)} \ 3x_1 + 2x_2 & \leq 12 & \text{(Resource R2 constraint)} \ x_1, x_2 & \geq 0 & \text{(Non-negativity constraint)} \end{align*} $$

Dual Problem Example

To formulate the dual problem, we follow these steps:

  • Each constraint in the primal problem corresponds to a variable in the dual problem.
  • The objective function coefficients in the primal problem become the right-hand side constants in the dual problem.
  • The right-hand side constants in the primal problem become the objective function coefficients in the dual problem.
  • The inequalities are reversed, and the primal's "less than or equal to" constraints become the dual's "greater than or equal to" constraints.

Dual Problem:

Minimize $$ w = 4y_1 + 12y_2 $$

subject to:

$$ \begin{align*} y_1 + 3y_2 & \geq 3 & \text{(from coefficient of } x_1 \text{ in primal objective)} \ 2y_1 + 2y_2 & \geq 5 & \text{(from coefficient of } x_2 \text{ in primal objective)} \ y_1, y_2 & \geq 0 & \text{(Non-negativity constraint)} \end{align*} $$

Interpretation

  • Primal Problem: The company wants to maximize profit by deciding how much of each product ($$x_1$$ and $$x_2$$) to produce, given the resource constraints.
  • Dual Problem: The dual problem can be interpreted as a resource allocation problem, where $$y_1$$ and $$y_2$$ represent the shadow prices of resources $$R1$$ and $$R2$$, respectively. The objective is to minimize the total cost of resources, subject to the constraint that the resource prices provide at least as much value as the profit contributions of the products.

Relationship Between Primal and Dual

According to the Strong Duality Theorem, if both the primal and dual problems have feasible solutions, then the optimal value of the objective function in the primal problem (maximum profit) equals the optimal value of the objective function in the dual problem (minimum cost). This relationship provides valuable insights into the economics of resource allocation and pricing in optimization problems.