Duality: Introduction

[Home Page]  [Back]  [Content of Contributions]  [Movement: Green Leaf World]

 

Introduction

Every linear programming problem has an mirror image based on the same data. The original problem is called Primal Problem and the other is called Dual Problem. Although, any one of the problems can be considered as primal and other as dual. The format of the simplex method is such that when the primal problem is solved, the dual of the problem is also solved. We can say, if the optimum solution to any one of the problem (either primal or dual) is known, the optimum solution of the other problem is readily available.

Formulation of Dual Problem

1. If the objective function in the primal problem is to be maximized, then the objective function is to be minimized in the dual problem and vice-versa.
   
2. Cj values will appear in the R.H.S of the constraints(bi) of the dual problem.
3. R.H.S constants(bi) of the constraints of the primal problem will appear as the Cj values in the dual problem.
4. Number of decision variables in the primal problem is equals to the number of constraints in the dual problem and number of constraints in the primal problem is equals to the number of decision variables in the dual problem. If there are n variables and m inequalities(ignoring non-negativity constraints ), then there are m variables and n n inequalities in the dual problem.
   
5. If the inequalities are of <= type in the primal problem, then that will be >= in the dual problem and vice-versa.
   
6. The matrix a in the primal problem will be transposed(row & column interchanged) in the dual problem.

 

Interpretation of Primal-Dual Optimum Solution

Once the dual problem has been formulated and solved the next vital step is to interpret the optimum solution of the primal problem from the solution of the dual problem. The solution values of the primal problem can be read directly from the optimum solution table of the dual as follows,

1. Locate the slack/ surplus variables in the dual problem. These are the primal basic variables in the optimum solution.
2. Read the values of the elements in the index row corresponding to the columns of the slack/ surplus variables with changed sign. This directly gives the optimum values of the basic primal variables.
3. Values of the slack variables of the primal problem are given by the index row under non-basic variables of the dual solution with changed sign.
4. The value of the objective function is same fro primal and dual problem.
   

Characteristic of Dual Problem

Major characteristics of the dual problem are as follows:

1. Dual of dual is the primal problem.
2. If the primal has a solution, then the dual has also the same solution and vice-versa.
3. If any of the two problems has only an infeasible solution, then the value of the objective function of the other is unbounded. 
4. If any of the two problems has unbounded solution, then the solution of the other is infeasible.
   
5. The value of the objective function for any feasible solution of the primal is less than the value of the objective function for any feasible solution of the dual.
6. If the primal has a feasible solution but the dual does not have, then the primal will not have a finite optimum solution and vice-versa.
   

Advantages of Duality

1. Computational procedure can be reduced significantly by converting it into dual when the primal problem has large number of constraints and smaller number of variables.
2. Solution of the dual checks the accuracy of the primal solution for computational errors.
3. Economic interpretation of the dual helps the management in making future decision.
4. Indicates that fairly fairly close relationship exist between linear programming and duality.
   

Example: Formulation of Dual Problem

Consider the given problem(Primal):

Minimize Z= 6000x1 + 4000x2

Subject to,

 4x1 +   x2 >= 12

 9x1 +   x2 >= 20

 7x1 +  3x2 >= 18

10x1 + 40x2 >= 40

     x1, x2 >= 0

There are 4 constraints, so, there will be four variables in the dual problem, say y1, y2, y3 & y4.

Formulation of the objective function:

By analyzing the facts,

1. R.H.S(bi) of the constraints of the primal problem are 12, 20, 18 & 40. So, Cj will be {12, 20, 18 & 40} and
2. The objective function of the primal problem is of the type minimize, so the objective function of the dual will be of the type maximize.
   

Thus, the objective function of the dual will be 

Maximize Z*= 12y1 + 20y2 + 18y3 + 40y4

Formulation of the constraints:

 

Construction of Constraint 1: 

• Coefficients of x1 in the constraints of the primal problem are 4, 9, 7, 10 which will be the coefficient of y1, y2, y3 & y4 respectively and 
• coefficient of x1 in the objective function of the primal problem is 6000 which will be R.H.S of the constraint and 
• The inequalities are of the type >= in the primal problem, so, the inequalities will have <= type.
  

Thus, first constraint will be

4y1 + 9y2 + 7y3 + 10y4 <= 6000

Construction of Constraint 2: 

• Coefficients of x2 in the constraints of the primal problem are 1, 1, 3, 40 which will be the coefficient of y1, y2, y3 & y4 respectively and 
• coefficient of x2 in the objective function of the primal problem is 4000 which will be R.H.S of the constraint and 
• The inequalities are of the type >= in the primal problem, so, the inequalities will have <= type.
  

Thus, first constraint will be

y1 + y2 + 3y3 + 40y4 <= 4000

 

So, the dual of the given problem is

 

Maximize Z*= 12y1 + 20y2 + 18y3 + 40y4

Subject to,

4y1 + 9y2 + 7y3 + 10y4 <= 6000

 y1 +  y2 + 3y3 + 40y4 <= 4000

        y1, y2, y3, y4 >= 0

Note that, if there are two types (<= & >=) of inequalities then all the constraints must be represented homogeneously, i.e. only <= or only >= types. Multiply any in-equation by (-1) having different type for this purpose.

Class Work (Do Now)

a) Solve the primal problem using simplex method

b) Solve the dual problem using simplex method