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.
evinda
Gold Member
MHB
Hello! (Wave)

The following system of restrictions is given:$$x_1+ 2 x_2 \leq 4 \\ 2x_1+x_2 \leq 2 \\ x_1+a x_2 \leq 3 \\ x_1, x_2 \geq 0$$
For which values of $a$ is there a degenarate basic feasible solution?

I wrote the above system of restrictions in canonical form as follows:$$x_1+ 2 x_2 +x_3= 4 \\ 2x_1+x_2 +x_4= 2 \\ x_1+a x_2 + x_5= 3 \\ x_1, x_2 , x_3, x_4, x_5\geq 0$$$$A=\begin{bmatrix} 1 & 2 & 1 & 0 & 0\\ 2 & 1 & 0 & 1 & 0\\ 1 & a & 0 & 0 & 1 \end{bmatrix}$$

The order of $A$ is $3$.I thought that for example for $x_1=x_2=0$ we get the non-degenerate basic feasible solution $(0,0,4,2,3)$.
Do we have to find an other non-degenerate basic feasible solution with a common component as the above one so that their subtraction gives a degenerate basic feasible solution? (Thinking)
How can we find an appropriate $a$? (Thinking)

Hey evinda! (Smile)

What does it mean if we have a degenerate basic feasible solution? (Wondering)

I like Serena said:
Hey evinda! (Smile)

What does it mean if we have a degenerate basic feasible solution? (Wondering)

A non-degenare basic feasible solution is a basic feasible solution with exactly $r(A)=m$ non-zero components.

That's why I thought that a degenerate basic feasible solution is a basic feasible solution with less than $m$ non-zero components.

Am I wrong? (Thinking)

evinda said:
A non-degenare basic feasible solution is a basic feasible solution with exactly $r(A)=m$ non-zero components.

That's why I thought that a degenerate basic feasible solution is a basic feasible solution with less than $m$ non-zero components.

Am I wrong? (Thinking)

That is correct. (Nod)
Moreover, it is equivalent with having an equation that has a right-hand-side of zero.
And it is also equivalent with having 3 boundary conditions that intersect in the same feasible point. (Nerd)

One way to find it, is to make a drawing, which will reveal where and when degeneracy can happen.
Alternatively, I think we have to walk through all possible basic feasible solutions to see if any of them satisfies the criteria. (Sweating)

I like Serena said:
Moreover, it is equivalent with having an equation that has a right-hand-side of zero.
And it is also equivalent with having 3 boundary conditions that intersect in the same feasible point. (Nerd)

Could you explain it further to me? (Thinking)

I like Serena said:
One way to find it, is to make a drawing, which will reveal where and when degeneracy can happen.
If we make a drawing what $a$ do we pick?
I like Serena said:
Alternatively, I think we have to walk through all possible basic feasible solutions to see if any of them satisfies the criteria. (Sweating)

You mean that we run the simplex method till we find a possible degenerate basic feasible solution? (Thinking)

evinda said:
Could you explain it further to me? (Thinking)

If we make a drawing what $a$ do we pick?

You mean that we run the simplex method till we find a possible degenerate basic feasible solution? (Thinking)

Let's say both $a=1$ and $a=2$.
And yes, we can run the simplex method in different directions until we find a possible degenerate solution.

Let's get back to the explanation once we got something that looks like a degenerate basic feasible solution. (Thinking)

I like Serena said:
And yes, we can run the simplex method in different directions until we find a possible degenerate solution.
The first tableau is:

$\begin{matrix} B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta & \\ P_3 & 4 & 1 & 2 & 1 & 0 & 0 & 2 & L_1\\ P_4 & 2 & 2 & 1 & 0 & 1 & 0 & 2 & L_2\\ P_5 & 3 & 1 & a & 0 & 0 & 1 & \frac{3}{a} & L_3 \end{matrix}$

We choose $P_2$ to get in the basis and we assume that $a \neq 0$.

$$\theta_0=\min \{ 2,2, \frac{3}{a} \}=\frac{3}{a}$$

assuming that $\frac{3}{a} \leq 2$.

The pivot is the element $a$ and so $P_5$ gets out of the basis.

