Procedure for finding an optimum solution for transportation problem

The basic steps of the transportation method are:

1. To set up the transportation table.

2. Examine whether total supply equals total demand. If not, introduce a dummy row/column having all its cost elements as zero and Supply/Demand as the (+ive) difference of supply and demand.

3. To find an initial basic feasible solution. An initial BFS for a TP with m sources and n destinations must include m+n–1 basic variables. This initial solution may or may not be optimal. Thus, the initial solution in the transportation method serves the same purpose as the initial solution in the simplex method. There are a few methods to find the initial solution. The widely used methods for finding a initial solution are:

  • North West corner rule
  • Row minima method
  • Column minima method
  • Matrix minima method (Lowest cost entry method)
  • Vogel’s approximation method (unit cost penalty method) (VAM)

4. To obtain an optimal solution by making successive improvements to initial basic feasible solution until no further decrease in the transportation cost is possible. An optimal solution is one where there is no other se of transportation routes that will further reduce the total transportation cost. Thus, we have to evaluate each unoccupied cell in the transportation table in terms of an opportunity of reducing total transportation cost. An unoccupied cell with the largest negative opportunity cost is selected to include in the new set of transportation routes (allocations). This value indicates the per unit cost reduction that can be achieved by raising the shipment allocation in the unoccupied cell from its present level of zero. This is also known as an incoming cell (or variable). The outgoing cell (or variable) in the current solution is the occupied cell (basic variable) in the unique closed path (loop) whose allocation will become zero first as more units are allocated to the unoccupied cell with largest negative opportunity cost. That is, the current solution cannot be improved further. This is the optimal solution.

The widely used methods for finding an optimal solution are:

  • Stepping stone method (not to be done).
  • Modified Distribution (MODI) method.

They differ in their mechanics, but will give exactly the same results and use the same testing strategy.

5. To develop the improved solution, if it is not optimal. Once the improved solution has been obtained, the next step is to go back to 3.

Note. Although the transportation problem can be solved using the regular simplex method, its special properties provide a more convenient method for solving this type of problems. This method is based on the same theory of simplex method. It makes use, however, of some shortcuts which provide a less burdensome computational scheme. There is one difference between the two methods. The simplex method performs the operations on a simplex table. The transportation method performs the same operations on a transportation table.

Remarks:

  • Cells in the transportation table having positive allocation will be called allocated/occupied cells, otherwise non-allocated/ non-occupied cells.
  • When the number of positive allocations at any stage of the feasible solution is less than the required number i.e. m + n – 1, the solution is said to be degenerate, otherwise non-degenerate.

Unbalanced transportation problems:

If in a transportation problem, the sum of all available quantities is not equal to the sum of requirements, that is, then, such problem is called an unbalanced transportation problem. There can be two different forms:

  1. Excess of availability
  2. Shortage of availability

Bookmark the permalink.