Question

Exercise 1. Please use the simplex method to solve the below LP min 2=3.01 - 22 s.t. 2.c +228 2 + xy S5 21 - 22<4 2,220 a) Write the LP in standard form. b) Provide tableaus, BV, NBV, solution, objective value for each iteration of the simplex method. (Hint: the optimal value z=-5).

Answer 1

Min Z = 3x1 - x2 subject to 2X1 + X258 X1 + X255 Xi - X254 and X1, X220; 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 variable S, 3. As the constraint-3 is of type's' we should add slack variable Sz After introducing slack variables Min Z = 3x1 - x2 + 05, +0S2 + OS subject to 2x1 + x2 + S = 8 x1 + x2 + S2 = 5 X1 - X2 S3 = 4 and X1, X2, 51, 52, 5320 Iteration-1 c 3 -1 0 0 0 MinRatio хв B Св Х. X1 ܕX Si S, $ X2 8 Si 0 8 2 1 1 0 0 = $ 1 S; 0 in 1 (1) 0 1 0 S3 0 4 1 -1 0 0 1 Z = 0 0 0 0 0 0 zi Z;-C; -3 11 0 0 0

Positive maximum 2;-C, is 1 and its column index is 2. So, the entering variable is xz. Minimum ratio is 5 and its row index is 2. So, the leaving basis variable is S. :: The pivot element is 1. Entering = x2, Departing = S, Key Element = 1 + R, (new) = R(Old) + R(new) = R (old) - Rz(new) + R3(new) - R3(old) + Rz(new) Iteration-2 C 3 -1 0 0 0 B Св Хв Xi X2 Si S, S3 MinRatio Si 0 3 1 0 1 - 1 0 X2 - 1 5 1 1 0 0 1 1 SE 0 9 2 0 0 Z= -5 Z; -1 -1 0 -1 0 Z; - C; -4 0 0 -1 0 Since all Z; -C; SO Hence, optimal solution is arrived with value of variables as: *1 = 0, x2 = 5 Min Z= -5