Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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