We get the following tableau:$\begin{matrix} B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta & \\ P_3 & 4-\frac{6}{a} & 1-\frac{2}{a} & 0 & 1 & 0 & -\frac{2}{a} & & L_1'=L_1-2L_3'\\ \\ P_4 & 2-\frac{3}{a} & 2-\frac{1}{a} & 0 & 0 & 1 & -\frac{1}{a} & & L_2'=L_2-L_3'\\ \\ P_2 & \frac{3}{a} & \frac{1}{a} & 1 & 0 & 0 & \frac{1}{a} & & L_3'=\frac{L_3}{a} \end{matrix}$

We have a degenerate basic feasible solution if $4-\frac{6}{a}=0$ or $2-\frac{3}{a}=0$.
Both of the above equalities give $a=\frac{3}{2}$.

But how can we find all $a$ s for which we have a degenerate basic feasible solution? (Thinking)

evinda said:
We have a degenerate basic feasible solution if $4-\frac{6}{a}=0$ or $2-\frac{3}{a}=0$.
Both of the above equalities give $a=\frac{3}{2}$.

But how can we find all $a$ s for which we have a degenerate basic feasible solution? (Thinking)

Good! (Nod)
To find all $a$ we to assume that either $a < \frac 32$ or $a > \frac 32$ and we need to keep going... (Sweating)

I like Serena said:
Good! (Nod)
To find all $a$ we to assume that either $a < \frac 32$ or $a > \frac 32$ and we need to keep going... (Sweating)

For $a> \frac{3}{2}$ we continue the algorithm.
We choose $P_5$ to get in the basis. The pivot is $\frac{1}{a}$ so $P_2$ gets out of the basis.
Then we get the same tableau as the initial one, so in this case the algorithm terminates.
Right?

If $\frac{3}{a}>2$ then $\theta_0=2$.
The pivot is $2$ and so $P_3$ gets out of the basis.

We get this tableau:

$\begin{matrix} B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta & \\ P_2 & 2 & \frac{1}{2} & 1 & \frac{1}{2} & 0 & 0 & & L_1'=\frac{L_1}{2}\\ \\ P_4 & 0 & \frac{3}{2} & 0 & -\frac{1}{2} & 1 & 0 & & L_2'=L_2-L_1'\\ \\ P_5 & 3-2a & 1-\frac{a}{2} & 0 & -\frac{a}{2} & 0 & 1 & & L_3'=L_3-aL_1' \end{matrix}$

In this case we get a degenerate basic feasible solution. So do we have to choose now $P_1$ , from the beginning, to get in the basis to check what happens? (Thinking)

evinda said:
For $a> \frac{3}{2}$ we continue the algorithm.
We choose $P_5$ to get in the basis. The pivot is $\frac{1}{a}$ so $P_2$ gets out of the basis.
Then we get the same tableau as the initial one, so in this case the algorithm terminates.
Right?

Not quite.
We need to walk through all possible basic feasible solutions.
Can't we choose another variable to get in the basis? (Wondering)
If $\frac{3}{a}>2$ then $\theta_0=2$.
The pivot is $2$ and so $P_3$ gets out of the basis.

We get this tableau:

$\begin{matrix} B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta & \\ P_2 & 2 & \frac{1}{2} & 1 & \frac{1}{2} & 0 & 0 & & L_1'=\frac{L_1}{2}\\ \\ P_4 & 0 & \frac{3}{2} & 0 & -\frac{1}{2} & 1 & 0 & & L_2'=L_2-L_1'\\ \\ P_5 & 3-2a & 1-\frac{a}{2} & 0 & -\frac{a}{2} & 0 & 1 & & L_3'=L_3-aL_1' \end{matrix}$

In this case we get a degenerate basic feasible solution. So do we have to choose now $P_1$ , from the beginning, to get in the basis to check what happens? (Thinking)

We found one! (Nod)
Can we avoid this degenerate basic feasible solution?
Because if we can't, what does that mean? (Wondering)Btw, did you notice that we have a $b$-value of $0$ and that it signifies a degenerate basic feasible solution? (Wondering)

I like Serena said:
Not quite.
We need to walk through all possible basic feasible solutions.
Can't we choose another variable to get in the basis? (Wondering)

We could choose $P_5$ to get in the basis... I will try it right now... (Smirk)

I like Serena said:
We found one! (Nod)
Can we avoid this degenerate basic feasible solution?
Because if we can't, what does that mean? (Wondering)

We could pick $P_1$ to get in the basis to check what happens. Or not? (Thinking)
I don't really know what it could mean... Could you give me a hint? (Thinking)

