0

Is there a method to algebraically determine if an extreme point is degenerate? Can someone please explain to me.

Here's my example: $$\max x + 2y $$

subject to, \begin{align} x - 4y &\leqslant 4 \\ -2x +y &\leqslant 2 \\ -3x +4y &\leqslant 12 \\ 2x + y &\leqslant 8 \\ x, y &\geqslant 0 \end{align} And you find your extreme points $(0,0), (4,0), (20/11, 48/11), (4/5, 18/5)$ and $(0,2)$. I know the optimal point is $(20/11, 48/11)$, but how can I determine if any of these points are degenerate without the graphs? thank you.

WA Don
  • 4,488
norma
  • 3

1 Answers1

0

Substitue those points in the inequalities and see how many are active. If exactly one pair of them is active, then it is not degenerate. For example $(0,0)$ only make $x \ge 0$ and $y \ge 0$ active. It is not degenerate.

Otherwise, if you can find more than two constraints. Verify if you can find two sets of two-constraints that are linearly independent. For example $(4,0)$ makes $x-4y \le 4$, $2x+y \le 8$ and $y \ge 0$ active. We can verify that $x-4y=4, 2x+y=8$ gives the solution uniquely. Also $x-4y=4$ and $y=0$ uniquely as well. It is degenerate.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • Hello! Thank you for the answer. By active do you mean like binding? I can see that now, and since this is two dimensional is that why its pairs of constraints? So if it was 3d it would three at a time, etc.? Also, what do you mean by the independence check, may you please tell? thank you so much!! – norma Jan 15 '21 at 23:43
  • yes, binding. For example, we check $x-4y=4, 2x+y=8$ gives a unique solution. Also $x-4y=4, y=0$ gives a unique solution. Hence it is degenerate. – Siong Thye Goh Jan 16 '21 at 03:00
  • Got it, thank you! – norma Jan 16 '21 at 16:53