Suppose that for a certain LP no basic feasible solution is degenerate. Does it follow that this LP has a unique optimal solution?

Question

I was wondering if the following is true. Suppose that for a certain LP no basic feasible solution is degenerate. Does it follow that this LP has a unique optimal solution?

Answer 1

The answer is no: a simple counterexample is \begin{equation} \begin{array}{rl} \max\ & x_1 \\ \text{s.t.}\ & x_1 \leqslant 1 \\ & x_2 \leqslant 1 \\ & x_1,x_2\geqslant 0 \end{array} \end{equation}

You object that the solution $(0,0)$ is degenerate, but in fact it is not. Try reviewing the definitions of basic solution and degenerate solution.

(If it really bothers you, you could easily shift the feasible region of my example:\begin{equation} \begin{array}{rl} \max\ & x_1 \\ \text{s.t.}\ & x_1 \leqslant 2 \\ & x_2 \leqslant 2 \\ & x_1,x_2\geqslant 1 \end{array} \end{equation} and the "problem" goes away.)