4.1 Networks and flows¶
Part 3 · Flows · Chapter 4 · Chapter 4: Flow models · Lecture notes, volume 3 (PDF) · Exercises: Flow models
Definition 4.1: network
A network is a directed graph \(G=(N,A)\), with \(n=|N|\) nodes and \(m=|A|\) arcs, together with the following data.
-
Every node \(i \in N\) has a balance \(b_i \in \R\). The node is a supply node if \(b_i>0\), a demand node if \(b_i<0\), and a transshipment node if \(b_i=0\).
-
Every arc \((i,j) \in A\) has a lower bound \(l_{ij}\) and a capacity \(u_{ij}\), with \(0 \le l_{ij} \le u_{ij} \le +\infty\), and a cost \(c_{ij} \in \R\) per unit of flow.
When the lower bounds are not given, \(l_{ij}=0\) for every arc.
Definition 4.2: flow
Let \(G=(N,A)\) be a network. A flow is a vector \(\vet{x} \in \R^m\) with one entry \(x_{ij}\), the amount sent along the arc, for every \((i,j) \in A\).
-
The flow satisfies the flow conservation constraint of node \(i\) if what leaves \(i\) minus what enters \(i\) equals the balance:
\[ \sum_{(i,j) \in \delta^+(i)} x_{ij} \;-\; \sum_{(j,i) \in \delta^-(i)} x_{ji} = b_i . \] -
The flow is feasible if it satisfies flow conservation at every node and \(l_{ij} \le x_{ij} \le u_{ij}\) for every arc. Its cost is \(\sum_{(i,j) \in A} c_{ij}\, x_{ij}\).
-
A supply node sends out \(b_i\) units more than it receives, a demand node receives \(-b_i\) units more than it sends, and a transshipment node passes on everything it receives.
-
With the node–arc incidence matrix \(\mat{B}\) of Chapter 1 «Graphs», flow conservation at all the nodes reads \(\mat{B}\vet{x}=\vet{b}\): row \(i\) of \(\mat{B}\vet{x}\) is the outflow minus the inflow of \(i\).
Example 4.1: the reference network
We add data to the reference graph of Chapter 1 «Graphs», with the arcs numbered \(a_1,a_2,\dots,a_9\) in lexicographic order. The balances are
so nodes \(1\) and \(2\) supply \(7\) units, nodes \(4\) and \(6\) demand them, and nodes \(3\) and \(5\) are transshipment nodes. The lower bounds are zero, and the costs and capacities are:
| arc | \((1,2)\) | \((1,3)\) | \((2,4)\) | \((3,2)\) | \((3,5)\) | \((4,3)\) | \((4,6)\) | \((5,4)\) | \((5,6)\) |
|---|---|---|---|---|---|---|---|---|---|
| \(c_{ij}\) | \(2\) | \(2\) | \(5\) | \(2\) | \(3\) | \(3\) | \(5\) | \(5\) | \(3\) |
| \(u_{ij}\) | \(4\) | \(4\) | \(4\) | \(2\) | \(4\) | \(3\) | \(5\) | \(3\) | \(2\) |
In the figure each arc carries the pair \(c_{ij},u_{ij}\), and each node its balance \(b_i\) (in blue).
The flow \(\bar{\vet{x}}\) with
is feasible. For example, at node \(4\) the outflow is \(\bar{x}_{43}+\bar{x}_{46}=2\), the inflow is \(\bar{x}_{24}+\bar{x}_{54}=5\), and \(2-5=-3=b_4\). The arcs \((1,3)\), \((3,5)\) and \((5,6)\) are at capacity, and the cost of \(\bar{\vet{x}}\) is \(63\).
4.1.1 Flow across a cut¶
- For a set of nodes \(S \subseteq N\), we denote by \(\delta^+(S)\) the arcs with the tail in \(S\) and the head outside \(S\), by \(\delta^-(S)\) the arcs with the head in \(S\) and the tail outside \(S\), and \(x(F)=\sum_{(i,j) \in F} x_{ij}\) for a set of arcs \(F\).
Lemma 4.3: flow across a cut
Let \(\vet{x}\) satisfy flow conservation at every node of a network \(G=(N,A)\). Then, for every \(S \subseteq N\),
Proof
Add up the conservation constraints of the nodes of \(S\); the right-hand side is \(\sum_{i \in S} b_i\).
-
An arc with both endpoints in \(S\) appears twice, with \(+x_{ij}\) in the row of its tail and \(-x_{ij}\) in the row of its head: it cancels.
-
An arc of \(\delta^+(S)\) appears only in the row of its tail, with \(+x_{ij}\); an arc of \(\delta^-(S)\) only in the row of its head, with \(-x_{ij}\); the other arcs do not appear.
□
- In Example 4.1, the set \(S=\{1,2,3\}\) has \(\delta^+(S)=\{(2,4),(3,5)\}\) and \(\delta^-(S)=\{(4,3)\}\). The flow \(\bar{\vet{x}}\) gives \(3+4-0=7=b_1+b_2+b_3\).
A network has balances on the nodes and lower bounds, capacities and costs on the arcs. A feasible flow satisfies \(\mat{B}\vet{x}=\vet{b}\) and the bounds; across every cut, the net outflow equals the total balance of the nodes inside.