Duality, Operation Research

For every LP formulation there exists another unique linear programming formulation called the 'Dual' (the original formulation is called the 'Primal'). Same data can be used for both 'Dual' and 'Primal' formulation.  Both can be solved in a similar manner as the Dual is also an LP formulation.

The Dual can be considered as the 'inverse' of the Primal in every respect. The column coefficients in the Primal constraints become the row co-efficients in the Dual constraints. The coefficients in the Primal objective function become the right-hand-side constraints in the Dual constraints. The column of constants on the right hand side of the Primal constraints becomes the row of coefficients of the dual objective function. The direction of the inequalities are reversed. If the primal objective function is a 'Maximization' function then the dual objective function is a 'Minimization' function and vice versa.

 Example 

Consider the following 'Primal' LP formulation.

Maximize   12x1 + 10x2

subject to         2x1 +   3x2  <  18

                       2x1 +    x2   <  14

                             x1, x >    0

The 'Dual' formulation for this problem would be

Minimize      18y1 + 14y2

subject to   2y1 +   2y2    > 12

                   3y1 + y2    > 10

                   y1 > 0,  y2  >  0

Note the following:

  1. The column coefficient in the Primal constraint namely (2,2) and (3,1) have become the row coefficient in the Dual constraints.

  2. The coefficient of the Primal objective function namely, 12 and 10 have become the constants in the right-hand-side of the Dual constraints.

  3. The constants of the Primal constraints, namely 18 and 14, have become the coefficient in the Dual objective function.

  4. The direction of the inequalities have been reversed. The Primal constraints have the inequalities of < while the Dual constraints have the inequalities of >.

  5. While the Primal is a 'Maximization' problem the Dual is a 'Minimization' problem and vice versa.              

Posted Date: 9/13/2012 9:05:19 AM | Location : United States







Related Discussions:- Duality, Assignment Help, Ask Question on Duality, Get Answer, Expert's Help, Duality Discussions

Write discussion on Duality
Your posts are moderated
Related Questions
Solve the following Linear Programming Problem using Simple method. Maximize Z= 3x1 + 2X2 Subject to the constraints: X1+ X2 = 4 X1 - X2 = 2 X1, X2 = 0

Demerits  of Range a.It gives  importance  to the  two  extreme  values and is very much affected by the extreme items. b.The range  provides  no information  about the  st

Deriving the Solution from the Model: This phase is devoted to the computation of those value of decision variables that maximize or minimize the objective function. Such

#A paper mill produces two grades of paper viz., X and Y. Because of raw material restrictions, it cannot produce more than 400 tons of grade X paper and 300 tons of grade Y paper

Show simple vapour compression Refrigeration cycle with showing all the devices and also draw T-sand P-R diagram and illustrate it also. A Bell-Coleman cycle works between 1 bar

The systematic methodology developed for an operation research study with problems involving conflicting multiple objective policies and alternatives. Operation research in

A paper mill produces two grades of paper viz., X and Y. Because of raw material restrictions, it cannot produce more than 400 tons of grade X paper and 300 tons of grade Y paper i

A paper mill produces two grades of paper viz., X and Y. Because of raw material restrictions, it cannot produce more than 400 tons of grade X paper and 300 tons of grade Y paper i

QUESTION 1 Change strategies and OD intervention techniques follow from diagnosis. An inappropriate intervention due to a faulty diagnosis may be very costly to an organization

mile-high microbrewery makes a light beer and a dark beer. mile-high has a limited supply of barley, limited bottling capacity, and a limited market for light beer. profits are $0.