The transportation problem describes a situation where the total cost of transporting identical goods over several routes between various sources of supply and points of demand is to be minimized. A starting solution – one that meets all the demand and uses all the supply, can be found using the 'north west corner method'. The costs of transporting gravel from quarries A, B and C to building sites 1, 2, 3 and 4 is shown below. The cost for each route is the sum of the source (quarry) and destination (building site) costs. These are called 'shadow costs'.
|
Site 1 |
Site 2 |
Site 3 |
Site 4 |
Supply of Gravel (Tons) |
|
|
Quarry A |
150 |
200 |
140 |
160 |
23 |
|
Quarry B |
130 |
110 |
190 |
220 |
16 |
|
Quarry C |
120 |
170 |
180 |
100 |
19 |
|
Demand for Gravel (Tons) |
12 |
13 |
11 |
22 |
58 |
The 'North West Corner Method' gives the starting solution shown below.
|
Site 1 |
Site 2 |
Site 3 |
Site 4 |
Supply of Gravel (Tons) |
|
|
Quarry A |
12 |
11 |
23 |
||
|
Quarry B |
2 |
14 |
16 |
||
|
Quarry C |
1 |
18 |
19 |
||
|
Demand for Gravel (Tons) |
12 |
13 |
15 |
18 |
58 |
To find an improved solution, we must find the shadow costs associated with each quarry and building site. The process is:
-
Set the cost associated with the source (quarry) to zero. The destination cost is then the total cost of transportation.
-
Move along the row to any other non empty squares and find the destination costs in the same way, by setting the source costs to zero.
-
When all possible destination costs for that row have been determined, go to the start of the next row.
-
Move along the row to any non empty squyares and use the destination costs found earlier to establish the source cost for the row. This done, find any other unknown destination costs.
-
Repeat 3 and 4 above until all source and destination costs have been found.
For example, destination and source costs are shown for the table at the top of the page in the table below, only the costs corresponding to the routes in the north west corner solution being considered.
C(1)
C(2)
C(3)
C(4)
C(A)
150
200
C(B)
110
190
C(C)
180
100
We have
C(A)+C(1)=150 (1)
C(A)+C(2)=200 (2)
C(B)+C(2)=110 (3)
C(B)+C(3)=190 (4)
C(C)+C(3)=180 (5)
C(C)+C(4)=100 (6)
Setting the cost associated with quarry A, C(A) to zero gives C(1)=150.
Then from (2), C(2)=200
From (3), C(B)=110-C(2)=110-200=-90
From (4), C(3)=190—C(B)=190- -90=280
From (5), C(C)=180-C(3)=180- 280=-100
From (6), C(4)=100-C(C)=100- -100=200.