Finding degenerate and nondegenerate BFS

Question

Consider the Linear programming problem

$$ maximize \; \; \; z = x_1 + 2x_2+ 3 x_3 $$

subject to

\begin{align*} x_1+x_2+2x_3 & \leq 4 \\ x_1 &\leq 4 \\ x_i &\geq 0 \end{align*}

Find a nondegenerate basic feasible solution, a degenerate BFS, and check whether there is an unfeasible solution.

Try:

First, I need to introduce slack variables $x_4,x_5$ so that $x_1+x_2+2x_3 + x_4 = 4 $ and $x_1+x_5=4$.

So our constrains we can write as matrix

$$ A (x_1,x_2,x_3,x_4,x_5)^T = (4,4)^T $$

where row 1 of a is $(1,2,3,1,0)$ and row 2 is $(1,1,2,0,1)$

If we take $B = I$ the identity matrix then $x_B = I^{-1} b = Ib = I \cdot (4,4)^T = (4,4)$ and this is BFS which is nondegenerate because its components are more than $0$.

On the other hand, if for example, we take $B$ to be the matrix with columns $(2, 1)^T$ and $(1,0)^T$ then $B^{-1} $ will be the matrix with columns $(0,1)^T$ and $(1, -2)^T$ and therefore

$$ x_B = B^{-1} b = {4 \choose -4} $$

and so this BFS is degenerate.

Am I correct so far? I m still on how to find unfeasible basic solutions. Are there any unfeasible basic solutions?

Answer 1

The two rows of $A$ in the question body are incorrect, so I don't feel that it's meaningful to look at the rest.

$$A = \begin{bmatrix}1&1&2&1&0\\1&0&0&0&1\end{bmatrix}, b = \begin{bmatrix}4\\4\end{bmatrix}, c = \begin{bmatrix}1\\2\\3\\0\\0\end{bmatrix}$$

$$\max c^Tx \\ Ax = b \\ x \ge 0$$

Explore all possible cases from the 2^nd constraint.

• nondegenerate BFS: set $x_5 = 4$, so the 2^nd constraint gives $x_1 = 0$. The coefficients for $x_2,x_3$ and $x_4$ are positive in the 1^st constraint, so we have $(0,4,0,0,4)$, $(0,0,2,0,4)$, $(0,0,0,4,4)$
• degenerate BFS: set $x_1 = 4$ and $x_5 = 0$ in the 2^nd constraint. This gives $(4,0,0,0,0)$.

If $x_1>0$ and $x_5>0$, the 2^nd constraint gives $x_1 = 4 - x_5 < 4$, so at least one of $x_2$, $x_3$ and $x_4$ is positive, so we get a feasible non-basic solution.

It's impossible that both $x_1=0$ and $x_5=0$, so there's no infeasible solution.