Question

Consider the following linear programming problem.

Maximize 5X1 + 3X2 Subject to: X1 + X2 ≤ 20 X1 ≥ 5 X2 ≤ 10 X1, X2 ≥ 0

What are the optimal values of X1 and X2 respectively?

Answer 1

Solution: Problem is Max Z = 5x1 + 3X2 subject to X1 + X2 s 20 Xi 25 X2<10 and x1, x2 = 0; 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'>' we should subtract surplus variable S, and add artificial variable 4, 3. As the constraint-3 is of type's' we should add slack variable S; After introducing slack,surplus,artificial variables Max Z = 5x1 + 3x2 + 05, + 0S2 + 0S3 - M41 subject to X1 + X2 + $i = 20 Xi - S2 + 4, = 5 X2 + 5z = 10 and x1,x2, S1, S2, S3, 4,20

Iteration-1 MinRatio 1 = 20 Z= -5M Z;- ; - M-51 Negative minimum z- CIS - M - 5 and its column index is 1. So, the entering variable is x - Minimum ratio is 5 and its row index is 2. So, the leaving basis variable is A1 · The pivot element is 1. Entering = x], Departing = 4], Key Element = 1

+ Rz(new) = Rz(old) + R(new) = R. (old) - Rz (new) + R3(new) = R3(old) Iteration 2 530 MinRatio B CB = 15 X Sz Z = 25 5 5 100-1 0 100 1001 - 2; 500- 50 Z;-0 0 -3 0 -59 0

Negative minimum 2; -; is - 5 and its column index is 4. So, the entering variable is S2 Minimum ratio is 15 and its row index is 1. So, the leaving basis variable is $1. · The pivot element is 1. Entering = 52, Departing = Si, Key Element = 1 + R, (new) = R(old) + Rz(new) = Rz(old) + R(new) + Rz(new) = R3(old) Iteration-3 3 B xz MinRatio S2 Z = 100 Z; - Z-c; 0 Activate Windows

Since all Z:-C;20 Hence, optimal solution is arrived with value of variables as: X 1 = 20,X2 = 0 Max Z = 100

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

Thank You !