I just want to know when to use which method.
This is my current understanding, please say if I am incorrect:
If all constraint equations can be turned into s.t. the RHSs of all are positive and all the signs are $\leq$, then use the simplex method.
If one or some of the constraint equations are $\geq$ then use Big-M.
I am really not sure about the dual simplex.
Please help me. I have an exam in two days!! I just want to know when to use which method.
In both situations of $\le$ and $\ge$ (and even $=$) we would use the Simplex method, as it is simply an algorithm that traverses the feasible region of a model from extreme point to extreme point until it finds an optimal extreme point that it cannot improve upon with another extreme point in the model.
What this question is really asking is, “when do we use the Big-M method?” The cases of when we use the Big-M method goes as follows:
Let’s look at this in action with the given model:
$$\max z=4x_1+3x_2+2x_3+x_4$$ Subject to: $$2x_1+x_3\ge4$$ $$x_1+x_2+x_4=1$$ $$x_3-x_4\le10$$ $$x_1,x_2,x_3,x_4\ge0$$
When we standardize this model, it will look like the following: $$\max z-4x_1-3x_2-2x_3-x_4 + M(a_1+a_2)= 0$$ Subject to: $$2x_1+x_3-e_1+a_1=4$$ $$x_1+x_2+x_4+a_2=1$$ $$x_3-x_4+s_3=10$$ $$x_1,x_2,x_3,x_4,e_1,a_1,a_2,s_3\ge0$$
Here we used $e_n$ to denote the excess amount that needs to be taken off the left-hand-side of the equation such that it makes the left-hand-side equal to the right-hand-side. However, there is an issue with this approach as it does not fulfill the requirement of a basic variable existing in every constraint (row) for Simplex. Thus, we add a artificial variable $a_n$ to the equation such that there now exists a basic variable within that constraint.
In the second constraint, there exists no basic variable, thus we add an artificial variable to force one to exist in that row.
In the third constraint, we add the surplus, basic variable, $s_n$ like we normally would.
(For clarity: $n$ denotes the row in which each variable we add lives in.)
However, notice that while we add artificial variables to make it possible to use Simplex on a model, we do not want the artificial variables to be in the basis in our final iteration. In other words, we want the artificial variables to become a non-basic variable at the conclusion of the Simplex method in which they are equal to zero, and we to ensure the model does not ever keep the artificial variable in the basis. Thus, in a maximization function we subtract the $M(a_1+\ldots+a_n)$ from the objective row to incentivize the model to always push it out as $M$ is the largest possible number in $\Bbb R$ (think of it as pseudo-infinity where its an uncountably large number). In a minimization function, we’ll do the opposite where we’ll add $M(a_1+\ldots+a_n)$ from the objective function row to discourage Simplex from ever keeping it within the basis.
Note: If Simplex hits a point in which it cannot pivot anymore, and the artificial variables are still in the basis as basic variables, then the model is infeasible.