Transportation Problem

Transportation Problem

The objective of transportation problem is to determine the amount to be transported from each origin to each destinations such that the total transportation cost is minimized.

Definition and formulation

The Structure of the Problem

Let there be m origins and n destinations. Let the amount of supply at the i th origin is a_i. Let the demand at j th destination is b_j.

The cost of transporting one unit of an item from origin i to destination j is c_ij and is known for all combinations (i,j). Quantity transported from origin i to destination j be x_ij

The objective is to determine the quantity x_ij to be transported over all routes (i,j) so as to minimize the total transportation cost. The supply limits at the origins and the demand requirements at the destinations must be satisfied.

The above transportation problem can be written in the following tabular form:

Now the linear programming model representing the transportation problem is given by

Some Definitions

Feasible Solution: A feasible solution to a transportation problem is a set of non-negative values x_ij(i=1,2,..,m, j=1,2,…n) that satisfies the constraints.

Basic Feasible Solution: A feasible solution is called a basic feasible solution if it contains not more than m+n–1 allocations, where m is the number of rows and n is the number of columns in a transportation problem.

Optimal Solution: Optimal Solution is a feasible solution (not necessarily basic) which optimizes(minimize) the total transportation cost.

Non degenerate basic feasible Solution: If a basic feasible solution to a transportation problem contains exactly m+n–1 allocations in independent positions, it is called a Non degenerate basic feasible solution. Here m is the number of rows and n is the number of columns in a transportation problem.

Degeneracy :If a basic feasible solution to a transportation problem contains less than m+n–1 allocations , it is called a degenerate basic feasible solution. Here m is the number of rows and n is the number of columns in a transportation problem.