Question

MAX 100X1 + 120X2 + 150X3 + 125X4 Subject to X1 + 2X2 + 2X3 + 2X4 s 108 X1 + 5X2 + X4 s 120 X1 + X3 = 25 X2 + X3 + X4 2 50 X1, X2, X3, X420 Using the simplex method, provide the solution

Answer 1

Solution: Problem is Max Z = 100 x1 + 120X2 + 150x3 + 125x4 subject to X1 + 2X2 + 2x3 + 2x4 < 108 X1 + 5x2 + X4S 120 *1 + x3 =25 X2 + x3 + x4250 and x1,x2,43,44 20; The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate 1. As the constraint-1 is of type's' we should add slack variable Si 2. As the constraint-2 is of type's' we should add slack variables, 3. As the constraint-3 is of type's' we should add slack variable S 4. As the constraint-4 is of type'>' we should subtract surplus variable S4 and add artificial variable A1 After introducing slack,surplus,artificial variables Max Z = 100X1 + 120x2 + 150x3 + 125x4 + 0S1 + 0 S2 + 0 S3 + 054 - MA subject to X1 + 2X2 + 2x3 + 2x4 + Si = 108 X] + 5x2 + x4 + S2 X + x3 + S3 = 25 x2 + x3 + x4 -S4 + 41 = 50 and X1, X2, X3, X4, S1, S2. S3, S4,4120 = 120 Iteration-1 ci 100 120 150 125 0000-M MinRatio xH S S S S4, 100 1 | 0 | 0 Z= -50M -M -M -M 0 -100 00 00 Z;-C; -M-120 -M - 150† -M-125 O

Negative minimum 2;-C; IS - M - 150 and its column index is 3. So, the entering variable is X3. Minimum ratio is 25 and its row index is 3. So, the leaving basis variable is S. : The pivot element is 1. Entering = x3, Departing = S3, Key Element = 1 + R3(new) = Rz(old) + R (new) = R (old) - 2Rz(new) + R2(new) = R2(old) + R_(new) = R (old) - R3(new) Iteration-2 C 100 0 0 0 MinRatio ss. S4, to -2 00 5 = 29 1 0 0 0 0 120 – 120 X3 150 00 25 -1 1 0 -1 -1 25 = 25 - Z= - 25M + 3750 2; M+ 150 -M 150 | 0 0 M + 150 M -M Z;-C; M+50 -M-120 0 -M-125 1 M+ 150

Negative minimum Z; -Cis-M - 125 and its column index is 4. So, the entering variable is X4- Minimum ratio is 25 and its row index is 4. So, the leaving basis variable is 4. .. The pivot element is 1. Entering = x4, Departing = A1, Key Element = 1 + R (new) = R (old) + R, (new) = R, (old) - 2R, (new) + R2(new) = RZ (old) - R.(new) + Rz(new) = Rz(old) Iteration-3 C 100 120 150 125 0 0 0 MinRatio lo NI. 24 0 TO 150 125 0001 1 0 0 -1 -1 125 0 0 25 -125 000 25 -125 Z = 6875 | 1 0 2; 25 125 150 2;-C; -7550 Negative minimum 2;-C; is - 125 and its column index is 8. So, the entering variable is 54- Minimum ratio is 4 and its row index is 1. So, the leaving basis variable is S. ... The pivot element is 2. Entering = 54, Departing = Si, Key Element = 2 + R, (new) = R(old) = 2 + Rz(new) = R, (old) - R, (new) + R3(new) = R3(old) + R (new) = R (old) + R, (new) Iteration-4 100 120 150 1250 10 10 10 X2 X3 X4 S S2 S3 S4 MinRatio XB 104 (0.5) 1000 0. 50 0 1 05-8- 0 O -0. 51 05 – 60.6667 1 0 Oo 0. 50 1 125 Z = 7375 125 62.5 Z;-C; -12.51 5 O 62.5 10

Negative minimum Z;-C; is - 12.5 and its column index is 1. So, the entering variable is X1. Minimum ratio is 8 and its row index is 1. So, the leaving basis variable is S. .: The pivot element is 0.5. Entering = x1, Departing = S4, Key Element = 0.5 + R, (new) = R, (old) = 0.5 + R,(new) = R2(old) - 1.5R (new) + Rz(new) = R3(old) - R, (new) + R, (new) = R.(old) + 0.5R(new) Iteration-5 C; 100 120 150 1250 0 0 В MinRatio 125 79 0400 -2 1 1 - 3 12 ooio -1 1 -2 | 3 3 0 0 1 0 - 1 2; 100125 125 75 25 25 Z;- CO5 00 75 02525 Z = 7475 Since all Z;-C;20 Hence, optimal solution is arrived with value of variables as x1 = 8.x2 = 0, X3 = 17.x4 = 33 Max Z = 7475