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?