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. The add-in presents the dialog
below with fields for the row and column of the cell that will
leave the basis.
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. |