Page 62 - DCOM303_DMGT504_OPERATION_RESEARCH

Unit 3: Linear Programming Problem – Simplex Method

Step 6: Third iteration of Simplex Method. Notes
BV CB XB Y1 Y2 S1 S2 S3 Min.
Ratio
y2 2 3.33 – 2(–0.33) = 3.99 –0.33 – 1(–0.33) = 0 1 – – – –
y1 1 2.67/1.35 = 2 1.33/1.33 = 1 0 – – – –
S3 0 5.33 – 2(0.67) = 3.99 0.67 – 1(0.67) = 0 0 – – – –
Zj 1 2 –
Cj 1 2
Zj – Cj 0 0 – –

Max. Z = C X
B B
= (2 × 3.99) + (1 × 2) + (0 × 3.99)
= 7.98 + 2 + 0
= .98

Therefore, min. Z = –9.98

Example:
Minimise ‘Z’ = – x – 3x + 2x [Subject to constraints]
1 2 3
3x – x + 3x  7
1 2 3
– 2x + 4x  12
1 2
– 4x + 3x + 8x  10
1 2 3
Where, x , x , x  0 [Non-negativity constraints]
1 2 3
Solution:
Step 1: Conversion of the minimization case into maximisation case.

Therefore, Maximise Z = – x + 3x – 2x [Subject to constraints]
1 2 2
Step 2: Convert of the inequalities into equalities by adding slack variables.
Therefore, 3x – x + 3x + x = 7
1 2 3 4
– 2x + 4x + x = 12
1 2 5
– 4x + 3x + 8x + x = 10
1 2 3 6
Where, x , x and x are slack variables.
4 5 6
Step 3: Fit the data into matrix form.
 x 
 Y 1 Y 2 Y 3 S 1 S 2 S 3   1 
   x 2 
7
 x 1 x 2 x 3 x 4 x 5 x   x   
 
A   3 1 3 1 0 0  X   3   B  1
 
   x 4   
0
 2 4 0 0 1 0   x   
 4 3 8 0 0 1   5 
   
 x 6 

LOVELY PROFESSIONAL UNIVERSITY 57