Return to Index
Operations Research Models and Methods
Models Section
The Teach Network Add-in
- The Iterative Step

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.


Return to Top

tree roots

Operations Research Models and Methods
by Paul A. Jensen
Copyright 2004 - All rights reserved

Next Page