Revision:Transportation Algorithm

TSR Wiki > Study Help >Subjects and Revision > Revision Notes > Mathematics > Transportation Algorithm

The Transportation Algorithm

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:

1. Finding an initial solution
2. Testing for Optimality
3. Improving the solution if not optimal.

North-West Corner

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).

For sake of argument, let

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

Where is the cost of moving something from bakery to warehouse .

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'

First, we let equal the number of items transfered in that cell. However, we need to decrease or increase the items around it. We do this by finding a cycle. The rules for the cycle are as follows:

• 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.

Since we are using this cycle to maximise , we need to work out what the values around it can be. These are worked out by corrected the table in the following way:

	Warehouse 1	Warehouse 2	Warehouse 3	Supply
Bakery 1	2			2
Bakery 2	5 -	3 +		8
Bakery 3		2 -	3	5
Demand	7	5	3	15

From this table, it is clear to see the maximum value of is 2. Any value greater than that will make cell (3, 2) negative. We can then make the necessary adjustments:

This is our improved table. Using the improvement indices we can use to see if it is optimal.

Unbalanced Problems

For information on unbalanced transportation problems, go to Revision Notes: Unbalanced Transportation Problems