I understood that when plotting the feasible area there had to be an intersection with more than two lines.

In the case of:

$$\text{Max } z=2x_1+x_2$$ S.T $$ \begin{cases} 4x_1+3x_2\leq 12\\ 4x_1+x_2 \leq 8\\ 4x_1-x_2 \leq 8\\ x_1,x_2\geq 0 \end{cases} $$

The plot is which mean that there is almost intersection of the there functions, is it still degeneracy?


Edit: yes this LP admits degenerate solutions, e.g., $(x_1, x_2)=(2,0)$, since the constraints $4x_1+x_2 \leq 8, 4 x_1-x_2 \leq 8, x_2 \geq 0$ are all active at this point, and $3$ active constraints in a 2d space implies degeneracy.

  • $\begingroup$ But using simplex I get that a basic variable has a value of zero, so it is degenerate right? $\endgroup$ – newhere Apr 17 '19 at 19:27
  • $\begingroup$ Ah right, I missed the non-negativity constraints. Yes, $4x_1+x_2 \leq 8, 4 x_1-x_2 \leq 8, x_2 \geq 0$ are all active at $(x_1, x_2)=(2,0)$, so yes that point is degenerate. $\endgroup$ – Ryan Cory-Wright Apr 17 '19 at 20:44
  • $\begingroup$ But still there is no intersection of 3 or more lines $\endgroup$ – newhere Apr 18 '19 at 8:20
  • $\begingroup$ In your plot, don't $x=0, 4x+y=8, 4x-y=8$ intersect at the same point? $\endgroup$ – Ryan Cory-Wright Apr 18 '19 at 14:12

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.