Transportation Models

TRANSPORTATION PROBLEMS

Introduction

This is a special class of optimization problems that deal with transportation of commodities from various sources (e.g. factories, distribution points etc) to various destinations (e.g. warehouses, customers etc) with the objective of optimizing the total payoff (cost  or contribution).

The assumptions of transportation methods

1. There are several sources and several destinations.
2. The unit transportation pay off is constant and known in advance with certainty.
3. The source capacities (supply) and the destination requirements (demand) are known in advance and with certainty.
4. The total supply and the total demand are equal. If the total demand is not equal to the total supply, an imaginary source or destination is introduced where there is a deficit. The imaginary source or destination is referred to as a “dummy” and its unit payoffs are all zeroes.
5. All variable values (supply, demand and payoffs) are greater than or equal to zero (non-negativity)
6. The number of sources is not necessarily equal to the number of destinations.

Solution of a transportation problem

Generally, a transportation problem is solved in two levels namely;

1. Developing the initial feasible solution (covered in this course)
2. Improving the initial feasible solution to ensure optimality (not covered in this course)

Developing the initial feasible solution

There are three transportation methods used in developing the initial feasible solution. These are;

1. The North-West corner method
2. The least-cost-cell method
3. The Vogel’s Approximation Method (VAM)

Method 1: The North-West Corner Method

The north-west corner method generates an initial allocation/feasible solution according to the following procedure:

Step I: Allocate the maximum amount allowable by the supply and demand constraints to the variable X11 i.e. the cell in the top left corner of the transportation tableau/payoff matrix

Step II: If a column (or row) is satisfied, cross it out since the remaining decision variables (cells) in that column (or row) are non-basic. If a row and column are satisfied simultaneously, cross only one out (it does not matter which).

Step III: Adjust supply and demand for the non-crossed rows and columns.

Step IV: Allocate the maximum feasible amount to the first available non-crossed out cell in the next column or row following the North-West principle. Repeat this allocation until exactly one row or column is left unallocated.

Step V: When exactly one row or column is left, all the remaining variables are basic and are assigned the only feasible and remaining allocation.

Step VI: Deduce the transportation schedule hence calculate the total transportation payoff.

Example I

Consider the problem represented by the following transportation tableau showing the unit cost of transporting items from factories F1 F2 and F3 to warehouses W1, W2, W3 and W4, the available supply and the demand/capacity for each warehouse.

Method 2: The Least-Cost-Cell Method

This method usually provides a better initial basic feasible solution than the North-West Corner method since it takes into account the cost variables in the problem. The Least-Cost-Cell Method generates an initial allocation/feasible solution according to the following procedure:

Step I: Assign as much as possible to the cell with the smallest unit cost in the entire tableau. If there is a tie break the tie arbitrarily.

Step II: If a column (or row) is satisfied, cross it out since the remaining decision variables (cells) in that column (or row) are non-basic. If a row and column are satisfied simultaneously, cross only one out (it does not matter which).

Step III: Adjust supply and demand for the non-crossed rows and columns.

Step IV: Allocate the maximum feasible amount to the next non-crossed out cell with the least unit cost. Repeat this allocation until exactly one row or column is left unallocated.

Step V: When exactly one row or column is left, all the remaining variables are basic and are assigned the only feasible and remaining allocation.

Step VI: Deduce the transportation schedule hence calculate the total transportation payoff.

Example

Solve Example I using the North-West Corner method.