2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I used the simplex method. $$$$ You said that: "A degenerate basic feasible solution exists if there is a solution for which more than two constraints are tight." $$$$ You mean that if we consider two of the inequalities, these imply the third one? $$$$ Also this holds only if we have three inequalities, right? $\endgroup$ – Evinda Jan 5 '16 at 17:09
  • $\begingroup$ @Evinda A degenerate basic feasible solution over $n$ variables is one in which more than $n$ constraints are tight. $\endgroup$ – Yuval Filmus Jan 5 '16 at 17:11
  • $\begingroup$ What do you mean with: "more than $n$ constraints are tight." ? $\endgroup$ – Evinda Jan 5 '16 at 17:13
  • $\begingroup$ @Evinda An inequality constraint is tight if equality holds. $\endgroup$ – Yuval Filmus Jan 5 '16 at 17:14
  • $\begingroup$ A ok...So now do we have to check the case when $y_1+by_2=3$ holds given then also an other equality holds? $\endgroup$ – Evinda Jan 5 '16 at 19:19

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.