Question

Problem 2: (This is from Problems 4 and 5. Page 172 of the textbook) (a) Use Phase I Simplex Algorithm to find an initial basic feasible solution. Next, use the Simplex Tableau Method to solve this problem. Show that if ties are broken in favor of lower-numbered rows, then cycling occurs when the Simplex method is used to solve the following LP: max z-3x1 +x2 - 6x3 9x1 x2 -9x3 -2 x40 xi + (1/3)X2 - 2x3 - (1/3)X0 9x1 2 9x3 + 2x41 x20 VI-14 (b) Show that if Bland's Rule to prevent cycling is applied to this problem, then cycling does not occur.

Answer 1

Given data max z = -3x_1 + x_2-6x_3 9x_1 + x_2-9x_3-2x_4 lessthanorequalto 0 x_1 + (1/3) x_2 -2x_3- (1/3) x_4 lessthanorequalto 0 -9x_1-x_2 + 9x_3 + 2x_1 lessthanorequalto 1 x_1 greaterthanorequalto 0 forall I = 1, ....4 now, adding slack, surplus variable where reduced we get: max z = -3x_1 + x_2-6x_3 + 0 (x_4 + x_3 + x_6 + x_7) subject to 9x_1 + x_2-9x_3-2x_4 + x_5 = 0 x_1 - (1/3) x_2 -2x_3- (1/3) (x_4) + x_6 = 0 -9x_1-x_2 + 9x_3 + 2x_4 - x_4 = 1 \r\n simple x table -3 1 -6 0 0 0 0 base c_0 p_0 p_1 p_2 p_3 p_4 p_5 p_6 p_7 p_5 0 0 9 1 -9 -2 1 0 0 p_6 0 0 1 1/3 -2 -1/3 0 1 0 p_7 0 1 9 -1 9 2 0 0