Flow: From Traffic to Pipes - An Application of Linear Algebra

The most practical applications of mathematics are those that apply to the most people. When it comes to linear algebra, one wide-reaching application is to the problem of flow. Whether it is data through a network, water through pipes, or cars through traffic, arranging an efficient flow is a crucial element of design. Just these three examples already show that solving flow problems is a wide topic that has relevance in many aspects of everyday life.

Many of the problems that arise with networks and traffic involve optimizing the flow through the system. This can be done in many ways and depends a lot on the particular situation. However, by looking at systems of linear equations, we can simplify flow problems. Linear algebra allows us to study these systems using matrices and determine which variables have forced values and which are free to be chosen. After this distinction has been made using linear algebra, we can use other techniques to choose the free variables.

In order to begin understanding these types of problems, it is best to look at a simple example. Consider a system of streets with traffic flow as described in the diagram below, where each number represents the number of cars passing through in one hour. In order to optimize traffic flow, the city planners need to determine how to set the traffic lights and how many cars to let through streets A, B, C, D, and E each hour.

First, the picture yields the following four equations:

B + E = 20 + A

C + 30 = B + 40

60 = C + D

D = E + 15

Next, the equations can be rearranged:

-A + B + E = 20

-B + C = 10

C + D = 60

D - E = 15

Now they can be placed into a matrix:

After row-reducing, the matrix becomes:

Finally, this gives four new equations:

A = 15

B + E = 35

C + E = 45

D - E = 15

From these equations, the city planners can see that A must be 15 cars per hour but they have some choice for the other streets. If they set E at 10 cars per hour, for example, B must be 25, C must be 35, and D must be 25. As another example, consider shutting down E street completely. Then it follows that B = 35, C = 45, and D = 15. And if the city reverses the direction of traffic flow on E and then allows 20 cars per hour the other streets are affected as follows: B = 55, C = 65, and D also changes direction and must admit 5 cars per hour.

When looking at the other applications mentioned earlier, such as data through a network or water through pipes, the system can be set up similarly. The reason that linear algebra is so key in solving these types of problems is that it allows for solving many linear equations simultaneously. Matrices use the symmetry of the equations to solve for the variables.

Now that it is clear how useful linear algebra can be in this application, it is important to look at the process in much more detail.

The Process

The first step is to come up with equations after looking at the picture, or actual situation. For a more general map, there needs to be one equation for each node on the graph. A node is a point where two or more lines intersect. At each node, the incoming traffic or flow needs to equal the outgoing traffic or flow.

The second step is to rearrange these equations in order to get the constant on one side and all of the variables on the other side. This is a very simple process and can be done with general algebra knowledge.

The third step is to create a matrix. This step is a little bit more involved. Matrices are measured by how many rows and columns they have. In general, we call a matrix with m rows and n columns an m-by-n matrix . The number of equations from steps 1 and 2 will be the number of rows the matrix has and the number of columms will be equal to the number of variables plus 1. Next, the matrix needs to be filled in. Each column of the matrix corresponds to one variable, so the coefficients of that variable in each respective equation should be filled in that column. The final column will contain the constants from each equation.

The fourth step is to row-reduce the matrix. There are four rules that have to be followed:

The Four Rules:

1. All nonzero rows must have a 1 as the furthest left nonzero entry (called a leading 1).

2. All columns containing leading 1s must have only zeros everywhere else.

3. All leading 1st must be further to the right than leading 1s in the above rows.

4. All rows containing only zeros must be at the bottom.

This step can be accomplished by using the three elementary row operations below:

The Three Operations:

A. Any two rows can be switched.

B. A row can be multiplied by a nonzero constant, if each element of the row is multiplied by the same constant.

C. A row can be replaced by the sum of itself plus another row.

The fifth step is to convert this matrix back into linear equations by using the reverse process of step 3 and using the entries in the matrix to determine the coefficients of the variables and the constants in the equations.

Now these equations can be used to see which variables have forced values and which are free to be chosen. Depending on the goal of the exercise, different methods can be used to choose the free variables. Free variables exist when there are more variables than there are equations. In the above example, we had five variables, but only four equations (because there were four nodes).

In problems involving data flowing through networks, a key issue that arises is efficiency and speed of travel, but also having a large amount of data traveling at once. When it comes to water flowing through pipes, the capacity of the pipes needs to be taken into consideration, and also any valves that might restrict flow to only one direction. For street traffic, the needs of the intersections might be dependent on time, capacity, direction, or a number of other factors. In all three situations, cost can also play a large role as companies and cities always need to reduce costs. The strength of linear algebra is that it is broad enough to be used in any and all of these possible situations and can be applied to help solve all of these issues.

Linear algebra can be used to solve increasingly more complex systems of equations, with hundreds or even thousands of variables. The reason linear algebra is so useful for these types of problems is that it can be thought of as an algorithm and the steps can be used in a computer program to facilitate the process. Many programmers use matrices to store and manipulate data due to these reasons. The concepts explained here can be applied to a variety of situations in the real world.

A Last Example

Now examine the following pipe flow problem:

One optimization problem could be to maximize the quantity of water flowing through pipe B. Using the process described above, the picture can be transformed into four equations, which can in turn be turned into a matrix. After row reduction, the following four equations will be apparent:

A + E = 60

B - F = 80

C - D = -10

D + E + F = 0

Because the goal in this particular situation is maximizing B, the focus should be on the equation involving B. Because B and F are output pipes, F cannot have negative flow. Therefore the minimum flow F can have is zero, making the maximum value for B equal to 80. Interestingly, the flow through B does not actually depend on A or D even though those pipes interact with the same node as B.

In the real world, it frequently occurs where many variables are not significant to the final solution of the system. It all depends on what the network is designed to do and what parameters are relevant. There are many directions in which to take this application.

Sami Prehn

Bucknell University

Math 345, Fall 2009

This template was provided free at www.free-templates.org