[Math] Convert capacitated network flow problem

network-flow

Assume a capacitated network flow problem with graph $G = (N,A)$ and capacities $u_{ij}$ (finite), costs for each path of $c_{ij}$ and I/O of $b_{i}$.

How can it be shown there is an equivalent transportation problem with a source node for every arc $(i,j)$ in $N$ having supply $u_{ij}$, and a sink node with demand $\sum _{k | (i,k) \in A} u_{ik}-b_{i}$ for every node $i$ in $N$?

At every supply node $(i,j)$ there are two outgoing infinite capacity arcs: one goes to demand node $i$, and its cost coefficient is 0; the other goes to demand node $j$ and its cost coefficient is $c_{ij}$.

Best Answer

What you're looking for is described on pages 247-249 of Robert Vanderbei's Linear Programming: Foundations and Extensions (2nd edition), although Vanderbei has some of his sign conventions opposite of yours. Take a close look in particular at Figure 14.4 on page 249 ("Adding a new node to accommodate an arc $(i,j)$ having an upper bound $u_{ij}$ on its flow capacity").

Related Question