Concept of Duality

Understand the Concept of Duality in Optimization Techniques.

1. CONCEPT OF DUALITY Optimization Techniques

2. Concepts of Duality One of the most important discoveries in the early development of linear programming was the concept of duality. Every LPP has associated with it another LPP. The original problem is called the “Primal” while the other is called its “Dual”. The optimal solution of either problem reveals information concerning the optimal solution of the other. This fact is important because the situation can arise where the dual is easier to solve than the primal.

3. Example … (Primal) The Following problem can be formulated as follows: Min z = 10x1 + 15x2, subject to constraints 5x1 + 7x2 >= 80 6x1 + 11x2 >= 100, x1 >= 0, x2 >= 0 In the formulation, we have assumed that taking more than the minimum requirement is not harmful.This LPP will be considered as the primal problem.

4. Basis of Conversion The costs associated with the objective function of one problem are just the requirements in the other’s set of constraints. The constraint coefficient matrix associated with one problem is simply the transpose of the constraint Coefficient matrix associated with the other. One of the problems is a maximization problem while the other one is a minimization problem.

5. Example …

6. Symmetric Primal-Dual Problem Transposing the coefficient matrix. Interchanging the role of constant terms and the role of the objective function. Reverting the inequalities. Minimizing the objective function instead of maximizing.

7. Rules For Conversion First convert the objective function to maximization form, if not already. If a constraint has inequality sign “≥”, then multiply both sides by −1 and make the inequality sign ≤. If a constraint has an equality sign “=”, then it is replaced by two constraints involving the inequalities going in opposite directions, simultaneously. Every unrestricted variable is replaced by the difference of two non-negative variables.

8. Rules of Conversion (contd…) We get the standard primal form of the given LPP in which: a) all the constraints have “≤” sign, where the objective function is of maximization form; or b) all the constraints have “≥” sign, where objective function is of minimization form. Finally, the dual of the given problem is obtained by: a) transposing the rows and columns of constraint coefficients; b) transposing the coefficients (c1, c2, ... , cn) of the objective function and the right-side constants (b1, b2, ... , bm); c) changing the inequalities from “≤” to “≥” sign; and d) minimizing the objective function instead of maximizing it.

9. Duality in Linear Programming Duality Theorem: The dual of the dual of a given primal is the primal. If the kth constraint of the primal is an equality, then the dual variable wk is unrestricted in sign. Also, if pth variable of the primal is unrestricted in sign, then the pth constraint of the dual is an equality. If the primal or the dual has a finite optimum solution, then the other problem also possesses a finite optimum solution and the optimum value in both the cases will be the same.

10. Example … (Tabular Form)

11. Dual Simplex Method Such a situation is recognized by first expressing the constraints in the form “≤” and the objective function in the maximization form. After adding the slack variables and putting the problem in the tabular form, if any of the right hand side elements are negative and if the optimality condition is satisfied, then the problem can be solved by the dual simplex method. negative element on the right hand side signifies that the corresponding slack variable is negative. In this method, we shall proceed towards feasibility maintaining optimality and at the iteration where the basic solution becomes feasible, it becomes the optimal basic feasible solution also.

12. Advantages of Dual Simplex we do not require any artificial variables in the dual simplex method. Hence a lot of effort is saved whenever this method is applicable. The dual simplex method is similar to the standard simplex method except that the starting initial solution in standard simplex method is feasible but not optimum while in the dual simplex it is infeasible but optimum or better than optimum. The dual simplex method works towards feasibility while simplex method works towards optimality.

13. THANK YOU Subham Satpathy