�ݺ�ߣ

Presentation on Transportation
and Assignment Problem
Research and Optimization Methods
Presenter:
Subash Chandra Pakhrin
072MSI616
MSC in Information and Comm. Engineering
Pulchowk Campus
1

Transportation Problem
Transportation means movement of goods from one place to another
place.
– It can be from one city to the next city.
– It can be from one place to the next place.
– It can be from one country to another country.
So, definitely this movement is going to incur some costs or some
expenses and we always try to minimize this expenses. This is what
we exactly do in the transportation problem.
In transportation of goods its going to incur some costs and we are going
to minimize that costs that is why this is also known as minimization type
of problem.
2

Details of Transportation Problem
This digits are per unit cost.
For example manufacturing company at Dhulikhel can supply shoes to Civil
Mall which costs 2 Rupees.
It also has last row (Demand) and last column (Supply) which are very
special
Civil Mall Kathmandu Mall People’s Plaza
Dhulikhel
Hetauda
Bharatpur
11 10
3
2
4
4
5 6
2
Supply
Demand
10
20
30
15
30
15
3
60
60

Destinations
Sources
Maximum Demand which means Civil Mall has maximum
demand of 15 units and Kathmandu Mall has maximum
demand of 30 units.
This is nothing
but maximum
supply which
means that
Dhulikhel
based
manufacturing
company can
supply
maximum 10
units of shoes.
4

5
When the total supply is equal to total demands than this is balanced type of
matrix / Balanced transportation problem.
While solving transportation problem if we have unbalanced matrix then we
should balance it and then solve it.
This is our transportation problem and we have to find out minimum costs as
possible while transporting shoes from Different city based manufacturing
company to different malls in Kathmandu city.

How to solve Transportation Problem ?
There are two kinds of solution for solving transportation problems.
6
Solutions
Initial Feasible Optimum
(This gives one solution for our
transportation problem but this may
not be our best solution.)
(Optimum solution is always
the best solution of our
transportation problem)
NWCM
LCM
VAM
MODI
Using this we can find out best
solution of transportation problem

How to solve Transportation Problem ?
We cannot directly find out optimum solution first method while solving
the transportation problem is we have to find out its Initial Basic Feasible
Solution and depending upon that solution we are going to decide if its
optimum solution exists or not if exists we are going to find it.
Initial Feasible :
NWCM (Northwest – Corner Method)
LCM (Least – Cost Method)
VAM (Vogel Approximation Method)
Optimum :
MODI (Modified Distribution Method)
7

Northwest – Corner Method
As the direction clearly signifies, we have to consider upper left side cells.
Check whether the matrix is balanced or not.
Allocation: Minimum of corresponding row and column min (20,40) = 20
So Dhulikhel Manufacturing company can supply 20 units but Civil Mall
has demand of 40 units for full supply.
Dhulikhel
Hetauda
Bharatpur
2 4
2
1
3
1
5 2
3
Supply
Demand
20
50
30
7
6
4
9
25
Pokhara
40 30 55
125
125
20
20
30
30
25

Northwest – Corner Method
So whatever row / column has zero we have to cut it out thoroughly. My
row has completely gone .
Continue further min(50,20) = 20.
This is how we find out initial basic feasible solution by NWCM.
Find out Total Cost (TC) :
TC = Allocations * per unit costs.
Wherever you have made allocations we are going to consider those
matrix cells.
TC = 20 * 3 + 20 * 2 + 30 * 4 + 30 * 2 + 25 * 7 = 455
10
Which Says that we are going to send 20 units from Dhulikhel to Civil Mall
and 20 units from hetauda to Civil Mall and 30 units from Hetauda to
Kathmandu Mall and so on.
Wherever allocations are made from those parts you are going to send the
units/ things

LCM (Least Cost Method)
11
You are going to consider the lowest costs.
We always try to minimize the costs so, whatever costs is least one we are
going to make allocations there.
3 3 2 1
2 4 1
3 5 2
4 6 7
Dhulikhel
Hetauda
Bharatpur
Pokhara
Supply
Demand
20
50
30
25
40 30 55 125
125
15 5
50
30
10 15

LCM (Least Cost Method)
How to allocate in Tie condition.
So, whenever I can make maximum allocations for that cell, I will have to
pursue. So, I will make allocations there wherever I can make maximum
allocations. I am going to do this when there is a tie.
Total Cost (T.C.) = 15 * 2 + 5 * 1 + 50 * 1 + 30 * 3 + 10 * 4 + 15 * 6
= 305
12
Min (20, 55) Min (50,55)
Allocation of 20 unit Allocation of 50 units

