Extra Topic: Applications of Systems of Linear Equations

Section 2.4 Extra Topic: Applications of Systems of Linear Equations

Subsection 2.4.1 Network Flows

This section was adapted from Sections 1.4 and 1.5 of Keith Nicholson’s Linear Algebra with Applications

open.umn.edu/opentextbooks/textbooks/linear-algebra-with-applications

. (CC-BY-NC-SA)

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.

Theorem 2.4.1. 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.

Example 2.4.2.

A network of one-way streets is shown in the accompanying diagram. The rate of flow of cars into intersection $A$ is 500 cars per hour, and 400 and 100 cars per hour emerge from $B$ and $C\text{,}$ respectively. Find the possible flows along each street.

$Example of a network flow.$

Answer.

Suppose the flows along the streets are $f_1\text{,}$ $f_2\text{,}$ $f_3\text{,}$ $f_4\text{,}$ $f_5\text{,}$ and $f_6$ 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 \amp 500 \amp = f_1 + f_2 + f_3 \\ \mbox{Intersection } B \amp \quad f_1 + f_4 + f_6 \amp = 400 \\ \mbox{Intersection } C \amp f_3 + f_5 \amp = f_6 + 100 \\ \mbox{Intersection } D \amp f_2 \amp = f_4 + f_5 \\ \end{array} \end{equation*}

These give four equations in the six variables $f_1, f_2, \dots , f_6 \text{.}$

\begin{equation*} \begin{array}{rlrlrlrlrlrcr} f_1 \amp + \amp f_2 \amp + \amp f_3 \amp \amp \amp \amp \amp \amp \amp = \amp 500 \\ f_1 \amp \amp \amp \amp \amp + \amp f_4 \amp \amp \amp + \amp f_6 \amp = \amp 400 \\ \amp \amp \amp \amp f_3 \amp \amp \amp + \amp f_5 \amp - \amp f_6 \amp = \amp 100 \\ \amp \amp f_2 \amp \amp \amp - \amp f_4 \amp - \amp f_5 \amp \amp \amp = \amp 0 \\ \end{array} \end{equation*}

The reduction of the augmented matrix is

\begin{equation*} \left[ \begin{array}{rrrrrr|r} 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 500 \\ 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 400 \\ 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp -1 \amp 100 \\ 0 \amp 1 \amp 0 \amp -1 \amp -1 \amp 0 \amp 0 \end{array} \right] \rightarrow \left[ \begin{array}{rrrrrr|r} 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 400 \\ 0 \amp 1 \amp 0 \amp -1 \amp -1 \amp 0 \amp 0 \\ 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp -1 \amp 100 \\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \end{array} \right] \end{equation*}

Hence, when we use $f_4\text{,}$ $f_5\text{,}$ and $f_6$ 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 $f_1, f_2, \dots , f_6 $ 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: $f_1 \geq 0$ and $f_3 \geq 0$ 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.

Subsection 2.4.2 Electrical Networks

The circuit diagrams in this section were made using circuit-diagram.org.

In an electrical network it is often necessary to find the current in amperes ($A$) flowing in various parts of the network. These networks usually contain resistors that retard the current. Resistance is measured in ohms ($\Omega$). The current is increased at various points by voltage sources (for example, a battery). The voltage of these sources is measured in volts (V). We use the following symbols to represent resistors and voltage sources:

Example of a resistor and a network source.

We assume these voltage sources have no resistance. The flow of current is governed by the following principles.

Theorem 2.4.3. Ohm’s Law.

The current $I$ and the voltage drop $V$ across a resistance $R$ are related by the equation $V = RI\text{.}$\index{Ohm’s Law}

Theorem 2.4.4. Kirchhoff’s Laws.

Each of the following is true in an electric circuit.

(Junction Rule) The current flow into a junction equals the current flow out of that junction.
(Circuit Rule) The algebraic sum of the voltage drops (due to resistances) around any closed circuit of the network must equal the sum of the voltage increases around the circuit.

