Transportation Problem, Data Analysis and Modeling || Bcis Notes

Transportations Problems

 

1 Introduction:
The transportation problem is concerned to determine the amount that should be shipped from each source to each destination to make the total transportation cost minimum and at the same time satisfying the supply limits and the demand requirements. The transportation problem is concerned with selecting routes to distribute the goods in the different destinations in order to minimize the total transportation cost or to maximize the total revenue of the problem by satisfying the requirements of the different destinations and supply quantities of different sources.

2  Formulation of transportation problems as a linear programming problem:
The transportation problem is in the tabular form (matrix form) as shown

From\ to	D1	D2	…	Dn	Supply(ai )
S1	C11       X11	C12       X12	…	C1n       X1n	a1
S2	C21       X21	C22       X22	…	C2n       X2n	a2
. . .	. . .	. . .	…… …	. . .	. . .
S m	Cm1       Xm1	Cm2       Xm2	…	Cmn       Xmn	a m
Demand(b j )	b1	b2	…	bn	=

 

Where, there are ‘m’ sources S₁ , S₂ , ………, S _m having a_i (i=1,2,…..,m ) units of supplies or capacity respectively to be transported among ‘n’ destinations D₁ , D₂ , ………, D _n  with b_j ( j= 1,2,……..,n ) units of requirements respectively.

C_ij be the cost of shipping one unit of the commodity from sources ‘i’ to destination ‘j’ and X_ij denotes the number of units shipped per route from source ‘i’ to destination ‘j’.

Now, this transportation problem is formulated to minimize the total transportation cost as

Minimize Z = C₁₁X₁₁ + C₁₂X₁₂ +………+ C _{m n} X _{m n}

Z = C_ij X_ij

Subjected to constraints

Supply constraints

X₁₁ + X₁₂ +………+  X _{1 n} = a₁

X₂₁ + X₂₂ +………+  X _{2 n} = a₂

………………………………

………………………………

X _m1 + X _m2 +………+  X _{m n} = a _m

Demand constraints

X₁₁ + X₂₁ +………+  X _m1 = b₁

X₁₂ + X₂₂ +………+  X  _m2 = b₂

………………………………

………………………………

X _{1 n} + X _{2 n} +………+  X _{m n} = b _n

X_{i j}  0 , for all i and j .

3  Types of transportations problems:
There are two types of transportation problems depending upon supply and demand.

1. Balanced transportation problem: If total supply equals total demand. Then problem is called a balanced transportation problem.
2. Unbalanced transportation problem: If total supply does not equal to total demands. Then problem is called an unbalanced transportation problem.

 Note: It should be noted that the transportation problem will be solved when we convert unbalanced transportation problem into balanced transportation problem.

4 Methods of converting unbalanced transportation problem into balanced transportation problem:

1. When demand exceeds supply.
   When total supply (a_i ) is less than total demand (b_j ), at that time, introduce a dummy source (dummy row) in the transportation table to make total supply equals to total demand. Here, in this dummy row, the unit cost of transporting from this source to any destination is set to zero.
2. When supply exceeds demand.
   When total supply (a_i ) is greater than total demand (_bj ), at that time, introduce a dummy destination (dummy column) in the transportation table to make total demand equals to total supply. Here, in this dummy column, the unit cost of transporting from different sources to this dummy destination is set to zero.

5 Definition of some basic terms:

1. Source: It is the place of origin from which the goods or services are supplied to the different places of destinations.
2. Destination: It is the place of demand where the goods are required in certain finite quantities.
3. Occupied (basic)cells and non-occupied (non-basic) cells: Squares (cells) in the transportation table having positive allocation are called occupied cells, otherwise, called empty or non-occupied cells.
4. The feasible solution: A set of non-negative values X_ij that satisfied the constraints of given T.P. is called a feasible solution to the transportation problem.
5. The basic feasible solution: A feasible solution that contains no more than (R+C-1) non-negative allocations is called a basic feasible solution, where ‘R’ is no. of rows and ‘C’ is the no. of columns in the transportation table.
6. Degeneracy: When the number of occupied cells (basic cells) of general T.P. is less than (R+C-1), Then it is called degeneracy in transportation problem, and the solution is called degeneracy basic feasible solution.
7. Non – degeneracy: when the number of occupied cells (basic cells) of general T.P. is exactly equal to (R+C-1), then it is called non-degeneracy in the transportation problem, and the solution is called non-degeneracy basic feasible solution.

 

6  Methods of obtaining the initial basic feasible solution of transportation problem:

1. Northwest corner method.
2. Least cost method Or Greedy Method.