13
We have to find out two minimum numbers in that row and column and
subtract it that’s our PENALTY.
Now find out the maximum penalty / allocation.
2 is the highest penalty so you are going to allocate on Pokhara and
Kathmandu Mall.
3 3 2 1
2 4 1
3 5 2
4 6 7
Dhulikhel
Hetauda
Bharatpur
Pokhara
Supply
Demand
20
50
30
25
40 30 55 125
125
20
Penalty
Penalty
1
1
1 2 0
1
2

14
Whenever the cost is minimum you have to make allocation there.
If there is a tie on the unit cost then you have to check maximum allocation, and
again if there is a tie then randomly take any one value .
Least cost 4 (Do not Allocate Here) ; Least cost 2 (Allocate Here).
3 3 2 1
2 4 1
3 5 2
4 6 7
Dhulikhel
Hetauda
Bharatpur
Pokhara
Supply
Demand
0
0
0
0
0 0 0 0
0
20
Penalty
Penalty
1
1
1 1 1
1
2
50
15 10 5
25

Total Costs (T.C.) = 20 * 2 + 50 * 1 + 15 * 3 + 10 * 5 + 5 * 2 + 25 * 4
= 295
Therefore:
TCNWCM > TCLCM > TCVAM
All of these methods can be used to find out initial basic feasible
solution (IBFS).
15
Now lets look methods to find out Optimal / Best
Solution i.e. MODI Method.

Modified Distribution Method (MODI)
16
Below is the IBFS found by NWCR. Find optimal transportation cost by MODI
method.
Definition: MODI Method or Modified Distribution Method is an optimization
technique used to find optimal transportation cost.
In MODI Method, we modify our existing Initial Basic Feasible Solution (IBFS)
via optimality test to find the optimal solution.
3 5 1 8
9 4 0
17 6 7
Supply
Demand
12
14
4
9 10 11
9 3
7 7
4
Allocation
Value
Value inside the cell are called the
Transportation Cost Value.

17
Initial Basic Feasible Solution (IBFS):
Total Costs (T.C.) = 9 * 5 + 3 * 1 + 7 * 4 + 7 * 0 + 4 * 7
= 104 ( From NWCM)
Check we can reduce Total Costs (T.C.) by MODI method or not

Step 1 : Checking for Degeneracy
Number of allocations (5) = ( m + n ) -1
where: m = no of rows
n = no of columns
Therefore It’s a non – degenerate problem.
Step 2: Calculating opportunity cost (Optimality Test)
u i + v j Method for occupied cells or Basic cells.
18
u 1 + v 1 = 5 u 1 = 0, v 1 = 5
u 1 + v 2 = 1 v 2 = 1
u 2 + v 2 = 4 u 2 = 3
u 2 + v 3 = 0 v 3 = -3
u 3 + v 3 = 7 u 3 = 10
Suppose

Calculating opportunity cost for un-occupied / non- basic cells
∆ ij = C ij – (u i + v j) where Cij = cell value
u i = Row no
v j = Column no
19
∆ 13 = C13 – (u 1 + v 3) = 8 – (0 – 3) = 11
∆ 21 = C21 – (u 2 + v 1) = 9 – (3 + 5 ) = 1
∆ 31 = C31 – (u 3 + v 1) = 17 – (10 + 5) = 2
∆ 32 = C32 – (u 3 + v 2) = 6 – (10 + 1) = -5

Rule for ∆ (opportunity costs) :
Rule 1: check the ∆ (opportunity costs) ≥ 0
if all the values are > 0 then the current solution is both optimal and
unique.
Rule 2: if all the values are greater than 0 but one value is 0 then the
solution is optimal but not unique.
Rule 3: But if there is at least one negative value then the solution is neither
optimal nor unique.
20
If our allocation is neither optimal nor
unique then to get optimal solution we have
to do looping and re-allocation

Rules for Looping:
Rule 1: The loop must be closed loop. i.e. the starting cell and ending cell
must be same cell.
Rule 2: The starting cell and ending cell must be an unoccupied cell.
Rule 3: The loop may take any path but at each corner point of the loop
their must be an occupied cell.
Rule 4: Next we will find out the smallest value among all the allocated
values within loop path.
+ -- + -- + -- ( Alternative Order)
21

22
New Allocated Matrix:
3 5 1 8
9
4 0
17 6
7
9 3
3 11
4
u 1 + v 1 = 5 u 1 = 0, v 1 = 5
u 1 + v 2 = 1 v 2 = 1
u 2 + v 2 = 4 u 2 = 3
u 2 + v 3 = 0 v 3 = -3
u 3 + v 2 = 6 u 3 = 5