When applying the Circuit Rule, select a direction (clockwise or counterclockwise) around the closed circuit and then consider all voltages and currents positive when in this direction and negative when in the opposite direction. %This is why the term algebraic sum is used in rule 2. Here is an example.

Example 2.4.5.

Find the various currents in the circuit shown.

Answer.

First apply the junction rule at junctions $A\text{,}$ $B\text{,}$ $C\text{,}$ and $D$ to obtain

\begin{equation*} \begin{array}{lccccccc} \mbox{Junction } A:\quad \amp \amp \amp I_1 \amp = \amp I_2 \amp +\amp I_3 \\ \mbox{Junction } B:\quad \amp \amp \amp I_6 \amp = \amp I_1 \amp +\amp I_5 \\ \mbox{Junction } C:\quad \amp I_2 \amp +\amp I_4 \amp = \amp I_6 \amp \amp \\ \mbox{Junction } D:\quad \amp I_3 \amp +\amp I_5 \amp = \amp I_4\amp \amp \\ \end{array} \end{equation*}

Note that these equations are not independent (in fact, the third is an easy consequence of the other three).

Next, the circuit rule insists that the sum of the voltage increases (due to the sources) around a closed circuit must equal the sum of the voltage drops (due to resistances). By Ohm’s law, the voltage loss across a resistance $R$ (in the direction of the current $I$) is $RI\text{.}$ Going counterclockwise around three closed circuits yields

\begin{equation*} \begin{array}{lcccccccc} \mbox{Upper left: } \quad\quad \amp 10 \amp + \amp 5 \amp = \amp 20I_1 \amp \amp \\ \mbox{Upper right: } \amp -5 \amp +\amp 20 \amp = \amp 10I_3\amp +\amp 5I_4 \\ \mbox{Lower: } \amp \amp \amp -10 \amp = \amp -5I_5 \amp -\amp 5I_4 \\ \end{array} \end{equation*}

Hence, disregarding the redundant equation obtained at junction $C\text{,}$ we have six equations in the six unknowns $I_1, \dots, I_6\text{.}$ The solution is

\begin{equation*} \begin{array}{ccccccc} I_1\amp =\amp \frac{15}{20}\amp \quad\amp I_2 \amp =\amp \frac{-1}{20}\\ \amp \amp \amp \amp \amp \amp \\ I_3\amp =\amp \frac{16}{20}\amp \quad\amp I_4 \amp =\amp \frac{28}{20}\\ \amp \amp \amp \amp \amp \amp \\ I_5 \amp =\amp \frac{12}{20}\amp \quad\amp I_6 \amp =\amp \frac{27}{20} \end{array} \end{equation*}

The fact that $I_2$ is negative means, of course, that this current is in the opposite direction, with a magnitude of $\frac{1}{20}$ amperes.

Subsection 2.4.3 Chemical Equations

When a chemical reaction takes place a number of molecules combine to produce new molecules. Hence, when hydrogen $\mbox{H}_2$ and oxygen $\mbox{O}_2$ molecules combine, the result is water $\mbox{H}_2\mbox{O}\text{.}$ We express this as

\begin{equation*} \mbox{H}_2 + \mbox{O}_2 \rightarrow \mbox{H}_2\mbox{O} \end{equation*}

Individual atoms are neither created nor destroyed, so the number of hydrogen and oxygen atoms going into the reaction must equal the number coming out (in the form of water). In this case the reaction is said to be balanced. Note that each hydrogen molecule $\mbox{H}_2$ consists of two atoms as does each oxygen molecule $\mbox{O}_2\text{,}$ while a water molecule $\mbox{H}_2\mbox{O}$ consists of two hydrogen atoms and one oxygen atom. In the above reaction, this requires that twice as many hydrogen molecules enter the reaction; we express this as follows:

\begin{equation*} 2\mbox{H}_2 + \mbox{O}_2 \rightarrow 2\mbox{H}_2\mbox{O} \end{equation*}

