3

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$.

mathreadler
  • 25,824
Panagiotis
  • 151
  • 1
    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. – Qwerty Jul 23 '16 at 18:58
  • 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? – mathreadler Jul 23 '16 at 19:45

2 Answers2

3

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.

Dietrich Burde
  • 130,978
0

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

Kemei Kimutai
  • 1