Module III

Transportation and assignment problems

Transportation problems
Transportation problems are particular class of allocation problems. The objective is to transport
various amounts of a single homogeneous commodity that are stored at several origins, to a number of
destinations. The transportation is effected in such a way that the destination’s demands are satisfied
within the capacity of origins and the total transportation cost is a minimum.
Eg. A manufacturing concern has ‘m’ plants located in ‘m’ different cities in India. There are ‘n’
retail shops in ‘n’ different cities, which can absorb all the products stored. Then the transportation
problem is to determine the transportation schedule that minimizes the total cost of transporting the
manufactured products, from various plants to various retail shops.
Transportation technique can be applied to other problems also. Machine allocation, product mix etc.
Transportation technique can be applied not only to the cost minimization problems, but also to time
minimizing problems, distance minimizing problems, profit maximizing problems etc.
Transportation table
Denote the origins as , , . . . , and destinations as , , . . . , . Let the quantity produced
at the origins be respectively , , . . . , . Let the requirements in various destinations be
respectively , , . . . , . The total quantity produced and the total quantity required must be
equal. That is, + + . . . + = + + . . . + . Or ∑ =∑ . Let be the cost of
th th
transportation of one unit from the i origin to the j destination.

Available

Required

This matrix is known as transportation table or cost effectiveness matrix.

Here total availability = total requirement. That is ∑ =∑ .
The problem is to determine the quantity to be transported fom the ith origin to the jth destination
such that the total cost, ∑ ∑ is minimum.
Transportation problem in the form of a LPP (Mathematical formulation)
Let be the number of units transported from the ith origin to the jth destination.
Let be the cost of transportation of one unit from the ith origin to the jth destination.
Let be the units available in the ith origin and be he units required in the jth destination.
Then the problem is
Minimize Z = ∑ ∑
Subject to ∑ = , for i = 1, 2, . . . , m
∑ = , for j = 1, 2, . . . , n
0 for i, j
Basic assumptions in transportation problem
1. Total quantity available for distribution is equal to the total requirement in different
destinations together. That is ∑ =∑
2. The unit transportation cost from one origin to a destination is certain.
3. The unit cost is independent of the quantity transported.
4. Objective is to minimize the total transportation cost.
Uses of transportation technique
1. To minimize transportation cost from factories to warehouses or from warehouses to markets.
2. To determine lowest cost location for new factory
3. To determine minimum cost production schedule.
Feasible solution
A feasible solution to a transportation problem is a set of non-negative individual allocations which
satisfy the row and column sum restrictions. So the sum of the allocations in the rows must be equal
to the availability in that row. Similarly sum of the allocations in the columns must be equal to the
demand in that column.
Basic feasible solution
A feasible solution to a m n transpotation problem is said to be a basic feasible solution if the total
number of allocations is exactly equal to m + n+ 1.
Optimal solution
A feasible solution is said to be optimal if it minimizes the total transportation cost.
Non degenerate basic feasible solution
A feasible solution of a m n transpotation problem is said to be non degenerate basic feasible
solution if
(1) The number of allocations is equal to m + n+ 1
(2) The allocations are in independent positions.
Loops in transportation table (non-independent position)
Allocations are said to be in independent positions, if it is impossible to increase or decrease any
allocation without either changing the position of the allocation or violating the rim requirements.
Therefore when the allocations are in independent positions, it is impossible to travel from any
allocation back to itself through a series of horizontal or vertical jumps.
For example;
 Table I
2
5 3 2
3 In table I, the allocations are in independent positions.
4 7 2
7 3
5 6 2

Table II
8 1
5 3 2
In table II, the allocations are not in independent positions.
4 7 2
7 3
5 6 2

Table III
8 2
5 3 2 3
5 2
4 7 2 4 In table III, the allocations are not in independent positions.
5 2
5 6 2 1

Steps for solving a transportation problem

1. Set up a transportation table with ‘m’ rows representing the origins and ‘n’ columns
representing the destinations.
2. Develop an initial feasible solution to the problem.
3. Test whether the solution is optimal or not.
4. If the solution is not optimal modify the allocations.
5. Repeat steps 4 and 5 until an optimal solution is obtained.
Note. If there are ‘m’ rows and ‘n’ columns, there will be ‘mn’ cells. Each cell is known by its row
number and column number. For example, cell (2, 3) means the cell in the second row and third
column.
Initial (basic) feasible solution
Initial feasible solutions are those which satisfy the rim requirement. That is, the allocations made in
every row taken together is equal to the availability shown in that row. Similarly for each column, the
total allocation should be equal to the requirement in that column.
The initial feasible solution can be obtained either by inspection or by some rules. The commonly
used methods for finding initial feasible solution are (1) North west corner rule (2) Lowest cost entry
method (matrix minima method) (3) Vogel’s approximation method (unit cost penalty method)
North-West corner rule
This method is used to find initial feasible solution.
Procedure
 Step 1
