Transportation
Problem
Learning Objectives
After reading this chapter the student must
be able to
a.. Formulate a transportation problem
b. Generate the initial basic solution for
the problem and resolve degeneracy
c. Optimize the initial basic solution using
MODI method
Transportation models
The basic transportation
problem was developed in 1941 by F.I. Hitchaxic. However it could be solved
for optimally as an answer to complex business problem only in 1951, when
Geroge B. Dantzig applied the concept of Linear Programming in solving the
Transportation models.Transportation models or problems are primarily
concerned with the optimal (best possible) way in which a product produced at
different factories or plants (called supply origins) can be transported to a
number of warehouses (called demand destinations).
The objective in a transportation problem is:-
To fully satisfy the
destination requirements within the operating production capacity constraints
at the minimum possible cost.Whenever there is a physical movement of goods
from the point of manufacture to the final consumers through a variety of
channels of distribution (wholesalers, retailers, distributors etc.), there is
a need to minimize the cost of transportation so as to increase the profit on
sales. Transportation problems arise in all such cases. It aims at providing
assistance to the top management in ascertaining how many units of a particular
product should be transported from each supply origin to each demand
destinations to that the total prevailing demand for the company’s product is satisfied, while at the same time the total
transportation costs are minimized.
Initial Feasible Solutions.
In a transportation problem,
the initial feasible solution can be generated by a number of methods. Three of
the most commonly methods are discussed as under:
1. The North-West Corner Rule (NWC Rule)
As the name itself suggests, under this rule, first
of all the upper-left or the north-west corner of each cell is selected. It is
one of the simplest methods which provides an initial feasible solution to a
transportation problem. The steps involved are as under:
Step I
Upper-left corner cell of the transportation table is
selected. Allocate as many units to this cell as possible. This will be the
least value of demand and supply. This process is repeated for all the
respective rows and columns.
Step II
After exhausting the supply for the first row, move
down vertically to the Ist cell in the 2nd row and Ist column. Then repeated
the above Step I.
Step III
After exhausting the demand for the first column,
move along i.e.; horizontally to the next cell in the IInd column & Ist
row.Then repeated the above Step I.
Step IV
Where demand = supply for a cell, then further
allocation is made in either the next row or the next column cell.
Thisprocedure is continued till the total quantity that is available is fully
allocated to the various cells, as required.
2. Least Cost Method (LCM)
This is a time-saving method since it drastically
reduces the numerous calculation required to be done under the northwest corner
rule.
The following steps are involved in this method:
Step I
Among all the rows and columns
in the transportation table, select that cell which has the lowest (minimum)
transportation cost.
Step II
Where the smallest cost is not
unique i.e.; there are other cells having the same smallest cost, select any
cell which has this smallest cost.
Step III
To the cell chosen in the above
step, allocated the maximum possible units. Eliminate that row or the column
where either the demand is satisfied or the supply is exhausted.
Step IV
For the reduced table so obtained, repeat the above
steps till total demand and supply are exhausted.
3. Vogel’s Approximation
Method (VAM)
The Steps involved in this method are give below :-
Step I
Calculate the penalty for all rows and columns.
(Penalty is the difference between the smallest and the next smallest cost)
Step II
Select the row or column having maximum penalty. In
this row or column, select the cell having the least cost. Allocate maximum
possible units (quantity) to this lowest cost cell.
Remarks
In case of a tie, select the row/column having
minimum cost. It, still, a tie persists, select the row/column having the
maximum possible assignments or you may simply select any row or column in case
of a tie without considering minimum costs etc.
Step III
Reduce the demand or supply by the amount assigned to
the cell.
Step IV
If row supply is zero-eliminate it If column demand
is zero-eliminate it If both are zero-eliminate both.
Step V
Again calculate penalty and repeat the same steps.
Remarks
At the end, check that the total number of filled
cells = M + N– 1. only then the initial solution would be feasible. If filled
cells are <M + N – 1, an empty cell is to be filled in a particular manner.
Modified Distribution
(MODI) Method
The following are the steps
involved in the Modified Distribution (MODI) method of testing the optimality
of a feasible solution in a transportation problem:-
Step I
By using any one of the three methods discussed
above,obtain an initial feasible solution, having M + N – 1
allocation in independent position.
Step II
Assign an arbitrary value (zero) to one of the
variables without violating the equations. (Since there are M + N – 1 occupied cells,
there will be M + N – 1 equations).
Step III
For every empty cell, calculate the improvement index
i.e.; its opportunity cost. This has to be calculated by adding the
corresponding row and column number and then substracting the actual cost of
this cell from it.
The solution is optimal, if the opportunity cost of
all the empty cells>0.
Step IV
Where the solution is not optimal i.e.; we have empty
cells with negative improvement index (opportunity cost), select the empty cell
having the largest value of negative opportunity cost.
Step V
For the empty cell selected in Step IV, draw a closed
path – and assign alternate positive (+) and negative (-) signs at the empty
cell – lying on the corner points of the path. The cell being evaluated i.e.;
as selected in Step IV will have a positive (+) sign.
Step VI
Repeat this procedure till an optimal solution is
achieved.
Example-1
Find initial basic feasible solution for the
following transportation problem
Solution: since here Demand =Supply =21, the given
problem is balanced. following north
west corner rule ,the first allocation is made in the
cell(1,1)
Here
corresponding demand is only 3 but available capacity is 4 ,there fore we can
allocate all required 3 to cell(1,1) .Now plant P remaining capacity is
1.destination A is completely satisfied. so we can leave corresponding column.
Destination
Again here
north west corner is cell (1,2 )
corresponding demand is 3 but Plant P
capacity is 1, there fore only 1 is allocated to cell (1,2).now plant P
capacity is exhausted there fore we can leave that particular row.
In the same way now north west
corner is cell (2,2) corresponding
demand is 2 but Plant Q capacity is 8, there fore all required 2 is
allocated to cell (2,2).Now at B all the requirement is satisfied so column B
can be deleted. There fore remaining at Q is 6.
At present north west corner is
cell (2,3) corresponding demand is 4 but
Plant Q capacity is 6, there fore all required 4 is allocated to cell (2,3).Now
at C all the requirement is satisfied so column C can be deleted. There fore
remaining at Q are 2.
Destination
Now the north west corner is cell (2,4)
corresponding demand is 5 but Plant Q
capacity is 2, there fore only two will be allocated to the cell (2,4).Now at D the demand is 3,there
fore 2nd row can be deleted. There fore remaining at D are 3.
the cell (3,4) is in north west corner
position, here the corresponding demand is 3 but the plant capacity is 9,there
fore all three can be allocated to the cell(2,4).
Now the corresponding demand is 6 and requirement
also 6.there fore the entire requirement will be satisfied.
Example-2
Find initial basic feasible solution for the
following transportation problem by least cost method
Solution:
since here Demand =Supply =100, the given problem is balanced transpor tation
problem.In the above table minimum cost cells are (1,1),(1,3) and (2,4).here
more than one minimum cost cells are available, therefore we can take
arbitrarily any one of the minimum cost cell for allocation. Here we can choose cell (1,1). Corresponding
demand is 20 but available is 30. therefore complete 20 can be allocated to the
cell (1,1). Now demand is satisfied therefore we can delete column.
To
In the above table there are
two minimum cost cells available namely (1, 3) and (2, 4). Let we choose
arbitrarily (1, 3). Corresponding demand is 30 but available is 10. Therefore
available 10 can be allocated to the cell (1, 3) complete 20 can be allocated
to the cell (1, 3). Now demand is not satisfied therefore we can delete
exhausted row.
From the above table minimum cost cell is (2,
4).corresponding demand is 10 but availability is 50, therefore all 10 can be
allocated to the cell (2, 4)
In the above table there are two minimum cost cells
available namely (2, 3) and (3, 2). Let we choose arbitrarily (2, 3).
Corresponding demand is 30 but available is 40. Therefore all the 30 can be
allocated to the cell (2, 3). Now demand is satisfied therefore we can delete
exhausted column.
Now the cell (3, 2) is having minimum cost, here
demand is 30 but available is 20.let we allocate all 20 to that cell. There fore the exhausted row
can be deleted.
Here demand and supply is equal there fore all 10 can
be allocated.
Example :3
Find initial basic feasible
solution for the following transportation problem by vogles method (VAM)
Destination
Solution: here
Demand=supply=950, there fore balanced transportation problem
From
the above table, let we calculate penalty value by subtracting minimum value
with just greater than of the same minimum value for each row and column. Among
the penalty value biggest can be opted, here 5 is the maximum penalty value.
But here there are two 5 is available. Let we choose any one arbitrarily; say
first column can be chosen. in the first column minimum cost cell is (1,1)Here
the corresponding demand is 200 but available is 250.there fore all 200 can be
allocated to the minimum cost cell (1,1).exhausted column must be deleted. And
again penalty will be calculated as follows
Here
maximum penalty value is 5and corresponding minimum cost cell is (2,1).demand
is 225 and available is 50,all 50 can be allocated. and exhausted row will be
deleted
Here maximum penalty value is 6and corresponding
minimum cost cell is (2,2).demand is 175 and available is 300,all175 can be
allocated. and exhausted column will be deleted
If we repeat
same process the following tables will be obtained
Followed to the
above table we can get the following table
Final allocation
will be made to the cell(3,3),
therefore 
Finding
optimal solution:
Modified Distribution
(MODI) Method
The following are the steps involved in the
Modified Distribution (MODI) method of testing the optimality of a feasible
solution in a transportation problem:-
Step I
By using any one of the three methods discussed
above, obtain an initial feasible solution, having M + N – 1
allocation in independent position.
Step II
Assign an arbitrary value to one of the variables without violating the
equations. (Since there are M + N – 1
occupied cells, there will be M + N – 1 equations).
Step III
For every empty cell, calculate the improvement
index i.e.; its opportunity cost. This has to be calculated by adding the
corresponding row and column number and then subtracting
the actual cost of this cell from it. The solution is optimal, if the
opportunity cost of all the empty cells>0.
Step IV
Where the solution is not optimal i.e.; we have
empty cells with negative improvement index (opportunity cost), select the
empty cell having the largest value of negative opportunity cost.
Step V
For the empty cell selected in Step IV, draw a
closed path – and assign alternate positive (+) and negative (-) signs at the
empty cell – lying on the corner points of the path. The cell being evaluated
i.e.; as selected in Step IV will have a positive (+) sign.
Step VI
Repeat this procedure till an optimal solution is
achieved.
Remarks
Both the stepping stone method and MODI differ
in approach but provide the same optimal solution. i.e.; both give the solution
(to the transportation problem) having the lowest shipping costs
Example4: Find
initial basic feasible solution for the following transportation problem by
vogles method (VAM)
Solution: here
Demand=supply=10, there fore balanced transportation problem
By using VAM if
we find IBFS we can get the following table
|
7
|
3
|
2
(2)
|
|
2
|
1
(1)
|
3
(2)
|
|
3
(4)
|
4
|
6
(1)
|
There fore
initial basic feasible solution is=
For optimality
First let we
check M+N-1= number of basic cells=5
(Here M= number of row and N = number of
column)
There fore the problem is non-degeneracy
Example5:
Find initial basic feasible solution for the
following transportation problem by vogles method (VAM) and find optimal
solution
Solution:
Here Demand=supply=340, there fore balanced transportation problem
By using VAM if
we find IBFS we can get the following table
|
4
|
1
(50)
|
2
(50)
|
6
|
9
|
|
6
(10)
|
4
|
3
(20)
|
5
|
7
(90)
|
|
5
(30)
|
2
|
6
|
4
(90)
|
8
|
There fore
initial basic feasible solution is=
For
optimality
First let we check
M+N-1= number of basic cells=7
(Here M= number of row and N = number of
column)
There fore the problem is non-degeneracy
There fore
this current table is not optimum, here cell (1, 1) is giving –ve 
.let we choose that corresponding cell for table
reconstruction. Let we draw loop from cell (1, 1) through basic cell corners
and in all corner of the loop alternative sign must be marked. among negative
corner we must take minimum allocation to add and subtract in all +ve corners
and –ve corners of the loop.
.let we choose that corresponding cell for table
reconstruction. Let we draw loop from cell (1, 1) through basic cell corners
and in all corner of the loop alternative sign must be marked. among negative
corner we must take minimum allocation to add and subtract in all +ve corners
and –ve corners of the loop. |
4
 (+) |
1
(50)
|
2
(50) (-)
|
6
|
9
|
|
6
(10)
(-)
|
4
|
3
(20) (+)
|
5
|
7
(90)
|
|
5
(30)
|
2
|
6
|
4
(90)
|
8
|
Here
among negative corners 10 is the minimum value,this 10 to be added with all +ve
corners and subtracted with all the negative corners. there fore the new table
is
|
4
(10)
|
1
(50)
|
2
(40)
|
6
|
9
|
|
6
|
4
|
3
(30)
|
5
|
7
(90)
|
|
5
(30)
|
2
|
6
|
4
(90)
|
8
|
Again
we have to check
Degeneracy in Transportation
In
transportation problem if we get M+N-1 <
number of basic cell, then the transportation problem is in degenerate. It may
occur either at the initial stage or at intermediate stage of the iteration. To
solve this we can introduce extremely small amount 
to one of the empty
cells of the table.
to one of the empty
cells of the table.
Example6:
Find initial basic feasible
solution for the following transportation problem by vogles method (VAM) also
find optimal solution
Destination
Solution:
Here Demand=supply=210, there fore balanced transportation problem
By using VAM if
we find IBFS we can get the following table
|
14
(70)
|
56
|
48
|
27
|
|
82
|
35
|
21
(45)
|
81
(2)
|
|
99
|
31
(35)
|
71
|
63
(58)
|
For
optimality
First let we check
M+N-1= 6
But number of basic
cells=5
Here M+N-1 = number of basic cells,
there fore the problem is in degeneracy
Let we introduce 
to the cell (1,4). So
the new table becomes
to the cell (1,4). So
the new table becomes|
14
(70)
|
56
|
48
|
27
(
 ) |
|
82
|
35
|
21
(45)
|
81
(2)
|
|
99
|
31
(35)
|
71
|
63
(58)
|
Now, M+N-1 = number of basic cells=6, there fore now it is non-degeneracy
There fore
this current table is not optimum, here cell (2, 2) is giving –ve 
.let we choose that corresponding cell for table
reconstruction. Let we draw loop from cell (2, 2) through basic cell corners
and in all corner of the loop alternative sign must be marked. among negative
corner we must take minimum allocation to add and subtract in all +ve corners
and –ve corners of the loop.
.let we choose that corresponding cell for table
reconstruction. Let we draw loop from cell (2, 2) through basic cell corners
and in all corner of the loop alternative sign must be marked. among negative
corner we must take minimum allocation to add and subtract in all +ve corners
and –ve corners of the loop. |
14
(70)
|
56
|
48
|
27
(
) |
|
82
|
 35
+ve
|
21
(45)
|
81(-ve)
(2)
|
|
99
|
31(-ve)
(35)
|
71
|
63(+ve)
(58)
|
Among the negative corner smallest negative corner
value is 2. There fore the new table is
|
14
(70)
|
56
|
48
|
27
(
) |
|
82
|
35
(2)
|
21
(45)
|
81
|
|
99
|
31
(33)
|
71
|
63
(60)
|
Unbalanced Transportation Problem:
A transportation
problem is said to be unbalanced if the supply and demand are not equal.
Two situations are possible:-
i.
If Supply < demand, a dummy supply variable is
introduced in the equation to make it equal to demand.
ii.
Likewise, if demand < supply, a dummy demand variable
is introduced in the
equation to make it equal to
supply.
Example 7: Find initial basic feasible
solution for the following transportation problem by vogles method (VAM) also
find optimal solution
Destination
Solution: Here
Demand not equal to supply there fore it is unbalanced transportation problem.
In this problem
Demand=215 and supply=195, that is supply is getting short of 20, there fore
let we introduce dummy row with zero cost. The new table is
|
6
|
1
|
9
|
3
|
|
11
|
5
|
2
|
8
|
|
10
|
12
|
4
|
7
|
|
0
|
0
|
0
|
0
|
By using VAM if
we find IBFS we can get the following table
|
6
(65)
|
1
(5)
|
9
|
3
|
|
11
|
5
(30)
|
2
(25)
|
8
|
|
10
|
12
|
4
(25)
|
7
(45)
|
|
0
(20)
|
0
|
0
|
0
|
IBFS is =
No comments:
Post a Comment