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?
$\endgroup$ 12 Answers
$\begingroup$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.
$\endgroup$ $\begingroup$Sol'n: x1=20, x2=100, x3=0, x4=80 Coefficient matrix [1 -1 0 1][x1]=[0] [0 1 -1 0][x2]=[100] [0 0 1 -1][x3]=[-80] [X4]
$\endgroup$
