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
alternating 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.
