Transportation

Transportation is a special case of Linear Programming which deals with transporting a commodity
from source ( e.g. factory) to destination (e.g. warehouse or godown). Here the objective is to
determine the transportation schedule which shall minimize the total cost of transportation.

The important assumption here is that costs of transportation are proportional to no. of units
transported.

Let us set up a transportation table as a matrix with rows being source (factory: F 1, F2,…Fm) and
column being destination (warehouse or godown W 1, W2, ….Wn). The last column shall denote the
supplies available from each factory while last column shall be the demand from each warehouse.

The no. of units transported by ‘x’ where x 11 shall be units transported from Factory 1(F 1) to
Warehouse 1 (W1) , x 21shall be units transported from Factory 2(F2) to Warehouse 1 (W1)and so on.

Corresponding to Units transported there shall be costs ; C 11,shall be cost per unit when units are
transported from Factory 1(F1) to Warehouse 1 (W1)

Factory → W1 ↓ W2 ↓ W3 ↓ W4 ↓ ……… Wn ↓ SS Available

Warehouse↓
F1 → x 11 ,C11 x 12 ,C12 x 13 ,C13 . . x 1 n ,C1n S1 (Total SS
from Factory 1)
F2 → x 21 ,C21 x 22 ,C22 x 23 ,C23 . . . S2
F3 → . . . .
. . . . .
. . . . .
Fm→ x m 1 ,Cm1 x mn ,Cm n Sm
DD or D1 (total D2 D3 . . Dn n m

Requirement DD from ∑ D i=∑ S J

i=1 J=1
from W/H W/H 1)

Here the Objective is to minimize total cost

m n
Min Z= TC=[∑ ∑ (x ij C ij )]
i=1 j=1

n
s.t ∑ (x ij) = Supply Constraint from factory S i
j=1

∑ (x ij) = Demand Constraint from warehouse W i

i=1

x ij ≥0, for all i,j.

Q Formulate a transportation model after constructing a matrix for the following : A product ‘A’
moves from three production centres P1,P2 & P3 to three different shops S1, S2 and S3 . The shops
have limited storage capacity of 150, 250 and 200 units respectively while three production centres
produce good A with an output of 100,200 and 300 units of the product respectively.
The transportation costs are P1 to S1 : 10 , P1 to S2 : 12, P1 to S3 : 8 , P2 to S1 : 15 , P2 to S2 : 12, P2 to S3 :
16 , P3 to S1 : 10 , P3 to S2 : 11, P3 to S3 : 8

From Prod C → S1 S2 S3 Supply

To Shop↓
P1 10 x 11 12 x 12 8 x 13 100
P2 15 x 21 12 x 22 16 x 23 200
P3 10 x 31 11 x 32 8 x 33 300
Demand 150 250 200 600

Min Z= 10 x 11+ 12 x 12 +8 x 13+15 x 21+12 x 22+16 x 23 +10 x 31+11 x 32+8 x 33

s.t x 11+ x 12+ x 13=100

x 21+ x 22+ x 23=200

x 31+ x 32+ x 33=300

x 11+ x 21+ x 31=150

x 12+ x 22+ x 32=250

x 13+ x 23+ x 33=200

x ij ≥0, for i=j=1,2,3.

Note : All the constraints carry equality sign as these must be equal for optimization.

Solution to Transportation Method: Techniques

Least Cost Method (LCM)and Vogel’s Approximation Method(VAM)

Least Cost Method (LCM)

Methodology : First allocate or load the cell which has the least cost (allocation would mean lower
of supply or demand ) till exhausted, then move to the next least cost cell and so on

Q. Find a feasible solution (least cost of transportation) to following transportation Problem when
costs of transportation are as under ;-

From Factory W1 W2 W3 W4 Supply

→
To W/H ↓

F1 21 16 25 13 11

F2 17 18 14 23 13
 F3 32 27 18 41 19

Demand 6 10 12 15 43

Sol.

