- (a)
-
- (b)
-
Click the arrow to see the answer.
, , parameters
Application to Network Flow
There are many types of problems that concern a network of conductors along which some sort of flow is observed. Examples of these include an irrigation network and a network of streets or freeways. There are often points in the system at which a net flow either enters or leaves the system. The basic principle behind the analysis of such systems is that the total flow into the system must equal the total flow out. In fact, we apply this principle at every junction in the system.
Junction Rule At each of the junctions in the network, the total flow into that
junction must equal the total flow out.
This requirement gives a linear equation relating the flows in conductors emanating from the junction.
A network of one-way streets is shown in the accompanying diagram. The rate of
flow of cars into intersection is 500 cars per hour, and 400 and 100 cars per
hour emerge from and , respectively. Find the possible flows along each
street.
Suppose the flows along the streets are , , , , , and cars per hour in the directions
shown.
Then, equating the flow in with the flow out at each intersection, we get \begin{equation*} \begin{array}{lrl} \mbox{Intersection } A & 500 & = f_1 + f_2 + f_3 \\ \mbox{Intersection } B & \quad f_1 + f_4 + f_6 & = 400 \\ \mbox{Intersection } C & f_3 + f_5 & = f_6 + 100 \\ \mbox{Intersection } D & f_2 & = f_4 + f_5 \\ \end{array} \end{equation*} These give four equations in the six variables . \begin{equation*} \begin{array}{rlrlrlrlrlrcr} f_1 & + & f_2 & + & f_3 & & & & & & & = & 500 \\ f_1 & & & & & + & f_4 & & & + & f_6 & = & 400 \\ & & & & f_3 & & & + & f_5 & - & f_6 & = & 100 \\ & & f_2 & & & - & f_4 & - & f_5 & & & = & 0 \\ \end{array} \end{equation*} The reduction of the augmented matrix is \begin{equation*} \left [ \begin{array}{rrrrrr|r} 1 & 1 & 1 & 0 & 0 & 0 & 500 \\ 1 & 0 & 0 & 1 & 0 & 1 & 400 \\ 0 & 0 & 1 & 0 & 1 &-1 & 100 \\ 0 & 1 & 0 &-1 &-1 & 0 & 0 \end{array} \right ] \rightarrow \left [ \begin{array}{rrrrrr|r} 1 & 0 & 0 & 1 & 0 & 1 & 400 \\ 0 & 1 & 0 &-1 &-1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 &-1 & 100 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right ] \end{equation*} Hence, when we use , , and as parameters, the general solution is \begin{equation*} f_1 = 400 - f_4 - f_6 \quad \quad f_2 = f_4 + f_5 \quad \quad f_3 = 100 - f_5 + f_6 \end{equation*} This gives all solutions to the system of equations and hence all the possible flows.
Of course, not all these solutions may be acceptable in the real situation. For example, the flows are all positive in the present context (if one came out negative, it would mean traffic flowed in the opposite direction). This imposes constraints on the flows: and become \begin{equation*} f_4 + f_6 \leq 400 \quad \quad f_5 - f_6 \leq 100 \end{equation*} Further constraints might be imposed by insisting on maximum values on the flow in each street.
Practice Problems
Find the possible flows in each of the following networks of pipes.
A proposed network of irrigation canals is described in the accompanying diagram.
At peak demand, the flows at interchanges , , , and are as shown.
- (a)
- Find the possible flows.
- (b)
- If canal is closed, what range of flow on must be maintained so that no
canal carries a flow of more than 30?
Click the arrow to see the answer.
A traffic circle has five one-way streets, and vehicles enter and leave as shown in the
accompanying diagram.
- (a)
- Compute the possible flows.
- (b)
- Which road has the heaviest flow?
AB BC CD DE EA
Text Source
This application was adapted from Section 1.4 of Keith Nicholson’s Linear Algebra with Applications. (CC-BY-NC-SA)
W. Keith Nicholson, Linear Algebra with Applications, Lyryx 2018, Open Edition, p. 27
2024-09-11 17:54:32