Return to Index
Operations Research Models and Methods
Models Section
Special Cases

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 gain.

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.

Figure 8. The relationships between network problems.

Return to Top

tree roots

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