Solutions 56:171 Operations Research Homework #3 Solutions – Fall 2002 1. Revised Simplex Method Consider the LP problem Maximize subject to z = 3 x1 − x2 + 2 x3 x1 + x2 + x3 ≤ 15 2 x1 − x2 + x3 ≤ 2 − x1 + x2 + x3 ≤ 4 x j ≥ 0, j = 1, 2,3 a. Let x4 , x5 , &, x6 denote the slack variables for the three constraints, and write the LP with equality constraints. Answer: Maximize z = 3 x1 − x2 + 2 x3 subject to x1 + x2 + x3 + x4 = 15 2 x1 − x2 + x3 + x5 = 2 − x1 + x2 + x3 + x6 = 4 x j ≥ 0, j = 1, 2,3, 4,5, 6 After several iterations of the revised simplex method, 1 0  the basis B={4,3,2} and the basis inverse matrix is ( AB ) −1 =  0 1 2  0 − 1   2 −1   1 . 2 1   2

b. Proceed with one iteration of the revised simplex method, by i. Computing the simplex multiplier vector π Answer: 1 0 −1    B −1 0 1 1  =  0, 3 , 1  π = CB ( A ) = [0 2 −1] 2 2  2 2  0 − 1 1    2 2  = [ 0, 1.5, 0.5] ii. “pricing”, i.e., computing the “relative profits”, of the non-basic columns. Answer:

56:171 O.R. -- HW #3 Solutions

Fall 2002

page 1 of 8

Solutions  1 0 0 C = [3 0 0 ] , A =  2 1 0     −1 0 1    N N N −3 −1  C = C −π A =  1 2 2  2 The relative profits for non-basic variables are C1 = 0.5 , C5 = −1.5 , C6 = −0.5 . iii. Selecting the column to enter the basis. Answer: Only the relative profit of X 1 is positive and the problem is Max problem, and so X 1 should enter the basic. iv. Computing the substitution rates of the entering column. Answer: The substitution rates of the entering variable X 1 is
N N

1 0 −1   1   2      B −1 0 1 1  2  = 1  α = ( A ) A1 = 2 2    2   0 − 1   1   −1  − 3    2 2 2     v. Select the variable to leave the basis. Answer: 11 The current right-hand-side is β = X B = ( A ) b =  3  and the ratios (right-hand-side over   1  
B −1

5.5 positive substitution rates) are  6