Network Definition Dialog
The opening dialog requests a problem name, number of arcs
and number of nodes. Options are allowed for the Pure or Generalized network
models. The pure option should be chosen if all the arc gains are 1. When
the Make Random Problem checkbox is checked, the arcs and node parameters
are automatically generated for a sample problem. If not checked, the
parameters are left at zero ready for the student to provide the data
for a specific problem. The purpose of random data is to allow multiple
instruction runs without extensive data entry. Since the parameters are
random, a variety of program situations can be observed with several runs.
The solution options provide different amounts of information
regarding the algorithm and different levels of interaction with the student.
As the algorithm progresses it is possible to shift between the options.
 Demonstration: This option provides a running
commentary of the steps taken by the algorithm as it progresses toward
the optimum. The student is only required to press a button from time
to time.
 Instruction: With this option, the student is
required to make decisions about the process taken by the algorithm.
For example, the student must select the arcs to enter and leave the
basis. A hint button provides various levels of help. Pressing the hint
button several times eventually reveals the correct step. The program
prevents any serious deviations from the proper procedures.
 Do it yourself: Here the student has the entire
responsibility of directing the algorithm. No hints or corrections are
given. If the student is hopelessly lost, it is possible to shift to
the Instruction option.
 Run without stopping: Here the algorithm is
allowed to run to the end without commentary or interaction. The entry
for delay controls the speed of this option. The program pauses for
the specified number of seconds at each stopping point. An integer number
of seconds should be entered here. Once this option begins, there is
no way to change option until the program finishes.
The Example Network
The example for this section is the figure below. The Network
Modeling pages provide a full discussion of the network model, however
we provide a brief description here.
The arcs are the directed lines and the nodes are the numbered
circles. An arc carries flow from one node to another. For example, arc
1 carries flow from node 1 to node 2. Arc parameters, shown in parentheses,
are the upper bound for flow and the unit cost of the flow.
Flow is conserved at the nodes. The number in the bracket
at a node is the flow entering or leaving the network, with a positive
number indicating flow that enters and a negative number indicating flow
that leaves. For example the +2 at node 1 means that 2 units of flow must
enter enter at the node. We call this the fixed flow. This flow must balance
the flows entering and leaving the node on the arcs. For example, the
flow entering node 1 on arc 8, plus the 2 units of fixed flow, must equal
the sum of the flows leaving the node on arcs 1 and 2.
Arcs such as arcs 6, 7 and 8, connect to only one node in
the network. These arcs carry variable external flows. Arcs 7 and 8 provide
for flow coming into nodes 2 and 1, respectively. Arc 6 allows flow to
leave the network at node 3. The negative cost on arc 6 represents a revenue.
All lower bounds on flow take the default value of zero
and all arc gains are 1. This program works for generalized networks,
where gains may be other than 1, but that is described in a later section.
The
First Arc Display
(Click on the title to see a separate window with the
arc display)
The arc display created by the program is shown in the window.
We have entered the arc parameters for the example, but have not yet clicked
on the Iterate button. The 4 arcs appearing at the bottom of the list
are "artificial arcs". They are used to obtain an initial feasible
solution. The yellow area on the upper left provides data for the program
and should not be changed by the student. In general all yellowed areas
hold data or formulas and should not be modified.
The program only solves minimization problems. The yellow
area under the word Min shows the objective function value. The Phase
entry shows the current phase of the two phase simplex procedure. The
Iter. entry shows the current iteration number and the Status provides
a running status of the solution.
The columns of the Arc Information section hold the data
describing the network model. The column labeled Cost 1, carries the costs
used for Phase 1 of the procedure. The column labeled Flow gives the arc
flows. The program will put the algorithm results in this column. We discuss
the columns labeled Optimality Information later. They have no meaning
for this first screen display.
The First Node
Display
The node display starts in column O of the worksheet. The fixed flows
of the model are in column Q, labeled Fixed. The other columns are described
later. Notice that there are now 5 nodes, where the original network had
only four. The new node is called the slack node. The artificial arcs
all start at the slack node.
