PRIMAL & DUAL PROBLEMS

This presentation is based on PRIMAL & DUAL realed to operation research.

1. PRIMAL & DUAL PROBLEMS OPERATION RESEARCH Submitted by : Khambhayata Mayur ( 130010119042) Khant Vijaykumar (130010119045) Lad Y ashkumar (130010119047) Submitted to :

2. Content Duality in Linear Programming Problems Different useful aspects Points to remember while converting into dual Conversion of primal to its dual Important modification Relationship between solutions of Primal and Dual Example

3. Duality in Linear Programming Problems For every Linear programming Problem, there is a corresponding unique problem involving the same data and it also describes the original problem. The original problem is called primal programme and the corresponding unique problem is called Dual programme. The two programs are very closely related and optimal solution of dual gives complete information about optimal solution of primal and vice versa.

4. Different useful aspects If primal has large number of constraints and small number of variables, computation can be considerably reduced by converting problem to Dual and then solving it. Economic interpretation of the dual helps the management in making future decision. Calculation of the dual checks the accuracy of the primal solution. Duality is used to solve LPP in which the initial solution is infeasible.

5. Points to remember while converting into dual If the primal contains n variables and m constraints, the dual will contain m variables and n constraints. The maximization problem in the primal becomes the minimization problem in the dual and vice versa. The maximization problem has (≤) constraints while the minimization problem has (≥) constraints. The constants c 1 , c 2 , …, c n in the objective function of the primal appear in the constraints of the dual. The constants b 1 , b 2 , …, b m in the constraints of the primal appear in the objective function of the dual. The variables in both problems are non-negative.

6. Conversion of primal to its dual The general L.P.P. or primal in canonical form is : Maximize z = c 1 x 1 +c 2 x 2 +…+ c n x n Subject to a 11 x 1 +a 12 x 2 +…+a 1n x n ≤ b 1 a 21 x 1 +a 22 x 2 +…+a 2n x n ≤ b 2 …………..…………………………………… ………………………………………………… a m1 x 1 +a m2 x 2 +…+a mn x n ≤ b m where , x 1, x 2, ...,x n, all ≥ 0. Now its dual is: Minimize w = b 1 y 1 +b 2 y 2 +…+b m y m Subject to a 11 y 1 +a 21 y 2 +…+a m1 y m ≤ c 1 a 12 y 1 +a 22 y 2 +…+a m2 y m ≤ c 2 …………..………………………………………….. ………………………………………………………... a 1n y 1 +a 2n y 2 +…+a mn y m ≤ c n where, the dual variables y 1 , y 2 ,…, y m, all ≥ 0.

7. Important modification Objective function : If the objective function is maximum in Primal then it will change to minimize in Dual LPP and vice versa. Co-efficient of objective function : Co-efficient of objective function in Primal LPP will be the RHS of constraints in Dual LPP. Constraints : RHS of constraints in Primal LPP will function as co-efficient of objective function in Dual LPP.

8. Co-efficient of decision variables in each constraints : Transverse matrix of Primal LPP is applicable to the co-efficient of decision variables in each constraint for Dual LPP. Constraint type : Primal LPP Dual LPP Constraint type ≤ type Constraint type ≥ type Constraint type ≥ type Constraint type ≤ type Primal constraint “ i ” is = type Dual variable “ Yj ” unrestricted in sign Primal variable “ Xi ” unrestricted in sign Dual constraint “ j ” is = type

9. Relationship between solutions of Primal and Dual Values for the non-basic variables of the Primal are given by the base raw of th e Dual solution, under the slack variables (if any) neglecting the –ve sign if any and under the artificial variables neglecting –ve sign as well as deleting M. Values of sack variables of the Primal are given by the base row under the non-basic variables of the Dual solution neglecting the –ve sign if any. The values of the objective function is same for Primal and Dual problem.

10. Example Primal : Dual :

11. THANK YOU