USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Introduction and Mathematical Formulation

Transportation problem (T.P.) is generally concerned with the distribution of a certain commodity/ product from several origins/sources to several destinations with minimum total cost through single mode of transportation. If different modes of transportation considered then the problem is called 'solid T.P'. In this chapter we shall deal with simple T.P.

 

Suppose there are m factories where a certain product is produced and n markets where it is needed. Let the supply from the factories be a1, a2, .... , am units and demands at the markets be b1, b2, ...., b n units.

 

Also consider

cij = Unit of cost of shipping from factory i to market j.

xij = Quantity shipped from factory i to market j.

Then the LP formulation can be started as follows :

 

Minimize z = Total cost of transportation

= ∑ cij xij

 

Subject to,   Σx1; ≤ ai, i = 1, 2, …. m.

(Total amount shipped from any factory does not exceed its capacity)

∑xij ≥ bj , j = 1, 2, …,n.

(Total amount shipped to a market meets the demand of the market)

xij ≥ 0 for all i and j.

 

Here the market demand can be met if

∑ aij ≥ ∑bij

If Σai Σbj i.e., total supply = total demand, the problem is said to be "Balanced T.P." and  all the constraints are replaced by equality sign.

xij 2: 0 for all i and j.

(Total m + n constraints and nm variables)

The T.P. can be represented by table form as given below :

In the above, each cell consists of decision variable xij and per unit transportation cost cij.

 

Theorem 1. A necessary and sufficient condition for the existence of a feasible solution to a T.P. is that the T.P. is balanced.

Proof. (Necessary part)

 

Total supply from an origin

Overall supply,

Total demand met of a destination

Overall demand,

Since overall supply exactly met the overall demand

xij ≥ 0 since a; and bj are non-negative.

 

Therefore xij satisfies all the constraints and hence xii is a feasible solution.

 

Theorem 2. The number of basic variables in the basic feasible solution of an m x n T.P. is m + n-1.

 

Proof. This is due to the fact that the one of the constraints is redundant in balanced T.P.

We have overall supply,

and overall demand

Since Σai= Σbj, the above two equations are identical and we have only m + n – 1 independent constraints. Hence the theorem is proved.

Note. 1. If any basic variable takes the value zero then the basic feasible solution (BFS) is said to be degenerate. Like LPP, all non-basic variables take the value zero.

 

2. If a basic variable takes either positive value or zero, then the corresponding cell is called 'Basic cell' or 'Occupied cell'. For non-basic variable the corresponding cell is called 'Non-basic cell' or 'Non-occupied cell' or 'Non-allocated cell'.

 

Loop. This means a closed circuit in a transportation table connecting the occupied (or allocated cells satisfying the following :

 

(i)              It consists of vertical and horizontal lines connecting the occupied (or allocated) cells.

(ii)            Each line connects only two occupied (or allocated) cells.

(iii)          Number of connected cells is even.

(iv)          Lines can skip the middle cell of three adjacent cells to satisfy the condition (ii).

 

The following are the examples of loops .Note. A solution of a T.P. is said to be basic if it does not consist of any loop.