Consider the following linear programming problem:
"Minimize 2x1 + 3x2 subject to the constraints
2x1 + x2 ≥ 4
2x1 – x2 ≥ -1
x1,x2 ≥ 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 2x1 + 3x2 + MA
subject to the constraints
2x1 + x2 – x3 + A ≥ 4
2x1 – x2 – x4 ≥ -1
x1,x2 ≥ 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?
Best Answer
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$