I like Serena said:
Btw, did you notice that we have a $b$-value of $0$ and that it signifies a degenerate basic feasible solution? (Wondering)

Yes, I did... (Nod)

If we start with $P_1$, independently of $a$, we get the following tableau:$\begin{matrix} B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta & \\ P_3 & 3 & 0 & \frac{1}{2} & 1 & -\frac{1}{2} & 0 & & L_1'=L_1-L_2'\\ \\ P_1 & 1 & 1 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & & L_2'=L_2-L_1'\\ \\ P_5 & 2 & 0 & a-\frac{1}{2} &0 & -\frac{1}{2} & 1 & & L_3'=L_3-aL_1' \end{matrix}$

In this case we get a non-degenerate basic feasible solution and so we continue the algorithm, right?

evinda said:
We could pick $P_1$ to get in the basis to check what happens. Or not? (Thinking)
I don't really know what it could mean... Could you give me a hint? (Thinking)

The problem statement asked for which values of $a$ we get a degenerate basic feasible solution.
We got one for a whole range of values of $a$! (Whew)

evinda said:
If we start with $P_1$, independently of $a$, we get the following tableau:

In this case we get a non-degenerate basic feasible solution and so we continue the algorithm, right?

Yep. (Smirk)

I like Serena said:
Not quite.
We need to walk through all possible basic feasible solutions.
Can't we choose another variable to get in the basis? (Wondering)

If we choose $P_1$ to get in the basis, we find the non-degenerate basic feasible solution $\left( \frac{2-3a}{2-\frac{1}{a}}, \frac{4}{2a-1}, \frac{6a-9}{2a-1},0,0\right)$ . Do we apply again the algorithm? (Thinking)

evinda said:
If we choose $P_1$ to get in the basis, we find the non-degenerate basic feasible solution $\left( \frac{2-3a}{2-\frac{1}{a}}, \frac{4}{2a-1}, \frac{6a-9}{2a-1},0,0\right)$ . Do we apply again the algorithm? (Thinking)

Is it a feasible solution considering that $a > \frac 32$? (Wondering)

Btw, I suggest to make a drawing. It should clear things up. (Thinking)

I like Serena said:
Is it a feasible solution considering that $a > \frac 32$? (Wondering)

Oh no, it isn't... (Shake)

So, if $\frac{3}{a}>2$ and we choose $P_2$ to get in the basis we find a degenerate basic feasible solution , so we do not have to take other cases. Right? (Thinking)
If $a=\frac{3}{2}$ and we choose again $P_2$ to get in the basis, we get a degenerate basic feasible solution.
By picking $P_2$ to get in the basis we haven't found so far a degenerate basic feasible solution for $a>\frac{3}{2}$.
So do we have to continue for this case the simplex algorithm by putting $P_1$ in the basis?
I like Serena said:
Btw, I suggest to make a drawing. It should clear things up. (Thinking)
Ok, I will try to... (Nerd)

evinda said:
Oh no, it isn't... (Shake)

So, if $\frac{3}{a}>2$ and we choose $P_2$ to get in the basis we find a degenerate basic feasible solution , so we do not have to take other cases. Right? (Thinking)
If $a=\frac{3}{2}$ and we choose again $P_2$ to get in the basis, we get a degenerate basic feasible solution.
By picking $P_2$ to get in the basis we haven't found so far a degenerate basic feasible solution for $a>\frac{3}{2}$.
So do we have to continue for this case the simplex algorithm by putting $P_1$ in the basis?

Yep to all. (Smirk)

I like Serena said:
Yep to all. (Smirk)

Having the following tableau$\begin{matrix} B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta & \\ P_3 & 3 & 0 & \frac{1}{2} & 1 & -\frac{1}{2} & 0 & & L_1'=L_1-L_2'\\ \\ P_1 & 1 & 1 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & & L_2'=L_2-L_1'\\ \\ P_5 & 2 & 0 & a-\frac{1}{2} &0 & -\frac{1}{2} & 1 & & L_3'=L_3-aL_1' \end{matrix}$

we choose either $P_2$ or $P_4$.

If we choose $P_2$ we get the solution $\left( \frac{a-\frac{3}{2}}{a-\frac{1}{2}}, \frac{2}{a-\frac{1}{2}}, \frac{3a-5}{2a-1}\right)$, which is basic feasible degenerate for $a=\frac{5}{3}$. Right?
Now do we have to take again cases? (Thinking)

I like Serena said:
Btw, I suggest to make a drawing. It should clear things up. (Thinking)

How can I make a drawing given that there are 5 unknown variables? (Thinking)

evinda said:
If we choose $P_2$ we get the solution $\left( \frac{a-\frac{3}{2}}{a-\frac{1}{2}}, \frac{2}{a-\frac{1}{2}}, \frac{3a-5}{2a-1}\right)$, which is basic feasible degenerate for $a=\frac{5}{3}$. Right?
Now do we have to take again cases? (Thinking)

Shouldn't that be $\left( \frac{a-\frac{3}{2}}{a-\frac{1}{2}}, \frac{2}{a-\frac{1}{2}}, \frac{6a-5}{2a-1}\right)$? (Wondering)

If so, when do we get a degenerate case exactly? (Wondering)

evinda said:
How can I make a drawing given that there are 5 unknown variables? (Thinking)

The original set of equations only has 2 unknown variables.
I think we can graph those. (Thinking)

For $a=1$ it should look like:
View attachment 5105

Attachments

• LP_degenerate.png
2.3 KB · Views: 58
I like Serena said:
Shouldn't that be $\left( \frac{a-\frac{3}{2}}{a-\frac{1}{2}}, \frac{2}{a-\frac{1}{2}}, \frac{6a-5}{2a-1}\right)$? (Wondering)
I will remake the operations...

I like Serena said:
If so, when do we get a degenerate case exactly? (Wondering)

We would get a degenerate solution only if $6a-5=0 \Rightarrow 6a=5 \Rightarrow a= \frac{5}{6}$.
But in this case we have $a> \frac{3}{2}=\frac{9}{6}$. So the above equality is never satisfied.

So now it remains to check the case where we put $P_4$ in the basis? (Thinking)

- - - Updated - - -

I like Serena said:
The original set of equations only has 2 unknown variables.
I think we can graph those. (Thinking)

For $a=1$ it should look like:

So at this graph do we see that the set of feasible solutions is the blue triangle? (Thinking)

evinda said:
We would get a degenerate solution only if $6a-5=0 \Rightarrow 6a=5 \Rightarrow a= \frac{5}{6}$.
But in this case we have $a> \frac{3}{2}=\frac{9}{6}$. So the above equality is never satisfied.

So now it remains to check the case where we put $P_4$ in the basis? (Thinking)

Yep. (Nod)
So at this graph do we see that the set of feasible solutions is the blue triangle? (Thinking)

Yes.
In particular we have 3 boundary conditions (lines) in the basic feasible solution $(x_1, x_2) = (0,2)$.
That is for respectively $x_1+2x_2\le 4$, $2x_1+x_2 \le 2$, and $x_1 \ge 0$.
It corresponds to a degenerate basic feasible solution.
It means that when we execute the simplex algorithm that we won't be able to tell in which direction we should go, and we might even get stuck in a cycle. (Nerd)

I like Serena said:
Yep. (Nod)

I chose $P_4$ to get in the basis and I got the following tableau:

$\begin{matrix} B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta & \\ P_3 & 4 & 1 & 1 & 1 & 0 & 0 & & L_1'=L_1+ \frac{1}{2}L_2'\\ P_4 & 2 & 2 & 1 & 0 & 1 & 0 & & L_2'=2L_2\\ P_5 & 3 & 1 & a & 0 & 0 & 1 & & L_3'=L_3+\frac{1}{2}L_2' \end{matrix}$

Is it right? If so, then we get the same basic feasible non-degenerate solution as the initial one and this means that at this point the algorithm terminates. Right?

So for $a> \frac{3}{2}$ we cannot find a degenerate basic feasible solution. Or am I wrong? (Thinking)

I like Serena said:
Yes.
In particular we have 3 boundary conditions (lines) in the basic feasible solution $(x_1, x_2) = (0,2)$.
That is for respectively $x_1+2x_2\le 4$, $2x_1+x_2 \le 2$, and $x_1 \ge 0$.
It corresponds to a degenerate basic feasible solution.
It means that when we execute the simplex algorithm that we won't be able to tell in which direction we should go, and we might even get stuck in a cycle. (Nerd)
So you mean that we take into consideration just the first two inequalities? (Thinking)

evinda said:
Is it right? If so, then we get the same basic feasible non-degenerate solution as the initial one and this means that at this point the algorithm terminates. Right?

