Lecture_15_Transportation Problem : Introduction ana mathematical formaulation

15.1 Introduction to Transportation Problem


The Transportation problem is to transport various amounts of a single homogeneous commodity that are initially stored at various origins, to different destinations in such a way that the total transportation cost is a minimum.

It can also be defined as to ship goods from various origins to various destinations in such a manner that the transportation cost is a minimum.

The availability as well as the requirements is finite. It is assumed that the cost of shipping is linear.



15.2 Mathematical Formulation
Let there be m origins, ith origin possessing ai units of a certain product
Let there be n destinations, with destination j requiring bj units of a certain product Let cij be the cost of shipping one unit from ith source to jth destination
Let xij be the amount to be shipped from ith source to jth destination
It is assumed that the total availabilities ?ai satisfy the total requirements ?bj i.e.

?ai = ?bj (i = 1, 2, 3 … m and j = 1, 2, 3 …n)

The problem now, is to determine non-negative of xij satisfying both the availability constraints


as well as requirement constraints


and the minimizing cost of transportation (shipping)


This special type of LPP is called as Transportation Problem.


15.4 Some Basic Definitions

• Feasible Solution
A set of non-negative individual allocations (xij ? 0) which simultaneously removes deficiencies is called as feasible solution.

• Basic Feasible Solution
A feasible solution to ‘m’ origin, ‘n’ destination problem is said to be basic if the number of positive allocations are m+n-1. If the number of allocations is less than m+n-1 then it is called as Degenerate Basic Feasible Solution. Otherwise it is called as Non- Degenerate Basic Feasible Solution.


• Optimum Solution
A feasible solution is said to be optimal if it minimizes the total transportation cost.