Page 92 - DCOM303_DMGT504_OPERATION_RESEARCH

Unit 4: Linear Programming – Duality

Notes
!
Caution The necessary and sufficient condition for any LPP and its dual to have optimal
solutions is that both have feasible solutions.

4.2 Dual Formulation

The following procedure is adopted to convert primal problem into its dual. Simplex method is
applied to obtain the optimal solution for both primal and dual form.
Step 1: For each constraint, in primal problem there is an associated variable in the dual problem.

Step 2: The elements of right-hand side of the constraints will be taken as the coefficients of the
objective function in the dual problem.
Step 3: If the primal problem is maximization, then its dual problem will be minimization and
vice versa.
Step 4: The inequalities of the constraints should be interchanged from ³ to  and vice versa and
the variables in both the problems are non-negative.
Step 5: The rows of primal problem are changed to columns in the dual problem. In other words,
the matrix A of the primal problem will be changed to its transpose (A) for the dual problem.
Step 6: The coefficients of the objective function will be taken to the right hand side of the
constraints of the dual problem.

Example 1: Write the dual of the following problem.
Maximise ‘Z’ = –6x + 7x
1 2
Subject to, –x + 2x  –5
1 2
3x + 4x  7
1 2
x , x  0
1 2
Solution: The given problem is considered as primal linear programming problem. To convert
it into dual, the following procedure is adopted.
Step 1: There are 2 constraints and hence the dual problem will have 2 variables. Let us denote
them as y and y .
1 2
Step 2: The right hand side of the constraints are –5 and 7 which are taken as the coefficients of the
variables y and y in the objective function.
1 2
Step 3: The primal objective problem is maximization and hence the dual seeks minimization
for the objective function. Hence, the objective functions for the dual problem is given by
Minimise Z = –5y + 7y
1 2
Step 4: The inequalities of the constraints for the primal problem are of the type (). Hence, the
inequalities for the dual constraints will be of the type ().
Step 5: The coefficient matrix for the primal problem is

  1 2
A 
  3 4 

LOVELY PROFESSIONAL UNIVERSITY 87