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.


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
In your role as a Consultant to a renowned organisation or institution, you have been asked to design and submit a research proposal to examine the future sustainability of its bus

Chi Square Test for Independence  of Attribute The chi square  test  can be  used to find out  whether two  or more attributes are associated or not. This  test helps  in fin

we have three reservoirs with daily supplies of15, 20 and 25 litres of fresh water respectively. on each day we must supply four cities A B C D whose demands are 8 10 12 and 15 res

Classification of documents by information Characteristics: The schemes of classification advocated by Hanson and Grogan are mainly based on the information characteristics of

How do I set this problem up for Excel: A National Credit Union has $250,000 available to invest in a 12 month commitment. The money can be placed in Treasury notes yielding an 8%

Determination of effectiveness Measures: Effectiveness measure is a measure of success of a model in representing a problem and providing a solution. It is the connecting link

In a big industry the numbers of factors influencing a decision have increased situation has become big and complex because these factors interact with each other in complica

Disadvantage  of standard Deviation It is not  easy  to understand  and calculate. It gives  more  weight  to the extremes  and less  to the items   nearer to mean. Since

solve the LPP using simple method, maximize z= 3x1+2x2 subject to constraints

1. Explain the effects that MIS, DSS, CRM and ERP have on organizational communication and decision making to increase productivity and efficiency in an increasingly competitive bu