$\begingroup$

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?

$\endgroup$

1 Answer

$\begingroup$

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.

$\endgroup$ 3

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy