Find value of b

Question

The following system of restrictions is given:

$$y_1+ 2 y_2 \leq 4 \\ 2y_1+y_2 \leq 2 \\ y_1+b y_2 \leq 3 \\ y_1, y_2 \geq 0$$

For which values of b is there a degenarate basic feasible solution?

Can we make a drawing to see when we will have a degenarate basic feasible 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 & b & 0 & 0 & 1 & \frac{3}{b} & L_3 \end{matrix}$

We assumw that $\frac{3}{b} \leq 2$.

We choose $P_2$ to get in the basis.

We get the following tableau $(\star)$:

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

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

Then we suppose that $b> \frac{3}{2}$.

We choose $P_5$ to get in the basis.

Then we get the same tableau as the initial one.

If after the tableau $(\star)$ we choose $P_1$ to get in the basis we get the following tableau:

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

Is it right so far? Do we have to check now what happens if P_4 gets in the basis and what if P_5 gets in the basis?

Answer 1

I don't know your method so I can't comment on it. Below is another method which gives the answer in this case, but may be less efficient than yours for larger systems.

---

A degenerate basic feasible solution exists if there is a solution for which more than two constraints are tight. So the first step is to find basic feasible solutions without the constraint $y_1+by_2 \leq 3$. Some of these might already be degenerate, and for these we can choose any value of $b$ for which the solution satisfies $y_1+by_2 \leq 3$. For the rest, we need to choose $b$ so that the solution satisfies $y_1+by_2 = 3$, if any.

We therefore need to go over all possible basic feasible solutions of the first two and last two inequalities, and this we can do by going over all $\binom{4}{2}$ choices of tight constraints:

1. $y_1 + 2y_2 = 4$, $2y_1 + y_2 = 2$: then $y_1 = 0$, $y_2 = 2$. The constraint $y_1 = 0$ is also tight, so any value of $b$ for which $0 + 2b \leq 3$ works here.

2. $y_1 + 2y_2 = 4$, $y_1 = 0$: covered by case 1.

3. $y_1 + 2y_2 = 4$, $y_2 = 0$: then $y_1 = 4$, so the second constraint is violated.

4. $2y_1 + y_2 = 2$, $y_1 = 0$: covered by case 1.

5. $2y_1 + y_2 = 2$, $y_2 = 0$: then $y_1 = 1$, so the first constraint is satisfied. For this to be degenerate, we need $1 + 0b = 3$.

6. $y_1 = y_2 = 0$: all constraints are satisfied. For this to be degenerate, we need $0 + 0b = 3$.

All in all, we get $b \leq 3/2$.