Module-2 - Transportation and Assignment Problem

Module 2
Transportation and Assignment Problems
DEPARTMENT OF MATHEMATICS
Outline
• Transportation Problems (North West Corner Rule,
Least Cost method and Vogel’s Approximation method),
optimal solution (MODI’s method).
• Assignment Problems (Hungarian method).
Transportation Modeling
➢ An interactive procedure that finds the least costly

means of moving products from a series of
sources to a series of destinations
➢ Can be used to help resolve distribution and
location decisions
Transportation example
• The following example was used to demonstrate the formulation of the transportation model.
• Bath tubes are produced in plants in three different cities—Des Moines , Evansville , and Fort
Lauder , tube is shipped to the distributers in railroad. Each plant is able to supply the
following number of units , Des Moines 100 units, Evansville 300 units and Fort Lauder
300 units
• tubes will shipped to the distributers in three cities Albuquerque , Boston, and Cleveland ,the
distribution requires the following unites ; Albuquerque 300 units , Boston 200 units and
Cleveland 200 units
Shipping cost per unit
To
From Albuquerque Boston Cleveland
Des Moines $5 $4 $3
Evansville $8 $4 $3
Fort Lauder $9 $7 $5
Transportation Problem
Boston
Cleveland (200 units
(200 units required)
Des Moines required)
(100 units
capacity)
Albuquerque
(300 units
required) Evansville
(300 units
capacity)
Fort Lauder
(300 units
capacity)
Transportation Matrix
To Factory Des Moines

Albuquerque Boston Cleveland capacity capacity
From constraint
$5 $4 $3
Des Moines 100
Cell
representing
$8 $4 $3 a possible
Evansville 300 source-to-
destination
$9 $7 $5 shipping
Fort Lauder 300 assignment
(Evansville
to Cleveland)
Warehouse
requirement 300 200 200 700
Cost of shipping 1 unit from Fort Cleveland Total demand

Lauder factory to Boston warehouse warehouse demand and total supply
Mathematical Model of Transportation Problem
Finding an Initial Feasible Solution
There are a number of methods for generating an initial feasible

