Initial Feasible Solution to the Transportation Problem: Composite Approximation Method

Abstract

Transportation Problem (TP) is a special case of Linear Programming Problem (LPP), and the algorithm is primarily designed to solve the minimization problem. TP involves allotment of homogenous products (or activities) from sources (factories, warehouses, etc.) to Sinks (retail shops, warehouses, destinations, etc.). Although generically known as a 'Transportation Problem' and considered as a problem solving method for transporting goods or for designing a schedule for shipping cargo, the model can also be used for solving problems of allocation of homogenous resources to activities, financial allocations, investment decisions, manpower allocation for various businesses, etc. Like the LPP, TP also aims at either maximization (of profits or benefits) or minimization (of costs or distance or some other quality) as a single objective, subject to the resource constraints. The TP has a special structure. The LPP solution methods like Simplex are unsuitable, complex or inefficient to solve problems mentioned above. The special algorithms of TP enable solving such problems with ease and in much less time.

For any simplex or other optimization algorithm, Initial Feasible Solution (IFS) is needed as a starting point. Once IFS is obtained, optimization algorithms improve the solution step by step by maintaining the feasibility. The solution obtained is considered optimal when a state is reached where no further improvement is possible.

This is an exercise to propose a simpler method to find an initial feasible solution. This simpler method depends on the principle of Matrix reduction. 'If a constant is added or subtracted from every element of a row or a column, the optimum solution remains the same.'

If he transportation cost to all destinations is reduced by the same mount from a given source, the decision would not change. The optimum route would remain the same. Similarly, if cost to any destination from every source is reduced by the same amount, the best route would remain the same. The method explained in this article is named as 'Composite Approximation Method'.