These notes carry on from Transportation Problems. In the worked example, we will use the table introduced there:
In order to find an optimal solution, ther are three parts:
- Finding an initial solution
- Testing for Optimality
- Improving the solution if not optimal.
The North-West Corner method is a way of finding an initial solution.
Step One: Start in the North-West (Top-Left) corner
Step Two: When you are in a cell, place the maximum possible number there without making the row or column total exceed the row or column total respectively.
Step Three: If you have not reached the South-East corner, then move onto the next step by either moving one step right (if you completed the column) or one step down (if you completed the row)
If we use the North-West corner rule on our initial table, we get:
The Optimality Check
This optimality condition works if, and only if occupied cells = number of rows + number of columns − 1. If this is not the case, then you should add a zero into one of the unoccupied cells.
The optimality condition works by creating "shadow costs". This means that for each bakery, we work out a cost for delivering a loaf from it; an for each warehouse we work out a cost for delivering a loaf to it. First, you must work out a set of equations:
To find values for each of these, we let one of the values be equal to zero. We could choose a non-zero value, but then all that would happen is our R values would be one higher, and K values one less (or vice versa).
We can work out from that:
Using the values we've got, we can work out how much we expect each transport route to cost. However, if any one of our routes costs less than using these shadow costs, then a transportation pattern using that route would be better than this.
To find out whether any routes are cheaper, we equate an "Improvement Index" for each unoccupied cell, defined as
Let us work this out for cell (1,2)
This is positive, so using this route would increase our costs, rather than decrease them. The other improvement indices can be worked out similarly:
If an improvement index equals 0, then a route using that would cost the same as a current route. If an improvement index is negative, then using a route using that cell would be cheaper. If all improvement indices are positive or zero, then our distribution is optimal.
The Stepping Stone Method
We know that by using cell (3,1) we will reduce the cost of our transportation. Therefore, we want to use it to transport as much as possible. We do this using the 'stepping stone technique'
- The first cell is unused and all the rest are used.
- Move to a cell in the same row or column (i.e. not diagonally), but we may skip cells
in a row or column.
- No three consecutive cells should be in the same row or column i.e. keep changing
direction from horizontal to vertical movement and vice versa.
- Don’t use any cell more than once.
Below, my cycle is marked in red.3 + 8 Bakery 3 2 - 3 5 Demand 7 5 3 15
This is our improved table. Using the improvement indices we can use to see if it is optimal.
For information on unbalanced transportation problems, go to Revision Notes: Unbalanced Transportation Problems