How can I determine if a solution in a linear programming problem is degenerate without I use any software or the graphical display of the solution;
For example in the model:
$$\max\{2x_1 + 4x_2\}\\\phantom{ aa}\\ \text{s.t.}\\\phantom{a}\\\begin{array}{rr} x_1 + 2x_2 & \leq 5\\ x_1 + x_2 & \leq 4\\ x_1 &\geq 0\\ x_2 &\geq 0 \end{array}$$
The variable $x_1$ takes the value $0$ but Ι think the solution is not degenerate. Specifically, the solution is $x_1 = 0$, $x_2 = 2.5$, $S_1 = 0$, $S_2 = 0$.
$\endgroup$ 22 Answers
$\begingroup$An Linear Programming is degenerate if in a basic feasible solution, one of the basic variables takes on a zero value. Degeneracy is caused by redundant constraint(s), e.g. see this example.
$\endgroup$ 1 $\begingroup$The above question is not degenerate since if you work out this by simplex method, $X_1$ is not a basic variable so it can take a value $>=0$. In the final tablue, the solution could be degenerate if either $X_2$ or $S_2$ was equal to 0
$\endgroup$
