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?
Best Answer
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 2nd constraint.
If $x_1>0$ and $x_5>0$, the 2nd 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.