Find the degenerate basic feasible solutions

Question

Find the degenerate basic feasible solutions for the polyhedron
$$x_1 + 4x_2 ≤ 8 ;$$ $$x_1 + 2x_2 ≤ 4 ;$$ $$x_1, x_2 ≥ 0.$$

Does degeneracy depend on the representation of the polyhedron?

Answer 1

Have you tried plotting your constraints and finding the solution(s) that have more active constraints than the number of variables? Since your problem is 2-dimensional this would be an easy way to find solutions you then can check.

As for your second question, yes! Degeneracy of a basic feasible solution does depend on the representation of the polyhedron. One example given in a Linear Optimization book by Dimitris Bertsimas is the following Polyhedron: $$ P=\{x \in \mathbb{R^3}: x_1-x_2 = 0, x_1+x_2+2x_3 = 2, \text{and } x_1,x_2,x_3 \geq 0 \} =\{x \in \mathbb{R^3}: x_1-x_2 = 0, x_1+x_2+2x_3 = 2, \text{and } x_1,x_3 \geq 0 \}. $$ The constraint $x_1-x_2=0$ gives us the possibility to remove the non-negativity constraint for $x_2$ in the first representation. For the first representation, the solution (0,0,1) is degenerate, but in the second representation it is not.