Assignment Problems | Mathematics Optional Notes for UPSC PDF Download

 Page 1


Edurev123 
7. Assignment Problems 
7.1 Solve the minimum time assignment problem : 
 
(2013 : 15 Marks) 
Solution: 
In assignment problem, the solution does not change if we subtract or add same values 
from a column or row. So, we create zeros by subtracting minimum of each row and 
column from that row or column. 
 
Now, we assign jobs using zero's taking care of choosing only one zero in a row or 
column. 
 
We have only 3 assignments so this is not optimum. 
We draw the minimum lines to cover all zeros. 
Page 2


Edurev123 
7. Assignment Problems 
7.1 Solve the minimum time assignment problem : 
 
(2013 : 15 Marks) 
Solution: 
In assignment problem, the solution does not change if we subtract or add same values 
from a column or row. So, we create zeros by subtracting minimum of each row and 
column from that row or column. 
 
Now, we assign jobs using zero's taking care of choosing only one zero in a row or 
column. 
 
We have only 3 assignments so this is not optimum. 
We draw the minimum lines to cover all zeros. 
 
Minimum of the unmarked entries i.e., 2. 
Subtract this from each unmarked row and add it to marked column. 
 
Now, we again assign the zeros. 
The assignment is optimal as 4 assignment have been made. 
 Min cost =3+9+12+4=28 
(Note: In actual exam you will provided less space and may club some of the steps) 
7.2 Solve the following assignment problem to maximize the sales. 
 
(2015: 10 marks) 
Solution: 
In order to convert it into a minimum problem, we multiply each element by 
So, table becomes : (We use Hungarian method) 
 No. of lines =3;? No. of rows =5 
So, solution is degenerate. 
Now table becomes 
Page 3


Edurev123 
7. Assignment Problems 
7.1 Solve the minimum time assignment problem : 
 
(2013 : 15 Marks) 
Solution: 
In assignment problem, the solution does not change if we subtract or add same values 
from a column or row. So, we create zeros by subtracting minimum of each row and 
column from that row or column. 
 
Now, we assign jobs using zero's taking care of choosing only one zero in a row or 
column. 
 
We have only 3 assignments so this is not optimum. 
We draw the minimum lines to cover all zeros. 
 
Minimum of the unmarked entries i.e., 2. 
Subtract this from each unmarked row and add it to marked column. 
 
Now, we again assign the zeros. 
The assignment is optimal as 4 assignment have been made. 
 Min cost =3+9+12+4=28 
(Note: In actual exam you will provided less space and may club some of the steps) 
7.2 Solve the following assignment problem to maximize the sales. 
 
(2015: 10 marks) 
Solution: 
In order to convert it into a minimum problem, we multiply each element by 
So, table becomes : (We use Hungarian method) 
 No. of lines =3;? No. of rows =5 
So, solution is degenerate. 
Now table becomes 
 
No. of lines =4 
No. of rows =5 
New table becomes 
 
? Optimal arrangement is ?? =IV,?? =II,?? =V,?? =III,?? =1 
 Maximum sales =6+15+11+15+8 
=55 
7.3 In a factory, there are five operators ?? ?? ,?? ?? ,?? ?? ,?? ?? ,?? ?? and five machines 
?? ?? ,?? ?? ,?? ?? ,?? ?? ,?? ?? . The operating costs are given when the ?? ?? operates the ?? ?? 
machine (?? ,?? =?? ,?? ,…?? ) . But there is a restriction that ?? ?? cannot be allowed to 
operate the third machine. ?? ?? and ?? ?? cannot be ailowed to operate the fifth 
machine. The cost matrix is given above. Find the optimal assignment and optimal 
assignment also. 
 
(2018 : 15 Marks) 
Page 4


Edurev123 
7. Assignment Problems 
7.1 Solve the minimum time assignment problem : 
 
(2013 : 15 Marks) 
Solution: 
In assignment problem, the solution does not change if we subtract or add same values 
from a column or row. So, we create zeros by subtracting minimum of each row and 
column from that row or column. 
 
Now, we assign jobs using zero's taking care of choosing only one zero in a row or 
column. 
 
We have only 3 assignments so this is not optimum. 
We draw the minimum lines to cover all zeros. 
 
Minimum of the unmarked entries i.e., 2. 
Subtract this from each unmarked row and add it to marked column. 
 
Now, we again assign the zeros. 
The assignment is optimal as 4 assignment have been made. 
 Min cost =3+9+12+4=28 