Allocate to cell (1, 1) maximum possible amount, which is minimum of row total and column total.
So either a row total or column total gets exhausted. Cross off that row or column as the case may be.
Step 2
Consider the reduced matrix. In that matrix, allocate to the cell (1, 1) maximum possible amount,
which is minimum of present row total and column total. So either a row total or column total gets
exhausted. So cross off that row or column as the case may be.
Step 3
Repeat the above steps until all the available quantities are exhausted.
Eg. Find the initial feasible solution to the transportation problem given below, by north west corner
rule.

Destinations
Supply
Origins
2 7 4 5

3 3 1 8

5 4 7 7

1 6 2 14

Demand 7 9 18
Answer. Allocate to cell (1, 1), minimum of 5 and 7 (row total and column total), which is 5. Then
row total is exhausted, since the supply of is completely met. So cross off row
Supply
5
2 7 4 5 x
3 3 1 8
/
5 4 7 7

14
1 6 2

Demand 7 9 18
(2)
Consider the reduced matrix after deleting row.
Allocate to cell (1, 1), minimum of 8 and 2, 2
8 (6)
which is 2. Then column is exhausted, 3 3 1
and it is crossed off. 7
5 4 7

1 6 2 14

2 9 18
x

Consider the reduced matrix after deleting column.

Allocate to cell (1, 1), minimum of 6 and 9, 6
which is 6. Then row is exhausted, 3 1 6 x
and it is crossed off.
4 7 7

6 2 14
9 18
(3)

Consider the reduced matrix after deleting row.

Allocate to cell (1, 1), minimum of 7 and 3, 3
7 (4)
which is 3. Then column is exhausted, 4 7
and it is crossed off.
6 2 14

3 18
x

Consider the reduced matrix after deleting column.

Allocate 4 to cell (1, 1) and 14 to cell (2, 1). 4
4
7
14
2 14

18
Thus the various allocations made to the cells are shown below and the solution is

Supply
5 5
2 7 4
2 6 8
3 3 1
/ 3 4 7
5 4 7
14 14
1 6 2

Demand 2 9 18

Total transportation cost = (5 2) + (2 3) +(6 3) +(3 4) +(4 7) +(14 2)

= 10 + 6 + 18 + 12 + 28 + 28 = 102.
Lowest cost entry method
Choose the cell, having the lowest cost in the matrix. Allocate there, the minimum of row total and
column total. Thus either a row total or column total is exhausted. Cross of the corresponding row or
column. From the reduced matrix, locate the cell having the lowest cost. Allocate to that cell, the
minimum of row total and column total. Thus either a row total or column total is exhausted. Cross of
the corresponding row or column. This leading to a reduced matrix. Continue this process until all the
available quantities are exhausted.
Eg. Find the initial feasible solution to the following transportation problem by lowest cost entry
method.

Supply

2 7 4 5

3 3 1 8

5 4 7 7

1 6 2 14

Demand 7 9 18
 Answer. The lowest cost is 1 in cells Supply
(2, 3) and (4, 1). Select one of these,
say (2, 3). Allocate to cell (2, 3), 2 7 4 5
minimum of 8 and 18 (row total and 8 8 x
column total), which is 8. Then 3 3 1
row total is exhausted. So cross off 7
5 4 7
the row .
14
1 6 2

Demand 7 9 18
(10)

The lowest cost in the reduced matrix

is 1 in the cell (3, 1). Allocate to this
cell, minimum of 7 and 14, which is 2 7 4 5
7. Then column total is exhausted.
5 4 7 7
So cross off the column .
7
1 6 2 14 (7)

7 9 10
x

The lowest cost in the reduced matrix 5

is 2 in the cell (3, 2). Allocate to this 7 4
cell, minimum of 7 and 10, which is 7
4 7
7. Then row total is exhausted. So
7
cross off the row . 6 2 7x

9 10
(3)

Allocate to the cell (2, 1), minimum

of 7 and 9, which is 7. Then row 5
total is exhausted. So cross off the 7 4
7
row .
4 7 7x

9 3
(2)

Finally allocate 2 to the cell (1, 1)

and 3 to the cell (1, 2). 2 3 5
7 4
2 3
 The solution is given in the following matrix.