solution for a transportation problem.
Consider three of the following
(i) North West Corner Method
(ii) Least Cost Method
(iii) Vogel’s Approximation Method
North West Corner Method (NWCM)
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 summarised 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
(a) If the supply for the first row is exhausted, then move down to
the first cell in t he second row and first column and go to step
2.
(b) 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 id fully
allocated to the cells as required.
Ex- 1: Obtain the initial basic feasible solution of the following transportation problem by using
North-West corner method.
To illustrate the NWCM,
As stated in this method, we start with the cell (P1 W1) and Allocate the min (S1, D1) = min (20,21)=20.
Therefore we allocate 20 Units this cell which completely exhausts the supply of Plant P1 and leaves a balance of
(21-20) =1 unit of demand at warehouse W1
Now, we move vertically downward to cell (P2 W1) At this stage the largest allocation possible is the (S2, D1 –20)
=min (28, 1)= 1. This allocation of 1 unit to the cell (P1 W2). Since the demand of warehouse W2 is 25 units while
supply available at plant P2 is 27 units, therefore, the min (27-5) = 25 units are located to the cell (P1 W2). The
demand of warehouse W2 is now satisfied and a balance of (27-225) = 2 units of supply remain at plant P2. Moving
again horizontally, we allocated two units to the cell (P2 W3) Which Completely exhaust the supply at plant P2 and
leaves a balance of 17 units to this cell (P3, W3).. At this, 17 Units ae availbale at plant P3 and 17 units are required
at warehouse W3. So we allocate 17 units to this cell (P3, W3). Hence we have made all the allocation. It may be
noted here that there are 5 (+3+1) allocation which are necessary to proceed further. The initial feasible solution is
shown below. The Total transportation cost for this initial solution is
Total Cost = 20x7 +1 X 5 + 25 x 7 + 2 X 3 + 17 + 8 = Rs. 462
Ex-2: Obtain the initial basic feasible solution of a transportation problem whose cost
and rim requirement table is given below.
Total cost = (5 × 2) + (2 × 3) + (6 × 3) + (3 × 4) + (4 × 7) + (14 × 2)
= 10 + 6 + 18 + 12 + 28 + 28 = Rs. 102
Ex-3: Determine an initial basic feasible solution to the following transportation
problem using NWCR.
Total cost = (6 × 6 ) + (8 × 4) + (2 × 9) + (14 × 2) + (1 × 6) + (4 × 2)
= Rs. 128
Ex-4: Four factories, A, B, C and D produce sugar and the capacity of each factory is given
below: Factory A produces 10 tons of sugar and B produces 8 tons of sugar, C produces 5 tons of
sugar and that of D is 6 tons of sugar. The sugar has demand in three markets X, Y and Z. The demand
of market X is 7 tons, that of market Y is 12 tons and the demand of market Z is 5 tons. The following
matrix gives the transportation cost of 1 ton of sugar from each factory to the destinations. Find the
Optimal Solution for least cost transportation cost.
Total cost = (7 × 4 ) + (3 × 3) + (8 × 6) + (1 × 4) + (4 × 3) + (1 × 4) + (5 × 0)
= Rs. 105
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.
Ex- 1: Obtain the initial basic feasible solution of the following transportation
problem by using Least cost method.
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.
Ex-2: Obtain an initial feasible solution to the following TP using the matrix minima
method.
Total cost = (6 × 2) + (2 × 2) + (6 × 0) + (4 × 0) + (6 × 2)
= Rs. 28
Ex-3: Determine an initial basic feasible solution for the
following TP, using least cost method.
Total cost = (14 × 1) + (6 × 8) + (9 × 9) + (1 × 2) + (1 × 3) + (4 × 2)
= Rs. 156
Vogel’s Approximation Method (VAM)
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.
The steps involved in this method for finding the initial solution are as follows.
Step 1 Find the penalty cost, namely the difference between the smallest and next to smallest costs in
each row and column.
Step 2 Among the penalties as found in step (1), choose the maximum penalty. If this maximum penalty
is more than one (i.e., if there is a tie), choose any one arbitrarily.
Step 3 In the selected row or column as by step (2), find out the cell having the least cost. Allocate to
this cell as much as possible, depending on the capacity and requirements.
Step 4 Delete the row or column that is fully exhausted. Again compute the column and row penalties
for the reduced transportation table and then go to step (2). Repeat the procedure until all the
rim requirements are satisfied.
Note: If the column is exhausted, then there is a change in row penalty, and vice versa.
Ex- 1: Obtain the initial basic feasible solution of the following transportation
problem by using Vogel’s approximation method.
Ex-2: Determine an initial basic feasible solution for the following TP, using VAM.
Total cost = 200 × 11 + 50 × 13 + 175 × 18 + 125 × 10 + 275 × 13 + 125 × 10
= Rs. 12,075
Ex-3: Find the initial solution to the following TP using VAM.
Total cost = 45 × 3 + 30 × 4 + 25 × 1 + 80 × 2 + 45 × 4 + 75 × 1
= Rs. 695
Ex-4: A dairy firm has three plants located in a state. The daily milk production at each plant is as follows:
Plant 1 : 6 million litres, Plant 2 : 1 million litres, and Plant 3 : 10 million litres
Each day, the firm must fulfil the needs of its four distribution centres. The minimum requirement of each centre is as follows:
Distribution centre 1 : 7 million litres, Distribution centre 2 : 5 million litres,
Distribution centre 3 : 3 million litres, and Distribution centre 4 : 2 million litres
Cost (in hundreds of rupees) of shipping one million litre from each plant to each distribution centre is given in the following
table:
Find the initial basic feasible solution for given problem by using following methods:
(a) North-west corner rule
(Ans:Total cost = Rs (2 × 6 + l × l + 8 × 5 + 15 × 3 + 9 × 2) × 100 = Rs 11,600)
(b) Least cost method
(Ans: Total cost = Rs (2 × 6 + 5 × l + 8 × 4 + 15 × 3 + 9 × 2) × 100 = Rs 11,200)
(c) Vogel’s approximation method
(Ans: Total cost = Rs (2 × 1 + 3 × 5 + 1 × 1 + 5 × 6 + 15 × 3 + 9 × 1) × 100 = Rs 10,200)
MODI METHOD(OPTIMALITY TEST)
Once the initial basic feasible solution has been computed, the next step in the problem is to
determine whether the solution obtained is optimum or not.
Optimality test can be conducted on any initial basic feasible solution of a TP provided such an
allocation has exactly m + n – 1, non-negative allocations where m is the number of origins and n
is the number ofdestinations. Also these allocations must be in independent positions
Step 1
Find the initial basic feasible solution of a TP by using any one of the three methods.
Step 2
Find out a set of numbers 𝑢𝑖 and 𝑣𝑗 for each row and column satisfying
𝑢𝑖 + 𝑣𝑗 = 𝑐𝑖𝑗 for each occupied cell. To start with, we assign a number ‘0’ to any row or column
having maximum number of allocations. If this maximum number of allocations is more than
one, choose any one arbitrarily.
Step 3
For each empty (unoccupied) cell, we find the sum ui and vj written in the bottom left corner of
that cell.
Step 4
Find out the net evaluation value ∆𝑖𝑗 = 𝑐𝑖𝑗 − (𝑢𝑖 + 𝑣𝑗 ) for each empty cell, which is written at
the bottom right corner of that cell. This step gives the optimality conclusion,
(i) If all ∆𝑖𝑗 > 0 (i.e., all the net evaluation value), the solution is optimum and a unique solution
exists.
(ii) If ∆𝑖𝑗 ≥ 0, then the solution is optimum, but an alternate solution exists.
(iii) If at least one ∆𝑖𝑗 < 0, the solution is not optimum. In this case we go to the next step, to
improve the total transportation cost.
Step 5
Select the empty cell having the most negative value of ∆𝑖𝑗 . From this cell we draw a closed
path by drawing horizontal and vertical lines with the corner cells occupied. Assign sign + and–
alternately and find the minimum allocation from the cell having negative sign. This allocation
should be added to the allocation having positive sign and subtracted from the allocation having
negative sign.
Step 6 The above step yields a better solution by making one (or more) occupied cell as empty
and one empty cell as occupied. For this new set of basic feasible allocations repeat from step (2)
onwards, till an optimum basic feasible solution is obtained.
Ex-1: Find the initial solution to the following TP using VAM and also verify the optimality.
Total cost = (11 × 13) + (3 × 14) + (4 × 23) + (6 × 17) + (10 × 17) + (9 × 18)
= Rs. 711
Since all ∆𝑖𝑗 > 0, the solution is optimal and unique. The optimum solution is given by,𝑥14 = 11, 𝑥21 =
6, 𝑥23 = 3, 𝑥24 = 4, 𝑥32 = 10, 𝑥33 = 9
Total cost = (11 × 13) + (3 × 14) + (4 × 23) + (6 × 17) + (10 × 17) + (9 × 18) = Rs. 711
Ex-2: A company has three plants A, B and C, 3 warehouses X, Y and Z. The number of units
available at the plants is 60, 70, 80 and the demand at X, Y, Z is 50, 80, 80 respectively. The
unit cost of the transportation is given in the following table (Least Cost Method):
Since all ∆𝑖𝑗 > 0, the solution is optimal and unique. The optimum solution is given by,𝑥13 = 60, 𝑥21 =
50, 𝑥23 = 20, 𝑥32 = 80, 𝑥33 = 0
Total cost = (60 × 3) + (50 × 3) + (20 × 9) + (80 × 3) + (0 × 5)

