Duality Principle. It either the primal or the dual problem has an optimum solution, then so does the other problem (dual or primal), and the optimal value of the prima’s objective function is the same as that of its dual.

The simplex procedure, studied earlier, will give us the optimum solution for both the primal and its dual problems simultaneously. To illustrate this, let’s consider the furniture manufacturer’s problem discussed in Example. The problem is to

Maximize          Z = 20x₁ + 30x₂
subject to
 
3x₁ + 3x₂ ≤ 36
5x₁ + 2x₂ ≤ 50
2x₁ + 6x₂  ≤ 60
         x₁, x₂ ≥  0

The dual to the above problem is:

Minimize       Z = 36y₁ + 50y₂ + 60y₃
subject to

3y₁ + 5y₂ + 2y₃  ≥ 20
3y₁ + 2y₂ + 5y₂ ≥  30
           y₁, y₂, y₃ ≥  0

To show that an optimal solution to a primal problem can always provide the optimal solution to its dual and vice versa, well first solve the primal problem and then the dual problem.

Solution of the Primal Problem.  Introducing slack variables in the above stated (primal) problem, the problem can be re-stated as

Maximize    Z = 20x₁ + 30x₂ + 0s₁ + 0s₂ + 0s₃
subject to

3x₁ + 3x₂ + s₁ = 36
5x₁ + 2x₂ + s₂ = 50
2x₁ + 6x₂ + s₃ = 60
x₁, x₂,s₁,s₂,s₃ ≥  0

The final simplex tableau (of the primal problem) obtained earlier.

The optimal solution (to the primal problem) is
x₁ = 3, x₂ = 9, s₁ = 0, s₂ = 17, s₃ = 0 and Z = 330

Solution to the Dual Problem. To solve the dual problem by simplex method, the first step is to convert inequalities into equalities by subtracting two surplus variables (s₁ and s₂) and then adding two artificial variables (A₁ and A₂). The objective function and inequalities become:

Minimize    Z = 36y₁ + 50y₂ + 60y₃ +0s₁ + 0s₂ + 0s₃ + MA₁ + MA₂
subject to

3y₁ + 5y₂ + 2y₃ = s₁ + A₁ = 20
3y1 + 2y₂ + 6y₃ – s₂ + A₂ = 30
y₁, y₂, y₃, s₁, s₂, A₁, A₂  ≥  0

Solving this problem by simplex method, it can be verified that the final simplex tableau is:

The optimal solution to the dual problem is:

y₁ =5, y₂ = 0, y₃ = 5/2, s₁ = 0, s₂ = 0 and Z = 330

If we now examine the two final tableaux, one as obtained in the primal problem and the other as obtained in the dual problem, we observe that 330 is the value of the objective function for both primal and dual, as it must be. Moreover, the solutions of both the problems (primal and its dual) are contained in either of the final tableau. In fact, the values in the Cj – Z_j row under columns s1 and s₂ of the final tableau of the dual are same as the values under the “Solution” column (corresponding to variables x₁ and x₂) in the final tableau of the primal problem. We further observe that magnitude of variables y₁ and y₃ are exactly the same as the entries (with signs reversed) in the C_j – Z_j row under columns s₁ and s₃ of final tableau of the primal problem. The zero entry in the Cj – Z_j row under column s₂ of the final tableau of the primal problem shows that magnitude of the variable y₂ should be zero as has been found in the optimal solution to the dual. Hence we may conclude that the solution to a primal problem can always provide solution to its dual and vice-versa.

For more help in Solution of A Dual Problem click the button below to submit your homework assignment