It may be recalled that the simplex method is bases on a set of rules whereby we proceed from one basic feasible solution to the next until and optimal solution, if it exists, is obtained. However, nothing wan said as what to do, if the various choice rules fo the simples method do not lead to a clear-cut decision, either because of ties or other similar ambiguities. In this section such things are considered.

Tie for the Entering Variable. In simplex tableau, suppose that two or more nonbasic variables are tied for having the largest positive C_j – Z_j entry. In such a case, we choose any one of these to find the entering variable. The optimal solution will be reached eventually, regardless of the tied variable chosen.

The for the Departing Variable- Degeneracy. Now suppose that two or more quotients in the ratio column are tied for being the smallest non-negative. We may choose any one of these quotients to find departing variable. When a tie for the smallest quotient exists, then along with the nonbasic variables, a basic feasible solution will have a basic variable that is 0. In this case we say that the basic feasible solution is degenerate or that the linear programming problem has degeneracy. It is possible, in a degrease situation, to obtain a se-quence of tableaus, that correspond to basic feasible solutions which give the same value of the objective function. Moreover, we may eventually retune to the first tableau in the sequence. This is called cycling. When cycling occurs, it is possible that we may never obtain the optimum value of the objective function. However, this phenomenon seldom occurs in practical problems.

For more help in Breaking In The Simplex Method click the button below to submit your homework assignment