• Vogel’s approximation method or penalty method.

i)   Northwest corner method (NWCM):

In this method, the following systematic steps are used to obtain the initial basic feasible solutions.

1. Step 1: Allocation starts with the cell (1,1) at the upper left ( northwest ) corner of the transportation table and allocates as much as a possible value equal to the minimum of first row values and first column values i.e. min ( a_1,b₁)
2. Step 2:
   • (a) If the allocation made in step 1 is equal to the capacity of the first row (a₁), then move vertically down to the cell (2, 1) to fulfill the remaining demand of the first column. Here allocation is made according to step 1.
   • (b) If the allocation made in step 1 is equal to the demand of the first column (b₁), then move horizontally to the cell (1, 2) to finish the remaining capacity (sources) of the first row (source). Here allocation is made according to step 1.
   • (c) If allocation made in step 1 is equal to the capacity of the first source (a ₁) and demand of first destination (b₁). Then move diagonally to the cell (2, 2). Here allocation is made according to step 1.

• Step 3: continue the procedure step by step till an allocation is made in the southeast corner cell of the transportation table i.e. ( continue the above steps until all the capacity of all the sources are finishes and the demands of all the destinations are full filled).

1. Step 4: Calculate the total transportation cost, which is obtained as, at first multiply the allocated values with the corresponding unit cost for all occupied cells separately and then add all the multiple values which you obtained.

ii)  Least cost method (LCM) Or Greedy Method:

In this method, the following systematic steps are used to obtain the initial basic feasible solution.

• Step 1: At first, select the cell having the smallest unit cost in the entire transportation table and allocate as much as possible value to this cell and then eliminate that row if the capacity of that row is finished or eliminate that column if the demand of that column (destination) is fulfilled.

Note 1: If both row (source) and column (destination) are satisfied simultaneously, then only one eliminates (crossed out)

Note 2: In case, the smallest unit cost is not unique, then select the cell where maximum allocation can be made.

• Step 2: After the first step, again select the cell having the smallest unit cost out of uncrossed (non -eliminated) rows and columns. Then allocation is made to this cell according to step 1. Then eliminate that row and column in which either supply or demand is exhausted. This process should repeat until the entire available supply at various sources and demand at various destinations is satisfied.

The solution so obtained need not be non-degeneracy.

• Step 3: Calculate the total transportation cost, which is obtained as, at first multiply the allocated values with the corresponding unit cost for all occupied cells separately and then add all the multiple values which you obtained.

 

iii)  Vogel’s approximation method:

In this method, the following systematic steps are used to obtain the initial basic feasible solution to the transportation problem.

• Step 1: At first, calculate the difference between the smallest and next to smallest unit cost for each row (source) and column (destination). These differences are known as row and column opportunities (penalties) cost
• Step 2: Select the row or column with the largest difference (opportunities cost). Then allocate as many units as possible to this row or column in the cell having the least unit cost.

Note: if there is a tie in the values of the opportunities cost. At that time, we select that row or column with minimum unit cost. Again if there is a tie in the unit cost, we select that cell of that row or column where maximum allocation can be made.

• Step 3: After step 2, if the capacity of that row is finished, we eliminate that row. If the demand of that column is fulfilled, we eliminate that column. If the capacity of that row and demand of that column are satisfied simultaneously then only one of them is eliminated and in the remaining one, we assign zero supply or zero demand. Any row or column with zero supply or zero demand should not be used in computing future penalties (opportunities cost)
• Step 4: Again, calculate the opportunity cost for the remaining rows and columns which are not eliminated.
• Step 5: Repeat steps 2 to step 4 until the entire available supply at various sources (rows) and demand at various destinations (columns) are satisfied.
• Step 6: Calculate the total transportation cost, which is obtained as, at first multiply the allocated values with the corresponding unit cost for all occupied cells separately and then add all the multiple values which you obtained.

 

Note: Among the three methods, the total transportation cost obtained by Vogel’s approximation is the least so Vogel’s approximation is a more effective method for obtaining the initial basic feasible solution than other methods.

7  Maximization of transportation problems:
Transportation problems may be of the maximization type, maximization may be profit or revenue or productions. To solve such type of maximization transportation problem, at first convert this maximization T.P. into minimization T.P. by subtracting each unit cost from the highest unit cost of maximization transportation problem. Then we will get the minimization transportation problem. Then we proceed with the same process, preceded in case of minimization T.P.

Note: during the calculation of the maximum value, we will consider the original table. In which we multiply allocated goods with corresponding unit cost separately and then add all the multiple values to obtain the maximum value.

 

You may also like this: Method of Construction of Index Number