TRANSPORTATION PROBLEM

UNIT III
 CONTENTS

• Introduction
• Balanced or unbalanced transport problems
• Applications of transport problems
• North-west corner method
• Least cost method
• Vogel’s approximation method
• Test of optimality by stepping stone method and
MODI method
 Introduction

• The transportation problem is a special type of LPP where the

objective is to minimize the cost of distributing a product from
a number of sources or origins to a number of destinations

• Because of its special structure the usual simplex method is

not suitable for solving transportation problems . These
problems require special method of solution.
 The Transportation Problem

• The problem of finding the minimum-cost distribution of a

given commodity from a group of supply centers (sources)
i=1,…,m
• To a group of receiving centers (destinations) j=1,…,n
• Each source has a certain supply(s1)
• Each destination has a certain demand (d1)
• The cost of shipping from a source to a destination is directly
proportional to the number of units shipped
 Mathematical Formulation

Let there be m origins, ith origin possessing ai units of a

certain product , where as there are n destinations with
destination j requiring bj units .Cost of shipping of an item
from each of m origins to each of n destinations are known
directly or indirectly in terms of shipping hours. Let cij be the
cost of shipping one unit product from ith origin to jth
destination, and xij be the amount to be shipped from ith
origin to jth destination. It is also assumed that total
availabilities Ʃ ai satisfy the total requirements Ʃ bj i.e.
Ʃ ai = Ʃ bj (i=1,2,……,m; j=1,2,…….,n)
(in case ,Ʃai ≠Ʃbj some manipulation is required to
make Ʃ ai =Ʃbj, which will be shown later).
The problem is to determine non-negative values of
xij satisfying both ,the availability constrains :
n
Ʃ xij = ai for i=1,2,….,m
j=1
As well as the requirement constrains :
m
Ʃ xij = bj for j=1,2,….,n
i=1
And minimizing the total cost of transportation (shipping)
m n
Z= Ʃ Ʃ xij cij (objective function)
i=1 j=1

Since the constraint equations and the objective function

are all linear in xij ,so it may be looked like a linear
programming problem .
This special type of LPP will be called a
Transportation Problem (T.P.).
 Simple Network Representation

Sources Destinations
supply s1 1 1 demand d 1

2 2
supply s2 demand d 2
: :
m : n :
supply sm xij demand dn

costs cij
 Few Important Definitions
A Feasible Solution A feasible solution to a transportation
problem is a set of non–negative individual allocation
(xij ≥0)with the row and column sum restrictions.
• Basic Feasible Solution(B.S.F.) A feasible solution of m by
n transportation problem is said to be a basic feasible
solution if the total no. of positive allocations xij is exactly
equal to m+n-1.
• Optimal Solution A feasible solution is said to be optimal if it
minimizes the total transportation cost.
• Non- Degenerate Basic Feasible Solution F.S. of an m*n
transportation problem is said to be non–degenerated if it has
the following two properties:
(1)Initial BFS must contain exactly m+n-1 number of
individual allocations .
(2)These allocation must be in “independent positions.”
Independent position of a set of allocations mean that it is
always impossible to form any closed loop through these
Balanced or unbalanced transport problems

allocations.

• Balanced transportation problem where the total supply equals

total demand

• Unbalanced transportation problem where the total supply is

not equal to the total demand
 Applications of transport problems

• Minimize shipping costs

• Determine low cost location

• Find minimum cost production schedule

• Military distribution system

 Phases of solution of transportation problem

Phase I-obtains the initial basic feasible solution

Phase II-obtains the optimal basic solution

 Initial basic feasible solution

• North west corner rule (NWCR)

• Least cost method

• Vogel’s approximation method (VAM)

 North west corner rule (NWCR)

• The simplest of the procedures used to generate an initial

feasible solution is NWCM. It is so called because we begin
with the North West or upper left corner cell of our
transportation table. Various steps of this method can be
summarized as under.
• Step 1
Select the North West (upper left-hand) corner cell of the
transportation table and allocate as many units as possible
equal to the minimum between available supply and demand
requirement i.e., min (S1, D1).
Step 2
Adjust the supply and demand numbers in the
respective rows and columns allocation.

Step 3
• 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.
• 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.
 Least Cost Method

• The allocation according to this method is very useful as it

takes into consideration the lowest cost and therefore, reduce
the computation as well as the amount of time necessary to
arrive at the optimal solution.
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
(column) in which either supply is exhausted or
demand is satisfied.
Repeat Steps 1 and 2 for the reduced table until the
entire supply at different plants is exhausted to
satisfied the demand at different warehouses.
 Unit Cost-Penalty Method (Vogel’s Approximation
Method i.e. V.A.M.)

