# Finding $a$ for a Degenerate BFS in Given System of Restrictions

• MHB
• evinda
In summary, the conversation discusses the concept of degenerate basic feasible solutions in a system of restrictions. A degenerate basic feasible solution is a basic feasible solution with less than $m$ non-zero components. The conversation also mentions that a degenerate basic feasible solution is equivalent to having an equation with a right-hand-side of zero or having 3 boundary conditions that intersect in the same feasible point. The participants discuss different methods for finding a degenerate basic feasible solution, such as making a drawing or running the simplex method. They also mention that in order to find all possible values of $a$ for which there is a degenerate basic feasible solution, one must continue the algorithm by choosing different pivots until all possibilities are exhausted.
I like Serena said:
It shouldn't be feasible since it corresponds to the intersection of the red line (non-basic variable $P_4$) and the green line (non-basic variable $P_5$).

When $a > \frac 32$ that intersection should have either $x_2 < 0$ or $x_1 < 0$.

So have I done something wrong at the calculations? (Thinking)Which $a$ did you pick to draw the third inequality?

evinda said:
So have I done something wrong at the calculations? (Thinking)Which $a$ did you pick to draw the third inequality?

I picked $a=3$.
Oh wait. (Wait)
It's the intersection of the blue line (non-basic variable $P_4$) and the green line (non-basic variable $P_5$).

I like Serena said:
It's the intersection of the blue line (non-basic variable $P_4$) and the green line (non-basic variable $P_5$).

So we have to continue the algorithm, picking either the column $P_4$ or the column $P_5$, right?

If we choose $P_4$ to get in the basis we have to distinguish the cases:

• $a \leq 2$ and
• $a>2$

Right? (Thinking)

I like Serena said:
One way to find it, is to make a drawing, which will reveal where and when degeneracy can happen.
Could you explain further to me how we can find from a drawing all the possible degenerate basic feasible solution although we don't have a specific value of $a$ ? (Thinking)

evinda said:
Could you explain further to me how we can find from a drawing all the possible degenerate basic feasible solution although we don't have a specific value of $a$ ? (Thinking)

Every point on the boundary of the feasible region where 3 or more lines intersect is a degenerate basic feasible solution.
When we get to such a point with the simplex method, we won't be able to tell in which direction to continue. (Nerd)

This is already the case in $(0,2)$, although it still depends on $a$ whether that is actually a feasible solution.
Actually, for $a=0$ we would also get degenerate basic feasible solutions. (Nerd)

I like Serena said:
Every point on the boundary of the feasible region where 3 or more lines intersect is a degenerate basic feasible solution.

Why is it like that? (Thinking)

I like Serena said:
When we get to such a point with the simplex method, we won't be able to tell in which direction to continue. (Nerd)

You mean that there will be more than one possibilities to check? (Thinking)

I like Serena said:
This is already the case in $(0,2)$, although it still depends on $a$ whether that is actually a feasible solution.
Actually, for $a=0$ we would also get degenerate basic feasible solutions. (Nerd)

How do we find $(0,2)$ ?

Also if we pick a specific $a$ and find the points on the boundary will we find all the possible degenerate basic feasible solutions?
i.e. if we pick a different one will we find the same points? (Thinking)

evinda said:
So we have to continue the algorithm, picking either the column $P_4$ or the column $P_5$, right?

If we pick $P_4$ to get in the basis, then if $a \leq 3$ $P_2$ will get out of the basis. Otherwise $P_3$ gets out of the basis. Right? (Thinking)

Replies
6
Views
941
Replies
4
Views
2K
Replies
28
Views
4K
Replies
3
Views
1K
Replies
32
Views
5K
Replies
1
Views
1K
Replies
12
Views
3K
Replies
3
Views
1K
Replies
2
Views
2K
Replies
2
Views
1K