(i) Lowest cost is 13 (cell : F1 W4 ), we allocate max no. of units to this cell (the
corresponding demand is 15 while supply is 11; allocation must be lower of these two or
11)

From F → W1 W2 W3 W4 Supply
To W/H↓
F1 21 16 25 11 13 11 0
F2 17 18 14 23 13
F3 32 27 18 41 19
Demand 6 10 12 15 4 43

(ii) Next Lowest is 14 (cell : F2 W3 ), we allocate max no. of units to this cell (the
corresponding demand is 12 while supply is 13; allocation must be lower of these two or
12)

From F → W1 W2 W3 W4 Supply
To W/H↓
F1 21 16 25 11 13 0
F2 17 18 12 14 23 13 1
F3 32 27 18 41 19
Demand 6 10 12 0 4 43

(iii) Next Lowest is 16, but there is no supply remaining , so we leave that. Next Lowest is 17
(cell : F2 W1 ), we allocate max no. of units to this cell (the corresponding demand is 6
while supply is 1; allocation must be lower of these two or 1)

From F → W1 W2 W3 W4 Supply
To W/H↓
F1 21 16 25 11 13 0
F2 1 17 18 12 14 23 1 0
F3 32 10 27 18 41 19
Demand 6 5 10 0 4 43

(iv) Next Lowest is 18 (cell : F2 W2 or F3 W3 ), we cannot consider any of these cells as

allocation is not possible . Hence we go further to 23 (F2 W4 ) again not possible, next is
27 (F3 W2 ) and allocate 10 units

From F → W1 W2 W3 W4 Supply
To W/H↓
 F1 21 16 25 11 13 0
F2 1 17 18 12 14 23 0
F3 32 10 27 18 41 19 9
Demand 5 10 0 0 4 43

(v) Next lowest is 32 (F3 W1 ), allocate 5 units

From F → W1 W2 W3 W4 Supply
To W/H↓
F1 21 16 25 11 13 0
F2 1 17 18 12 14 23 0
F3 5 32 10 27 18 41 9 4
Demand 5 0 0 0 4 43

(vi) Finally we have 41 (F3 W1 ), allocate 5 units

From F → W1 W2 W3 W4 Supply
To W/H↓
F1 21 16 25 11 13 0
F2 1 17 18 12 14 23 0
F3 5 32 10 27 18 4 41 4 0
Demand 0 0 0 4 0 43

Cost Associated shall be 1 x 17 + 5x32 + 17 x 10 + 12 x14 + 11 x 13 + 41 x 4=

926

Vogel’s Approximation Method(VAM)

(i) Method computes penalty Cost; Penalty Cost = Difference between two cheapest costs ;
either two rows or two columns. This cost is computed for all rows and columns
(ii) Out of different penalty costs, identify the highest penalty cost.
(iii) Against corresponding highest penalty cost, there must be a row or column
(iv) Allocate max units to lowest cost cell in that row or column
(v) Eliminate the row or column when DD or SS becomes zero
(vi) Next proceed by computing penalty costs again and process is repeated

Q. Apply VAM to above transportation Problem

From Factory W1 W2 W3 W4 Supply

→
To W/H ↓
 F1 21 16 25 13 11

F2 17 18 14 23 13

F3 32 27 18 41 19

Demand 6 10 12 15 43

Sol Penalty Cost for Rows

Row F1 : 16-13 =3, Row F2 : 17-14 =3, Row F3 : 27-18 =9

Penalty Cost for Columns

Column W1: 21-17=4, Column W2: 18-16=2, Column W3: 18-14=4, Column W4: 23-13=10

The highest Penalty Cost is 10 which falls under column W4:

Next in find out in W4; the cell which has lowest cost , it is 13(F1 W4), we allocate max no. of units i.e.
11 to this cell

Matrix 1
From Factory W1 W2 W3 W4 Supply
→
To W/H ↓

F1 21 16 25 11 13 11 0

F2 17 18 14 23 13

F3 32 27 18 41 19

Demand 6 10 12 15 4 43

Now as per rule whichever row/colm has ‘0’ SS or DD gets removed , hence we remove F 1 and our
new matrix 2 is as under . Again Computing row and column penalty

Penalty Cost for Rows

Row F2 : 17-14 =3, Row F3 : 27-18 =9

Penalty Cost for Columns

Column W1: 32-17=15, Column W2: 27-18=9, Column W3: 18-14=4, Column W4: 41-23=18

The highest Penalty Cost is 18 which falls under column W4:

Next in find out in W4; the cell which has lowest cost , it is 23(F2 W4), we allocate max no. of units i.e.
4 to this cell

Matrix 2
 From Factory W1 W2 W3 W4 Supply
→
To W/H ↓

F2 17 18 14 4 23 13 9

F3 32 27 18 41 19

Demand 6 10 12 4 0 43

Now as per rule whichever row/colm has ‘0’ SS or DD gets removed , hence we remove W 4 and our
new matrix 3 is as under . Again Computing row and column penalty

Penalty Cost for Rows

Row F2 : 17-14 =3, Row F3 : 27-18 =9

Penalty Cost for Columns

Column W1: 32-17=15, Column W2: 27-18=9, Column W3: 18-14=4,

The highest Penalty Cost is 15 which falls under column W1:

Next in find out in W1; the cell which has lowest cost , it is 17(F2 W1), we allocate max no. of units i.e.
6 to this cell

Matrix 3
From Factory W1 W2 W3 Supply
→
To W/H ↓

F2 6 17 18 14 9 3

F3 32 27 18 19

Demand 6 0 10 12 43

Now as per rule whichever row/colm has ‘0’ SS or DD gets removed , hence we remove W 1 and our
new matrix 4 is as under . Again Computing row and column penalty

Penalty Cost for Rows

Row F2 : 18-14 =4, Row F3 : 27-18 =9

Penalty Cost for Columns

Column W2: 27-18=9, Column W3: 18-14=4

The highest Penalty Cost is 9 which falls under column W2 and also in row F3: As per rule we may
select either of the two, so let us select F3 .Next in find out in F3; the cell which has lowest cost , it is
18(F3 W3), we allocate max no. of units i.e. 12 to this cell
Matrix 4
 From Factory W2 W3 Supply
→
To W/H ↓

F2 18 14 3

F3 27 12 18 19 7

Demand 10 12 0 43

We finally have the matrix as

Matrix 5
From Factory W2 Supply
→
To W/H ↓

F2 3 18 3 0

F3 27 7

Demand 10 7 43

Penalty Cost for Column W2: 27-18=9, allocate 3 units of 18(F2 W2) and finally 7 units of 27(F3 W2 ),
hence entire demand and supply gets satisfied and cost allocation on the basis of VAM shall be

11 x13 + 6x17+4x23+12x18+3x 18 + 7 x 27 = 796

Q. Compute the Cost of transportation using LCM & VAM

From Factory I II III IV Supply

→
To W/H ↓

A 7 3 5 5 34

B 5 5 7 6 15

C 8 6 6 5 12

D 6 1 6 4 19

Demand 21 25 17 17 80

Sol : LCM = 330, VAM =324

 Question of Optimality
Although both LCM and VAM aim at achieving allocation of costs so as to minimize the
transportation costs, however we are still not sure that the solution provided by these techniques is
optimal or not ( i.e. we have reached a point whereby further reduction of cost is not possible). This
is because both these techniques are not of type of linear programming. Hence another exercise is
required which will tell us whether solution is optimal or still there is a scope of improvement and
this exercise is provided by Stepping Stone or MODI Method. The starting point of these two
techniques is LCM or VAM and then some improvement is attempted

Stepping Stone Steps (i) Transfer units from occupied cell to empty cell i.e. from a cell having max
cost to cell where units have not be assigned so far