There is another basic feasible solution with the basis $P_1, P_3, P_5$ that I haven't seen yet.
Did we miss it? (Wondering)

So for $a> \frac{3}{2}$ we cannot find a degenerate basic feasible solution. Or am I wrong? (Thinking)

That is correct.

So you mean that we take into consideration just the first two inequalities? (Thinking)

We only need to take the inequalities that touch the feasible region into account.
In this case (with $a < \frac 32$) those are the first two inequalities and the non-negativity inequalities.
The 3rd inequality does not touch the feasible region, so we can ignore it. (Nerd)

I like Serena said:
There is another basic feasible solution with the basis $P_1, P_3, P_5$ that I haven't seen yet.
Did we miss it? (Wondering)

Which tableau should we use to get it? (Sweating)
I like Serena said:
We only need to take the inequalities that touch the feasible region into account.
In this case (with $a < \frac 32$) those are the first two inequalities and the non-negativity inequalities.
The 3rd inequality does not touch the feasible region, so we can ignore it. (Nerd)

In general, the set of feasible solutions is the set where all the inequalities hold.
Why can we ignore the third inequality in this case? Could you explain it further to me? (Thinking)

evinda said:
Which tableau should we use to get it? (Sweating)

Oh wait, we did already get it: (Wait)
evinda said:
If we start with $P_1$, independently of $a$, we get the following tableau:
$\begin{matrix} B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta & \\ P_3 & 3 & 0 & \frac{1}{2} & 1 & -\frac{1}{2} & 0 & & L_1'=L_1-L_2'\\ \\ P_1 & 1 & 1 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & & L_2'=L_2-L_1'\\ \\ P_5 & 2 & 0 & a-\frac{1}{2} &0 & -\frac{1}{2} & 1 & & L_3'=L_3-aL_1' \end{matrix}$

In general, the set of feasible solutions is the set where all the inequalities hold.
Why can we ignore the third inequality in this case? Could you explain it further to me? (Thinking)

The blue triangle represents the feasible region.
In that region the third constraint ($x_1 + ax_2 \le 3$) is always satisfied if $a < \frac 32$, so we can leave it out. (Nerd)

I like Serena said:
The blue triangle represents the feasible region.
In that region the third constraint ($x_1 + ax_2 \le 3$) is always satisfied if $a < \frac 32$, so we can leave it out. (Nerd)
How do we deduce that the third constraint ($x_1 + ax_2 \le 3$) is always satisfied if $a < \frac 32$ ?

We have $x_1+ a x_2< x_1+ \frac{3}{2} x_2 \leq x_1+2 x_2 \leq 4$

How can we get that $x_1+ a x_2 \leq 3$ ? (Thinking)

evinda said:
How do we deduce that the third constraint ($x_1 + ax_2 \le 3$) is always satisfied if $a < \frac 32$ ?

We have $x_1+ a x_2< x_1+ \frac{3}{2} x_2 \leq x_1+2 x_2 \leq 4$

How can we get that $x_1+ a x_2 \leq 3$ ? (Thinking)

By looking at the graph? (Wondering)
The blue triangle is strictly below the green line everywhere (in the first quadrant). (Nerd)

I like Serena said:
Not quite.
We need to walk through all possible basic feasible solutions.
Can't we choose another variable to get in the basis? (Wondering)

Don't we also have to check the case where we have the following tableau:

$\begin{matrix} B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta & \\ P_3 & 4-\frac{6}{a} & 1-\frac{2}{a} & 0 & 1 & 0 & -\frac{2}{a} & & L_1'=L_1-2L_3'\\ \\ P_4 & 2-\frac{3}{a} & 2-\frac{1}{a} & 0 & 0 & 1 & -\frac{1}{a} & & L_2'=L_2-L_3'\\ \\ P_2 & \frac{3}{a} & \frac{1}{a} & 1 & 0 & 0 & \frac{1}{a} & & L_3'=\frac{L_3}{a} \end{matrix}$

where $a> \frac{3}{2}$

and we choose $P_1$ to get in the basis instead of $P_5$ ?

evinda said:
Don't we also have to check the case where we have the following tableau:

