Until now I have not mentioned one aspect, called degeneracy, that
sometimes could cause some trouble in the simplex method mechanism.
In a few words one can say that degeneracy occurs when different bases spot the same vertex of the polyhedron P.
From a geometric point of view this happens because the number of hyperplanes corresponding to the constraints of the problem that pass through the vertex are more than n, where n is the dimension of the variables vector.
Without going into detail, we may say that in the presence of degeneracy the following situations might occur: what can happen is that the current basic solution is optimal but the optimality conditions are not satisfied, that means that some reduced cost is strictly positive; in this case the method might perform a pivot operation giving as a result a new basic solution that corresponds to the same vertex. As a consequence, in particular cases, the method might keep in visting with a cyclic pattern the same set of basic solutions without coming to an end. This inconvenience may be overcome by using ad hoc anticycling rules that guide the choice of the variables exiting and entering the basis.
With the degenercy we conclude the description of the simplex method. Let's now begin with a new topic, the duality.