Transportation problem: Construction of starting solution 3
The Transportation Problem
In General
The transportation problem deals with the transport of supplies to different demand places. There are i supply locations with ai quantities of the product x and there are j demand locations with bj quantities, whereby it is important that supply is always equal to demand. The concept aims that the transportation costs cij are minimal.
Mathematical modell
ai : Supply quantity at supply location i (i=1,...,m)
bj : Demand quantity at demand location j (j=1,...,n)
cij : Transportation costs per unit from supply location i to demand location j
xij : Transporting amount x from i to j
Goal function:
C = ∑i ∑j cijxij →min! ∑j xij = ai for all i ∑i xij = bj for all j xij ≥ 0 for all i,j
A solution only exists if
∑i ai = ∑j bj
There are different methods to find an optimal solution
1. North-West corner method
2. Simple row sequence or column-sequence methods
3. Row-column succession
4. Matrix-Minimum method
5. Cost difference method
6. Frequency method according to Habr
7. Modified North-West corner method
In detail we are going to explain the North-West corner method and the Cost difference method to you.
General example
1. North-West corner method
First you start in the ´North-West´ corner, which means it is the first field in the first row and first column. You give it the maximum amount which sums up from supply and demand. If the minimum is demand you continue in the row, if it is supply you continue in the column. And so on.
The North-West corner method does not consider the upcoming transportation costs. In general that is the reason why it does not always reach an optimal solution.
5. Cost difference method (Vogel'sche approximation method VAM)
Main difference to the North-West corner method is that this method considers the upcoming transportation costs. This method gives you the best approximation to an optimal solution. First, you start up by generating the difference between the lowest and the second lowest number in the row and in the column. You do this for every row and every column. The row or column where you can find the highest difference will be selected and you buy everything from the field where you can see the lowest number. Depending on which restriction is reached either the row or the column will be finished. If you reach the restriction in both row and column you may choose one. Then you start over again with the first step. You repeat all this until the whole tableau is completed.
Sources:
WiSo Kurzlehrbücher, Operations Research, Hans Corsten/Hilde Corsten, Carsten Sartor, Verlag Vahlen, Feb. 2005
OR-Skript 2013