This is now balanced because there are 4 hydrogen atoms and 2 oxygen atoms on each side of the reaction.

Example 2.4.6.

Balance the following reaction for burning octane $\mbox{C}_8\mbox{H}_{18}$ in oxygen $\mbox{O}_2\text{:}$

\begin{equation*} \mbox{C}_8\mbox{H}_{18} + \mbox{O}_2 \rightarrow \mbox{CO}_2 + \mbox{H}_2\mbox{O} \end{equation*}

where $\mbox{CO}_2$ represents carbon dioxide. We must find positive integers $x\text{,}$ $y\text{,}$ $z\text{,}$ and $w$ such that

\begin{equation*} x\mbox{C}_8\mbox{H}_{18} + y\mbox{O}_2 \rightarrow z\mbox{CO}_2 + w\mbox{H}_2\mbox{O} \end{equation*}

Equating the number of carbon, hydrogen, and oxygen atoms on each side gives $8x = z\text{,}$ $18x = 2w$ and $2y = 2z + w\text{,}$ respectively. These can be written as a homogeneous linear system

\begin{equation*} \begin{array}{rlrlrlrcr} 8x \amp \amp \amp - \amp z \amp \amp \amp = \amp 0 \\ 18x \amp \amp \amp \amp \amp - \amp 2w \amp = \amp 0 \\ \amp \amp 2y \amp - \amp 2z \amp - \amp w \amp = \amp 0 \end{array} \end{equation*}

which can be solved by gaussian elimination. In larger systems this is necessary but, in such a simple situation, it is easier to solve directly. Set $w = t\text{,}$ so that $x = \frac{1}{9}t\text{,}$ $z = \frac{8}{9}t\text{,}$ $2y = \frac{16}{9}t + t = \frac{25}{9}t\text{.}$ But $x\text{,}$ $y\text{,}$ $z\text{,}$ and $w$ must be positive integers, so the smallest value of $t$ that eliminates fractions is $18\text{.}$ Hence, $x = 2\text{,}$ $y = 25\text{,}$ $z = 16\text{,}$ and $w = 18\text{,}$ and the balanced reaction is

\begin{equation*} 2\mbox{C}_8\mbox{H}_{18} + 25\mbox{O}_2 \rightarrow 16\mbox{CO}_2 + 18\mbox{H}_2\mbox{O} \end{equation*}

The reader can verify that this is indeed balanced.

It is worth noting that this problem introduces a new element into the theory of linear equations: the insistence that the solution must consist of positive integers.

Exercises 2.4.4 Exercises

1.

Find the possible flows in each of the following networks of pipes.

$A network flow.$
$A network flow.$

Answer.

The answer to Item 2.4.4.1.b is

\begin{equation*} \begin{array}[t]{rcrrr} f_1 \amp = \amp 85 \amp - f_4 \amp - f_7 \\ f_2 \amp = \amp 60 \amp - f_4 \amp - f_7 \\ f_3 \amp = \amp -75 \amp + f_4 \amp + f_6 \\ f_5 \amp = \amp 40 \amp - f_6 \amp - f_7 \\ \end{array} \end{equation*}

where $f_4\text{,}$ $f_6\text{,}$ $f_7$ are parameters.

2.

A proposed network of irrigation canals is described in the accompanying diagram. At peak demand, the flows at interchanges $A\text{,}$ $B\text{,}$ $C\text{,}$ and $D$ are as shown.

$A network flow.$

Find the possible flows.
If canal $BC$ is closed, what range of flow on $AD$ must be maintained so that no canal carries a flow of more than $30\text{?}$

Answer.

$\begin{array}[t]{l} f_5 = 15 \\ 25 \leq f_4 \leq 30 \end{array}$

3.

A traffic circle has five one-way streets, and vehicles enter and leave as shown in the accompanying diagram.

$A network flow.$

Compute the possible flows.
Which road has the greatest flow?

