Q1 [12 marks] In this exercise we show that an LP can have multiple optimal solutions. (a) [4 marks] Consider the linear program: max{cTx : Ax = b, x 2 0} where 1 0 0 1 1 oooo A = 01 0 1 b = C = 0 0 1 0 Find two distinct optimal solutions. Your need to justify the optimality of the two solutions you give. (b) [4 marks] Consider the linear program: max{c x : Ax = b, x 2 0} where 1 0 0 1 0 A = 0 1 0 01 0 0 1 0 0 Find an example of c for which both of the two basic feasible solutions (1 1 1 0 0) and (0 1 1 1 0) are optimal solutions. You need to justify the optimality of (1 1 1 0 0) and (0 1 1 10) given your choice of c. (c) [4 marks] Prove that if max{cx : Ax = b, x 2 0} has two distinct optmial solutions x(1) and x(2) then it has infinitely many optimal solutions. (hint: verify that Ax(1) + (1 - A)x(2) is an optimal solution for any > E [0, 1].)