(2) If the exercise is feasible then the occupied cell is removed and in its place new cell is added to
the final solution. This also would mean that the original solution (by LCM or VAM) was not optimal
and needed improvement

(3) Shifting of the Cells (from occ to empty) also affects the arrangement of other nearby cells, a loop
or a rectangle is formed resulting in compulsory shifting of cells once.

e.g. You are given initial solution using VAM technique. Apply stepping stone and check if any
improvement is possible

From Factory → D E F Supply

To W/H ↓

A 20 6 30 4 1 50
B 3 40 8 7 40
C 4 25 4 35 2 60
Demand 20 95 35 150
Initial TC = 20 X 6 + 30 X 4 + 40 X8 +25 X4 +35 X 2 = 730

Empty Cells : AF, BD, CD Occupied Cells :AD,AE,BE,CE, CF

In terms of Cost, BE has max cost of 40, we start by shifting max no. of units from BE to adjacent cells
. The adjacent cells to BE which are unoccupied are BD and BF. We select one cell which provides
max of savings in cost. By moving from BE to BD we save Rs 5 (Old Cost 8- New Cost 3), however
moving from BE to BF saves only Rs 1.

How much Units to be Shifted : Max 20 as BD cannot accommodate more than that as it has supply
restriction. Forming a Rectangle /Loop : The rectangle must result in savings , BE to BD : 5 (8-5)
saved, BD to AD :No assignment , AD to AE another savings of Rs 2 (6-4) , AE to BE : No assignment
Thus Rectangle gives a total savings of Rs 7

D E F Supply
From
Factory →
To W/H ↓
A 20 6 30 4 1 50

B 3 40 8 7 40
 C 4 25 4 35 2 60

Demand 20 95 35 150

From Factory D E F Supply

→
To W/H ↓

A 6 50 4 1 50

B 20 3 20 8 7 40

C 4 25 4 35 2 60

Demand 20 95 35 150

(4)

Checking if TC has fallen = 50 x 4 +20 x 3 +20 x 8 +25 x 4 + 35 x2=590

Rules for forming a rectangle

1. Rectangle is a Closed Path , starting and ending cell is same

2. There should be shifting of units followed by no shift, then again shifting of units and again
no shift i.e. 1st and 3rd must have units (2nd and 4th may or may not have units)
3. By passing an assignment /Jumping is not allowed
4. There must be savings in terms of cost from entire exercise
5. There must be assignment, followed by no assignment, then assignment, no assignment.
This would mean re-shifting of units after first shift is not allowed.
Check for Optimality

Can we form another rectangle resulting in further savings . Yes . If we shift some units from AE to AF
(we save 3 Rs) We check whether feasible as entire rectangle must give savings

From Factory D E F Supply

→
To W/H ↓

A 6 50 4 1 50

B 20 3 20 8 7 40

C 4 25 4 35 2 60

Demand 20 95 35 150

From Factory D E F Supply

→
To W/H ↓
A 6 15 4 35 1 50
B 20 3 20 8 7 40
C 4 60 4 2 60
Demand 20 95 35 150

Checking if TC has fallen = 15 x 4 +35 x 1 + 20 x 3 +20 x 8 +60 x 4 =555

Check for Optimality: Can we form another rectangle resulting in further savings . The process
continues till all the possibilities of net savings are exhausted by forming rectangles.

Limitation : With large Matrices, no. of empty cells rise making this exercise time
consuming and to overcome this another method MODI has been developed. Here to the
initial solution we add a new row and new column. Let C be the Cell of the matrix with
subscript as i th row and j th column then new column shall be u i while new row shall
be v j Consider the above problem (VAM stage) we have this as :-
From Factory D E F Supply vj
→
To W/H ↓
A 20 6 30 4 1 50
 B 3 40 8 7 40