Supply
2 3 5
Total transportation cost = 2 7 4
= (2 7) + (3 4) + (8 1) + (7 4) 8 8
+ (7 1) + (7 2) = 14 + 12 + 8 + 28 + 7 3 3 1
+ 14 = 83. 7 7
5 4 7
7 7 14
1 6 2

Demand 7 9 18

Vogel’s approximation method

Step 1
Under this method we write the difference between smallest and second smallest costs in
each column below the corresponding column, within brackets. Similarly write similar
differences in each row to the right of corresponding row. These differences are known as
penalty.
Step 2
Select the row or column having the largest penalty and allocate the maximum possible
amount to the cell with lowest cost in that row or column as the case may be. Thus either the
row total or column total is completely exhausted. Cross off that row or column. Construct
the reduced matrix with the remaining rows and columns.
Step 3
For the reduced matrix obtained, apply steps 1 and 2 until all rows and columns totals are
exhausted.
Note. Vogel’s approximation method is better than the other two methods.
Eg. Find the initial feasible solution for the transportation problem by Vogel’s method.

Supply

2 7 4 5

3 3 1 8

5 4 7 7

1 6 2 14

Demand 7 9 18
 Answer. Write penalties in brackets for all rows and columns.
Penalties (difference between smallest and second smallest costs)
Row 1; 4 – 2 = 2, row 2; 3 – 1 = 2 , row 3; 5 – 4 = 1, row 4; 2 – 1 = 1
Column 1; 2 – 1 =1, column 2; 4 – 3 = 1, column 3; 2 – 1 = 1 .

Supply
Maximum penalty 2 is associated
with row and row . Select one of 5
2 7 4 5 (2) x
these, say row . The lowest cost in
the row is in the cell (1, 1). 3 3 1 8 (2)
Allocate to cell (1, 1), minimum of 5
and 7 (row total and column total), 5 4 7 7 (1)
which is 5. Then row total is
exhausted. So cross off the row . 1 6 2 14 (1)
Demand 7 9 18
(1) (1) (1)

Maximum penalty 2 is associated

with column and row . Select 8
one of these, say row . The lowest 3 3 1 8 (2) x
cost in the row is in the cell (1, 3).
Allocate to cell (1, 3), minimum of 8 5 4 7 7 (1)
and 18, which is 8. Then row total
1 6 2 14 (1)
is exhausted. So cross off the row .
2 9 18
(2) (1) (1)

Maximum penalty 5 is column . The

lowest cost in the column is in the 5 4 7 7 (1)
cell (1, 3). Allocate to cell (2, 3), 10
minimum of 14 and 10, which is 10. So 1 6 2 14 (1)
cross off column .
2 9 10
(4) (2) (5)
x

Maximum penalty 5 is row The

lowest is in the cell (2, 1). Allocate 2 to 7 (1)
5 4
cell (2, 1) and cross off column . 2 4 (5)
1 6

2 9
(4) (2)
x
Allocate 2 to cell (2, 1) and 7 to cell (1, 1)
7
7
4
2
2
6

The solution is given below.

Supply
5
2 7 4 5
8
3 3 1 8
7
5 4 7 7
2 2 10
1 6 2 14

Demand 7 9 18

Total transportation cost = (5 2) + (8 1) +(7 4) +(2 1) +(2 6) +(10 2)

= 10 + 8 + 28 + 2 + 12 + 20 = 80.
Optimal solution for transportation problem
By applying Vogel’s method or lowest cost entry method or north west corner rule, an initial
feasible solution is obtained. The next step is to examine whether the solution is optimal or
not. For this we conduct test of optimality.
For this we use the modified distribution method (MODI method)
MODI method
Step 1
When the initial feasible solution is obtained some cells are occupied (allocation made) and
others unoccupied. Number of occupied cells is m + n – 1 (m – number of rows, n – number
columns in the matrix). Let be the cost of the cell (i, j).
Then we form m + n -1 equations of the form + = corresponding to each occupied
cell. Determine m + n values and , satisfying the above equation. For example if one of
the occupied cells is (2, 3), then the equation is + = , where = is the cost in the
cell (2, 3). For solving the equations, we take one of or values as zero. (since the
number of unknowns is more than the number of equations)
Step 2
Then we calculate cell evaluations known as values for unoccupied cells, by the formula
= – ( + ).
Step 3
If all values are positive, the solution is optimal and unique. If at least one of them is
 zero and others positive the solution is optimal but alternative solution exists. If at least one
is negative, the solution is not optimal.
Step 4
If the solution is not optimal, make reallocations. Give maximum allocation to the cell for
which is negative, making one of the occupied ells empty.
Then we repeat the steps 1 to 4 until solution becomes optimal.
Eg. Solve the following transportation problem

