Page 94 - DCOM303_DMGT504_OPERATION_RESEARCH

Unit 4: Linear Programming – Duality

Notes
Example 3: Write the dual of the following problem. Show that the optimal solution for
primal and dual are same.
Minimise ‘Z’ = 4x + 3x + 6x
1 2 3
Subject to x + x  2
1 3
x + x  5
2 3
x , x , x  0
1 2 3
Solution:
The dual for the given problem can be written as
Maximise Z = 2y + 5y
1 2
 1 0 1 
A   
 0 1 1 
Subject to y  4
1
y  3
2
y + y  6
1 2
 1 0 
 
| 0 1
A =  
 1 1 
 
y , y  0
1 2
Let us use simple technique to obtain the optimum solution.
Maximise ‘Z’ = 2y + 5y
1 2
Subject to y + y = 4
1 3
y + y = 3
2 4
y + y + y = 6
1 2 5
 
  
 
 
Where, y , y and y are slack variables.
3 4 5
BV CB XB Y1 Y2 S1 S2 S3 Min. Ratio
S1 0 4 1 0 1 0 0 –
S2 0 3 0 1 0 1 0 3/1 = 3 (KR) ?
S3 0 6 1 1 0 0 1 6/1 = 6
ZJ 0 0 0 0 0
CJ 2 5 0 0 0
ZJ – CJ –2 –5 0 0 0
( KC)

LOVELY PROFESSIONAL UNIVERSITY 89