Chapter 2 linear programming problems

2.4 Computational Problems in Simplex Method

There are a number of computational problems that may arise during the actual

application of the simplex method for solving a linear programming problem. In
this section we discuss some complication that may occur.

1. Ties in the selection of the nonbasic variable:
In a maximization problem, the nonbasic variable with the largest positive value in the c_j −z_j row is chosen. In case there exists more than one variable with the same largest positive value in the c_j −z_j row, then we have a tie for
selecting the nonbasic variable.

2. Ties in the minimum ratio rule and degeneracy:
While applying the minimum ratio rule it is possible for two or more con-
straints to give the same least ratio value. This result in a tie for selecting
which basic variable should leave the basis. This complication causes degen-
eracy in basic feasible solution.

Degenerate basic feasible solution: A basic feasible solution is said to
be degenerate basic feasible solution if at least one basic variable in the so-
lution equals zero.

3. Cycling:
At a degenerate basic solution, there is a risk of getting trapped in a cycle.
When there exist degeneracy in feasible solution we can’t say that simplex
method will be terminated in a finite number of iterations, because this phe-
nomenon causes that we obtain a new basic feasible solution in the next
iteration which has no effect on the objective function value. It is then the-

35

oretically possible to select a sequence of admissible bases that is repeatedly
selected without over satisfying the optimality criteria and, hence, never
reaches a optimal solution. A number of anticycling procedure have been
developed [17, 14, 66, 49, 10]. These anticycling method are not used in
practice partly because they would slow the computer program down and