The primal simplex method starts with some initial feasible
solution and proceeds through a series of iterative steps.
At each step some arc that violates the optimality condition
is selected to enter the basis. Since the number of basic
arcs is fixed at one less than the number of nodes, some arc
must leave the basis. These steps are accomplished by rules
that are illustrated on this page. We have chosen a feasible
starting solution arbitrarily. The discussion covers two basis
changes. The graphics are reached by clicking on the title
to each section. The displays are shown in separate pages,
so you can read this page and see the figure at the same time.
When you are through with the display simply close the page.
Arc Display
(2, 4, 7, 8)
The initial basis includes arcs 2, 4, 7, and 8. Nonbasic
arc 5 has upper bound flow, while all others have 0 flow.
The status column indicates whether an arc is basic, indicated
with a B, nonbasic at its lower bound, indicated with an L,
or nonbasic at its upper bound, indicated with a U. The cells
are color coded with red, white and blue, respectively to
emphasize these features. The column labeled NB flows shows
the flows on the nonbasic arcs. An entry will be zero if the
arc is basic or if the arc is nonbasic at its lower bound.
The entry will be at the upper bound for the arc when it is
nonbasic with flow at its upper bound. This column is used
to compute the basic arc flows.
The optimality measure is displayed in the reduced cost column.
A nonbasic arc satisfies the optimality condition if its flow
is zero for a positive reduced cost, or if its flow is at
the upper bound for a negative reduced cost. If the reduced
cost is zero, the flow may be anywhere between the upper and
lower bounds. An arc that violates optimality is a candidate
to enter the basis. On the display we see that both arcs 3
and 5 are candidates.
Selecting
an Arc to Enter the Basis
One rule for selecting the entering arc is to choose the
one that most violates the optimality condition. For this
case, arc 5 would be selected by this rule. Actually, any
nonoptimum arc can be selected, and we have chosen arc 3.
The dialog shown is for the Instruction option. When this
dialog is first displayed no hints are provided. When the
hint button is clicked once, instructions appear on the dialog
and the reduced cost of all candidates are colored yellow
on the arc display. Clicking the hint button a second time
selects the candidate that most violates the optimality condition.
Clicking the button additional times cycles through the list
of candidates. Clicking the OK button accepts the choice.
The solution option can be changed at any time by clicking
one of the buttons at the bottom.
Selecting
an Arc to Leave the Basis
Given, the arc to enter the basis, we now must determine
the arc that must leave the basis. To do this we first identify
the set of arcs that will experience flow changes as the flow
in the entering arc is changed. These arcs comprise a cycle
of basic arcs and the entering arc. The identity of the basic
cycle arcs and the direction of flow changes are shown in
the Delta column of the display. We notice in this case that
the cycle is {3, -8, 7, -2}. We list the entering arc as the
first member of the cycle. Its sign is positive because flow
is increasing on the arc.
The arc to leave the basis is the one whose flow goes to
either 0 or its upper bound with the smallest change in the
flow on the entering arc. This information is shown in the
Ratio column of the display. We see the ratios for arcs {3,
-8, 7, -2} are {3, 1, 2, 3} respectively. The ratio for the
entering arc is shown at the top of the sheet. The smallest
ratio occurs for arc 8, so that arc will leave the basis.
Since arc the flow in arc 8 is decreasing, it leaves the basis
with its flow going to zero.
The dialog for selecting the arc to leave the basis opens
with no selection or hint. Clicking on the hint box causes
the relevant rule to be displayed and colors the candidates
to leave the basis. The rule for selecting the leaving arc
is less flexible than that for selecting the entering arc.
The arc to leave must be the one with the smallest ratio.
The only case when there is more than one candidate is when
there is more than one arc that has the smallest ratio. In
that case the choice is arbitrary. On the next iteration,
however, the flow on all the candidates will go to a bound.
This situation is called a degenerate solution.
Node
Display (2, 4, 7, 8)
This figure shows the node display just before the basis
change. The row for the leaving variable is highlighted. The
pivot button is provided to make the change in basis. Clicking
on the pivot completes the iteration. Attention returns to
the arc display for the next iteration.
Arc Display
(2, 3, 4, 7)
This display shows the new basis. The flow, reduced cost,
status and NB flow columns are updated to reflect the change.
Selecting
an Arc to Enter the Basis
Now we see that arcs 5 and 6 are candidates. We choose arc
5. When a nonbasic arc is at its upper bound, it enters the
basis by having its flow decrease. This is important for the
determination of the leaving arc.
Selecting
an Arc to Leave the Basis
In this case, we find the cycle of arcs as {-5, -3, 4}. Since
arc 3 has the smallest ratio, it is the one to leave the basis.
We should note that if arc 5 had smallest ratio, it would
have been the one to leave. It is possible to have an arc
enter and leave in the same iteration. In this case the selection
of basic arcs will not change, but the arc selected to enter
the basis will move to the opposite nonbasic state. The arc
flows also change.
Node
Display (2, 3, 4, 7)
The node display shown is just before the change of basis.
Clicking on the pivot button changes the basis, and we go
again to the arc display.
Arc Display
(2, 4, 5, 7)
The new basis is not optimum, because arc 6 violates the
optimality condition.
Node
Display (2, 4, 5, 7)
After selecting arc 6 to enter the basis, we see the node
display just before the pivot. We notice that there is a tie
for the smallest ratio. Both arcs 4 and 7 are candidates to
leave. Either can be chosen. From the ratios we know that
both arcs 4 and 7 have flow increasing. Both will be at their
upper bounds in the next iteration. Arc 4 will be degenerate
in the next iteration.
