07.pdf

CHAPTER 7: NETWORK FLOW MODELS Overview 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 netw...

CHAPTER 7: NETWORK FLOW MODELS Overview 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. 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. Learning Outcomes At the end of this lesson students must be able to; 1. Differentiate the netwok components and apply computer solutions for the problem 2. Learn the process of building a flow of network and its components COURSE MATERIALS 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. 85 Figure 7.1 Network of railroad routes 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. 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 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. For example, the Stagecoach Shipping Company transports oranges by six trucks from Los Angeles to six cities in the West and Midwest. The different routes between Los Angeles and the destination cities and the length of time, in hours, required by a truck to travel each route are shown in Figure 7.2. 86 Figure 7.2 Shipping routes from Los Angeles The shipping company manager wants to determine the best routes (in terms of the minimum travel time) for the trucks to take to reach their destinations. This problem can be solved by using the shortest route solution technique. In applying this technique, it is convenient to represent the system of truck routes as a network, as shown in Figure 7.3. Figure 7.3 Network of shipping routes To repeat our objective as it relates to Figure 7.3, we want to determine the shortest routes from the origin (node 1) to the six destinations (nodes 2 through 7). The Shortest Route Solution Approach We begin the shortest route solution technique by starting at node 1 (the origin) and determining the shortest time required to get to a directly connected (i.e., adjacent) node. The three nodes directly connected to node 1 are 2, 3, and 4, as shown in Figure 7.4. Of these three nodes, the shortest time is 9 hours to node 3. Thus, we have determined our first shortest route from nodes 1 to 3 (i.e., from Los Angeles to Phoenix). We will now refer to nodes 1 and 3 as the permanent set to indicate that we have found the shortest route to these nodes. (Because node 1 has no route to it, it is automatically in the permanent set.) 87 Figure 7.4 Network with node 1 in the permanent set Notice in Figure 7.4 that the shortest route to node 3 is drawn with a heavy line, and the shortest time to node 3 (9 hours) is enclosed by a box. The table accompanying Figure 7.4 describes the process of selecting the shortest route. The permanent set is shown to contain only node 1. The three branches from node 1 are 1–2, 1–4, and 1–3, and this last branch has the minimum time of 9 hours. Next, we will repeat the foregoing steps used to determine the shortest route to node 3. First, we must determine all the nodes directly connected to the nodes in the permanent set (nodes 1 and 3). Nodes 2, 4, and 6 are all directly connected to nodes 1 and 3, as shown in Figure 7.5. Figure 7.5 Network with nodes 1 and 3 in the permanent set The next step is to determine the shortest route to the three nodes (2, 4, and 6) directly connected to the permanent set nodes. There are two branches starting from node 1 (1–2 and 1–4) and two branches from node 3 (3–4 and 3–6). The branch with the shortest time is to node 2, with a time of 16 hours. Thus, node 2 becomes part of the permanent set. Notice in our computations accompanying Figure 7.5 that the time to node 6 (branch 3–6) is 31 hours, which is determined by adding the branch 3–6 time of 22 hours to the shortest route time of 9 hours at node 3. As we move to the next step, the permanent set consists of nodes 1, 2, and 3. This indicates that we have found the shortest route to nodes 1, 2, and 3. We must now determine which nodes are directly connected to the permanent set nodes. Node 5 is the only adjacent node not currently connected to the permanent set, so it is connected directly to node 2. In addition, node 88 4 is now connected directly to node 2 (because node 2 has joined the permanent set). These additions are shown in Figure 7.6. Figure 7.6 Network with nodes 1, 2 and 3 in the permanent set Five branches lead from the permanent set nodes (1, 2, and 3) to their directly connected nodes, as shown in the table accompanying Figure 7.6. The branch representing the route with the shortest time is 3–4, with a time of 24 hours. Thus, we have determined the shortest route to node 4, and it joins the permanent set. Notice that the shortest time to node 4 (24 hours) is the route from node 1 through node 3. The other routes to node 4 from node 1 through node 2 are longer; therefore, we will not consider them any further as possible routes to node 4. To summarize, the shortest routes to nodes 1, 2, 3, and 4 have all been determined, and these nodes now form the permanent set. Next, we repeat the process of determining the nodes directly connected to the permanent set nodes. These directly connected nodes are 5, 6, and 7, as shown in Figure 7.7. Notice in Figure 7.7 that we have eliminated the branches from nodes 1 and 2 to node 4 because we determined that the route with the shortest time to node 4 does not include these branches. Figure 7.7 Network with nodes 1, 2, 3, and 4 in the permanent set From the table accompanying Figure 7.7 we can see that of the branches leading to nodes 5, 6, and 7, branch 3–6 has the shortest cumulative time, of 31 hours. Thus, node 6 is added to our permanent set. This means that we have now found the shortest routes to nodes 1, 2, 3, 4, and 6. 89 Repeating the process, we observe that the nodes directly connected (adjacent) to our permanent set are nodes 5 and 7, as shown in Figure 7.8. (Notice that branch 4–6 has been eliminated because the best route to node 6 goes through node 3 instead of node 4.) Figure 7.8 Network with nodes 1, 2, 3, 4, and 6 in the permanent set Of the branches leading from the permanent set nodes to nodes 5 and 7, branch 4–5 has the shortest cumulative time, of 38 hours. Thus, node 5 joins the permanent set. We have now determined the routes with the shortest times to nodes 1, 2, 3, 4, 5, and 6 (as denoted by the heavy branches in Figure 7.8). The only remaining node directly connected to the permanent set is node 7, as shown in Figure 7.9. Of the three branches connecting node 7 to the permanent set, branch 4–7 has the shortest time, of 43 hours. Therefore, node 7 joins the permanent set. Figure 7.9 Network with nodes 1, 2, 3, 4, 5, and 6 in the permanent set The routes with the shortest times from the origin (node 1) to each of the other six nodes and their corresponding travel times are summarized in Figure 7.10 and Table 7.1. Figure 7.10 Network with optimal routes from Los Angeles to all destination 90 Table 7.1 Shortest travel time from origin to destination Steps of the shortest route solution method 1. Select the node with the shortest direct route from the origin. 2. Establish a permanent set with the origin node and the node that was selected in step 1. 3. Determine all nodes directly connected to the permanent set nodes. 4. Select the node with the shortest route (branch) from the group of nodes directly connected to the permanent set nodes. 5. Repeat steps 3 and 4 until all nodes have joined the permanent set. Computer Solution of the Shortest Route Problem with QM for Windows QM for Windows includes modules for each of the three network flow models that will be presented in this chapter—shortest route, minimal spanning tree, and maximal flow. The QM for Windows solution for the shortest route from node 1 to node 7 for the Stagecoach Shipping Company example is shown in Exhibit 7.1. 91 The solution screen in Exhibit 7.1 provides the shortest route from the start node, 1 (Los Angeles), to the end node, 7 (St. Louis). The shortest route from any node in the network to any other node can be determined by indicating the desired origin and destination nodes at the top of the solution screen. For example, the shortest route from node 1 to node 5 is shown in Exhibit 7.2. Exhibit 7.2 Computer Solution of the Shortest Route Problem with Excel We can also solve the shortest route problem with Excel spreadsheets by formulating and solving the shortest route network as a 0–1 integer linear programming problem. To formulate the linear programming model, we first define a decision variable for each branch in the network, as follows: xij = 0 if branch i-j is not selected as part of the shortest route and 1 if branch i-j is selected. To reduce the complexity and size of our model formulation, we will also assume that items can flow only from a lower node number to a higher node number (e.g., 3 to 4 but not 4 to 3). This greatly reduces the number of variables and branches to consider. The objective function is formulated by minimizing the sum of the multiplication of each branch value and the travel time for each branch: There is one constraint for each node, indicating that whatever comes into a node must also go out. This is referred to as conservation of flow. This means that one ―truck‖ leaves node 1 (Los Angeles) either through branch 1–2, branch 1–3, or branch 1–4. This constraint for node 1 is formulated as x12 + x13 + x14 = 1 At node 2, a truck would come in through branch 1–2 and depart through 2–4 or 2–5, as follows: 92  x12 = x24 + x25 This constraint can be rewritten as x12 - x24 - x25 = 0 Constraints at nodes 3, 4, 5, 6, and 7 are constructed similarly, resulting in the complete linear programming model, summarized as follows: This model is solved in Excel much the same way as any other linear programming problem, using ―Solver‖. Exhibit 7.3 shows an Excel spreadsheet set up to solve the Stagecoach Shipping Company example. The decision variables, xij, are represented by cells A6:A17. Thus, a value of 1 in one of these cells means that branch has been selected as part of the shortest route. Cells F6:F17 contain the travel times (in hours) for each branch, and the objective function formula is contained in cell F18, shown on the formula bar at the top of the screen. The model constraints reflecting the flow through each node are included in the box on the right side of the spreadsheet. For example, cell I6 contains the constraint formula for node 1, =A6+A7+A8, and cell I7 contains the constraint formula for node 2, =A6-A9-A10. Exhibit 7.3 93 Exhibit 7.4 shows the Solver Parameters screen, which is accessed from the ―Data‖ tab at the top of the screen. Notice that the constraint for node 1 embedded in cell I6 equals 1, indicating that one truck is leaving node 1, and the constraint for node 7, embedded in cell I12, also equals 1, indicating that one truck will end up at node 7. This is an integer programming model, so be sure to click on ―Options‖ and deactivate the ―Ignore Integer Constraints‖ button. Exhibit 7.4 The Excel solution is shown in Exhibit 7.5. Notice that cells A7, A11, and A15 have values of 1 in them, indicating that these branches, 1–3, 3–4, and 4–7, are on the shortest route. The total distance in travel time is 43 hours, as shown in cell F18. Exhibit 7.5 94 The Minimal Spanning Tree Problem The minimal spanning tree problem is to connect all nodes in a network so that the total branch lengths are minimized. The resulting network spans (connects) all the points in the network at a minimum total distance (or length). A tree has one path joins any two vertices. A spanning tree of a graph is a tree that: Contains all the original graph’s vertices. Reaches out to (spans) all vertices. Is acyclic. In other words, the graph doesn’t have any nodes which loop back to itself. Example The Metro Cable Television Company is to install a television cable system in a community consisting of seven suburbs. Each of the suburbs must be connected to the main cable system. The cable television company wants to lay out the main cable network in a way that will minimize the total length of cable that must be installed. The possible paths available to the cable television company (by consent of the town council) and the feet of cable (in thousands of feet) required for each path are shown in this figure: 95 Steps of the minimal spanning tree solution method are as follows: 1. Select any starting node (conventionally, node 1 is selected). 2. Select the node closest to the starting node to join the spanning tree. 3. Select the closest node not currently in the spanning tree. 4. Repeat step 3 until all nodes have joined the spanning tree. The Maximal Flow Problem There are network problems in which the branches of the network have limited flow capacities. The objective of these networks is to maximize the total amount of flow from an origin to a destination. These problems are referred to as maximal flow problems. Maximal flow problems can involve the flow of water, gas, or oil through a network of pipelines; the flow of forms through a paper processing system (such as a government agency); the flow of traffic through a road network; or the flow of products through a production line system. In each of these examples, the branches of the network have limited and often different flow capacities. Given these conditions, the decision maker wants to determine the maximum flow that can be obtained through the system. An example of a maximal flow problem is illustrated by the network of a railway system between Omaha and St. Louis shown in Figure 7.18. The Scott Tractor Company ships tractor parts from Omaha to St. Louis by railroad. However, a contract limits the number of railroad cars the company can secure on each branch during a week. Figure 7.18 Network of railway systems Given these limiting conditions, the company wants to know the maximum number of railroad cars containing tractor parts that can be shipped from Omaha to St. Louis during a week. The number of railroad cars available to the tractor company on each rail branch is indicated by the number on the branch to the immediate right of each node (which represents a rail junction). For example, six cars are available from node 1 (Omaha) to node 2, eight cars are available from node 2 to node 5, five cars are available from node 4 to node 6 (St. Louis), and so forth. The number on each branch to the immediate left of each node is the number of cars available for shipping in the opposite direction. For example, no cars are available from node 2 to node 1. The branch from node 1 to node 2 is referred to as a directed branch because flow is possible in only one direction (from node 1 to node 2, but not from 2 to 1). Notice that flow is possible in both directions on the branches between nodes 2 and 4 and nodes 3 and 4. These are referred to as undirected branches. 96 The Maximal Flow Solution Approach The first step in determining the maximum possible flow of railroad cars through the rail system is to choose any path arbitrarily from origin to destination and ship as much as possible on that path. In Figure 7.19, we will arbitrarily select the path 1–2–5–6. The maximum number of railroad cars that can be sent through this route is four. We are limited to four cars because that is the maximum amount available on the branch between nodes 5 and 6. This path is shown in Figure 7.19. Notice that the remaining capacities of the branches from node 1 to node 2 and from node 2 to node 5 are now two and four cars, respectively, and that no cars are available from node 5 to node 6. These values were computed by subtracting the flow of four cars from the original number available. The actual flow of four cars along each branch is shown enclosed in a box. Notice that the present input of four cars into node 1 and output of four cars from node 6 are also designated. The final adjustment on this path is to add the designated flow of four cars to the values at the immediate left of each node on our path, 1–2–5–6. These are the flows in the opposite direction. Thus, the value 4 is added to the zeros at nodes 2, 5, and 6. It may seem incongruous to designate flow in a direction that is not possible; however, it is the means used in this solution approach to compute the net flow along a branch. (If, for example, a later iteration showed a flow of one car from node 5 to node 2, then the net flow in the correct direction would be computed by subtracting this flow of one in the wrong direction from the previous flow of four in the correct direction. The result would be a net flow of three in the correct direction.) We have now completed one iteration of the solution process and must repeat the preceding steps. Again, we arbitrarily select a path. This time we will select path 1–4–6, as shown in Figure 7.20. The maximum flow along this path is four cars, which is subtracted at each of the nodes. This increases the total flow through the network to eight cars (because the flow of four along path 1–4–6 is added to the flow previously determined in Figure 7.19). As a final step, the flow of four cars is added to the flow along the path in the opposite direction at nodes 4 and 6. 97 Now, we arbitrarily select another path. This time, we will choose path 1–3–6, with a maximum possible flow of six cars. This flow of six is subtracted from the branches along path 1–3–6 and added to the branches in the opposite direction, as shown in Figure 7.21. The flow of 6 for this path is added to the previous flow of 8, which results in a total flow of 14 railroad cars. Notice that at this point the number of paths we can take is restricted. For example, we cannot take the branch from node 3 to node 6 because zero flow capacity is available. Likewise, no path that includes the branch from node 1 to node 4 is possible. The available flow capacity along the path 1–3–4–6 is one car, as shown in Figure 7.22. This increases the total flow from 14 cars to 15 cars. The resulting network is shown in Figure 7.23. Close observation of the network in Figure 7.23 shows that there are no more paths with available flow capacity. All paths out of nodes 3, 4, and 5 show zero available capacity, which prohibits any further paths through the network. This completes the maximal flow solution for our example problem. The maximum flow is 15 railroad cars. The flows that will occur along each branch appear in boxes in Figure 7.23. Steps of the maximal flow solution method 1. Arbitrarily select any path in the network from origin to destination. 2. Adjust the capacities at each node by subtracting the maximal flow for the path selected instep 1. 3. Add the maximal flow along the path in the opposite direction at each node. 4. Repeat steps 1,2,and 3 until there are no more paths with available flow capacity. 98 Computer Solution of the Maximal Flow Problem with QM for Windows The program input and maximal flow solution for the Scott Tractor Company example using QM for Windows is shown in Exhibit 7.7. (Note that this problem has multiple optimal solutions, and the branch flows are slightly different for this solution.) Computer Solution of the Maximal Flow Problem with Excel The maximal flow problem can also be solved with Excel, much the same way as we solved the shortest route problem, by formulating it as an integer linear programming model and solving it by using ―Solver‖. The decision variables represent the flow along each branch, as follows: xij = flow along branch i-j and integer. To reduce the size and complexity of the model formulation, we will also eliminate flow along a branch in the opposite direction (e.g., flow from 4 to 2 is zero). Before proceeding with the model formulation and developing the objective function, we must alter the network slightly to be able to solve it as a linear programming problem. We will create a new branch from node 6 back to node 1, x61. The flow along this branch from the end of the network back to the start corresponds to the maximum amount that can be shipped from node 6 to node 1 and then back through the network to node 6. In effect, we are creating a continual flow through the network so that the most that goes through and comes out at node 6 is the most that can go through the network beginning at node 1. As a result, the objective is to maximize the amount that flows from node 6 back to node 1: maximize Z = x61 The constraints follow the same premise as the shortest route problem; that is, whatever flows into a node must flow out. Thus, at node 1, we have the following constraint, showing that the amount flowing from 6–1 must flow out through branches 1–2, 1–3, and 1–4: x61 = x12 + x13 + x14 This constraint can be rewritten as x61 – x12 – x13 – x14 = 0 99 Similarly, the constraint at node 2 is written as x12 – x24 – x25 = 0 We must also develop a set of constraints reflecting the capacities along each branch, as follows: The capacity for x61 can be any relatively large number (compared to the other branch capacities); we set it at the sum of the capacities on the branches leaving node 1. The complete linear programming model for our Scott Tractor Company example is summarized as follows: The Excel spreadsheet set up to solve this integer linear programming model for the Scott Tractor Company example is shown in Exhibit 7.8. The decision variables, xij, are represented by cells C6:C15. Cells D6:D15 include the branch capacities. The objective function, which is to maximize the flow along branch 6–1, is included in cell C16. The model constraints reflecting the flow through each node are included in the box on the right side of the spreadsheet. For example, cell G6 contains the constraint formula at node 1, =C15-C6-C7-C8, and cell G7 contains the constraint formula for node 2, =C6-C9-C10. The constraints for the branch capacities are obtained by adding the formula C6:C15 ≤ D6:D15 in Solver in Exhibit 7.9. 100 Exhibit 7.9 shows the Solver Parameters screen for this model. The Excel solution is shown in Exhibit 7.10. Notice that the flows along each branch are shown 101 in cells C6:C15 and the total network flow is 15 in cell C16. Activities/Assessments I. Answer the following: ___________ 1. The purpose of a _______ is to determine the shortest distance, shortest length of time, or lowest cost between points in the network. ___________ 2. The goal in the __________________ problem is to connect all nodes in a network so that the total branch lengths are minimized. ___________ 3. The _____________________ determines the shortest distance between an originating point and several destination points ___________ 4. Networks are illustrated as diagrams consisting of ________ and ________. ___________ 5. This type of a network problem occurs due to is the branches of the network have limited flow capacities. II. Application 1. Draw a simple network flow for the following situations a. Toll highway with one entry and five various destinations. A tll booth must be setup in every exit 2. Apply network analysis in these two situations a. Road constructions b. Accounting system in a company Supply the necessary data all are fictitious including constraints 102