Suppose there are suppliers and customers. The 'th supplier can supply up to units of supply, and the 'th customer has units of demand. It costs to transport a unit of product from 'th supplier to the 'th customer. We want to find a transportation schedule to satisfy all demands with minimum transportation cost.
Let denote the amount of product trasnported from 'th supplier to 'th customer for and . The LP is then:
Maximum Flow Problem
Figure 1: Maximum flow problem
Let for , where is the set of arcs. Figure 2 shows the I/O for a single node.
Figure 2: Maximum flow problem on a single node
Then we can formulate the problem as an LP:
Here, the first constraint is called the flow conservation constraint. The second constraint is called the
Shortest Path Problem
Figure 3 shows a directed network, where then number on each edge is the distance for traversing that edge. We want to go from starting point to the target point .
Figure 3: Shortest path problem
The basic idea is to find a minimum cost way to ship 1 unit of flow from to all other nodes as shown in Figure 4.
Figure 3: Shortest path problem reformulated
The shortest distance from to can be formulated as an LP:
