TRANSPORTATION PROBLEMS
Consider a problem of transporting goods from m sources (factories) F1,F2
---Fm to n destinations (warehouses) W1, W2,
--- Wn The capacities of the sources are S1, S2,
---Sm respectively while the expected demands at the respective
warehouses are d1,d2, --- dn.
Cij indicates the cost of transporting one unit from the
source Fi to destination Wj. Thus C12, is per
unit transportation cost from the first factory F1, to the second
warehouse W2.
It is assumed that the total supply available at the sources will exactly
satisfy the total demand required at all the destinations i.e. S1 +
S2 + ... + Sm= d1 + d2 + ... + d
n.
|
Source |
Destination |
|
|||
|
W1 |
W2 |
------- |
Wn |
Supply capacity |
|
|
F1 |
C11 |
C12 |
------- |
C1n |
S1 |
|
F2 |
C21 |
C22 |
------- |
C2n |
S2 |
|
------- |
------- |
------- |
------- |
------- |
------- |
|
------- |
------- |
------- |
------- |
------- |
------- |
|
Fm |
Cm1 |
Cm2 |
------- |
Cmn |
Sm |
|
Demand |
d1 |
d2 |
------- |
dn |
N=Total supply/Demand |
The problem is to find the number of units to be transported from each of
the sources to each of the destinations. So that the total cost of
transportation is minimised .
Terminology of
Transportation problem
i.
Balanced Transportation Problem: - Here the total capacity of the
supply points or source is equal to the total demand at
the destination.
ii.
Unbalanced Transportation :-Here the total supply is not equal to the total demand
iii.
Transportation Table :-It is used to represent
the data about the supply at sources demand at destination and per unit transportation cost from
each source to each destination.
e.g. The above table
has 3 rows for three sources, 3 columns corresponding to 3 warehouses along
with one row and column indicating the demands and supply. Each square at the
intersection of the rows and columns is called as a 'cell’. The figures in the
right hand top corner for each cell indicate the per unit transportation cost
between the respective source and destination, while the figures in circles
indicate the number of units to be transported. eg. 300 units to be transported
from Mumbai to Delhi where unit cost of transportation is Rs 10. We have to
identify these figures to obtain the optimum solution.
iv. Dummy Source or Destination :- This is
represented by adding an extra row or column the transportation table with 0
per unit cost for each of its cells. It is used to balance an unbalanced
problem by considering appropriate supply or demand for it.
v. Initial Feasible solution :- It is a solution that satisfies the
supply and demand conditions and yet it may or may not be the optimum one.
There are three methods of obtaining this solution. viz. North West Corner
Method (NWCM), Least Cost Method (LCM) and Voge Approximation Method (VAM).
Vi. Optimum solution : It is the feasible
solution which also gives a transportation plan with minimum total cost. This
can be obtained by using the Stepping Stone Method or Modified Distribution
Method (MODI Method), once we get the initial feasible solution.
Finding the Initial Feasible
Solution
There are three methods which are use for finding the initial
feasible solution
A ) North-West Corner Method (NWCM)
B) Least Cost Method (LCM) Or Matrix
Minima Method
C) Vogel’s Approximation Method (VAM)
A.
North-West Corner Method (NWCM)
Step1:- Select
the North - West corner cell in the transportation table and allocate as many
units as possible to it after checking the supply (in row) and the demand (in
column) position for that cell.
Step2: Reduce the supply and demand figures for the corresponding
row and column accordingly.
Step3: Cover the row or column where the supply or demand gets
fully exhausted (i.e. becomes 0) to get a reduced transportation table.
Step 4:
Go to step 1 and repeat the procedure until total supply is fully allocated to
the cells so as to fulfill the total demand.
Example 1 : Consider
the following transportation table with supply, demand and unit cost figures as shown : This is a
balanced table with total demand = total supply = 125.
|
|
D1 |
D2 |
D3 |
Supply |
|
S1 |
30 2 |
4 |
1 |
0 30 |
|
S2 |
3 |
5 |
2 |
25 |
|
S3 |
4 |
6 |
7 |
20 |
|
S4 |
3 |
2 |
1 |
50 |
|
Demand |
15 45 |
25 |
55 |
125 |
i. Choose the North - West corner cell i.e. S1 D1. The row supply is 30 and column demand is 45
for S1D1 cell . Hence we can assign at most 30 units to it.
ii. After
assigning these 30 units, the supply of S1 becomes (30-30=0 unit) the demand for D1 reduces to 45-30
=15
iii. Thus, cover row S1 now as its
supply has been fully used to get a reduced table.
|
|
D1 |
D2 |
D3 |
Supply |
|
S1 |
30 2 |
4 |
1 |
30 |
|
S2 |
15 3 |
5 |
2 |
10 25 |
|
S3 |
4 |
6 |
7 |
20 |
|
S4 |
3 |
2 |
1 |
50 |
|
Demand |
15 45 |
25 |
55 |
125 |
2. In this table go
again to the north west corner cell i.e. S2D1 and
allocate 15 units to it as 15 unit of
demand and 25 units of supply available.
This reduces supply 25 - 15 = 10 and demand of D1 to 15 - 15 = 0.
Now reduce table for avoid confusion by reducing D1 column and S1
row.
|
D2 |
D3 |
Supply |
|
|
S2 |
10 5 |
2 |
10 |
|
S3 |
6 |
7 |
20 |
|
S4 |
2 |
1 |
50 |
|
Demand |
15 25 |
55 |
125 |
3. In this table go
again to the north west corner cell i.e. S2D2 and
allocate 10 units to it , as 25 units of
demand and 10 units of supply available.
This reduces supply 10-10 = 0 and demand of D2 to 25 - 10 = 15. Again
reducing S2 row.
|
D2 |
D3 |
Supply |
|
|
S3 |
15 6 |
7 |
5 20 |
|
S4 |
2 |
1 |
50 |
|
Demand |
15 25 |
55 |
125 |
4. In this table go
again to the north west corner cell i.e. S3D2 and
allocate 15 units to it, as 15 units of
demand and 20 units of supply available.
This reduces supply 20-15 = 5 and demand
of D2 to 15 - 15 = 0.
Again reducing D2 coloum.
|
D3 |
Supply |
|
|
S3 |
5 7 |
5 20 |
|
S4 |
50 1 |
50 |
|
Demand |
50 55 |
125 |
4. In this table go
again to the north west corner cell i.e. S3D3 and
allocate 5 units to it, as 50 units of
demand and 5 units of supply available.
This reduces supply 5-5 = 0 and demand of D2 to 55 - 5 = 50. Again reducing S3 row. Now last cell is
remaining S4D3 here demand is 50 and supply is also 50 so
assign 50 to this cell.
Finally
we get
|
|
D1 |
D2 |
D3 |
Supply |
|
S1 |
30 2 |
4 |
1 |
30 |
|
S2 |
15 3 |
10 5 |
2 |
25 |
|
S3 |
4 |
15 6 |
5 7 |
20 |
|
S4 |
3 |
2 |
50 1 |
50 |
|
Demand |
45 |
25 |
55 |
125 |
Total=
30 × 2+ 15 × 3+ 10 ×5 +15 ×6 + 5 ×7+ 50×1 = 330 as total transportation cost.
Since there are m+n-1 =
4+3-1 = 6 number of independent occupied cells , the solution is feasible.
we go on making allocations to the minimum cost cell in the table
Step 1:
(i) Select a cell with minimum unit transportation cost from the table.
(ii)If there are more
than one cells with minimum unit cost i.e. there is a tie, then select that
cell among them where more number of units can be allocated (after considering
their row supply and column demands.) If there is a tie again, then select a
cell randomly from them.
Step 2: Allocate maximum possible number of units
to it. Reduce the corrosponding supply and demand figures accordingly to get a
reduced transportation table as in case of NWCM.
Step 3 : Repeat steps 1
and 2 until entire supply is exhausted to fulfil the entire demand.
Example 2 : For the
same problem as in Example 1
i. Choose the cell with minimum unit cost.
There are two such cells S1D3 and S4D3
both having unit cost 1 i.e. there is a tie.
ii. Hence select that cell where
more units can be allocated. After considering the row supply and column demand
for these cells we see that we can allocate 30 units to S1D3and 50 units to S4D3. Hence select S4D3.
2. Allocate 50 units to it and then reduce its row supply and column
demand by 50. Thus, the supply of S, gets fully exhaused and demand for D, becomes
5. Hence, cover S, to get the reduced table.
|
|
D1 |
D2 |
D3 |
Supply |
|
S1 |
2 |
4 |
1 |
25 30 |
|
S2 |
3 |
5 |
2 |
25 |
|
S3 |
4 |
6 |
7 |
20 |
|
S4 |
3 |
2 |
50 1 |
50 |
|
Demand |
45 |
25 |
5 55 |
125 |
3. Next minimum cost cell is S1D3
having unit cost 1, here supply capacity is 25 but demand is only 5 so assign 5
to cell ,after supply capacity of S1 become 30-5-25
|
|
D1 |
D2 |
D3 |
Supply |
|
S1 |
2 |
4 |
5 1 |
25 30 |
|
S2 |
3 |
5 |
2 |
25 |
|
S3 |
4 |
6 |
7 |
20 |
|
S4 |
3 |
2 |
50 1 |
50 |
|
Demand |
45 |
25 |
5 55 |
125 |
4.Here minimum cost cell is S1D1
having unit cost 2 here supply capacity is 25 but demand is 45 so assign 25 to
cell ,after supply capacity of S1 become 25-25=0, and demand 45-25 =20
|
|
D1 |
D2 |
Supply |
|
S1 |
25 2 |
4 |
25 30 |
|
S2 |
20 3 |
5 5 |
5 25 |
|
S3 |
4 |
20 6 |
20 |
|
Demand |
20 45 |
25 |
125 |
5.After this minimum cost cell is S2D1
having unit cost 3, here supply capacity is 25 but demand is 20 so assign 20 to
cell ,after supply capacity of S2 become 25-20=5, and demand 20-20=0
Now only S2D2 and S3D2 cells are remaining and out of this S2D2 having minimum value so assign 5 to this cell and remaining 20 to S3D2
|
|
D1 |
D2 |
D3 |
Supply |
|
S1 |
25 2 |
4 |
5 1 |
30 |
|
S2 |
20 3 |
5 5 |
2 |
25 |
|
S3 |
4 |
20 6 |
7 |
20 |
|
S4 |
3 |
2 |
50 1 |
50 |
|
Demand |
45 |
25 |
55 |
125 |
Total cost
is = 25× 2+ 20 × 3+ 5×5+ 20× 6+5 ×1 +50 ×1 = 310
m+n -1 = 4+3-1=6
Here we go on making
allocations to the minimum cost cell of a row or column for the penalty for not
making an allocation is high.
Step 1: Compute the penalty (ie. the
difference between the two smallest unit cost figure cells) for each row and
column.
Step 2: Identify the
row or column with highest penalty and choose the cell with smallest unit cost
in it.
(If there is a tie for
highest penalties, select the row or column containing the
minimum cost
cell among them If there is a tie again, then select that cell where
maximum allocation is possible cell or we can select it randomly) .
Step 3: Allocate
maximum possible units to the selected cell and reduce its row supply and
column demand accordingly. Obtain the reduced table then as done previously.
Step 4:- Recompute the penalties for
reduced table. Repeat the above procedure until the entire demand and supply
gets exhausted.
Example
1)
Find penalty by the difference between
the two smallest unit cost figure cells for each row and column
|
|
D1 |
D2 |
D3 |
Supply |
Penalty |
|
S1 |
2 |
4 |
1 |
30 |
2-1=1 |
|
S2 |
3 |
5 |
2 |
25 |
3-2=1 |
|
S3 |
4 |
6 |
7 |
20 |
6-4=2 |
|
S4 |
3 |
25 2 |
1 |
25 50 |
2-1=1 |
|
Demand |
45 |
0 25 |
55 |
125 |
|
|
Penalty |
3-2=1 |
4-2=2 |
2-1=1 |
|
2) Identify the row or column with highest
penalty and choose the cell with smallest unit cost in it, in this row S3
and D2 column having highest penalty so there is tie then select the
row or column containing the minimum cost cell among them so , in D2
column having minimum cost cell 2 in is S4D2 cell , Here
supply is 50 and demand is 25 so assign 25 to this cell so demand of D2 is
25-25=0 and S2 supply is 50-25=25.
|
D1 |
D2 |
D3 |
Supply |
Penalty |
|
|
S1 |
2 |
4 |
1 |
30 |
2-1=1 |
|
S2 |
3 |
5 |
2 |
25 |
3-2=1 |
|
S3 |
20 4 |
6 |
7 |
20 |
7-4=3 |
|
S4 |
3 |
25 2 |
1 |
25 50 |
3-1=2 |
|
Demand |
25 45 |
25 |
55 |
125 |
|
|
Penalty |
3-2=1 |
4-2=2 |
2-1=1 |
|
3) Again find out penalty by above method, Here highest penalty is 3 in
row S3 and lowest cost is 4 in cell S3D1 .For
this cell supply capacity is 20 and demand is 45 so assign 20 to this cell so
supply become 0 and demand become 45-20=25
|
|
D1 |
D2 |
D3 |
Supply |
Penalty |
|
S1 |
2 |
4 |
1 |
30 |
2-1=1 |
|
S2 |
3 |
5 |
2 |
25 |
3-2=1 |
|
S3 |
20 4 |
6 |
7 |
20 |
7-4=3 |
|
S4 |
3 |
25 2 |
25 1 |
25 50 |
3-1=2 |
|
Demand |
25 45 |
25 |
30 55 |
125 |
|
|
Penalty |
3-2=1 |
4-2=2 |
2-1=1 |
|
4) Find penalty again, we get S4
row having maximum penalty 2 and minimum cost is 1 in cell S4D3.
For this cell supply capacity is 25 and demand is25, so assign 25 to this cell
so supply become 0 and demand become 55-25=30
5)
|
|
D1 |
D2 |
D3 |
Supply |
Penalty |
|
S1 |
2 |
4 |
30 1 |
30 |
2-1=1 |
|
S2 |
25 3 |
5 |
2 |
25 |
3-2=1 |
|
S3 |
20 4 |
6 |
7 |
20 |
7-4=3 |
|
S4 |
3 |
25 2 |
25 1 |
25 50 |
3-1=2 |
|
Demand |
25 45 |
25 |
30 55 |
125 |
|
|
Penalty |
3-2=1 |
4-2=2 |
2-1=1 |
|
5) Find penalty, there is tie then select the row or column containing the minimum cost cell among them so , in row S1and D3 column having minimum cost cell 1 in S1D3 cell , Here
supply is 30 and demand is 30 so assign 30 to this cell so demand of D3 is
30-30=0 and S1 supply is 30-30=0.
Final
|
|
D1 |
D2 |
D3 |
Supply |
|
S1 |
2 |
4 |
30 1 |
30 |
|
S2 |
25 3 |
5 |
2 |
25 |
|
S3 |
20 4 |
6 |
7 |
20 |
|
S4 |
3 |
25 2 |
25 1 |
50 |
|
Demand |
45 |
25 |
55 |
125 |
M+n-1=6 but here we get only cell 5
so this is not feasible solution
Comments
Post a Comment