Chapter 8 provided examples of a number of managerial problems that could be modeled using linear programming (LP), and this chapter will provide even more such examples. However, all of the problems in this chapter can be modeled as networks as well as linear programs. The use of networks helps in visualizing and understanding the managerial problem. These models include the transportation problem, the transshipment problem, the assignment problem, the maximal-flow problem, the shortest-route problem, and the minimal-spanning tree problem. The use of linear programming software will be the primary means of solving these problems in this chapter. However, to take advantage of the unique structure of some of these problems, specialized algorithms have been developed to solve very large problems more quickly and efficiently. These algorithms are presented on the Companion Website for this textbook in Module 8.

The basic transportation problem is concerned with finding the best (usually least-cost) way to distribute goods from sources, such as factories, to final destinations, such as retail outlets. If there are intermediate points, such as regional distribution centers, where the items must go before being shipped to the final destination, then the transportation problem becomes a transshipment problem. The assignment problem involves finding the best (usually least-cost) way to assign individuals or pieces of equipment to projects or jobs on a one-to-one basis. In other words, each person is assigned to only one job, and each job only needs one person assigned to it.

The maximal-flow technique finds the maximum flow of any quantity or substance through a network. This technique can determine, for example, the maximum number of vehicles (cars, trucks, and so forth) that can go through a network of roads from one location to another. The shortest-route technique can find the shortest path through a network. For example, this technique can find the shortest route from one city to another through a network of roads. The minimal-spanning tree technique determines the path through the network that connects all the points while minimizing total distance. When the points represent houses in a subdivision, the minimal-spanning tree technique can be used to determine how to connect all of the houses to electrical power, water systems, and so on, in a way that minimizes the total distance or length of power lines or water pipes.

While there are many different types of examples in this chapter, some terminology is common to all of the network models. The points on the network are referred to as nodes and the lines on the network that connect these nodes are called arcs. Typically nodes are presented as circles, although sometimes squares or rectangles are used for the nodes.