= Rs. 750
Ex-3: Find the initial solution to the following TP using VAM and also verify the optimality.
Total cost = 65 × 6 + 5 × 1 + 30 × 5 + 25 × 2 + 25 × 4 + 45 × 7 + 20 × 0
= Rs. 1010
Since all ∆𝑖𝑗 > 0, the solution is optimal and unique. The optimum solution is given by,𝑥11 = 40, 𝑥12 = 30, 𝑥22 =
5, 𝑥23 = 50, 𝑥31 = 25, 𝑥34 = 45, 𝑥41 = 20
Total cost = 6 × 40 + 1 × 30 + 5 × 5 + 2 × 50 + 10 × 25 + 7 × 45 + 0 × 20
= Rs. 960
Ex-4. Solve the transportation problem to maximize profit using MODI method:
P Q R S Capacity
A 22 26 20 21 450
B 21 24 20 19 300
C 18 20 19 20 250
Demand 200 300 150 270
Solution : total demand ≠ Total capacity that is., σ 𝑏𝑗 ≠ σ 𝑎𝑖
It is a maximization problem. Convert it into minimization. Subtract all other element by largest element of the matrix (26).
P Q R S T Capacity
A 4 0 6 5 0 450
B 5 2 6 7 0 300
C 8 6 7 6 0 250
Demand 200 300 150 270 80
P Q R S T Capacit
y
A 4 0 6 5 0 450
B 5 2 6 7 0 300
C 8 6 7 6 0 250
Demand 200 300 150 270 80
1. NWCR
P Q R S T Capacity
A 4 200 0 250 6 5 0 450 250 0

B 5 2 50 6 150 7 100 0 300 250 100 0
C 8 6 7 6 170 0 80 250 80 0
Demand 200 300 150 270 80

0 50 170 1000
0 0 0 0
Total Profit= 200X22+250X26+50X24+150X20+100X19+170X20+80X0=20400

2. LCM
P Q R S T Capacity
A 4 150 0 300 6 5 0 450 150 0
B 5
50
2 6 150 7 20 0 80 300 220 170
20
C 8 6 7 6 0 250 0
250 0
Demand 200 300 150 270 80

50 0 0 20 0
0
0
Total profit= =20530
2. VAM
P Q R S T Capacity 50
A 4 0 6 5 0 450 0 4 1
150 300 150
0
B 5 2 6 7 0 300 02 3 1 1 1
50 150 100 250 150
C 8 6 7 6 0 80 250 6 0 1 1 1
170 0
170
Demand 200 300 150 270 80
50
0 0 100 0
0 0
1 2 0 1 0
1 2 0 1 Total Profit =20450

1 0 1
3 1 1
1 1
P Q R S T Capacity
A 4 150 0 300 6 5 0 450 -1

-1
−𝜽 +𝜽
B 5 50 2 6 7 0 300 0
150 100 -1
+𝜽 −𝜽
C 8 6 7 6
170 0 80 250 -1
Demand 200 300 150 270 80
5 1 6 7 1
𝜃 is minimum of negative (100- 𝜃 ) , (150- 𝜃 ) ===== 𝜃 =100 DEPARTMENT OF MATHEMATICS

P Q R S T Capacity
A 4 50 0 300 6 5 0 450 0
100
B 5 150 2 6 7 0 300 1
150
C 8 6 7 6
170 0 80 250 1
Demand 200 300 150 270 80
4 0 5 5 -1
Since all cell evaluation are +ve, the solution id optimum = 20550 DEPARTMENT OF MATHEMATICS
Assignment Problem
It is an special case of Transportation problem
Objective: Assign number of origins (jobs) to the equal number of destination(person) at

minimum cost or(maximum profit).
4/22/2024
by: vishal Patil 61 DEPARTMENT OF MATHEMATICS
Assignment Problem
An assignment problem can be stated in the form of 𝑛 × 𝑛 cost matrix 𝐶𝑖𝑗 of real numbers as
given in the following table.
Each person
can do each
job at a time.
4/22/2024
Mathematical formulation
4/22/2024
Difference between TP & AP
Transportation Problem Assignment Problem
1 Number of sources & destination need not to be Since assignment is done one to one basis, the
equal. Hence the cost matrix is not necessarily a number of sources & destination are equal, Hence the
square matrix. cost matrix to be a square matrix.
2 xij , the quantity to be transported form ith origin to Jth job is to be assigned to the ith person (worker)
jth destination can take any possible positive value, and can take either value 1 or 0.
and it satisfies the rim requirement.
3 The capacity and the requirement The capacity and the requirement value
value is equal to 𝑎𝑖 and 𝑏𝑗 for is is exactly one , i.e., for each source
𝑖𝑡ℎ source and 𝑗𝑡ℎ destination. and each destination.
4 The problem is unbalanced if the total supply and The problem is unbalanced if the cost matrix is not a
total demand are not equal square matrix.
4/22/2024
Hungarian method of solving Assignment problem
Procedure:
• Phase 1
Step 0: Consider the given matrix.
Step 1: In a given problem, if the number of rows is not

