# Network Flow Problem - How to solve with a matrix?

Find the general flow pattern of the network. Assuming that the flows are all nonnegative, what is the smallest possible value for $x_4$?

Points of Intersection: Flow In = Flow Out

A: $x_1+x_4 = x_2$

B: $x_2 = x_3 + 100$

C: $x_3 + 80 = x_4$

The total flow in equals the total flow out, so you can set up other equations...

How do I turn this into a solvable matrix to get the answer?

-
This question is entirely unintelligible to me -- you've explained almost none of the things you introduced. – joriki Sep 12 '12 at 8:25

## 1 Answer

Put it each column the corresponding variable, last column is used for constants. So rewrite each equation in the form $...=0$. Then, for $A$ we get $x_1-x_2+x_4=0$, $B$: $x_2-x_3-100=0$, $C$: $x_3-x_4+80=0$. Put that in a matrix: $\begin{pmatrix} 1 & -1 & 0 & 1 & 0\\ 0 & 1 & -1 & 0 & -100\\ 0 & 0 & 1 & -1 & 80\\ \end{pmatrix}$

Solving that matrix results into $\begin{pmatrix} 1 & 0 & 0 & 0 & 20\\ 0 & 1 & 0 & -1 & -20\\ 0 & 0 & 1 & -1 & 80\\ \end{pmatrix}$

So, in other words, $x_1=20, x_2=-x_4-20, x_3=-x_4+80$. Since the flows are non-negative, it must hold that $x_4\le -20$ (for $x_2\ge 0$) and $x_4 \le 80$ for $x_3 \ge 0$. So, $x_4 \le -20$. But that is not possible, since $x_4 \ge 0$ so there are no solutions.

-