## Solution Of A Dual Problem

**Solution Of A Dual Problem** Assignment Help | **Solution Of A Dual Problem** Homework Help

# Solution of A Dual Problem

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

subject to

3x

5x

2x

x

The dual to the above problem is:

Minimize Z = 36y

subject to

3y

3y

y

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

subject to

3x

5x

2x

x

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

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

_{1}+ 30x_{2}subject to

3x

_{1}+ 3x_{2}≤ 365x

_{1}+ 2x_{2}≤ 502x

_{1 }+ 6x_{2}≤ 60x

_{1}, x_{2}≥ 0The dual to the above problem is:

Minimize Z = 36y

_{1}+ 50y_{2}+ 60y_{3}subject to

3y

_{1}+ 5y_{2}+ 2y_{3}≥ 203y

_{1}+ 2y_{2}+ 5y_{2 }≥ 30y

_{1}, y_{2}, y_{3}≥ 0To 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

_{1}+ 30x_{2 }+ 0s_{1}+ 0s_{2}+ 0s_{3}subject to

3x

_{1}+ 3x_{2}+ s_{1}= 365x

_{1}+ 2x_{2}+ s_{2}= 502x

_{1}+ 6x_{2}+ s_{3}= 60x

_{1}, x_{2},s_{1},s_{2},s_{3}≥ 0The final simplex tableau (of the primal problem) obtained earlier.

C Basic Solution 20 30 0 0 0Variable _{ x1 x2 s1 s2 s3} |

20 _{x1} 3 1 0 1/2 0 -1/40 _{s2} 17 0 0 -13/6 1 3/430 _{ x2} 9 0 1 -1/6 0 1/4 |

Zj 330 20 30 5 0 5/2 Cj - Zj 0 0 -5 0 -5/2 |

The optimal solution (to the primal problem) is

x

_{1}= 3, x

_{2}= 9, s

_{1}= 0, s

_{2}= 17, s

_{3 }= 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

_{1}and s

_{2}) and then adding two artificial variables (A

_{1}and A

_{2}). The objective function and inequalities become:

Minimize Z = 36y

_{1}+ 50y

_{2}+ 60y

_{3 }+0s

_{1}+ 0s

_{2 }+ 0s

_{3 }+ MA

_{1}+ MA

_{2}

subject to

3y

_{1}+ 5y

_{2}+ 2y

_{3}= s

_{1}+ A

_{1}= 20

3y1 + 2y

_{2}+ 6y

_{3}– s

_{2 }+ A

_{2}= 30

y

_{1}, y

_{2}, y

_{3}, s

_{1}, s

_{2}, A

_{1}, A

_{2}≥ 0

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

C Basic Solution 36 50 60 0 0 M MVariable _{ y1 } _{ y2 } _{y3 } _{ s1} _{s2} _{A1} _{A2} |

36 _{y1 } 5 1 13/6 0 -1/2 -1/6 1/2 -1/660 _{ y3 } 5/2 0 -3/4 1 1/4 -1/4 -1/4 1/4 |

Zj 330 36 33 60 -3 -9 3 9 Cj - Zj 0 17 0 3 9 M-3 M-9 |

The optimal solution to the dual problem is:

y

_{1}=5, y

_{2}= 0, y

_{3}= 5/2, s

_{1}= 0, s

_{2}= 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

_{2}of the final tableau of the dual are same as the values under the “Solution” column (corresponding to variables x

_{1}and x

_{2}) in the final tableau of the primal problem. We further observe that magnitude of variables y

_{1}and y

_{3}are exactly the same as the entries (with signs reversed) in the C

_{j}– Z

_{j}row under columns s

_{1}and s

_{3}of final tableau of the primal problem. The zero entry in the Cj – Z

_{j}row under column s

_{2}of the final tableau of the primal problem shows that magnitude of the variable y

_{2}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