Applications Practice: Section 1.6
This recap is problems only. Three problems are worked in full below; four more are left for you, with solutions you can open after trying. All eight come from the exercises of Section 1.6 and none of them appeared in the lecture or in Homework 2.
- Translate the story into a system of linear equations (one equation per sector, element, or junction).
- Write the augmented matrix of the system.
- Row reduce, one operation at a time.
- Read off the general solution, then apply the extra requirements of the problem (natural numbers, nonnegative flows, a fixed price, and so on).
Worked problems
When solutions of sodium phosphate and barium nitrate are mixed, the result is barium phosphate (as a precipitate) and sodium nitrate. Balance the unbalanced equation \[(x_1)\,\mathrm{Na_3PO_4}+(x_2)\,\mathrm{Ba(NO_3)_2}\ \longrightarrow\ (x_3)\,\mathrm{Ba_3(PO_4)_2}+(x_4)\,\mathrm{NaNO_3}.\]
Solution. Step 1 (equations). For each compound build a vector listing its atoms of sodium (Na), phosphorus (P), oxygen (O), barium (Ba), and nitrogen (N). Count carefully: \(\mathrm{Ba(NO_3)_2}\) has \(2\) N and \(6\) O; \(\mathrm{Ba_3(PO_4)_2}\) has \(3\) Ba, \(2\) P, \(8\) O: \[\mathrm{Na_3PO_4}:\begin{bmatrix}3\\1\\4\\0\\0\end{bmatrix},\quad \mathrm{Ba(NO_3)_2}:\begin{bmatrix}0\\0\\6\\1\\2\end{bmatrix},\quad \mathrm{Ba_3(PO_4)_2}:\begin{bmatrix}0\\2\\8\\3\\0\end{bmatrix},\quad \mathrm{NaNO_3}:\begin{bmatrix}1\\0\\3\\0\\1\end{bmatrix}.\] The balance condition is the vector equation \(x_1\mathbf v_1+x_2\mathbf v_2=x_3\mathbf v_3+x_4\mathbf v_4\). Comparing the two sides one entry at a time gives one equation per element: the first entries (sodium) give \(3x_1=x_4\), the second entries (phosphorus) give \(x_1=2x_3\), the third entries (oxygen) give \(4x_1+6x_2=8x_3+3x_4\), the fourth entries (barium) give \(x_2=3x_3\), and the fifth entries (nitrogen) give \(2x_2=x_4\). Moving every term to the left produces the homogeneous system \[\begin{aligned}3x_1-x_4&=0\\ x_1-2x_3&=0\\ 4x_1+6x_2-8x_3-3x_4&=0\\ x_2-3x_3&=0\\ 2x_2-x_4&=0\end{aligned}\]
Steps 2 and 3. Row reduce the augmented matrix. Swap \(R_1\leftrightarrow R_2\) to get a leading 1, then clear column 1 (\(R_2\to R_2-3R_1\), \(R_3\to R_3-4R_1\)): \[\left[\begin{array}{cccc|c}3&0&0&-1&0\\1&0&-2&0&0\\4&6&-8&-3&0\\0&1&-3&0&0\\0&2&0&-1&0\end{array}\right]\sim \left[\begin{array}{cccc|c}1&0&-2&0&0\\0&0&6&-1&0\\0&6&0&-3&0\\0&1&-3&0&0\\0&2&0&-1&0\end{array}\right]\] Swap \(R_2\leftrightarrow R_4\) to put a 1 in the second pivot, then clear column 2 (\(R_3\to R_3-6R_2\), \(R_5\to R_5-2R_2\)) and scale \(R_3\to\tfrac13R_3\): \[\sim\left[\begin{array}{cccc|c}1&0&-2&0&0\\0&1&-3&0&0\\0&0&18&-3&0\\0&0&6&-1&0\\0&0&6&-1&0\end{array}\right]\sim \left[\begin{array}{cccc|c}1&0&-2&0&0\\0&1&-3&0&0\\0&0&6&-1&0\\0&0&6&-1&0\\0&0&6&-1&0\end{array}\right]\] Rows 3, 4, 5 are now identical, so \(R_4\to R_4-R_3\) and \(R_5\to R_5-R_3\) produce two zero rows: \[\sim\left[\begin{array}{cccc|c}1&0&-2&0&0\\0&1&-3&0&0\\0&0&6&-1&0\\0&0&0&0&0\\0&0&0&0&0\end{array}\right]\] Five equations collapsed to three: the element balances are not independent.
Step 4 (read and answer). The pivots are in columns 1, 2, 3, so \(x_4\) is free. Read the nonzero rows from the bottom up, each one as an equation, and solve each for its pivot variable. Row 3 says \(6x_3-x_4=0\); solving for \(x_3\) gives \(\boldsymbol{x_3=\tfrac16x_4}\). Row 2 says \(x_2-3x_3=0\), that is, \(x_2=3x_3\); substituting \(x_3=\tfrac16x_4\) gives \(\boldsymbol{x_2=\tfrac12x_4}\). Row 1 says \(x_1-2x_3=0\), that is, \(x_1=2x_3\); substituting \(x_3=\tfrac16x_4\) again gives \(\boldsymbol{x_1=\tfrac13x_4}\). The smallest natural numbers come from \(x_4=6\): \[2\,\mathrm{Na_3PO_4}+3\,\mathrm{Ba(NO_3)_2}\ \longrightarrow\ \mathrm{Ba_3(PO_4)_2}+6\,\mathrm{NaNO_3}.\] Check. Na: \(6=6\). P: \(2=2\). O: \(8+18=26=8+18\). Ba: \(3=3\). N: \(6=6\).
Find the general flow pattern of the network shown in the figure. Assuming that the flows are all nonnegative, what is the largest possible value for \(x_3\)?
Solution. Step 1 (one equation per junction, flow in = flow out).
| Junction | Flow in | Flow out | |
|---|---|---|---|
| A | \(x_1+x_3\) | \(=\) | \(20\) |
| B | \(x_2\) | \(=\) | \(x_3+x_4\) |
| C | \(80\) | \(=\) | \(x_1+x_2\) |
Steps 2 and 3. Rearrange with unknowns on the left and row reduce: \(R_3\to R_3-R_1\), then \(R_3\to R_3-R_2\): \[\left[\begin{array}{cccc|c}1&0&1&0&20\\0&1&-1&-1&0\\1&1&0&0&80\end{array}\right]\sim \left[\begin{array}{cccc|c}1&0&1&0&20\\0&1&-1&-1&0\\0&1&-1&0&60\end{array}\right]\sim \left[\begin{array}{cccc|c}1&0&1&0&20\\0&1&-1&-1&0\\0&0&0&1&60\end{array}\right]\] The pivots are in columns 1, 2, 4, so \(x_3\) is free.
Step 4 (read and answer). Read the rows from the bottom up, each one as an equation. Row 3 says \(\boldsymbol{x_4=60}\). Row 2 says \(x_2-x_3-x_4=0\), that is, \(x_2=x_3+x_4\); substituting \(x_4=60\) gives \(\boldsymbol{x_2=60+x_3}\). Row 1 says \(x_1+x_3=20\), so \(\boldsymbol{x_1=20-x_3}\). The general flow pattern is \[x_1=20-x_3,\qquad x_2=60+x_3,\qquad x_4=60,\qquad x_3\text{ free}.\] Nonnegativity: \(x_1\ge0\) forces \(x_3\le20\), and \(x_3\ge0\) allows anything up to that. The largest possible value of \(x_3\) is 20 (then \(x_1=0\): all the traffic reaching A comes along the branch \(x_3\)).
Check with the whole network. Total in is \(80\); total out is \(20+x_4=80\), so \(x_4=60\), which agrees with the reduction.
(a) Find the general traffic pattern in the freeway network shown in the figure (flow rates in cars/minute). (b) Describe the general traffic pattern when the road whose flow is \(x_4\) is closed. (c) When \(x_4=0\), what is the minimum value of \(x_1\)?
Solution. Step 1 (one equation per junction).
| Junction | Flow in | Flow out | |
|---|---|---|---|
| A | \(x_1\) | \(=\) | \(40+x_3+x_4\) |
| B | \(200\) | \(=\) | \(x_1+x_2\) |
| C | \(x_2+x_3\) | \(=\) | \(100+x_5\) |
| D | \(x_4+x_5\) | \(=\) | \(60\) |
(Whole-network check: in \(=200\), out \(=40+100+60=200\); consistent.)
Steps 2 and 3. With unknowns on the left, in the order B, A, C, D, the augmented matrix reduces by \(R_2\to R_2-R_1\), then \(R_3\to R_3+R_2\), then \(R_4\to R_4+R_3\): \[\left[\begin{array}{ccccc|c}1&1&0&0&0&200\\1&0&-1&-1&0&40\\0&1&1&0&-1&100\\0&0&0&1&1&60\end{array}\right]\sim \left[\begin{array}{ccccc|c}1&1&0&0&0&200\\0&-1&-1&-1&0&-160\\0&1&1&0&-1&100\\0&0&0&1&1&60\end{array}\right]\sim \left[\begin{array}{ccccc|c}1&1&0&0&0&200\\0&-1&-1&-1&0&-160\\0&0&0&-1&-1&-60\\0&0&0&1&1&60\end{array}\right]\sim \left[\begin{array}{ccccc|c}1&1&0&0&0&200\\0&-1&-1&-1&0&-160\\0&0&0&-1&-1&-60\\0&0&0&0&0&0\end{array}\right]\] Pivots in columns 1, 2, 4; the free variables are \(x_3\) and \(x_5\).
Step 4 (read and answer).
(a) Read the nonzero rows from the bottom up, each one as an equation, and solve each for its pivot variable. Row 3 says \(-x_4-x_5=-60\), that is, \(x_4+x_5=60\); solving for the pivot variable gives \(\boldsymbol{x_4=60-x_5}\). Row 2 says \(-x_2-x_3-x_4=-160\), that is, \(x_2=160-x_3-x_4\); substituting the expression \(x_4=60-x_5\) from row 3 gives \(x_2=160-x_3-(60-x_5)\), that is, \(\boldsymbol{x_2=100-x_3+x_5}\). Row 1 says \(x_1+x_2=200\), so \(x_1=200-x_2\); substituting the expression for \(x_2\) gives \(x_1=200-(100-x_3+x_5)\), that is, \(\boldsymbol{x_1=100+x_3-x_5}\). The general traffic pattern is \[x_1=100+x_3-x_5,\qquad x_2=100-x_3+x_5,\qquad x_4=60-x_5,\qquad x_3,x_5\text{ free}.\]
(b) Closing the \(x_4\) road means \(x_4=0\). The general pattern says \(x_4=60-x_5\), so \(60-x_5=0\), that is, \(x_5=60\). Substituting \(x_5=60\) into the expressions for \(x_1\) and \(x_2\): \[x_1=40+x_3,\qquad x_2=160-x_3,\qquad x_4=0,\qquad x_5=60,\qquad x_3\text{ free}.\] All the traffic for D must now arrive along \(x_5\).
(c) With \(x_4=0\) we have \(x_1=40+x_3\) and \(x_3\ge0\), so the minimum value of \(x_1\) is 40, reached when \(x_3=0\).
Now you try
Work each problem on paper with the same four-step routine before opening the solution. The solutions show the full reduction so you can compare line by line.