Transportation Problem

Transportation Problem

Learning objectives

• To formulate a transportation problem.
• Locate a basic feasible solution of a transportation problem by various methods.

In Operations Research, Linear programming is one of the models in mathematical programming, which is very broad and vast. Mathematical programming includes many more optimization models known as Linear programming, Non – linear Programming, Stochastic programming, Integer Programming and Dynamic Programming-each one of them is an efficient optimization technique to solve the problem with a specific structure, which depends on the assumptions made in formulating the model.

The TRANSPORTATION problem is a special kind of Linear Programming Problem whose objective is totransport a homogeneous commodity from various originsor factories to different destinations or markets at a totalminimumcost. The model can be represented by the network in the given Figure 1.

Figure 1: Representation of the transportation model

Source: Taha, Hamdy A., “Operations Research An Introduction”(Book), Pearson

There are m sources and n destinations, each represented by a node. The arcs represent the routes linking the sources and the destinations. Arc (i, j) joining source i to destination j carries two pieces of information: the transportation cost per unit, c_ij, and the amount shipped, x_ij. The amount of supply at source i is a_i, and the amount of demand at destination j is b_j. The objective of the model is to minimize the total transportation cost while satisfying all the supply and demand restrictions.

Example

• To understand the problem more clearly, let us take an example and discuss the rationale of transportation problem.
• Three factories A, B and C manufacture sugar and are located in different regions. Factory A manufactures b1 tons of sugar per year and factory B manufactures b2 tons of sugar per year and C manufactures b3 tons of sugar. The sugar is required by four markets W, X, Y and Z. The requirement of the four markets is as follows: Demand for sugar in Markets W, X, Y and Z is d1, d2, d3 and d4 tons respectively.

The transportation cost of one ton of sugar from each factory to market is given in the matrix below.

The objective is to transport sugar from factories to the markets at a minimum total transportation cost.

The above problem has got the following properties:

• It has an objective function.
• It has structural constraints.
• It has a non-negativity constraint.
• The relationship between the variables and the constraints are linear. We know very well that these are the properties of a linear programming problem. Hence the transportation model is also a linear programming problem. But a special type of linear programming problem.

 Initial Basic Feasible Solution

Step 1.

• Balancing the given problem. Balancing means check whether sum of availability constraints must be equals to sum of requirement constraints. That is Σbi = Σdj . Once they are equal, go to step two.
• If not by opening a Dummy row or Dummy column balance the problem. The cost coefficients of dummy cells are zero.
• If Σbi is greater than Σdj, then open a dummy column, whose requirement constraint is equals to Σbi – Σdj and the cost coefficient of the cells are zeros.
• In case if Σdj is greater than Σbi, then open a dummy row, whose availability constraint will be equals to Σdj – Σbi and the cost coefficient of the cells are zeros. Once the balancing is over, then go to second step.

Step II.

A Basic feasible solution can be obtained by three methods,

• North – west corner method.
• Least – cost cell method.
• Vogel’s Approximation Method, generally known as VAM.

After getting the basic feasible solution (b.f.s.) give optimality test to check whether the solution is optimal or not. There are two methods of giving optimality test:

(a) Stepping Stone Method.

(b) Modified Distribution Method, generally known as MODI method.

Properties of a Basic feasible Solution

Now, when we have a basic feasible solution, we need to check its properties, say

1. The allocation made must satisfy the rim requirements, i.e., it must satisfy availability constraints and requirement constraints.
2. It should satisfy non-negativity constraint.
3. Total number of allocations must be equal to (m + n – 1), where ‘m’ is the number of rows and ‘n’ is the number of columns.

 Example

Four factories, A, B, C and D produce sugar and the capacity of each factory is given below: Factory A produces 10 tons of sugar and B produces 8 tons of sugar, C produces 5 tons of sugar and that of D is 6 tons of sugar. The sugar has demand in three markets X, Y and Z. The demand of market X is 7 tons, that of market Y is 12 tons and the demand of market Z is 4 tons.

The following matrix gives the transportation cost of 1 ton of sugar from each factory to the destinations. Find the Optimal Solution for least cost transportation cost.

Here Σbi is greater than Σdj hence we have to open a dummy column whose requirement constraint is 6, so that total of availability will be equal to the total demand.

North-west corner method

• Balance the problem. That is see whether Σbi=Σdj. If not open a dummy column or dummy row as the case may be and balance the problem.
• Start from the left hand side top corner or cell and make allocations dependingon the availability and requirement constraint.If the availability constraint isless than the requirement constraint, then for that cell make allocation in unitswhich is equal to the availability constraint. In general, verify which is the smallest among the availability and requirement and allocate the smallest one to the cell under question. Then proceed allocating either side wise or downward to satisfy the rim requirement. Continue this until all the allocations are over.
• Once all the allocations are over, i.e., both rim requirement (columnand row i.e., availability and requirement constraints) are satisfied, write allocations and calculate the cost of transportation.

The count the allocations, if it is equals to m + n – 1, then the solution is basic feasible solution. The solution, we got have 6 allocations which is not = 4 + 4 – 1 = 7. Hence the solution is not a basic feasible solution.

Transportation cost = Rs 4 x 7 +Rs 3 x 3 + Rs 6 x 8 + Rs 4 x 1 + Rs 3 x 4 + Rs 0 x 6 =  101

Matrix minimum method or Least cost method

Step1: Identify the lowest cost cell in the given matrix. In this particular example it is equal to 0. Four cells of dummy column are having zero. When more thanone cell has the same cost, then both the cells are competing for allocation.This situation in transportation problem is known as tie.To break the tie, select any one cell of your choice for allocation.

Step 2: Make allocations to this cell either to satisfy availability constraint orrequirement constraint. Once one of these is satisfied, then mark crosses (×) in all the cells in the row or column which ever has completely allocated.

Step3: Next search for lowest cost cell and proceed this way until all allocations are made. Then write allocations and find the cost of transportation.

As the total number of allocations are 7 which is equals to 4 + 4 – 1 = 7, the solution is basic feasible solution.

Transportation cost = Rs 0 x 6 + Rs 1 x 2 + Rs 2 x 2 + Rs 3 x 8 + Rs 3 x 6 + Rs 4 x 4 + Rs 6 x 1 = 70

The transportation cost using the North-West Corner Rule was Rs. 101.

In the next blog, we will continue with the third method of finding the initial basic feasible solution of a transportation problem and its name is Vogel Approximation Method, also known as VAM.

Out of the three methods, the VAM method gives the least transportation cost.

OK Students, Happy Learning!

Author Name: Dr. Priyadarshini Singh

Department: Computer Applications (MCA)

Email-Id:-singh.priyadarshini80@gmail.com