(Note: In actual exam you will provided less space and may club some of the steps) 
7.2 Solve the following assignment problem to maximize the sales. 
 
(2015: 10 marks) 
Solution: 
In order to convert it into a minimum problem, we multiply each element by 
So, table becomes : (We use Hungarian method) 
 No. of lines =3;? No. of rows =5 
So, solution is degenerate. 
Now table becomes 
 
No. of lines =4 
No. of rows =5 
New table becomes 
 
? Optimal arrangement is ?? =IV,?? =II,?? =V,?? =III,?? =1 
 Maximum sales =6+15+11+15+8 
=55 
7.3 In a factory, there are five operators ?? ?? ,?? ?? ,?? ?? ,?? ?? ,?? ?? and five machines 
?? ?? ,?? ?? ,?? ?? ,?? ?? ,?? ?? . The operating costs are given when the ?? ?? operates the ?? ?? 
machine (?? ,?? =?? ,?? ,…?? ) . But there is a restriction that ?? ?? cannot be allowed to 
operate the third machine. ?? ?? and ?? ?? cannot be ailowed to operate the fifth 
machine. The cost matrix is given above. Find the optimal assignment and optimal 
assignment also. 
 
(2018 : 15 Marks) 
Solution: 
Since, O
3
 cannot operate on M
3
 and O
2
 cannot operate on ?? 5
, we assign a very large 
say ?? to both the corresponding cells. The matrix now becomes 
 
 
Since, by covering all zeroes, 
Number of lines =4<5. 
So, solution is degenerate. 
New matrix by hungarian method is 
Page 5


Edurev123 
7. Assignment Problems 
7.1 Solve the minimum time assignment problem : 
 
(2013 : 15 Marks) 
Solution: 
In assignment problem, the solution does not change if we subtract or add same values 
from a column or row. So, we create zeros by subtracting minimum of each row and 
column from that row or column. 
 
Now, we assign jobs using zero's taking care of choosing only one zero in a row or 
column. 
 
We have only 3 assignments so this is not optimum. 
We draw the minimum lines to cover all zeros. 
 
Minimum of the unmarked entries i.e., 2. 
Subtract this from each unmarked row and add it to marked column. 
 
Now, we again assign the zeros. 
The assignment is optimal as 4 assignment have been made. 
 Min cost =3+9+12+4=28 
(Note: In actual exam you will provided less space and may club some of the steps) 
7.2 Solve the following assignment problem to maximize the sales. 
 
(2015: 10 marks) 
Solution: 
In order to convert it into a minimum problem, we multiply each element by 
So, table becomes : (We use Hungarian method) 
 No. of lines =3;? No. of rows =5 
So, solution is degenerate. 
Now table becomes 
 
No. of lines =4 
No. of rows =5 
New table becomes 
 
? Optimal arrangement is ?? =IV,?? =II,?? =V,?? =III,?? =1 
 Maximum sales =6+15+11+15+8 
=55 
7.3 In a factory, there are five operators ?? ?? ,?? ?? ,?? ?? ,?? ?? ,?? ?? and five machines 
?? ?? ,?? ?? ,?? ?? ,?? ?? ,?? ?? . The operating costs are given when the ?? ?? operates the ?? ?? 
machine (?? ,?? =?? ,?? ,…?? ) . But there is a restriction that ?? ?? cannot be allowed to 
operate the third machine. ?? ?? and ?? ?? cannot be ailowed to operate the fifth 
machine. The cost matrix is given above. Find the optimal assignment and optimal 
assignment also. 
 
(2018 : 15 Marks) 
Solution: 
Since, O
3
 cannot operate on M
3
 and O
2
 cannot operate on ?? 5
, we assign a very large 
say ?? to both the corresponding cells. The matrix now becomes 
 
 
Since, by covering all zeroes, 
Number of lines =4<5. 
So, solution is degenerate. 
New matrix by hungarian method is 
 
Again, ????????????????????????????????????????????? Number of lines =4<5 
By following hungarian method, new matrix is 
 
Number of lines =5 
? Optimal assignment is : ?? 1
 at ?? 3
,?? 2
 at ?? 1
,?? 3
 at ?? 4
,?? 4
 at ?? 5
,?? 5
 at ?? 2
 and optimal cost 
is 18+17+17+24+16=92. 
7.4 A department of a company has five employees with five jobs to be performed. 
The time (in hours) that each man takes to perform each job is given in the 
effectiveness matrix. Assign all the jobs to these five employees to minimize the 
total processing time : 
 
(2021: 10 marks) 
Solution: