Essay on Transportation Problem| Operations Research | Linear Programming

After reading this essay you will learn about:- 1. Meaning of Transportation Problem 2. General Structure of the Transportation Problem 3. Linear Programming Formulation 4. Solution Procedure 5. Method for Finding Initial Basic Feasible Solution.

Essay on the Meaning of Transportation Problem:

The transportation problems deals with the transportation of product manufactured at different plants or factories (supply origins) to a number of different warehouses (demand destination). The objective is to satisfy the destination requirements within the plant’s capacity constraints at the minimum transportation cost.

Transportation problems thus typically arise in situations involving physical movement of good from plants to warehouses, warehouses to warehouses, wholesalers to retailers and retailers to customers.

Solution of the transportation problems requires the determination of how many units should be transported from each supply origin to each demand destination in order to satisfy all the destination demands while minimizing the total associated cost of transportation.

The easiest way to recognise a transportation problem is to consider a typical situation as shown in the following figure. Assume that a manufacturer has three factories F₁, F₂ and F₃ producing the same product. From these factories, the product is transported to three warehouses W₁, W₂, and W₃.

Each factory has a limited supply and each warehouse has specific demand. Each factory can transport to each warehouse but the transportation costs vary for different combinations. The problem is to determine the quantity each factory should transport to each warehouse in order to minimize total transportation costs.

Essay on The General Structure of the Transportation Problem:

The important feature of the standard transportation problem is that it can be expressed in the form of a table, which displays the values of all the data coefficients (s_i, d_j, c_ij) associated with the problem. In-fact, the constraints and the objective function of the transportation model can be read off directly from the table.

The supply constraints can be obtained by merely equating the sum of all the variables in each row to the factory capacities, similarly the demand constraints are obtained by equating the sum of all the variables in each column to the warehouse demands.

To facilitate presentation and solution the general transportation problem with m factories (capacity centres or source of supply) and n- warehouses (demand or requirements) is portrayed in a tabular form by means of a transportation tableau shown in Table 5.1 and 5.2 below:

In general, Table (5.1) & (5.2) are combined by inserting each unit cost C_ij together with the corresponding amount x_ij into the cell (i, j). The product x_ij (c_ij) gives the net cost of shipping x_ij units from factory F_i to warehouse W_j.

The problem of the company is to distribute the available product to different warehouse in such a way so as to minimize the total transportation cost for all the possible factory – warehouse shipping pattern.

Here,

i = index for origins (factory); i= 1,2….m.

j = – n – destinations (warehouse) j= 1, 2…n.

x_ij = no. of units shipped per route from origin i to destination j for each route.

C_ij = Cost per unit of shipping from origin (i) to destination (J)

S_i = supply in units at origin; i.

a_j = demand in units at destination j.

Mathematically:

The problem may be stated as a linear programming problem as follows:

The general mathematical L.P. model may be given as follows:

Linear Programming Formulation of the Transportation Problem:

Example 1:

Express the following transportation problem as LP problem.

Solution:

Let x_ij represent the amount of commodity to be transported from source i (i = 1, 2, 3) to destination ‘j’ (j = 1, 2, 3, 4). Then the objective function of the problem (minimization of total transportation cost) can be formulated as:

Where x_ij represents the number of unit of the product shipped from the i^th production centre (i = 1,2,3,4)to j^th selling centre (j = 1,2,3). The value of each x_ij will be positive whole number or zero. If in a particular solution, the x_tj value is missing for a cell, it means that no quantity is shipped between the production centre and selling centre in question.

Essay on the Solution Procedure of Transportation Problem:

Step (1):

Define the objective function to be minimized with the constraints imposed on the Problem.

Step (2):

Set up the transportation table with m-rows, representing the source and n- columns representing the destinations.

Step (3):

Develop an initial feasible solution to the problem.

Step (4):

Examine whether the initial solution is feasible or not. The solution is said to be feasible if the solution has allocations in (m+n-1) cells with independent positions. The cells having allocations are known as occupied cells and remaining cells they are known as empty cells.

Step (5):

Test whether the solution obtained in step (4) is optimal or not. This is done by computing opportunity costs for all the empty cells signifies optimal solutions.

Step (6):

If the solution is not optimal, modify the shipping schedule by including that empty cell whose inclusion in the program results in largest savings.

Step (7):

Repeat steps (5) and (6) until an optimal solution is obtained.

Let us consider the illustration discussed in Article (5.1.4). The supply of each plant or factory the demand of each warehouse and per unit transportation costs are shown in following Table:

In this table each row corresponds to specific factory and each column corresponds to a specific warehouse. Factory supplies are shown to the right of the table and warehouse requirement are shown below the table.

The largest box also known as cells. At the intersection of specific row and column will contain both quantity to be transported and per unit transportation cost. The quantity to be transported will be shown in the centre of the box and will be encircled and the per unit transportation cost is shown in the smaller rectangular box at the right hand side corner of each cell.

Therefore method of finding an optimal solution of transportation problem will consist of two main steps:

(1) To find an initial basic feasible solution.

(2) To obtain an optimal solution by making successive improvement to initial basic feasible solution.

Essay on the Method for Finding Initial Basic Feasible Solution:

An initial solution is a first attempt to match supply and demand along advantageous distribution routes for it to be a feasible solution, it must meet the following conditions.

(1) The rein condition of the transportation table must be satisfied – the sum of the quantities in occupied cells for rows and columns must equal the corresponding rein quantities.

(2) The no. of occupied cells must equal one less than the sum of the number of origins (m) and destinations (n); i.e., in + n – 1.

(3) The occupied cell must be independent positions. Dependent positions allow a round trip from an occupied ceil back to itself using only horizontal and vertical movements with right angle turns at occupied cells.

There are several methods available to obtain an initial solution.

Some are listed below:

(1) North – West corner method (NWCM)

(2) Least cost method

(3) Vogel’s approximation method

(1) North – West Corner Method:

Various steps of this method are following:

Step (1):

Start with the North – West (upper left) corner of transportation matrix and allocate as many units as possible equal to the minimum between available supply and demand requirement, i.e., min (s₁, d₁).

Step (2):

Adjust the supply and demand numbers in the respective rows and columns allocation.

Step (3):

(a) If the supply for the first row is exhausted then move down to the first cell in the second row and first column and go to step (2).

(b) If the demand for the first column is satisfied, then move horizontally to the next cell in the second column and first row and go to step (2).

Step (4):

If for any cell, supply equals demand, then the next allocation can be made in cell either in the next row or column.

Step (5):

Continue the procedure until the total available quantity is fully allocated to the cells as required.

Example:

To illustrate the NWCM, let us consider the transportation table as given in the Article (5.1.4).

Step (1):

First we start with the cell (F₁, W₁), and allocate them in (s₁, d₁) = (11.6) = 6

.^.. We allocate 6 units to this cell which completely exhausts requirement of warehouse w₁ and leaves a balance of (11 – 6) = 5 unit of supply at factory F₁.

Step (2):

Next we move horizontally to the next cell in the second column and first row i.e. (F₂, W₁). At this stage, the largest allocation possible is the min (s, – 6, d₂) = min (5, 10) = 5.

This allocation of 5 units to the cell IV,) completely satisfied the supply of factory F₁. However this leaves a balance of (10 – 6) = 4 units of demand at warehouse W₂

Step (3):

Now we move again vertically to the cell (F₂, W₂). Since the supply available at factory F₂ is 13 units and demand of warehouse W₂ is 5 units, the min (13, 5) = 5 units are allocated to cell (F₂, W₂). The requirement of warehouse W₂ is now satisfied and a balance of (13 – 5) = 8 units of supply remain at factory F₂. Moving again horizontally, we allocate 8 units to the cell (F₂, W₃) which completely exhausts the supply at factory F₂ and leaves a balance of 4 units demand at warehouse W₃.

Step (4):

Further, we move vertically downward to the cell (F₃, W₃). At this cell, 4 units are required at warehouse W₃ and 19 units are available at factory F₃. So we allocate 4 units to this cell (F₃, W₃). Finally, we eel locate 15 units to cell (F₄, W₄) to meet the rein requirements. Hence we have made all the allocations. It may be here that 6 (4 + 31) allocation which are necessary to proceed further. The initial feasible solution is shown below.

The total cost of transportation with this solution is obtained by multiplying each x_ij in occupied cell with the corresponding c_ij and summing up as follows:

Total cost = 6 (21) + 5 (16) + 5 (18) + 8 (14)+ 4 (18) + 15 (41) = Rs. 1055

(2) Least-Cost Method:

The main steps of this method are:

Step (1):

(a) Select the cell with the lowest transportation cost among all the rows or columns of the transportation table.

(b) If the minimum cost is not unique, then select arbitrarily any cell with this minimum cost.

Step (2):

Allocate as many units as possible to the cell determined in step 1 and eliminate that row in which either supply is exhausted or demand is satisfied.

Step (3):

Repeat step (1) and (2) for the reduced table until the entire supply at different factories is exhausted to satisfy the demand at different warehouses.

Example:

Consider again the previous transportation table for the illustration of least cost method.

Step (1):

Here the lowest cost (i.e. Rs 14) appears in cell (F₂, W₃).

Because production at factory F₂ and warehouse requirement of W₃ are 13 and 12 units respectively:

we assign x₂₃ = 12

This allocation meets the requirements of warehouse W₃ and still leaves a supply of 1 unit at factory F₂. Consequently, we delete the third column, adjust the supply remaining at the factory, and reduce the requirements of warehouse to zero as shown in Table (5.5).

(2) Since all three rows and the first, second and fourth columns are not yet crossed out, we return to step (1) and repeat the process. The smallest cost in the remaining matrix is 13 in cell (F₁, W₄).

Because the capacity of factory F₁ is 11 units and the requirements of warehouse W₄ is 15 units, we allocate x₄ = 11 and cross out first row. The requirement of warehouse W₄ not yet met is shown in Table (5.6).

Step (3):

Because there are two rows and three columns not yet crossed out, we go back to step (1) The smallest entry in the remaining cost matrix 11 in cell (F₂, W₁) located in the middle left hand corner obviously exhausts the supply at factory F₂ and we cross out the second row.

This algorithm requires two more steps to assign successively x₃₂ = 10 and then allocate the assignments x₃₁= 5 and x₃₄ = 4 in the third row. The complete initial basic feasible solution, along with the original rein condition is shown in Table (5.7) below.

Step (4):

The total transportation cost of initial solution by LC method is calculated as given below.

Total Cost = (11×13)+(1×17) + (12×14)+(5×32)+(10×27)+(4×41) = Rs.922

(3) Vogel’s Approximation Method (VAM):

The various steps in VAM are summarized as follows:

Step (1):

Calculate penalties for each row (column) by taking the difference between the smallest and next smallest unit transportation cost in the same row (column). This difference indicates the penalty which has to be paid if one fails to allocate to the cell with the minimum unit transportation cost. These no. also represents the difference between the distribution cost on the best route in the row (column) and the second best route in the row (column).

Step (2):

Identify the row (or column) with the largest penalty and allocate the maximum possible quantity to the lowest cost cell in that selected row (or column) so as to exhaust either the supply at a particular Source or satisfy demand at a warehouse.

If a tie occurs in the value of penalties, select that row/column which has minimum cost. If there is a tie in the minimum cost also, select that row (column) which will have maximum possible assignment. It will considerably reduce computational work.

Step (3):

Adjust the supply and demand and cross out the satisfied row or column. If a row and a column are satisfied simultaneously, only one of them is crossed out and the remaining row is assigned a zero supply (demand). Any row (column) with zero supply or demand should not be used in computing future penalties.

Step (4):

Re-compute the row and column differences for the reduced transportation table, omitting rows (or columns) crossed out in the preceding step.

Step (5):

Repeat step (1) to (3) until an initial feasible solution has been obtained (i.e., until the entire available supply at various sources are exhausted to satisfy demand at different destinations).

Example:

Consider again the transportation table of the previous illustration for the explanation of Vogel’s approximation method.

The highest difference of penalty rating of 10 falls under row F₁. Because first allocation is to be made to the lowest cost cell under row F₁. We assign x₁₃ =11.

This allocation meets the requirement of F₁ and leaves a supply of 4 units at warehouse W₄. Deleting the row corresponding to route for each origin and the remaining destination as shown in Table (5.9) below.

Now the highest penalty rating of 18 falls in the fourth column. We therefore, make an allocation of 4 units to the lowest cost cell that exhausts the requirement of warehouse W₄ and leaves partially the capacity of factory F₂. Removing the fourth column from the matrix, we make suitable adjustments in the supply remaining at factory F₂ and the demand at warehouse W₄. The difference for the remaining origins and destination are recomputed.

The result is shown in table (5.10) below.

Because the maximum difference occurs in the column for W₂ and the row for W₃, we may arbitrarily select any one of these. Suppose we select row corresponding to F₃ and make an allocation of 12 units to the lowest-cost all in the row. This assignment of x₃₃ = 12 satisfies the requirement of warehouse W₃ and reduce capacity at factory F₃ accordingly.

The next step brings in the cell (F₂, W₂) the assignment x₂₂, = 3 followed by the entry x₃₂ = 7 units which certainly satisfies the demand of warehouse W₂. Finally all the assignments made are displayed in the following table (5.12).

The initial basic feasible solution thus obtained is: