Page 70 - DCOM303_DMGT504_OPERATION_RESEARCH

Unit 3: Linear Programming Problem – Simplex Method

Therefore, Maximize Z = C X Notes
B B
= (–4 × 2) + (–3 × 1)
= –8 – 3
= –11

Therefore, Minimize Z = 11

Example:

Minimise ‘Z’ = 3x + 5x [Subject to constraints]
1 2
2x + 8x  40
1 2
3x + 4x  50
1 2
x , x  0 [Non-negativity constraints]
1 2
Solution:
Step 1: Convert the above minimization case into maximisation case.
Therefore, Maximise Z = –3x – 5x
1 2
Step 2: Convert the inequalities into equalities adding slack variables and artificial variables.

2x + 8x – x + x = 40
1 2 3 5
3x + 4x – x + x = 50
1 2 4 6
Where, x & x are surplus variables and x and x are artificial variables.
3 4 5 6
Step 3: Bring the objective function into a standard form.

Maximise ‘Z’ = – 3x – 5x – 0x + 0x – Mx – Mx
1 2 3 4 5 6
Step 4: Fit the data into a matrix form.
 x 1 
 
 y 1 y 2 S 1 S 2 a 1 a 2   x 2 
 x x x x x x   x   40 
A   1 2 3 4 5 6  X   3   B   
 2 8 1 0 1 0   x 4   50 
     
 3 4 0 1 0 1   x 5 
 
 x 6 

Step 5: First iteration of Simplex Method.

BV CB XB y1 y2 S1 S2 a1 a2 Min. Ratio
a1 –M 40 2 8 –1 0 1 0 40/8 = 5 (KR)
a2 –M 50 3 4 0 –1 0 1 50/4 = 12.5
Zj –5M –12M
Cj –3 –5
Zj – Cj –5M + 3 12M + 5

Therefore, Z = C X
B B
= (40x – M) + (50x – M)

LOVELY PROFESSIONAL UNIVERSITY 65