∆ 13 = C13 – (u 1 + v 3) = 8 – (0 – 3) = 11
∆ 21 = C21 – (u 2 + v 1) = 9 – (3 + 5 ) = 1
∆ 31 = C31 – (u 3 + v 1) = 17 – (5 + 5) = 7
∆ 33 = C33 – (u 3 + v 3) = 7 – (5 - 3) = 5
Since all ∆ ij values are positive (+ ve ), the solution is both optimal and
unique.
# Unique means there is no alternative solution to this problem. This
solution is optimal and final.
Therefore: Calculating the optimal Transportation cost (T.C.)
TC = 9 * 5 + 3 * 1 + 3 * 4 + 11 * 0 + 6 * 4
= 84
Therefore: We have reduced our cost of transportation by 20 units by
using MODI method.
23

Assignment Problem
Assignment : Allotment of something to someone.
These two things something and someone are very important here
1. Something - Job, Task
2. Someone - Machine, Person
A job can be performed by machine or person and in assignment
problem you are given with number of jobs and no of machines and you
have to assign those jobs to those machines, so that you can get
optimum solution or effective solution.
Assignment problem is same like transportation problem.
24

Assignment Problem
These machines are going to perform these jobs.
Random numbers are nothing but effectiveness factors. It can be anything
can be profit figures, cost, sales or times.
If this figures we assume as profit / sales this type of assignment problem
will be maximization problem, because we always try to maximize it.
But if these figures are given as costs or as time so we always try to
minimize the cost and time so in this case these type of matrix will be your
minimization type of assignment problem.
So, these can be anything maximization or minimization problem.
Lathe A Lathe B Lathe C
Filing
Polishing
Thread
Cutting
11 10
3
2
4
4
5 6
2
25

Assignment Problem
In assignment problem your matrix must be n X n which means that n
no. of rows and n no. of columns.
These are time figures, which means that Job no 1. can be performed by
machine A at 14 minutes.
This is minimization problem because this matrix contains time figures.
How to solve this matrix ???
We solve it by using Hungarian Method. This method is used to
solve minimization type of matrix.
26

Assignment Problem
1. First case check whether your matrix is n X n matrix or not if not you have
to add w row or w column which ever with all 0’s as figure.
27
2. Row Subtraction
You have to consider each row separately. In each row you have considered you
have to find out minimum digit / number (smallest one) and you have to subtract
that number from all other number in the corresponding row. You are going to
perform all the same operation on other rows too.

Assignment Problem
3. Column Subtraction
28
After row subtraction and column subtraction whatever matrix we get that matrix
is known as reduced matrix.
4. You have to draw minimum no. of lines which have to cover all zeros. And
those lines should be vertical or horizontal.

Assignment Problem
If you go column wise, we will still have the same result so it doesn’t
matter.
Your combination might differ that doesn’t matter what matters is the
number of lines. You provide any type of combination you require four
number of lines to cover all these zeros.
So if your total number of lines which is 4 in this case. If this equals to the
number of rows and number of columns .
4 = 4
Then their lies your optimum solution for the assignment problem
if the no. of lines is not equal to the no. of rows then we have to do other
methods.
29
optimum solution

Assignment Problem
This is my solution for assignment problem but how to find which job is
assigned to which machine. How to know that ???
30
So, first find out which ever row / columns contain only one zero there for
same we are going to make allocation.
As job no 4 is assigned to Machine C no any other job can be assigned to
Machine C.
We are going to cut all the 0’s on that particular column and row , if any.

Assignment Problem
Job no 2 is assigned to Machine B
31
Job no 1 is assigned to Machine A
Job no 3 is assigned to Machine D

Assignment Problem
The above matrix shows that
For job 1 Machine A is allocated.
For job 2 Machine B is allocated.
For job 3 Machine D is allocated.
For job 4 Machine C is allocated.
32
49 minutes are required to perform all this jobs on these machines which
is the optimum solution you cannot get lesser than this time this is the
least time which we can obtain by Hungarian Method.

Question Section:
1. Calculate the Transportation Cost of the following Matrix
using NWCM, LCM, VAM of the following Matrix.
33
2. Calculate the Optimal Cost of the following Assignment
problem using Hungarian Method
3. Describe in Brief about MODI method.

References:
1. https://www.youtube.com/watch?v=1Ukw6yxpmcg
By: Tejashree
2. https://www.youtube.com/watch?v=fTTrjKL-rJ0
By: Sujoy Krishna Das
3. https://www.youtube.com/watch?v=q7VMzOTZvqM
By: Tejashree
4 Operation Research: An Introduction, Eight Edition
By: Hamdy A. Taha
34

�ݺ�ߣ

Presentation%20on%20Transportation%20and%20Assignment%20Problem.pptx

More Related Content

Presentation%20on%20Transportation%20and%20Assignment%20Problem.pptx