I have a linear programming problem:
Maximise, $z = x_1 + x_2$
Subject to:
$$ x_1 + x_2 \ge 10 $$ $$ 2x_1 + x_2 \le 40 $$ $$ x_1, x_2 \ge 0 $$
When I construct the simplex tableau adding 2 slack variables and 1 artificial variable we obtain the matrix of constraint $A$ to be:
$$ \left[ \begin{matrix} x_1 & x_2 & s_1 & s_2 & a_1 \\ 1 & 1 & -1 & 0 & 1 \\ 2 & 1 & 0 & 1 & 0 \\ \end{matrix} \right] $$
with the z-row of our tableau being:
$$ \left[ \begin{matrix} -2M & -1 & 0 & 0 & M \\ \end{matrix} \right] $$
Which will produce the correct result, however, I also want to check for unboundedness. I am following to detect this:
- if all the constraint coefficients in the column of any non-basic variable are zero or negative
In this case, the solution is unbounded toward $s_1$. But clearly, this is not true, we cannot maximise $s_1$ to infinity and still have a solution that satisfies constraint 1.
Therefore I am unsure what I have wrong here?
Your tableau is not represented at a feasible point, since you still have a column for the auxiliary variable $a_1$.
By taking into account the auxiliary variable $a_1$, your LP is indeed unbounded:
The first constraint writes: $$x_1+x_2 +s_1 - a_1 \geq 10$$
If you augment $s_1$, you can augment $a_1$ the same amount, so the first constraint will remain satisfied without touching $x_1$ and $x_2$.