Weak and Strong Duality

Weak and strong duality in linear programming are conditions of optimality of primal and dual of a linear programming problem. Every linear programming problem is associated with another linear programming problem called the dual, and the original problem is called the primal. The optimal solution of both renders information about the given problem.

Let the given primal problem be:

subject to:

and x_j ≥ 0 for j = 1, 2, 3, …, n.

The dual associated with this problem is defined as

subject to:

and y_i ≥ 0 for i = 1, 2, 3, …, m.

Weak Duality

Let x_j; j = 1, 2, 3, …, n be the feasible solution of the primal problem P and y_i; i = 1, 2, 3, …, m be the feasible solution of the dual problem D, if

Then the given linear programming is said to have weak duality.

Weak Duality Theorem

For any feasible solution x_j; j = 1, 2, 3, …, n and y_i; i = 1, 2, 3, …, m of the given primal and dual respectively,

Let x = x_j; j = 1, 2, 3, …, n and y = y_i; i = 1, 2, 3, …, m. Then as per the conditions of primal and dual ∑_j a_ij x ≤ b_i (i = 1, 2, 3, …, m) and ∑_i a_ij y ≥ c_j (j = 1, 2, 3, …, n). Then we have,

∑_i ∑_j a_ij x y ≤ ∑_i b_i y and ∑_j ∑_i a_ij y x ≥ ∑_j c y

From both the inequalities we have

∑_j c y ≤ ∑_i b_i y

Thus, the weak duality property implies that the duality gap is either zero or greater zero. If the duality gap is zero, then the obtained solution of primal and dual are optimal respective of their problem.

Strong Duality

If the primal (dual) problem has an optimal solution, then so does the dual (primal) problem. That means, strong duality is a condition of optimization where the primal optimal solution is equal to the dual optimal solution.

Strong Duality Theorem

A primal linear programming problem has a finite optimal solution if and only if the dual linear programming problem has a finite optimal solution.

The direct consequence of strong duality is that the duality gap is zero. The strong duality also results in optimality properties.

Unboundedness Property

If the primal (dual) problem has an unbounded solution, then the dual (primal) problem is infeasible.

This property directly implies the weak duality property.

Related Articles

• Types of Linear Programming Problem
• Vogel’s Approximation Method
• Optimization
• Graphical Method of Solving Linear Programming

Solved Example on Weak and Strong Duality

Example:

Check the weak and strong duality property for the following linear programming problem.

Max Z = 30x₁ + 23x₂ + 29x₃

subject to: 6x₁ + 5x₂ + 3x₃ ≤ 26

4x₁ + 2x₂ + 5x₃ ≤ 7

and x₁, x₂, x₃ ≥ 0

Solution:

Introducing the slack variables x₄ and x₅ the given problem reduces to,

Max Z = 30x₁ + 23x₂ + 29x₃ + 0.x₄ + 0.x₅

subject to: 6x₁ + 5x₂ + 3x₃ + x₄ = 26

4x₁ + 2x₂ + 5x₃ + x₅ = 7

and x₁, x₂, x₃, x₄, x₅ ≥ 0

Taking x₁ = x₂ = x₃ = 0, we get x₄ = 26 and x₅ = 7 which is the starting basic feasible solution.

Then we have simplex table computations:

Since no Δ_j > 0, so this is the optimal solution

Thus x₁ = 0, x₂ = 7/2 and x₃ = 0

Max Z = 161/2

To write the dual of the primal

Given, Z = (30, 23, 29) [x₁, x₂, x₃]

subject to

and x₁, x₂, x₃ ≥ 0

Therefore, the dual of the given problem is

Min Z_D = (26, 7)[w₁, w₂]

subject to

and w₁, w₂ ≥ 0

Or, Min Z_D = 26w₁ + 7w₂

s.t. 6w₁ + 4w₂ ≥ 30

5w₁ + 2w₂ ≥ 23

3w₁ + 5w₂ ≥ 29

and w₁, w₂ ≥ 0

We can use the simplex table of primal to read the solution of dual.

In the table, x₄ and x₅ are slack variables and Δ_j below the corresponding columns Y₄ and Y₅ are Δ₄ and Δ₅, respectively.

Therefore, w₁ = – Δ₄ and w₂ = – Δ₅ = 23/2

and Min. Z_D = 161/2

Since, Max Z = Min Z_D, hence weak and strong duality theorems are satisfied.