Big-M Simplex Method Returns Unfeasible Solution

Question

Consider the following linear programming problem:
"Minimize 2x₁ + 3x₂ subject to the constraints
2x₁ + x₂ ≥ 4
2x₁ - x₂ ≥ -1
x₁,x₂ ≥ 0"

Since there are ≥ signs in both constraints, I want to use the big-M method. The original solution in standard form shows that the auxiliary variable has to be added to the first constraint.

So I've got the problem in standard form for the big-M method as:
"Minimize 2x₁ + 3x₂ + MA
subject to the constraints
2x₁ + x₂ - x₃ + A ≥ 4
2x₁ - x₂ - x₄ ≥ -1
x₁,x₂ ≥ 0"

I've performed the method on this, with tableau:
| 1 | 2 | 1 | 0 | 0 | -M | 0
|0 | 2 |  1 |-1 | 0 |  1  | 4
|0 | 2 |-1 | 0 |-1 |  0  |-1

(Row 0 at the top is the objective function)

But this gives a tableau with a negative and a zero in the entering column after two iterations, implying that the feasible region is unbounded and I can perform no more iterations despite the objective row not being optimal.
I can see from drawing the constraints that the optimal solution is at 4, so this cannot be the correct conclusion. What have I done wrong? Or is the method impossible with this problem?

Answer 1

You do not have the right objective function. It is described here, how the objective function has to be created.

$$\begin{array}{|m{cm}|m{1cm}|} \hline x_1 &x_2 &s_1 & s_2 & a_1 & RHS \\ \hline \hline \hline \color{blue}{-2+2M}& -3+M & M & 0 & 0 & 4M\\ \hline \color{red}{\boxed{ 2}} & 1 & -1 & 0&1&4 \\ \hline -2 &1&0&1&0&1 \\ \hline \end{array}$$

$s_1$ and $s_2$ are the slack variables. $a_1$ is the artificial variable for the first constraint.

The pivot element is $\color{red}2$, because $\color{blue}{-2+2M}$ is the biggest value in the first row.

$$\begin{array}{|m{cm}|m{1cm}|} \hline x_1 &x_2 &s_1 & s_2 & a_1 & RHS \\ \hline \hline \hline 0& -2 & -1 & 0 & 1-M & 4\\ \hline 1 & \frac{1}{2} & -\frac{1}{2} & 0&\frac{1}{2}&2 \\ \hline 0 &2&-1&1&1&5 \\ \hline \end{array}$$

All coefficients in the first row are non-positive. $x^*_1=2,x_2^*=0,s_1=0,s_2=5,a_1=0,z^*=4$

Remark:

The second constraint has to be transformed, before you can put it in the table. The RHS has to be non-negative.

$2x_1-x_2\geq -1$

The easiest way is to multibly the equation by (-1). The relation sign turns around.

$-2x_1+x_2\leq 1$

Inserting the slack variable

$-2x_1+x_2+s_2= 1$