Page 93 - DCOM303_DMGT504_OPERATION_RESEARCH

Operations Research

Notes The transpose of this matrix which serves as the coefficient matrix for the dual problem is given
by.

  1 3
A   
 2 4
Step 6: The coefficients of the objective function for the given primal are –6 and 7. They are taken
on the right hand side of the constraints for the dual problem. Hence, the constraints for the dual
problem are represented as
–y + 3y  –6
1 2
2y + 4y  7
1 2
y , y  0
1 2
Example 2: Find the dual of the following problem:

Minimise Z = 3x + 4x + 5x
1 2 3
Subject to x + x  3
1 3
x + x  4
2 3
x ,x ,x  0
1 2 3
Solution: Let the given problem be denoted as primal. The objective of the primal is minimization
and hence the objective of the dual is maximization. There are two constraints for the primal
problem. Hence, the problem has 2 variables namely, y and y . The right hand side of the
1 2
constraints are 3 and 4 which are the coefficients for y and y in the objective function for the
1 2
dual problem given as
Maximise Z = 3y + 4y
1 2
The coefficient of the objective function in the primal problem are 3, 4 and 5 which serve as the
right hand side of the constraints for the dual problem. The inequalities of the constraints of the
type () are converted as () type for the dual problem. The coefficient matrix for primal problem
is
 1 0 1 
A   
 0 1 1 
And hence the coefficient matrix for the dual problem is
 1 0 

A 1  0 1 
 
 1 1 
 
Hence, the dual problem is represented as
Maximise ‘Z’ = 3y + 4y
1 2
Subject to
y + y  3 is y  3
1 2 1
y + y  4 y  4
1 2 2
y + y  5 y + y  5
1 2 1 2
y , y  0 y , y  0
1 2 1 2

88 LOVELY PROFESSIONAL UNIVERSITY