Lecture 19_Assignment problem :Unbalanced and maximal Assignment Problems

19.1
Unbalanced Assignment Problems
If the number of rows and columns are not equal then such type of problems are called as
unbalanced assignment problems.
Example
A company has 4 machines on which to do 3 jobs. Each job can be assigned to one and only one
machine. The cost of each job on each machine is given in the following table

Machines
Jobs
W X Y Z
A 18 24 28 32
B 8 13 17 19
C 10 15 19 22
Solution
Lecture 19
Assignment problem :
Unbalanced and maximal Assignment Problems
18 24 28 32
8 13 17 19
10 15 19 22
0 0 0 0
Row Reduced matrix
0 6 10 14
0 5 9 11
0 5 9 12
0 0 0 0
I Modified Matrix
N < n i.e. 2 < 4
II Modified Matrix
1
N < n i.e. 3 < 4
III Modified Matrix
N = n
Zero assignment
Multiple assignments exists
Solution -I
Minimum cost = 18 + 13 + 19 = Rs 50
Solution -II
Minimum cost = 18 + 17 + 15 = Rs 50
19.2 Maximal Assignment Problem
Example
A company has 5 jobs to be done. The following matrix shows the return in terms of rupees on
assigning ith ( i = 1, 2, 3, 4, 5 ) machine to the jth job ( j = A, B, C, D, E ). Assign the five jobs to
the five machines so as to maximize the total expected profit.