3
$\begingroup$

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}$.

$\endgroup$
3
$\begingroup$

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").

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.