$\begin{matrix} B & b & P_1 & P_2 & P_3 & P_4 & P_5 & \theta & \\ P_3 & 4-\frac{6}{a} & 1-\frac{2}{a} & 0 & 1 & 0 & -\frac{2}{a} & & L_1'=L_1-2L_3'\\ \\ P_4 & 2-\frac{3}{a} & 2-\frac{1}{a} & 0 & 0 & 1 & -\frac{1}{a} & & L_2'=L_2-L_3'\\ \\ P_2 & \frac{3}{a} & \frac{1}{a} & 1 & 0 & 0 & \frac{1}{a} & & L_3'=\frac{L_3}{a} \end{matrix}$

where $a> \frac{3}{2}$

and we choose $P_1$ to get in the basis instead of $P_5$ ?

Ah, did we miss that one?
Yes, we should also check that one. (Nod)

The corresponding graph is:
View attachment 5111
The tableau corresponds to the intersection of the green line with the y-axis.
If we bring in $P_1$ and leave $P_3$, we move to the intersection of the blue line with the green line. (Nerd)
Hmm... didn't we already do that? (Wondering)

Attachments

• LP_degenerate_2.png
1.8 KB · Views: 57
I like Serena said:
Ah, did we miss that one?
Yes, we should also check that one. (Nod)

Then we get the following tableau, right?
$\begin{matrix} B & b & P_1 & P_2 & P_3 & P_4 & P_5 & & \theta & \\ P_3 & \frac{6a-9}{2a-1} & 0 & 0 & 1 & \frac{2-a}{2a-1} & \frac{3}{1-2a} & & &L_1''=L_1'-\left( 1-\frac{2}{a} \right )L_2'' \\ \\ P_1 & \frac{2-\frac{3}{a}}{2-\frac{1}{a}} & 1 & 0 & 0 & \frac{1}{2-\frac{1}{a}} & \frac{1}{1-2a} & & & L_2''=\frac{L_2'}{2-\frac{1}{a}}\\ \\ P_2 & \frac{4}{2a-1} & 0 & 1 & 0 & \frac{1}{1-2a} & \frac{2}{2a-1} & & &L_3''=L_3'-\frac{1}{a}L_2'' \end{matrix}$

This gives a non-degenerate basic feasible solution so we have to continue the algorithm. Right? (Thinking)

I like Serena said:
Hmm... didn't we already do that? (Wondering)

Did we? At which point? (Thinking)

evinda said:
Then we get the following tableau, right?
$\begin{matrix} B & b & P_1 & P_2 & P_3 & P_4 & P_5 & & \theta & \\ P_3 & \frac{6a-9}{2a-1} & 0 & 0 & 1 & \frac{2-a}{2a-1} & \frac{3}{1-2a} & & &L_1''=L_1'-\left( 1-\frac{2}{a} \right )L_2'' \\ \\ P_1 & \frac{2-\frac{3}{a}}{2-\frac{1}{a}} & 1 & 0 & 0 & \frac{1}{2-\frac{1}{a}} & \frac{1}{1-2a} & & & L_2''=\frac{L_2'}{2-\frac{1}{a}}\\ \\ P_2 & \frac{4}{2a-1} & 0 & 1 & 0 & \frac{1}{1-2a} & \frac{2}{2a-1} & & &L_3''=L_3'-\frac{1}{a}L_2'' \end{matrix}$

This gives a non-degenerate basic feasible solution so we have to continue the algorithm. Right? (Thinking)

I don't think that is a feasible solution for $a > \frac 32$.
Instead I think we should move to the basis $P_1, P_2, P_4$. (Thinking)
Did we? At which point? (Thinking)

Turns out we covered basis $P_2, P_3, P_4$ in post #7.
But I can't find basis $P_1, P_2, P_4$. (Nerd)

I like Serena said:
I don't think that is a feasible solution for $a > \frac 32$.

Why isn't it feasible? Aren't all the components positive? (Thinking)

$a> \frac{3}{2} \Rightarrow 2a>3 \Rightarrow 6a>9$

$2a>3 \Rightarrow 2a>1$

$\frac{2-\frac{3}{a}}{2-\frac{1}{a}}=\frac{2a-3}{2a-1}>0$

evinda said:
Why isn't it feasible? Aren't all the components positive? (Thinking)

$a> \frac{3}{2} \Rightarrow 2a>3 \Rightarrow 6a>9$

$2a>3 \Rightarrow 2a>1$

$\frac{2-\frac{3}{a}}{2-\frac{1}{a}}=\frac{2a-3}{2a-1}>0$

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$).
https://www.physicsforums.com/attachments/5111
When $a > \frac 32$ that intersection should have either $x_2 < 0$ or $x_1 < 0$.

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