Page 64 - DCOM303_DMGT504_OPERATION_RESEARCH

Unit 3: Linear Programming Problem – Simplex Method

Notes
Example:
Minimise ‘Z’ = – 10x – 12x – 15x [Subject to constraints]
1 2 3
0.10x + 12x + 0.15x  36
1 2 3
0.06x + 0.05x + 0.09x  30
1 2 3
0.18x + x + 0.07x  37
1 2 3
0.13x + 0.10x + 0.08x  38
1 2 3
x  200
1
x  100
2
x  180
3
Where, x , x , x  0 [Non-negativity constraints]
1 2 3
Solution:
Step 1: Conversion of minimization case into maximisation case.
Therefore, Maximise ‘Z’ = 10x + 12x + 15x [Subject to constraints]
1 2 3
Step 2: Convert the inequalities into equalities adding slack variables.

0.10x + 0.12x + 0.15x + x = 36
1 2 3 4
0.06x + 0.05x + 0.09x + x = 30
1 2 3 5
0.18x + x + 0.07x + x = 37
1 2 3 6
0.13x + 0.10x + 0.08x + x = 38
1 2 3 7
x + x = 200
1 8
x + x = 100
2 9
x + x = 180
3 10
Where, x , x , x , x , x , x and x are slack variables.
4 5 6 7 8 9 10
Step 3: Fit the data into matrix form.
 x 
 Y 1 Y 2 Y 3 S 1 S 2 S 3 S 4 S 5 S 6 S 7   1 
 x x x x x x x x x x   x 2 
 1 2 3 4 5 6 7 8 9 10   x   36 
 0.10 0.12 0.15 1 0 0 0 0 0 0   3   30 
   x 4   
 0.06 0.05 0.09 0 1 0 0 0 0 0   x   37  


A  0.18 1 0.07 0 0 1 0 0 0 0  X   5   B  200 

   x 6 
 0.13 0.10 0.08 0 0 0 1 0 0 0     200 
 1 0 0 0 0 0 0 1 0 0   x 7   
   x   100 
 0 1 0 0 0 0 0 0 1 0   8    180  
   x 9 
 0 0 1 0 0 0 0 0 0 1   
 x 10 

LOVELY PROFESSIONAL UNIVERSITY 59