GS 2006/Math - Collins

Lab 3
Network Flow


Preliminaries

This is the first application lab. The goal is to look at some real-world type problems and understand ways to represent them in terms of things we are studying (like matrices). Then we can use the techniques we know to solve the mathematical problem and then interpret the answer in terms of the original problem.

At the end of the lab are a series of exercises for you to complete and turn in. Hopefully you can get this done in one day, but if not you can return to it later either during open lab time or before or after class.

Network Flow

Network
A network consists of a set of points (junctions, nodes, ...) and lines connecting some of the points. The lines (or branches) each has a direction of flow and a value for the flow amount (either known or unknown). For example, in this figure

there is 1 junction and three branches. One branch has a flow amount of 25 and the other 2 are unknow but labeled as x and y.
Flow Rules
The rule that every flow satisfies is the conservation law. At every junction, the flow in equals the flow out. Thus in our example above, we know that
25 = x + y.
For particular types of networks there may be additional rules.
Traffic Flow
Consider the following configuration of one-way streets with flow values:

For traffic flow the only rule is conservation, thus examining the 4 junctions, we have 4 equations:
E + D = A + 600
A + 300 = B + 700
C + 300 = D + 200
B + 500 = C + 100
We can rewrite this as a linear system of equations:
-A + D + E = 600
A - B = 400
C - D = -100
B - C = -400
Either using MATLAB or by hand, solve this system. Either way you should put it in augmented form and then find the row-reduced form of the augmented matrix. You should get this
     1     0     0    -1     0  -100
     0     1     0    -1     0  -500
     0     0     1    -1     0  -100
     0     0     0     0     1   500
Thus we can conclude that E = 500 and that A = D - 100, B = D - 500 and C = D - 100, where D is free. Since we want all the flows to be positive we see that we need D > 500.
Now we can use this solution to answer some questions. See if you can use this solution to answer these questions:
  1. Suppose we need to work on road B, can we close it down completely? If not, what is the least amount of traffic we can have on that road?
  2. Same question, but for road C.
  3. Same question, but for road E.
Answers: (1) Yes, if B = 0, then D = 500 and all the other flows are positive. (2) No, since D > 500, we must have C > 400, thus the least we can have is 400. (3) No, there is an overall conservation of flow into the city equals flow out and thus we must have E = 500.
Electrical Networks
Read Section 11.2 in the book. Besides conservation (known as Kirchoff's Current Law) we have to use Ohm's Law and Kirchoff's Voltage Law to get our system of equations.

Exercises

1. For this English roundabout, find the general solution and find the smallest possible value for each flow amount:

2. Design and solve a traffic flow problem.
3. Exercise 1 in Section 11.2
4. Exercise 4 in Section 11.2


Print out your solutions with your name and turn it in to Dr. Collins or Eliza.

Mail: ccollins@math.utk.edu