Operations Research Models and Methods / Methods / Network Methods /

 Select a Cell to Leave the Basis

 Choosing the Leaving Cell The entering cell always determines a cycle that consists of the entering cell and basic cells in the current solution. We find that cycle by starting at the entering cell and moving from one cell to another in horizontal or vertical moves. For small problems, students can usually identify the cycle by observation. Once the cycle is found, we identify with positive (+) signs and negative (-) signs the cells in which flow is changing and the direction of change for each cell. The entering cell has a positive sign because flow is increasing in that cell. The next cell in the cycle has a negative sign because flow is decreasing. The cells in the cycle are thus labeled with alternate positive and negative signs. The cell that must leave the basis is a cell taken from the set with negative signs. It is the cell from the set with the smallest flow. If there is more than one cell holding the smallest flow any one can be chosen. Hints about the Leaving Cell The instruction option provides hints concerning the leaving cell. This image shows the dialog after two clicks of the hint button. The cell labeled with a negative that has the smallest flow is selected. The cycle is shown on the graphic with alternating positive and negative signs. Clicking the OK button presents the next step of the algorithm. Clicking the hint button again will show any other cells that are candidates to leave the basis. With the Self option, the student must choose a basic cell to leave. If the wrong cell is chosen, the solution may become infeasible. The next step in the process is to change the basis.

Next

Operations Research Models and Methods
by Paul A. Jensen and Jon Bard, University of Texas, Copyright by the Authors