equal to the number of columns and vice versa, then add a
dummy row or a dummy column. The assignment costs for
dummy cells are always assigned as zero.
Step 2: Reduce the matrix by selecting the smallest element

in each row and subtract with other elements in that row.
4/22/2024
Hungarian method of solving Assignment problem
Phase 2:
• Step 3: Reduce the new matrix column-wise using the same method as given in step
2.
•
Step 4: Draw minimum number of lines to cover all zeros.
•
Step 5: If Number of lines drawn = order of matrix, then optimally is reached, so
proceed to step 7. If optimally is not reached, then go to step 6.
•
Step 6: Select the smallest element of the whole matrix, which is NOT COVERED by
lines. Subtract this smallest element with all other remaining elements that are NOT
COVERED by lines and add the element at the intersection of lines. Leave the
elements covered by single line as it is. Now go to step 4.
•
Step 7: Take any row or column which has a single zero and assign by squaring it.
Strike off the remaining zeros, if any, in that row and column (X). Repeat the process
until all the assignments have been made.
•
Step 8: Write down the assignment results and find the minimum cost/time.
4/22/2024
Problem 1. Using following matrix, determine a) optimal job
assignment, b)the cost of the assignment.
JOBS COST
1 2 3 4 5 MATRIX
A 10 3 3 2 8
B 9 7 8 2 7
MECHANICS C 7 5 6 2 4
D 3 5 8 2 4
E 9 10 9 6 10
SOLUTION:
STEP 1: In a given problem, the number of rows ARE equal to the number of
columns. (square matrix of order 5).
STEP 2: Reduce the matrix
Row by selecting the smallest
1 2 3 4 5 min
A 10 3 3 2 8 2
element in each row and
B 9 7 8 2 7 2 subtract with other
C 7 5 6 2 4 2 elements in that row
D 3 5 8 2 4 2
E 9 10 9 6 10 6
4/22/2024
1 2 3 4 5
Step 3: Reduce the new
A 8 1 1 0 6
B 7 5 6 0 5 matrix column-wise using
C 5 3 4 0 2 smallest element in each
D 1 3 6 0 2 column and subtract with
E 3 4 3 0 4 other elements in that
column.
COL
MIN 1 1 1 0 2
1 2 3 4 5 Step 4: Draw minimum

A 7 0 0 0 4 number of lines to cover
B 6 4 5 0 3
all zeros.
C 4 2 3 0 0
D 0 2 5 0 0
E 2 3 2 0 2
Step 5: If Number of lines
1 2 3 4 5 drawn(N) = order of matrix (n),
A 7 0 0 0 4 N=4, n=5, N<n. optimality not
B 6 4 5 0 3 reached , go to step 6.
C 4 2 3 0 0
D 0 2 5 0 0
E 2 3 2 0 2
4/22/2024
1 2 3 4 5 STEP 6: Select the smallest element of the
A 7 0 0 0 4 whole matrix, which is NOT COVERED by lines.
B 6 4 5 0 3
C 4 2 3 0 0
Subtract this smallest element with all other
D 0 2 5 0 0 remaining elements that are NOT COVERED by
E 2 3 2 0 2 lines and add the element at the intersection of
lines. Leave the elements covered by single line
as it is. Now go to step 4
1 2 3 4 5
A 9 0 0 2 6
B 6 2 3 0 3 2
C 4 0 1 0 0 Step 4: Draw minimum
D 0 0 3 0 0 number of lines to cover
E 2 1 0 0 2 all zeros.
1 2 3 4 5
A 9 0 0 2 6
B 6 2 3 0 3
C 4 0 1 0 0
D 0 0 3 0 0
E 2 1 0 0 2
Number of lines drawn(N) = order of matrix (n)
N=5, n=5, N= n. optimality reached , go to step 7

