Network flow models

316 Chapter 7   Network Flow Models A network is an arrangement of paths connected at various points, through which items move. Networks are popular because they provide a picture of a system and because a large number of systems can be easily modeled as networks. Network flow models describe the flow of items through a system. Nodes, denoted by circles, represent junction points connecting branches. Branches, represented as lines, connect nodes and show flow from one point to another. A network is an arrangement of paths connected at various points, through which one or more items move from one point to another. Everyone is familiar with such networks as highway systems, telephone networks, railroad systems, and television networks. For example, a railroad network consists of a number of fixed rail routes (paths) connected by terminals at various ­junctions of the rail routes. In recent years, using network models has become a very popular management science technique for a couple of very important reasons. First, a network is drawn as a diagram, which literally provides a picture of the system under analysis. This enables a manager to visually interpret the system and thus enhances the manager’s understanding. Second, a large number of real-life systems can be modeled as networks, which are relatively easy to conceive and construct. In this and the next chapter, we will look at several different types of network models. In this chapter, we will present a class of network models directed at the flow of items through a system. As such, these models are referred to as network flow models. We will discuss the use of network flow models to analyze three types of problems: the shortest route problem, the minimal spanning tree problem, and the maximal flow problem. In Chapter 8, we will present the network techniques PERT and CPM, which are used extensively for project analysis. Network Components Networks are illustrated as diagrams consisting of two main components: nodes and branches. Nodes represent junction points—for example, an intersection of several streets. Branches connect the nodes and reflect the flow from one point in the network to another. Nodes are denoted in the network diagram by circles, and branches are represented by lines connecting the nodes. Nodes typically represent localities, such as cities, intersections, or air or railroad terminals; branches are the paths connecting the nodes, such as roads connecting cities and intersections or railroad tracks or air routes connecting terminals. For example, the different railroad routes between Atlanta, Georgia, and St. Louis, Missouri, and the intermediate terminals are shown in Figure 7.1. Figure 7.1 Network of railroad routes Nashville 2 St. Louis 6 4 1 Atlanta 4 5 3 3 Memphis The network shown in Figure 7.1 has four nodes and four branches. The node representing Atlanta is referred to as the origin, and any of the three remaining nodes could be the destination, depending on what we are trying to determine from the network. Notice that a number has been assigned to each node. Numbers provide a more convenient means of identifying the nodes and branches than do names. For example, we can refer to the origin (Atlanta) as node 1 and the branch from Atlanta to Nashville as branch 1–2. Typically, a value that represents a distance, length of time, or cost is assigned to each branch. Thus, the purpose of the network is to determine the shortest distance, shortest length The Shortest Route Problem     317 The values assigned to branches typically represent distance, time, or cost. The shortest route problem is to find the shortest distance between an origin and various destination points. of time, or lowest cost between points in the network. In Figure 7.1, the values 4, 6, 3, and 5, corresponding to the four branches, represent the lengths of time, in hours, between the attached nodes. Thus, a traveler can see that the route to St. Louis through Nashville requires 10 hours and the route to St. Louis through Memphis requires 8 hours. The Shortest Route Problem The shortest route problem is to determine the shortest distance between an originating point and several destination points.