Supply

2 7 4 5

3 3 1 8

5 4 7 7

1 6 2 14

Demand 7 9 18
Answer. To find the initial basic feasible solution, we apply Vogel’s method

Supply
5
Table I 2 7 4 5 (2) x
Allocate to cell (1, 1), minimum of 5 and
3 3 1 8 (2)
7, which is 5. Then cross off the row .
5 4 7 7 (1)

1 6 2 14 (1)
Demand 7 9 18
(2) (1) (1)

Table II 8
Allocate to cell (1, 3), minimum of 8 and 18, 3 3 1 8 (2) x
which is 8. Then cross off the row .
5 4 7 7 (1)

1 6 2 14 (1)

3 9 18
(2) (1) (1)
Table III 7 (1)
5 4 7
Allocate to cell (2, 3), minimum of 10 and 14, 10
14 (1)
which is 10. Then cross off the column . 1 6 2
2 9 10
(4) (2) (5)
x

Allocate 2 to cell (2, 1) and cross off

column . 7 (1)
5 4
2 4 (5)
1 6

2 9
(4) (2)
x

7
7
4
Allocate 2 to cell (2, 1) and 7 to cell (1, 1)
2
2
6

Supply
5
The initial basic feasible solution is 2 7 4 5
8
3 3 1 8
7
5 4 7 7
2 2 10
1 6 2 14
Demand 7 9 18

To test the optimality; form the equations + = for occupied cells.

Occupied cells are (1, 1), (2, 3), (3, 2), (4, 1), (4, 2), (4, 3). The costs ( ) in these occupied
cells are 2, 1, 4, 1, 6, 2. The equations are,
+ =2 + =1
+ =1 + =6
+ =4 + =2
To solve these equations, take = 0 (which occurs more number of times)
+ =1 =1
+ =6 =6
 + =2 =2
+ =2 +1=2 =2–1=1
+ =1 +2=1 =1–2=-1
+ =4 +6=4 = 4 – 6 = -2

Calculate the cell evaluation for unoccupied cells; = –( + ).

–( + )=
+
𝑖
7 4
1+6=7 1+2=3 1
3 3
-1 + 1 = 0 -1 + 6 = 5 -1
5 7
-2 + 1 = -1 -2 + 2 = 0 -2
0

1 6 2

7–7=0 4–3=1
3–0=3 3–5=-2
5+1 =6 7–0=7

Since one of the values is negative, the solution is not optimal.

Make reallocations. Give maximum allocation to the cell having negative , that is the cell
(2, 2).
Consider the four cells below

Transfer 2 from ( , ) to ( , ). 8 8
Correspondingly subtract 2 from ( , ) 3 1
and add 2 to ( , ). The resulting table is 2 10 12
given below. 6 2

2 9

2 8-2 2 6 8
8 = 3 1
3 1
2-2 10+2 12 12
12 6 2
6 2
2 18
2 18
The reallocation gives the following matrix.
 5
2 7 4 5
2 6
3 3 1 8
7
7
5 4 7
2 12
14
1 6 2
7 9 18
Test the optimality again; the equations + = for occupied cells are
+ =2 + =4
+ =3 + =1
+ =1 + =2
To solve these equations, take =0
Then = 1, = 4, = 2, = 1, = - 1, =0
Calculate the cell evaluation for unoccupied cells; = –( + ).

–( + )=
+ 𝑈𝑖
7 4
1+4=5 1+2=3 1
3
-1 + 1 = 0 -1
5 7
0+1=1 0+2=2 0
6 0
0+4 =4
𝑉𝑗 1 4 2

7–5=2 4–3=1
3–0=3
5-1 =4 7–2=5
6–4=2

No value is negative, the solution is optimal. The optimal solution is;

to : 5 to : 7
to : 2 to : 2
to : 6 to : 12
Total transportation cost = (5 2) + (2 3) +(6 1) +(7 4) +(2 1) +(12 2) = 10 + 6
+ 6 + 28 + 2 + 24 = 76.
Degeneracy in transportation problems
In transportation problem, degeneracy occurs whenever the number of individual allocations
is less than m + n – 1, where m and n are respectively the number of rows and columns of the
transportation matrix. Degeneracy in transportation problem can develop in two ways
 (1) The basic feasible solution may degenerate from the initial stage onwards.
(2) They may degenerate at any intermediate stage.
In such cases we allocate to one o more empty cells so that the total number of allocations
is m + n – 1. is a very small number almost equal to zero.
Eg. Solve the following transportation problem.

A B C Available

X 50 30 220 1

Y 90 45 170 3

Z 250 200 50 4

Required 4 2 2