4/22/2024
1 2 3 4 5 Step 7: Take any row or column which has a
A 9 0 0 2 6 3 single zero and assign by squaring it. Strike off
B 5 2 3 0 3 1 the remaining zeros, if any, in that row and
C 4 0 1 0 0 4 column (X). Repeat the process until all the
D 0 0 3 0 0 5 assignments have been made.
E 2 1 0 0 2 2
JOB MECHANIC COST

1 2 3 4 5
A 9 0 0 2 6 1 D 3
B 5 2 3 0 3 2 A 3
C 4 0 1 0 0
3 E 9
D 0 0 3 0 0
E 2 1 0 0 2 4 B 2
5 C 4
TOTAL 21
4/22/2024
Problem 2: solve the following assignment problem.
JOBS
I II III IV
A 42 35 28 21
MECHANICS B 30 25 20 15
C 30 25 20 15
D 24 20 16 12
SOLUTION:
STEP 1: In a given problem, the number of rows ARE equal to the number of columns.
(square matrix of order 4).
JOBS JOBS
I II III IV ROW MIN I II III IV
A 42 35 28 21 21 A 21 14 7 0
MECHANICS B 30 25 20 15 15 B 15 10 5 0
C 30 25 20 15 15 C 15 10 5 0
D 24 20 16 12 12 D 12 8 4 0
COL
MIN 12 8 4 0
4/22/2024
JOBS JOBS
I II III IV I II III IV
A 9 6 3 0 A 7 4 2 0
MECHANICS B 3 2 1 0 MECHANICS B 1 0 0 0
C 3 2 1 0 C 1 0 0 0
D 0 0 0 0 D 0 0 1 2
N=n, 4=4
JOBS JOBS
A 9 6 3 0 A 7 4 2 0
MECHANICS B 3 2 1 0 MECHANICS B 1 0 0 0
C 3 2 1 0 C 1 0 0 0
D 0 0 0 0 D 0 0 1 2
N<n, 2<4
JOBS
JOBS I II III IV
I II III IV A 7 4 2 0
A 8 5 2 0 MECHANICS B 1 0 0 0
MECHANICS B 2 1 0 0 C 1 0 0 0
C 2 1 0 0 D 0 0 1 2
D 0 0 0 1
4/22/2024
by: vishal Patil N<n, 3<4 72 DEPARTMENT OF MATHEMATICS
JOB MECHANIC COST JOB MECHANIC COST
I D 24 I D 24
II C 25 II B 25
III B 20 III C 20
IV A 21 IV A 21
TOTAL 90 TOTAL 90
4/22/2024
Problems
Problem 3: SOLVE THE FOLLOWING ASSIGNMENT PROBLEM.
MECHANICS
A B C D E
1 13 8 16 18 19
JOBS 2 9 15 24 9 12
3 12 9 4 4 4
4 6 12 10 8 13
5 15 17 18 12 20
SOLUTION:
STEP 1: In a given problem, the number of rows ARE equal to the number of
columns. (square matrix of order 5).
MECHANICS MECHANICS
A B C D E A B C D E
1 5 0 8 10 11 1 5 0 5 10 8
JOBS 2 0 6 15 0 3 JOBS 2 0 6 12 0 0
3 8 5 0 0 0 3 11 8 0 3 0
4 0 6 4 2 7 4 0 6 1 2 4
5 3 5 6 0 8 5 3 5 3 0 5
N<n, 4<5 N=n, 5=5

4/22/2024
MECHANICS JOB MECHANIC COST
A B C D E
1 5 0 5 10 8 1 B 8
JOBS 2 0 6 12 0 0
2 E 12
3 11 8 0 3 0
4 0 6 1 2 4 3 C 4
5 3 5 3 0 5
4 A 6
5 D 12
TOTAL 42
Problem 4: SOLVE THE FOLLOWING
ASSIGNMENT PROBLEM.
MECHANICS MECHANICS
A 5 7 11 6 A 0 2 6 1
JOBS B 8 5 9 6 JOBS B 3 0 4 1
C 4 7 10 7 C 0 3 6 3
D 10 4 8 3 D 7 1 5 0
4/22/2024 75 DEPARTMENT OF MATHEMATICS

