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 a_{1}, a_{2}, .... , a_{m} units and demands at the markets be b_{1}, b_{2}, ...., b _{n} units.

Also consider

c_{ij} = Unit of cost of shipping from factory i to market j.

x_{ij} = Quantity shipped from factory i to market j.

Then the LP formulation can be started as follows :

Minimize z = Total cost of transportation

= ∑ c_{ij} x_{ij}

Subject to, Σx_{1}; ≤ a_{i}, i = 1, 2, …. m.

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

∑x_{ij} ≥ b_{j} , j = 1, 2, …,n.

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

x_{ij} ≥ 0 for all i and j.

Here the market demand can be met if

∑ a_{ij }≥ ∑b_{ij}

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

x_{ij} 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 x_{ij} and per unit transportation cost c_{ij}.

**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)

Overall supply,

Total demand met of a destination

Since overall supply exactly met the overall demand

x_{ij} ≥ 0 since a; and b_{j }are non-negative.

Therefore x_{ij} 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,

Since Σa_{i}= Σb_{j}, 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.