When learning to use network models, it is helpful to recognize
several special cases of network flow programming. These are
the transportation, assignment, shortest path, and maximum
flow models. The problems differ primarily in the set of arc
parameters that are relevant or the arrangement of nodes and
arcs. For example, for the transportation model only the arc
costs are relevant and all arcs originate at one set of nodes
and terminate at another. We describe in this section the
classes in terms of the network model defined above and note
that for each only a subset of the parameters is relevant.
All irrelevant parameters will take on the default values.
For the special network models of this section we set the
parameter default values as: 0 for the lower bound, M (a large
number) for the upper bound, 0 for the cost, and 1 for the
Using the default values for parameters, all of the classes
can be solved using algorithms defined for the more general
case. There are, however, a number of algorithms for solving
each class that do not use the irrelevant parameters at all.
In this way the special case algorithms can be more efficient
than the more general ones. Fig. 8 shows the relationships
between the various network flow programming models and linear
programming. The models on the left are the least general.
As we move to the right, the problems become more general.
Thus all the problems to the left of the generalized minimum
cost flow problem can be solved with an algorithm designed
for the generalized problem. The generalized problem is itself
a special case of the linear program.