Question 6 (6 + 6 = 12 marks)

Consider the following LP:

min z = -4x1 - x2 - 2x3

s.t. 6x1 + x2 + x3 8

8x1 + 3x2 + x3 12

x1 0, x2 0, x3 0

having the following final optimal Simplex tableau:

basic x1 x2 x3 s1 s2 rhs

z -8 -1 0 -2 0 -16

x3 6 1 1 1 0 8

s2 2 2 0 -1 1 4

where s1 and s2 are the slack variables for the first and second constraints, respectively.

(a) Suppose that a new decision variable x4 is introduced into the considered LPas shown below:

min z = -4x1 - x2 - 2x3 + 4x4s.t. 6x1 + x2 + x3 - 3x4 88x1 + 3x2 + x3 - 2x4 12x1 0, x2 0, x3 0, x4 0.

Please check whether the optimal solution to the original LP is still optimal

to the new LP. If not, please find an optimal solution to the new LP using the

above Simplex tableau.

(b) Suppose that a new constraint "2x1 + x2 + 2x3 6" is introduced into the

considered LP. Please check whether the optimal solution to the original LP

is still optimal to the new LP. If not, please find an optimal solution to the

new LP using the above Simplex tableau