• This method is preferred over the other two methods because

the initial feasible solution obtained is either optimal or very
close to the optimal solution.
Step 1:
Compute a penalty for each row and column in the
transportation table.
Step 2:
Identify the row or column with the largest penalty.
Step 3:
Repeat steps 1 and 2 for the reduced table until entire supply at
plants are exhausted to satisfy the demand as different
warehouses.
 Optimum basic solution

• Stepping stone method

• MODI method
 Stepping stone method
Step 1:
For each unoccupied cell, calculate the reduced cost by the MODI
method described below.
Select the unoccupied cell with the most negative reduced cost.
(For maximization problems select the unoccupied cell with the
largest reduced cost.) If none, STOP.
Step 2:
For this unoccupied cell generate a stepping stone path by forming
a closed loop with this cell and occupied cells by drawing
connecting alternating horizontal and vertical lines between them.
Determine the minimum allocation where a subtraction is to be
made along this path.
Step 3:
Add this allocation to all cells where additions are to be made,
and subtract this allocation to all cells where subtractions are to
be made along the stepping stone path.
(Note: An occupied cell on the stepping stone
path now becomes 0 (unoccupied). If more than one cell
becomes 0, make only one unoccupied; make the others
occupied with 0's.)
GO TO STEP 1.
 MODI method
• In applying the MODI method, we begin with an initial
solution obtained by using the northwest corner rule or any
other rule. But now we must compute a value for each row
(call the values u1 , u2, u3 if there are three rows) and for each
column (v1 , v2 , v3 ) in the transportation table. In general, we
let

ui = value assigned to row i

vj = value assigned to column j
cij = cost in square ij (cost of shipping from source i to
destination j)
The MODI method then requires five steps:
1. To compute the values for each row and column, set
cij = ui + vj
but only for those squares that are currently used or occupied.
For example, if the square at the intersection of row 2 and
column 1 is occupied, we set
c21 = u2 + v1
2. After all equations have been written, set u1 = 0.
3. Solve the system of equations for all u and v values.
4. Compute the improvement index for each unused square by
the formula improvement index
(dij) = cij - ui - vj
5. Select the largest negative index and proceed to solve the
problem as you did using the stepping-stone method.
 Computational procedure of optimality test
After getting the initial B.F.S. of a transportation problem ,we
test solution for optimality as follows:
1. For a B.F.S. we determine a set of (m + n) numbers
ui i=1,2,…,m
vi i=1,2,…,n
Such that, for each occupied cell(r , s)
crs = ur + vs
For this we assign an arbitrary value to one of the ui or vj then
the rest (m+n-1) of them can easily be solved algebraically from
the relation crs = ur + vs , for occupied cells.
 Generally we choose that ur or vs =0 for which the
corresponding row or column have the maximum number of
individual allocations.
2.Then we calculate the cell evaluations for each unoccupied cell
(i,j) by using the formula
dij = cij - (ui+ vj )
3.Then we examine the matrix of cell evaluations and conclude that
(1) if all dij >0, then the solution under test is optimal and unique.
(2) if all dij ≥0, with at least one dij =0 , then the solution under test
is optimal and alternative optimal solution exists.
(3) if at least one dij<0, then the solution is not optimal.
In the last case we proceed to the next step 4.
4. If at least one dij<0, in step 3,then we form a new B.F.S in the
next B.F.S . We give maximum allocation to the cell for which
dij is minimum and negative ,by making an occupied cell
empty.
5. Then we repeat the steps 1 to 3 to test the optimality to this new
B.F.S we continue the process till we get an optimal solution.
 Example
Solve the following transportation problem
To Supply
w1 w2 w3
2 7 4 5
F1

From 3 3 1 8
F2

5 4 7 7
F3
 Solution By North-West Corner Method

• We move to the right of this cell. We start with cell (1,1) at the
north-west corner (top most left corner)and allocate it
maximum possible amount 5.
• Since there is no amount left available at source F1 so we move
downwards to the cell (2,1) in place of moving to right and
allocate it maximum possible amount. Since the column1 still
need the amount 2 and the amount 8 is available in row 2, so we
allocate the maximum amount 2 to this cell(2,1).now the
allocation for column 1 is complete ,so we move to the right of
this cell.
• Since the amount 6 is still available in row 2 and amount 9 is
needed in column2,so we allocate the maximum amount 6 in
this cell (2,2).
• Thus , allocation for row2 is complete, so we move downwards to
the cell(3,2) . Since the amount 3 is still needed in column 2 and
amount 7 is available in row 3 ,so we allocate the maximum
amount 3 in this cell(3,2). Thus allocation for column 2 is
complete ,so
• Since the amount 4 is still available in row 3 and amount 18 is
needed in column 3,so we allocate the maximum amount 4 in this
cell (3,3). Thus , allocation for row 3 is complete, so we move
downwards to the cell(4,3) . Since the amount 14 is still available
in row3 and an equal amount 14 is needed in row 4 ,so we
allocate the maximum amount 14 in this cell(4,3). This complete
the allocation and the resulting feasible solution are shown in the
following table.
 To
w1 w2 w3
5(2 )
F1 5 = a1

F2 8= a2
\

From
F3 7= a 3

2(3) 6(3)
F4 14=a4

7=b1 9=b2 18=b3

3(4) 4(7)
Therefore the total transportation cost of this feasible solution is
=Rs.(5*2+2*3+6*3+3*4+4*7+14*2) 14(2) =Rs. 102
 SOLUTION BY Least cost method

• First we write the cost and requirement matrix as follows:

To
w1 w2 w3

F1 (2) 2(7) 3(4) 5= a1

(3) (3) 8(1)

F2 8= a2
From (5) 7(4) (7)
F3 7= a3
7(1) (6) 7(2)

F4 14=a4

7= b1 9= b2 18= b3
 Examining the cost matrix we find that there is lowest cost 1
in cell(2,3) and in (4,1).We choose the cell(2,3) as we can
allocate the maximum amount 8 to this cell which is more than
the max. amount 7 that can be allocated to cell(4,1).Leaving
this cell we find that there is lowest cost 1 in cell (4,1) where
we allocate the max. amount 7.Continuing in this way we get
the required feasible solution as shown in the above table.
The total transportation cost to this F.S. is
=Rs.(2*7+3*4+8*1+7*4+7*1+7*2)=Rs.83
 Vogel’s approximation method (VAM)
• First we write the cost and requirement matrix as follows:
w1 w2 w3 Available Penalties
F1 (2) (7) (4)
5 (2)

F2 8 (2)

F3 (3) (3) 8(1) 7 (1)

F4 (5) (4) (7) 14 (1)

(1) (6) (2)
Demand 7 9 18

Penalties (1) (1) (1)

• Since the maximum penalty (2) is associated with row 1 and
row 2 , and we can allocate more amount 8 to the lowest cost
cell (2,3) of row 2 than the maximum amount 5 that we can
allocate at the lowest cost cell (1,1) of row 1,so we allocate the
amount 8 to the cell (2,3) and cross this row 2.the first reduced
matrix after leaving row 2,with remaining demands and
availabilities is as follows:
 w1 w2 w3 Available Penalties

F1 (2) (7) (4)

5 (2)
(5) (4) (7)
F2 7 (1)
(1) (6) 10(2)
F4 14 (1)

Demand 7 9 18

Penalties (1) (2) (2)

• Since the maximum penalty (2) is associated with row
1,column 2 and 3,so the maximum possible amount 10 is
allocated to the cell (3,3) with lowest cost in 3rd column.
• The second reduced matrix after leaving column 3rd of the
above matrix with remaining demands and availability is as
follows:
• Note that the maximum amounts that can be allocated to
lowest cost cell (1,1) in row 1 and cell (2,2) in column 2 are
less than amount 10 that can be allocated to lowest cost cell
(3,3) in column 3rd .
 w1 w2 Available Penalties
(2) (7)
F1 5 (5)
(5) (4)
F3 7 (1)
4(1) (6)
F4 14 (5)

Demand 7 9

Penalties (1) (2)

Since the maximum penalty (5) is associated with row 2 and 3

of the matrix, so the maximum possible amount 4 is allocated
to the cell (3,1) with lowest cost in row 3.
The third reduced matrix after leaving row 3 of the above
matrix with remaining demand and availability is as follow :
 w1 w2 Available Penalties
3(2) 2(7)
F1 5 (5)
(5) 7(4)
F3 7 (1)
Demand 3 9
Penalties (3) (3)
Since the maximum penalty (5) is associated with row 1 so the
maximum possible amount 3 is allocated to the cell (1,1) with
lowest cost in this row .the remaining amount 2 in row 1 is
allocated to the cell (1,2) and then we allocate the remaining
amount 7 to the cell (2,2).Thus, we get the required feasible
solution as shown in the following table:
 w1 w2 w3 Available

F1 3(2) 2(7) (4)

5
(3) (3) 8(1)
F2 (5) 7(4) (7) 7
4(1) (6) 10(2)
F4 14
Demand 7 9 18
the total transportation cost to this F.S.
=Rs.(3*2+2*7+8*1+7*4+4*1*10*2) = Rs.80
Which is less than the cost associated with the feasible solution obtained
by the previous methods 1and 2.
 Example

• Solve the following transportation problem

To Supply

w1 w2 w3 w4
F1 1 2 1 4 30

from F2 3 3 2 1 50

F3 4 2 5 9 20

Demand 20 40 30 10 100
• Determine the optimal transportation cost , for the
following transportation model:
D1 D2 D3 D4 Supply
O1 2 2 2 1 3
O2 10 8 5 4 7
O3 7 6 6 8 5
Demand 4 3 4 4
• Determine the optimal transportation cost , for the following
transportation model:

M1 M2 M3 M4 Supply
W1 5 3 6 2 19
W2 4 7 9 1 37
W3 3 4 7 5 34
Demand 16 18 31 25
 To Modify Unbalanced T.P.to Balanced Type

• An unbalanced T.P. may occur in two different forms

Excess of availability
Shortage in availability
We now discuss these two cases by considering our usual m-origin,n
destination T.P. with the condition that
m n
∑ ai ≠ ∑ bj
i=1 j=1

Case 1. (excess Availability, i.e. ∑ ai ≥ ∑ bj ).

The general T.P. may be stated as follows:
minimize m n
Z= ∑ ∑ xij cij , subject to the constraints
i=1 j=1
 n
∑ xij ≤ ai, i =1,2,……m
j=1
m
∑ xij = bj, j=1,2,……n
i=1
and xij ≥ 0, i=1,2,……..m; j=1,2,……n.

The problem will possess a feasible solution if ∑ai ≥ ∑bj .In

the first constraint, the introduction of slack variable
xi,n+1(i=1,2,..m) gives
n
∑ xij + xi,n+1 =ai, i =1,2,……m
j=1
 m n m
∑ ( ∑ xij + xi,n+1 ) = ∑ ai, or
i=1 j=1 i=1

n m m m
∑ ( ∑ xij )+ ∑ xi,n+1 = ∑ ai,
j=1 i=1 i=1 i=1
Or m m n m
∑ xi,n+1 = ∑ ai - ∑ bj =Excess of Availability.( ∑ xij = bj)
i=1 i=1 j=1 i=1
If this excess availability is denoted by b n+1 , the modified general T.P. can be
reformulated as:
Minimize m n+1
Z= ∑ ∑ xij (cij,), subject to the constraints
i=1 j=1
• n
∑ xij + xi,n+1 =ai, i =1,2,……m
j=1
m
∑ xij = bi, j =1,2,……n
i=1
xij ≥ 0, for all i and j , m n+1
where ci,n+1 =0 for i=1,2,…..m ∑ ai = ∑ bj
i=1 j=1

This is clearly the balanced T.P. and thus can be easily

solved by transportation algorithm
Working rule : whenever (∑ ai ≥ ∑ bj ), we introduce a dummy destination- column in
the transportation table .The unit transportation costs to this dummy destination are all
set equal to zero . The requirement at this dummy destination is assumed to be equal to
the difference ∑ ai - ∑ bj .

Case 2.(shortage of availability ,i.e. ∑ ai ≤ ∑ bj ).

in this case, the general T.P. becomes:
Minimize m n
Z= ∑ ∑ xij (cij,), subject to the constraints:
i=1 j=1
n
∑ xij = ai, i =1,……, m
j=1
m
∑ xij ≤ bj j=1,……, n
i=1
xij ≥ 0, i=1,…..,m; j=1,…..n
Now, introducing the slack variable xm+1, j (j=1,…n)
In the second constraint, we get
m
∑ xij + xm+1, j =bj, ij=1,……n
i=1
Or n m n
∑ (∑ xij + xm+1, j ) = ∑ bj
j=1 i=1 j=1
Or m n n n
∑ (∑ xij )+ ∑ xm+1, j = ∑ bj
i=1 j=1 j=1 j=1
Or n n m
∑ xm+1, j = ∑ bj - ∑ ai = shortage in availability am+1, say.
j=1 j=1 i=1
Thus the modified general T.P. in this case becomes:
Minimize m+1 n
Z= ∑ ∑ xij cij,, subject to the constraints:
i=1 j=1
 n
∑ xij =ai , i=1,2…….m
j=1
m
∑ xij + xm+1,j= bj j=1,2,……m
i=1
xij ≥ 0, i=1,…..m+1; j=1….n
where cm+1,j =0 for j=1,…..n and n
m+1 n
∑ ai, = ∑ bj .
i=1 j=1
Working rule : whenever (∑ ai ≤ ∑ bj ), introduce a dummy
source in the transportation table .The cost of
transportation from this dummy source to any destination
are all set equal to zero . The availability at this dummy
source is assumed to be equal to the difference( ∑ bj - ∑