Answer. To find the initial basic feasible solution, we apply Vogel’s method

A B C

X 1 (20)
Table I 50 30 220
Allocate to cell (3, 3), minimum of 4 and Y 3 (45)
90 45 170
2, which is 2. Then cross off column C.
Z 2 4 (150) ←
250 200 50

4 2 2
(40) (15) (120)
x

A B
Allocate 2 to cell (3, 2 and cross off
row Z and column B X 1 (20)
50 30
Y 3 (45)
90 45
2
Z 2 (50) ← x
250 200
4 2
(40) (15)
x
A
Allocate 1 to cell (1, 1) and 3 to cell (2, 1)
X 1 1
50
Y 3 3
90

4
The initial basic feasible solution is given below.

A B C

X 1
50 30 220 1
Y 3
90 45 170 3
Z 2 2
250 200 50 4

4 2 2

Here m + n -1 = 3 + 3 -1 = 5. Total number of allocations is 4, which is less than m + n -1. So

the solution is degenerate. Now to resolve this degeneracy, we allocate a very small amount
to the cell (2, 2), getting 5 allocations at independent positions.
The new basic feasible solution is;

A B C

1
X 50 30 220 1
3
Y 90 45 170 3
2 2
Z 250 200 50 4

4 2 2

To test the optimality; form the equations + = for occupied cells.

Occupied cells are (1, 1), (2, 1), (2, 2), (3, 2), (3, 3). The costs ( ) in these occupied cells
are 50, 90, 45, 200, 50. The equations are,
+ = 50 + = 200
+ = 90 + = 50
+ = 45
To solve these equations, take = 0, then = 200, = 50,
+ = 45 + 200 = 45 = 45 – 200 = - 155
+ = 90 -155 + = 90 = 90 + 155 = 245
+ = 50 + 245 = 50 = 50 – 245 = - 195.

Calculate the cell evaluation for unoccupied cells; = –( + ).

+
𝑈𝑖
30 220 5 -145 25 365
-195
170 -105 275
-155
250 245 5
0
𝑉𝑗 245 200 50
No is negative, so the solution is optimal. The optimal solution is
X to A; 1, Y to A: 3, Z to B: 2, Z to C: 2.
Total transportation cost = (1 50) + (3 90) +( 45) +(2 200) +(2 50)
= 50 + 270 + 0 + 400 + 100 = 8200.
Unbalanced transportation problems
A transportation problem is said to be unbalanced if the sum of all available amounts is not
equal to the sum of all requirements in all destinations together. That is, ∑ ∑ . An
unbalanced transportation problem is converted into a balanced transportation problem, by
introducing a fictitious source or destination. The cost of transportation corresponding to it is
taken to be zero.
Eg. Find the initial feasible solution for the transportation problem.

Availability

11 20 7 8 50
21 16 10 12 40

8 12 18 9 70

Requirement 30 25 35 40

Answer. Here total requirement = 30 + 25 + 35 + 40 = 130. Total availability = 50 + 40 + 70

= 160. They are not equal, so this is an unbalanced transportation problem. Here total
availability is 30 more than the total requirement. We convert it into a balanced problem by
introducing a fictitious destination, with requirement 30 and cost or transportation 0. The
balanced transportation problem is given below.

11 20 7 8 0 50

21 16 10 12 0 40

8 12 18 9 0 70

30 25 35 40 30

To find initial basic feasible solution, we use Vogel’s method.

 50 (7)
Allocate to cell (2, 5), minimum 11 20 7 8 0
of 40 and 30, which is 30. Then 30 40 (10) ←
cross off column . 21 16 10 12 0
70 (8)
8 12 18 9 0
30 25 35 40 30
(3) (4) (3) (1) (0)
X

Allocate to cell (3, 2), minimum

of 70 and 25, which is 25. Then 11 20 7 8 50 (1)
cross off column .
21 16 10 12 10 (2)
25
8 12 18 9 70 (1)

30 25 35 40
(3) (4) (3) (1)
↑
X

Allocate to cell (3, 1), minimum 11 7 8 50 (1)

of 30 and 45, which is 30. Then
cross off column . 21 10 12 10 (2)
30
8 18 9 45 (1)

30 35 40
(3) (3) (1)
↑
X

7 8 50 (1)
Allocate to cell (3, 2), minimum
of 40 and 15, which is 15. Then 10 12 10 (2)
cross off row . 15
18 9 15 (9) ← X

35 40
(3) (1)
Allocate to cell (1, 2), minimum 25
50 (1)
of 50 and 25, which is 25. Then 7 8
cross off column . 10 (2) ←
10 12
35 25
(3) (4)
↑
X

Allocate 25 to cell (1, 2) and 10 25 25

to cell (2, 1) . 7
10 10
10

35

The initial basic feasible solution is given below.

25 25
11 20 7 8 0 50
10 30
21 16 10 12 0 40
30 25 15
8 12 18 9 0 70
30 25 35 40 30

Maximization in transportation problems

A transportation problem in which the objective is to maximize, can be solved by converting
it into a minimization problem. For this select the highest value and subtract all other values
from this highest value. Then the given problem becomes minimization problem.
Eg. Solve the following transportation problem to maximize profit.

Profit in Rs./unit distribution

A B C D
Supply
I 15 51 42 33 23
II 80 42 26 81 44

III 90 40 66 60 33

Demand 23 31 16 30
Answer. This is a maximization problem. Convert it into a minimization problem. For this
select the highest profit, which is 90. Subtract each profit from 90. The modified matrix is,

A B C D
Supply
I 75 39 48 57 23

II 10 48 64 9 44

0 50 24 30 33
III

Demand 23 31 16 30

Then by using Vogel’s method find initial basic feasible solution and by using MODI
method, find optimal solution as before, in the minimization problem.

Assignment problem
Assignment problem is a special case of transportation problem, in which the objective is to
assign a number of origins (persons) to the equal number of destinations (tasks) at a
minimum cost. For example, a department has four persons available for assignment and four
jobs to fill. Then the interest is to find the best assignment which will be in the best interest of
the department.
The assignment problem can be stated in the form of n x n matrix called cost of effectiveness
matrix.
Destination
1 2 ... n

1 ...

2 ...

. .
n ...

Mathematical formulation of assignment problems

Let be the cost of assigning ith source (person) to the jth destination (job) .
Mathematically an assignment problem can be stated as follows.
The problem is
Minimize the total cost Z = ∑ ∑
Subject to the conditions
∑ = 1, for j = 1, 2, . . . , n, which means that only one job is done by the ith person
where i = 1, 2, 3, . . . , n
 ∑ = 1, for i = 1, 2, . . . , n, which means that one person should be assigned to the jth
job , where j = 1, 2, 3, . . . , n
Difference between transportation problem and assignment problem
1. Transportation problem is a LPP in which the objective is to transport various
quantum of commodity that are stored at various origins, to different destinations with
minimum transportation cost.
The assignment problem is a special case of transportation problem in which the
objective is to assign a number of origins to the equal number of destinations at a
minimum cost.
2. In transportation problems number of origins and number of destinations need not be
equal, so that the number of rows and the number of columns of the matrix need not
be equal.
In assignment problems the number of persons and the number of jobs are equal, so
that the number of rows and the number of columns of the matrix are equal.
3. Transportation problems are said to be unbalanced if the total demand and the total
supply are not equal.
Assignment problems are said to be unbalanced if the number of rows are not equal to
the number of columns.
4. In transportation problems a positive quantity is allocated from a source to a
destination.
In assignment problems a source (job) is assigned to a destination (person).
Method of solving assignment problem
Assignment algorithm (Hungarian method)
Step 1
Subtract the smallest element of each row, in the cost matrix, from every element of that row.
Step 2
Subtract the smallest element of each column, in the reduced matrix, from every element of
that column.
Step 3
(a) Starting with row 1 of the matrix obtained, examine all rows having exactly one zero
(0) element. Enclose this zero within showing that assignment is made there.
Cross out all other zeros in the column in which zero is enclosed. Proceed in this way
until the last row is examined.
(b) Examine all columns with one unmarked zero. Mark at this zero. Cross out all
other zeros in the row in which zero is marked. Proceed in this way until the last
column is examined.
(c) Continue these operations (a) and (b) successively until we reach any of the following
two situations.
(i) All the zeros are enclosed by or crossed off.
(ii) The remaining unmarked zeros lie in at least two rows or columns.
In case (i) we have a maximal assignment.
In case (ii) still we have some zeros to be treated. For this we use trial and error method.
After the above operations, there arise two situations.
(1) It has an assignment in every row and column so that we get the solution.
 (2) It does not contain assignment in all rows and columns. In this case the following
method is used.
Step 4
 Mark all rows for which assignments have not been made.
 Mark all columns which have zeros in marked rows.
 Mark all rows (not already marked) which have assignment in marked columns.
 Draw lines through unmarked rows and through marked columns to cover all the
zeros.
Step 5
Select the smallest of the elements that is not covered by lines. Subtract it from all the
elements that do not have a line through them. Add it to every element that lies at the
intersection of two lines. Leave the remaining elements of the matrix unchanged.
Step 6
Reapply the steps 3 to 5 to the modified matrix.
Eg. Find the optimum solution to the following assignment problem showing the cost for
assigning workers to jobs.

Job
X Y Z

A 18 17 16
Workers B 15 13 14
C 19 20 21

Answer.
X Y Z

Subtracting the smallest element of every row 2 1 0

A
from all the elements of that row
B 2 0 1
C 0 1 2

X Y Z
Subtracting the smallest element of every A 2 1 0
column from all the elements of that column 2 0 1
B
C 0 1 2

Mark to zero in every row, starting from the X Y Z

first row. Now all the rows and all the columns have 2 1 0
assignment. So the solution is optimum. The solution A
is A to Z, B to Y, and C to X. Total cost of B2 2 0 1
C 0 1 2
assignment = 16 + 13 + 19 = 48
 Eg. Solve the following assignment problem.

Man
1 2 3 4

I 12 30 21 15
Job II 18 33 9 31
III 44 25 21 21
14 30 28 14
IV

Answer. 1 2 3 4

I
0 18 9 3
Subtracting the smallest element of each row II 9 24 0 22
from every element of that row III 23 4 0 0
IV 0 16 14 0

1 2 3 4
Subtracting the smallest element of every I
column from all the elements of that column 0 14 9 3
II 9 20 0 22
III 23 0 3 0
IV 0 12 14 0

1 2 3 4
Starting from the first row, mark to zero in
the row containing only one zero and cross out 0 I 0 14 9 3
the zeros in the column in which it lies, 9 20 0 22
II
23 0 3 0
III
0 12 14 0
IV

1 2 3 4
Starting from the first column, mark to zero I
in the column containing only one unmarked or 0 0 14 9 3
II 9 20 0 22
uncrossed zero and cross out the zeros in the row
in which it lies, III 23 0 3 0
IV 0 12 14 0
 Now all the rows and all the columns have assignment.
So the solution is optimum. Th e solution is
Job: I II III IV.
Man: 1 3 2 4
Total cost of assignment = 12 + 9 + 25 + 14 = 60

Eg. Solve the following assignment problem.

Man
1 2 3 4

I 12 10 8 9
Job II 8 9 11 7
III 11 14 12 10
9 9 8 9
IV

Answer.

1 2 3 4

Subtracting the smallest element of each row I

from every element of that row. 4 2 0 1
II 1 2 4 0
III 1 4 2 0
IV 1 1 0 1
.

1 2 3 4

I
Subtracting the smallest element of each column 3 1 0 1
from every element of that column. II 0 1 4 0
III 0 3 2 0
IV 0 0 0 1

1 2 3 4

Starting from the first row, mark to zero in 0 3 1 0 1

I
the row containing only one zero and cross out 0 1 4 0
the zeros in the column in which it lies, II
0 3 2 0
III
0 0 0 1
IV
 1 2 3 4

Starting from the first column, mark to zero I

0 3 1 0 1
in the column containing only one unmarked or II 0 1 4 0
uncrossed zero and cross out the zeros in the row
III 0 3 2 0
in which it lies,
IV 0 0 0 1

1 2 3 4
Again starting row wise, assignment is done I
already in the first row. Consider the second row. 0 3 1 0 1
II 0 1 4 0
There are two zeros. Select any one zero in that
row, say first one and complete the assignment. III 0 3 2 0
IV 0 0 0 1

1 2 3 4
We can have an alternative solution if we had I
selected last zero in the second row. 0 3 1 0 1
II 0 1 4 0
III 0 3 2 0
IV 0 0 0 1

The two solutions are

(a) I to 3, II to 1, III to 4, IV to 2. Total cost = 8 + 8 + 10 + 9 = 35
(b) I to 3, II to 4, III to 1, IV to 2. Total cost = 8 + 7 + 11 + 9 = 35
Eg. Solve the following assignment problem showing the cost for assigning workers to jobs.
Job
X Y Z

A 17 25 31
Workers B 10 25 16
C 12 14 11

Answer.

X Y Z

Subtracting the smallest element of every row A 0 8 14

from all the elements of that row B 0 15 6
C 1 3 0
 Subtracting the smallest element of every X Y Z
column from all the elements of that column
A 0 5 14
B 0 12 6
C 1 0 0

X Y Z

A 0 5 1
Mark to zero in every row, starting from B 0 12 6
the first row and then from each column. C 1 0 0

X Y Z
Now all the rows and columns do not have assignment.
So mark in the second row as it has no assignment. A 0 5 14
Then mark in the first column as it has zeros in the B 0 12 6
C
ticked row. Then mark in the first row as it has 1 0 0
assigned zero of ticked column. Draw lines in the
unticked rows and ticked columns.
The smallest element not covered by the lines is 5
(i) Subtract 5 from all elements not covered by the lines
(ii) Add 5 to the elements at the intersection of two lines. Then make assignment.

X Y Z
Now every row and column has assignment. the
solution is optimal. The solution is 0 0 9
A
A to Y, B to X, C to Z
B 0 7 1
Total cost = 25 + 10 + 11 = 46
C
6 0 0

Maximization in assignment problems

The objective of some assignment problem is to maximize the effectiveness like maximizing
profit. Such problems can be converted into minimization problems. For this subtract each
element of the matrix from the highest element. Then minimization of the resulting matrix
gives the solution.
 Eg. Given below is the profit for different jobs done through different machines. Find the
assignment programme which maximizes the total profit.

Machines
A B C D

I 51 53 54 50
Job II 47 50 48 50
III 49 50 60 61
63 64 60 61
IV

Answer.
.

A B C D
Since the problem is a maximization
problem, convert it into a minimization I
13 11 10 14
problem. The highest element is 64. Subtract II 17 14 16 14
all elements from 64.
III 15 14 4 3
IV 1 0 4 3
.

A B C D

I
3 1 0 4
Subtracting the smallest element of each row
II 3 0 2 0
from every element of that row.
III 12 11 1 0
IV 1 0 4 3
.
.

A B C D

I 2 1 0 4
Subtracting the smallest element of each column
from every element of that column. II 2 0 2 0
III 11 11 1 0
0 0 4 3
IV
.
.
 A B C D

Making zero assignment starting from the first

I
row. Then making assignment starting from the 2 1 0 4
first column. II 2 0 2 0
III 11 11 1 0
IV 0 0 4 3
.
Now all rows and colums have zero assignment. So the solution is optimal.
The solution is I to C, II to B, III to D, IV to A. Total profit = 54 + 50 + 61 + 63 = 228.
Unbalanced assignment problems
An assignment problem is sad to be unbalanced, whenever the number of jobs is not equal to
the number of persons. That is, in the cost matrix the number of rows is not equal to the
number of columns. It is not a square matrix. To solve such a problem, we add dummy rows
or dummy columns to the given matrix to make it a square matrix. The cost in the dummy
rows or columns are taken to be zero. Now it is a balanced problem and we can solve it.
Eg. Solve the assignment problem given below.
Machines
A B C D

I 18 24 28 32
Job II 8 13 17 19
III 10 15 19 22

A B C D
Answer.
.
Given problem is unbalanced since the I 18 24 28 32
number of rows (3) is less than the number II 8 13 17 19
of columns (4). So introducing a dummy
III 10 15 19 22
row with cost 0. 0 0 0 0
IV

A B C D

.
Subtracting the smallest element of I 0 6 10 14
each row from every element of that II 0 5 9 11
row and subtracting the smallest III 0 5 9 12
element of eachcolumn from every 0 0 0 0
element of that column. IV

.
 A B C D
.
Making zero assignment. I 0 6 10 14
II 0 5 9 11
III 0 5 9 12
0 0 0 0
IV

All the rows and columns do not have assignment. We proceed further.

A B C D

So mark. in the second and third rows

as they have no assignment. Then mark I 0 6 10 14
in the first column as it has zeros in II 0 5 9 11
the ticked row. Then mark in the first III 0 5 9 12
row as it has assigned zero of ticked IV 0 0 0 0
column. Draw lines in the unticked rows
and ticked columns.

A B C D

[Link] element not covered by the

I 0 1 5 9
lines is 5. Subtract 5 from all elements not
covered by the lines. Add 5 to the II 0 0 4 6
elements at the intersection of two lines. III 0 0 4 7
Then make assignment. 5 0 0 0
IV

A B C D
Again. the assignment is not complete. We
proceed further. Making marks in row I 0 1 5 9
1, 2 and 3 and columns 1, 2. Then draw II 0 0 4 6
lines in unticked rows and ticked
III 0 0 4 7
columns.
IV 5 0 0 0

A B C D

.
The smallest element not covered by the I
II 0 1 1 5
lines is 4. Subtract 4 from all elements not II 0 0 0 2
III
covered by the lines. Add 4 to the 0 0 0 3
III
IV
elements at the intersection of two lines. 9 9 4 0 0
Then make assignment. IV
One solution is I to A, II to B, III to C, A B C D
IV to D.. Another solution is I to A, II to
C, III to B, IV to D. I
II 0 1 1 5
II
III 0 0 0 2
III 0 0 0 3
IV
9 9 4 0 0
IV