2
$\begingroup$

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$
  • $\begingroup$ If there are 2 distinct points in a space , for which the LPP is optimum, then all the points on the line joining the points and in between them , will serve as a optimum solution. $\endgroup$ – Qwerty Jul 23 '16 at 18:58
  • $\begingroup$ Hi and welcome to the site. Please consider learning LaTeX / mathjax typesetting. It will make questions and answers more readable by all participants. I assumed the $S_1$ and $S_2$ are slack variables. Is this the case? $\endgroup$ – mathreadler Jul 23 '16 at 19:45
2
$\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$
  • $\begingroup$ I edited my question for more details $\endgroup$ – Ezazel Jul 23 '16 at 19:37

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.