### Minimum Cost Flow Problem Formulation

Supposed you have several locations, indexed $i=1,...,n$

These locations have demands and supplies.  We’ll denote $b_i$ as the supply from location $i$.  A negative $b_i$ indicates a demand at location $i$.

The arc set A contains arcs $(i,j)$ for directed arcs from location $i$ to $j$.  The node set N contains the location indices ${1,...,n}$

Define $x_{ij}=$ amount of commodity moved from location $i$ to$j$.

Define $c_{ij}=$cost of moving one unit of commodity from location $i$ to $j$.

The LP is then

Minimize$\displaystyle\sum_{(i,j)\in A}{c_{ij}x_{ij}}$

Subject to $\displaystyle\sum_{(j\colon(i,j)\in A)} {x_{ij}}-\sum_{(j\colon(j,i)\in A)}x_{ij}=b_i$           $\forall i\in N$

The constraints’ first terms are all the flow leaving $i$ to the various $j$s.  The second terms are all the flow entering $i$ from the various $j$s.

$b_i$ will be 0 if the location is an intermediary, <0 if it’s a demand node and >0 if it’s a supply node.