The Transportation Problem

Suppose we have suppliers having supplies
and buyers having demands .
(WLOG assume their sums are the same).
The transportation cost from to is .
Hence, this is a Linear Program:
” Minimise subject to and . ”
Calculate the Lagrangian:

Now, as we certainly need .
Also, by Complimentary Slackness,
whenever , we need .

The transportation algorithm

Firstly, find any feasible
(with not too many nonzero - achieve this by being greedy).
This will give equations of form .
Solve them (taking for example).
If now for all , we are done
because we have a feasible Dual Problem and Complimentary Slackness
(Dual Problem in Linear Programs).
Otherwise, find the largest
Change to while also redistributing the values in the initial flow (by each)
so that remains feasible.
Find the largest such where this is possible
(i.e. one of the will become 0).
Note that we have made the Lagrangian smaller by .
But for a feasible (which it is),
the Lagrangian only depends on
so we can shuffle the and again.
Now we have a new set of equations for and so recalculate them,
check if they are feasible,
if not, repeat the algorithm,
making the Lagrangian (and hence the cost) smaller every time.