2. [Degeneracy and Uniqueness]

(a) Consider the program (P)

min z = x2

subject to x2 = 1

x1; x2 >= 0;

i. Write the dual (D) of this problem.

ii. Put the dual into standard form.

iii. It is generally said that if one of the primal or dual has a basic

optimal solution, the other has a unique solution. Does this rule hold for these problems?

Is this rule true for these problems? Does (P) have a degenerate solution? a unique solution? Does (D) have a degenerate solution ? a unique solution ?

(b) Prove in the general case that if no optimal solution of the primal is

degenerate, then the dual has a unique solution.

(c) Is it true that the dual always has more than one solution when the primal has a degenerate optimal solution?