How do I find the minimal upper bound of flow that can pass for each edges in this graph?

51 Views Asked by At

What is in red is the supply/demand. If it's 0 that means that the node is just there for transfering the flow. If it's negative this means that it's the demand and if it's positive then it's the supply.

Brackets in black on edges are the capacity limit. If there is no [ ] on an edge this simply mean that there is no limit. Otherwise, the numbers on the edges are the cost per unit of transfer.

I'm asked for each edge to find the lowest upper bound of flow that can pass through it. However, I'm not sure how to do this? For the node 1 I can put 10 units on each of its edges. Is this the lowest upper bound? How do I figure this out?

enter image description here

1

There are 1 best solutions below

10
On BEST ANSWER

Let $b_i$ be the supply or demand at node $i \in N$. For each arc $(i,j)\in A$, introduce a nonnegative flow variable $x_{i,j}$ (some with upper bounds). For each node $i\in N$, impose linear flow-balance constraints: $$\sum_{(i,j)\in A} x_{i,j} - \sum_{(j,i)\in A} x_{j,i} = b_i \quad \text{for $i\in N$}$$ For each arc $(i,j)$, maximize $x_{i,j}$. The maximum values turn out to be: \begin{matrix} i & j & \max \\ \hline 1 &2 &10 \\ 1 &3 &20 \\ 1 &4 &20 \\ 2 &5 &30 \\ 3 &2 &25 \\ 3 &4 &30 \\ 4 &5 &30 \\ \end{matrix}