The simplex method is not always well behaved

AbstractThis paper deals with the rounding-error analysis of the simplex method for solving linear-programming problems. We prove that in general any simplex-type algorithm is not well behaved, which means that the computed solution cannot be considered as an exact solution to a slightly perturbed problem. We also point out that simplex algorithms with well-behaved updating techniques (such as the Bartels-Golub algorithm) are numerically stable whenever proper tolerances are introduced into the optimality criteria. This means that the error in the computed solution is of a similar order to the sensitivity of the optimal solution to slight data perturbations