Suppose you own 4 factories, from A to D, which provides production for 3 shops, from 1 to 3. The productivities for factories A to D are 1000, 2000, 2500 and 1500 respectively, and the demand of store 1 to 3 are 3000, 2000 and 2000. The costs of transportation are as following (in dollars per unit):

How can you decide the arrangement of transportation in order to access the lowest cost? Difficult?

We can translate this problem to the following diagram:

Transportation Problem

Which each node represent a factory or a store. Each connection represents a possible way of transportation.

Initially, pick up ways to transport in the order of lowest cost to highest cost. For each chosen way, the amount should be transported equals to min{factory’s remaining production, store’s remaining demand}. By doing this, we have the following chart:

Transportation Problem

The cost for this is 1000 * 2 + 2000 * 2 + 500 * 4 + 2000 * 1 + 1500 * 9 = $23,500

Obvious, if we let D send 1500 to 3 and C send 2000 to 1:

Transportation Problem

The new cost can be 1000 * 2 + 2000 * 2 + 2000 * 4 + 500 * 1 + 1500 * 5 = $22,000, which is $1,500 cheaper than before.

So how can we obtain the cheapest transportation?

We should exam every edge to see whether increase transportation through it and decrease transportation through it can lead to a decrease in cost. To do this we should build up a table like this (x mean this way is in current transportation arrangement). Let start with the very connections at the very beginning.

Take A-3 as first example, if we add A-3, there will be a loop: A – 3 – c – 1 – A

And the change in cost: +10 – 1 + 4 – 2 = 11, which means the cost will increase if we add A-2 in

Take A-2 as second example, A – 2 – B – 1 – A, and the cost is +3 – 2 + 3 – 2 = +2. Here we need to mark B-1 with x as we consider it as an edge

After doing this, we can fill the table as

Because negative numbers exist, we can obtain lower transportation cost by include d-3 in:

For d – 3 – c – 1 – d, the amount we should change: d – 3: + x, 3 – c: 2000 - x, c – 1: 500 + x, 1 – d: 1500 – x. So the max amount we can change in 1500.

Then, we have a new diagram with cheaper cost:

Transportation Problem

We repeat the above process:

Because all not negative number exist, we have the optimal solution!