MECHANICS MECHANICS
A 0 2 2 1 A 0 0 0 1
JOBS B 3 0 0 1 JOBS B 5 0 0 2
C 0 3 2 3 C 0 1 0 3
D 7 1 1 0 D 8 0 0 0
N=n, 4=4
N<n, 3<4
MECHANICS MECHANICS
A 0 1 1 1 A 0 0 0 0
JOBS B 4 0 0 2 JOBS B 5 0 0 2
C 0 2 1 3 C 0 1 0 3
D 7 0 0 0 D 8 0 0 0
N<n, 3<4 A-II, B-III, C-I, D-IV,

7+9+4+3=23
4/22/2024
UNBALANCED ASSIGNMENT PROBLEM
Any assignment problem is said to be unbalanced if cost matrix is not square matrix.
Problem 1: Solve the following assignment problem.
MECHANICS
A B C D E
1 4 3 6 2 7
JOBS 2 10 12 11 14 16
3 4 3 2 1 5
4 8 7 6 9 6
SOLUTION:
STEP 1: In a given problem, the number of rows ARE not equal to the number of
columns.
4/22/2024
MECHANICS MECHANICS
Row A B C D E
A B C D E Min 1 2 0 3 0 4
1 4 3 6 2 7 2 JOBS 2 0 1 0 4 5
JOBS 2 10 12 11 14 16 10 3 3 1 0 0 3
3 4 3 2 1 5 1 4 3 1 0 4 0
4 8 7 6 9 6 6 5 1 0 0 1 0
5 0 0 0 0 0 0
MECHANICS
A B C D E N=n, 5=5
1 2 1 4 0 5 MECHANICS
JOBS 2 0 2 1 4 6 A B C D E
3 3 2 1 0 4 1 2 0 3 0 4
4 2 1 0 3 0 JOBS 2 0 1 0 4 5
5 0 0 0 0 0 3 3 1 0 0 3
Col min 0 0 0 0 0 4 3 1 0 4 0
5 1 0 0 1 0
MECHANICS
A B C D E
1 2 1 4 0 5
JOBS 2 0 2 1 4 6 A-2, B-1, C-4, D-3,E-5
3 3 2 1 0 4
4 2 1 0 3 0 10+3+6+1+0=20
5 0 0 0 0 0
N<n, 4<5
4/22/2024
Problem 2: A company has 4 machines to do 3 jobs. Each job can be assigned to
only one machine. The cost of each job on each machine is given below.
Determine the job assignment that will minimize the total cost.
MECHANICS
w x y z
A 18 24 28 32
JOBS B 8 13 17 18
C 10 15 19 22
SOLUTION:
columns.
MECHANICS MECHANICS MECHANICS

w x y z RM w x y z w x y z
A 18 24 28 32 18 A 0 6 10 14 A 0 6 10 14
JOBS B 8 13 17 18 8 JOBS B 0 5 9 10 JOBS B 0 5 9 10
C 10 15 19 22 10 C 0 5 9 12 C 0 5 9 12
D 0 0 0 0 0 D 0 0 0 0 D 0 0 0 0
CM 0 0 0 0
4/22/2024
MECHANICS MECHANICS
w x y z w x y z
A 0 6 10 14 A 0 1 51 5
JOBS B 0 5 9 10 JOBS B 0 0 0 1
C 0 5 9 12 C 0 0 0 3
D 0 0 0 0 D 9 4 0 0
MECHANICS MECHANICS
w x y z w x y z
A 0 1 5 9 A 0 1 51 5
JOBS B 0 0 4 5 JOBS B 0 0 0 1
C 0 0 4 7 C 0 0 0 3
D 5 0 0 0 D 9 4 0 0
MECHANICS
w x y z
A 0 1 1 5
JOBS B 0 0 0 1 A-W, B-X, C-Y, D-Z, / A-W, B-Y, C-X, D-Z,
C 0 0 0 3
18+13+19=50
D 9 4 0 0
4/22/2024
MAXIMIZATION OF ASSIGNMENT PROBLEM
Objective is to maximize the profit:

Convert the given profit matrix into the loss matrix by subtracting all the elements from the
highest element.
Then apply same procedure.
4/22/2024
Problem 2: A company has 4 machines to do 5 jobs. Each job can be assigned to
only one machine. The PROFIT MATRIX of each job on each machine is given
below. Find the assignment of machines to the job that will result in maximun
profit.
JOBS
A B C D E
1 62 78 50 111 82
MECH 2 71 84 61 73 59
3 87 92 111 71 81
4 48 64 87 77 80
SOLUTION:
columns.
STEP 2: convert max to min (111 subtract to all)
JOBS JOBS
A B C D E A B C D E
1 62 78 50 111 82 1 49 33 61 0 29
MECH 2 71 84 61 73 59 MECH 2 40 27 50 38 52
3 87 92 111 71 81 3 24 19 0 40 30
4 48 64 87 77 80 4 63 47 24 34 31
5 0 0 0 0 0 5 111 111 111 111 111
A-5, B-2, C-3, D-1,E-4

4/22/2024 DEPARTMENT OF MATHEMATICS
by: vishal Patil 386
82
Problem 2: Solve for maximizing the profit
JOBS
A B C D E
1 32 38 40 28 40
MECH 2 40 24 28 21 36
3 41 27 33 30 37
4 22 38 41 36 36
5 29 33 40 35 39
SOLUTION:
1-B, 2-A, 3-E, 4-C, 5-D
1-B, 2-A, 3-E, 4-D, 5-C
191
4/22/2024

Module-2 - Transportation and Assignment Problem

Uploaded by

Copyright:

Available Formats

Module-2 - Transportation and Assignment Problem

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Module-2 - Transportation and Assignment Problem

Uploaded by

Copyright:

Available Formats

Module 2

Transportation and Assignment Problems

• Assignment Problems (Hungarian method).

➢ An interactive procedure that finds the least costly

To Factory Des Moines

Cost of shipping 1 unit from Fort Cleveland Total demand

There are a number of methods for generating an initial feasible

Consider three of the following

(i) North West Corner Method

(ii) Least Cost Method

(iii) Vogel’s Approximation Method

The simplest of the procedures used to generate an initial feasible

Adjust the supply and demand numbers in the respective rows

To illustrate the NWCM,

Total Cost = 20x7 +1 X 5 + 25 x 7 + 2 X 3 + 17 + 8 = Rs. 462

Total cost = (60 × 3) + (50 × 3) + (20 × 9) + (80 × 3) + (0 × 5)

Solution : total demand ≠ Total capacity that is., σ 𝑏𝑗 ≠ σ 𝑎𝑖

A 4 200 0 250 6 5 0 450 250 0

Demand 200 300 150 270 80

Total Profit= 200X22+250X26+50X24+150X20+100X19+170X20+80X0=20400

A 4 150 0 300 6 5 0 450 150 0

Demand 200 300 150 270 80

Total profit= =20530

1 2 0 1 Total Profit =20450

A 4 150 0 300 6 5 0 450 -1

Demand 200 300 150 270 80

𝜃 is minimum of negative (100- 𝜃 ) , (150- 𝜃 ) ===== 𝜃 =100 DEPARTMENT OF MATHEMATICS

Demand 200 300 150 270 80

It is an special case of Transportation problem

Objective: Assign number of origins (jobs) to the equal number of destination(person) at

Step 0: Consider the given matrix.

Step 1: In a given problem, if the number of rows is not

Step 2: Reduce the matrix by selecting the smallest element

1 2 3 4 5 Step 4: Draw minimum

Number of lines drawn(N) = order of matrix (n)

N=5, n=5, N= n. optimality reached , go to step 7

JOB MECHANIC COST

N<n, 4<5 N=n, 5=5

4/22/2024 75 DEPARTMENT OF MATHEMATICS

N<n, 3<4 A-II, B-III, C-I, D-IV,

MECHANICS MECHANICS MECHANICS

Objective is to maximize the profit:

A-5, B-2, C-3, D-1,E-4

1-B, 2-A, 3-E, 4-C, 5-D

1-B, 2-A, 3-E, 4-D, 5-C

You might also like