Exercise Group.

Find the currents in each of the circuits.

4.

Answer.

$I_1 = \frac{40}{11}\text{,}$ $I_2 = -\frac{5}{11}\text{,}$ $I_3 = \frac{45}{11}$

5.

Answer.

$I_1 = \frac{3}{5}\text{,}$ $I_2 = -\frac{1}{5}\text{,}$ $I_3 = \frac{4}{5}$

6.

Answer.

$I_1 = 2\text{,}$ $I_2 = 2\text{,}$ $I_3 = 0\text{,}$ $I_4 = 0\text{,}$ $I_5 = \frac{3}{4}\text{,}$ $I_6 = \frac{3}{4}$

7.

Answer.

$I_1 = 2\text{,}$ $I_2 = 1\text{,}$ $I_3 = \frac{1}{2}\text{,}$ $I_4 = \frac{3}{2}\text{,}$ $I_5 = \frac{3}{2}\text{,}$ $I_6 = \frac{1}{2}$

8.

Find the voltage $x$ such that the current $I_1 = 0\text{.}$

Answer.

$x = 1$

Exercise Group.

Balance each of the chemical reactions.

9.

$\mbox{CH}_{4} + \mbox{O}_2 \to \mbox{CO}_{2} + \mbox{H}_{2}\mbox{O}$

This is the burning of methane $\mbox{CH}_{4}\text{.}$

10.

$\mbox{NH}_{3} + \mbox{CuO} \to \mbox{N}_{2} + \mbox{Cu} + \mbox{H}_{2}\mbox{O}$

Here $\mbox{NH}_{3}$ is ammonia, $\mbox{CuO}$ is copper oxide, $\mbox{Cu}$ is copper, and $\mbox{N}_{2}$ is nitrogen.

Answer.

$2\mbox{NH}_{3} + 3\mbox{CuO} \to \mbox{N}_{2} + 3\mbox{Cu} + 3\mbox{H}_{2}\mbox{O}$

11.

$\mbox{CO}_{2} + \mbox{H}_{2}\mbox{O} \to \mbox{C}_{6}\mbox{H}_{12}\mbox{O}_{6} + \mbox{O}_{2}$

This is called the photosynthesis reaction---$\mbox{C}_{6}\mbox{H}_{12}\mbox{O}_{6}$ is glucose.

12.

$\mbox{Pb}(\mbox{N}_{3})_{2} + \mbox{Cr}(\mbox{MnO}_{4})_{2} \to \mbox{Cr}_{2}\mbox{O}_{3} + \mbox{MnO}_{2} + \mbox{Pb}_{3}\mbox{O}_{4} + \mbox{NO}$

Answer.

$15\mbox{Pb}(\mbox{N}_{3})_{2} + 44\mbox{Cr}(\mbox{MnO}_{4})_{2} \to 22\mbox{Cr}_{2}\mbox{O}_{3} + 88\mbox{MnO}_{2} + 5\mbox{Pb}_{3}\mbox{O}_{4} + 90\mbox{NO}$

13.

$\mbox{KNO}_{3}+\mbox{H}_{2}\mbox{CO}_{3}\rightarrow \mbox{K}_{2}\mbox{CO}_{3}+\mbox{HNO}_{3}$

14.

$\mbox{AgI}+\mbox{Na}_{2}\mbox{S}\rightarrow \mbox{Ag}_{2}\mbox{S}+\mbox{NaI}$

15.

$\mbox{Ba}_{3}\mbox{N}_{2}+\mbox{H}_{2}\mbox{O}\rightarrow \mbox{Ba}\left( \mbox{OH}\right) _{2}+\mbox{NH}_{3}$

16.

$\mbox{CaCl}_{2}+\mbox{Na}_{3}\mbox{PO}_{4}\rightarrow \mbox{Ca}_{3}\left( \mbox{PO}_{4}\right) _{2}+\mbox{NaCl}$

Prev Top Next