4.3 Feasibility conditions¶
Part 3 · Flows · Chapter 4 · Chapter 4: Flow models · Lecture notes, volume 3 (PDF) · Exercises: Flow models
Definition 4.5: balanced network
A network is balanced if \(\sum_{i \in N} b_i=0\), that is, if the total supply equals the total demand.
Proposition 4.6: a feasible network is balanced
If a network \(G=(N,A)\) has a feasible flow, then \(\sum_{i \in N} b_i=0\).
Proof
Apply Lemma 4.3 with \(S=N\): no arc leaves or enters \(N\), so \(\delta^+(N)=\delta^-(N)= \emptyset\) and \(\sum_{i \in N} b_i=0\). In matrix form, the rows of \(\mat{B}\) add up to the zero vector, hence so do the entries of \(\vet{b}=\mat{B}\vet{x}\). □
Proposition 4.7: cut condition
If a network \(G=(N,A)\) has a feasible flow, then for every \(S \subseteq N\)
where \(u(F)\) and \(l(F)\) are the sums of the capacities and of the lower bounds of the arcs of \(F\).
Proof
Let \(\vet{x}\) be a feasible flow. By Lemma 4.3 and the bounds \(x_{ij} \le u_{ij}\) on \(\delta^+(S)\) and \(x_{ij} \ge l_{ij}\) on \(\delta^-(S)\),
□
-
The supply of the nodes of \(S\), net of their demand, must be able to leave \(S\) through the arcs of \(\delta^+(S)\), while the arcs of \(\delta^-(S)\) bring at least their lower bounds into \(S\).
-
A balanced network can still have no feasible flow: the balance is only a necessary condition.
Example 4.3: balanced networks without a feasible flow
We keep the arcs, costs and capacities of the reference network and change the balances.
-
With \(b_5=-1\), \(b_6=1\) and \(b_i=0\) for the other nodes, the network is balanced. But node \(6\) has no leaving arc: for \(S=\{6\}\) we get \(\delta^+(S)=\emptyset\), and the cut condition fails, since \(b_6=1>0\).
-
With \(b_1=9\), \(b_6=-8\) and the other balances as in Example 4.1, the network is balanced, since \(9+2-3-8=0\). For \(S=\{1\}\) we get \(u(\delta^+(S))=u_{12}+u_{13}=8<9=b_1\): node \(1\) cannot send out its supply.
For the reference network itself, all the \(62\) sets \(S\) with \(\emptyset \neq S \neq N\) satisfy the cut condition, and the flow \(\bar{\vet{x}}\) of Example 4.1 is feasible.
A network with a feasible flow is balanced, and every cut can carry the net supply of the nodes inside it. These conditions are necessary: a balanced network may have no feasible flow.