C 4 25 4 35 2 60
Demand 20 95 35 150
ui
The above matrix has two type of cells :With assignment of Units and Without assignment of
units
For cells with assignment of units we apply the formula u i + v j = Cij ; where Cij is the cost
of the associated cell e.g. Cost of AD cell ( i=1, j=1; i th row and j th column) is given as 6 i.e.
C11 = 6 To begin with let u 1 =0, Now since C11 = 6 = u i + v j and u 1 =0, we get v 1 = 6

From Factory D E F Supply vj

→
To W/H ↓
A 20 6 30 4 1 50 6
B 3 40 8 7 40
C 4 25 4 35 2 60
Demand 20 95 35 150
ui 0

Now we complete rest of the entries

C12 = 4 = u 1 + v 2 and u 1 =0, we get v 2 = 4
C22 = 8 = u 2 + v 2 and v 2 = 4, we get u 2 = 4
C32 = 4 = u 3 + v 2 and v 2 = 4, we get u 3 = 0
C33 = 2 = u 3 + v 3 and u 3 = 0, we get v 3 = 2

From Factory D E F Supply vj

→
To W/H ↓
A 20 6 30 4 1 50 6
B 3 40 8 7 40 4
C 4 25 4 35 2 60 2
Demand 20 95 35 150
ui 0 4 0

Note : Total of u i need not be equal to v j .

Now we are left with unassigned cells for which we use another formula u i + v j - Cij
AF (C13) = 1, according to formula AF would be u i + v j - Cij = u 1 + v 3 - C13 =0+2-1=1
BD (C21) = 3, according to formula BD would be u i + v j - Cij = u 2 + v 1 - C21 =4+6-3=7
BF (C23) = 7, according to formula BF would be u i + v j - Cij = u 2 + v 3 - C23 =4+2-7= -1
CD (C31) = 4, according to formula CD would be u i + v j - Cij = u 3 + v 1 - C31 =0+6-4=2
Check for Optimality : If any costs are (+) for unassigned cells, there is a scope for
improvement and solution is not optimal. Max Improvement possible is for cell with max
cost i.e. BY INCLUDING BD IN THE NEXT MATRIX. Rest of the process is same as for
Stepping Stone Method
BD can be included only by forming a rectangle /loop . Two ways are possible First Method

BE to BD then AD to AE results in saving of 5 and loss of 2, net saving of 3

From Factory D E F Supply vj

→
To W/H ↓
A 20 6 30 4 1 50 6
B 3 40 8 7 40 4
C 4 25 4 35 2 60 2
Demand 20 95 35 150
ui 0 4 0

Second Method BE to BD then BD to CD (but CD has no units) so not feasible so only possibility is as
above. In case the two possibilities are feasible, select the one which results in more savings in cost

From Factory D E F Supply vj

→
To W/H ↓
A 6 50 4 1 50 6
B 20 3 20 8 7 40 4
C 4 25 4 35 2 60 2
Demand 20 95 35 150
ui 0 4 0

(Again apply the two formulas; for with and without assignment u i + v j = Cij and u i + v j -
Cij , We are more interested in second formula as we want to know if the unassigned cells
have still costs as (+), if yes go for further improvement )
Check for Optimality :
If any costs are (+) for unassigned cells, there is a scope for improvement and solution is not
optimal. So calculate again the u i + v j - Cij for the unassigned cells
AD (C11) = 6, according to formula AD would be u i + v j - Cij = u 1 + v 1 - C11 =0+6-6=0
AF (C13) = 1, according to formula AF would be u i + v j - Cij = u 1 + v 3 - C13 =0+2-1=1
BF (C23) = 7, according to formula BF would be u i + v j - Cij = u 2 + v 3 - C23 =4+2-7= -1
CD (C31) = 4, according to formula CD would be u i + v j - Cij = u 3 + v 1 - C31 =0+6-4=2
There are still two positive costs, see calculations above CD=2, AF=1 Note : No
improvement possible in BF as it is already (-). Thus we include CD as it has
cost > AF , in next matrix.
And this process continues till all the costs are 0 or (-)