



Solution 


Share with Your Friends :

Solve Assignment Problem (Using Hungarian Method)

1. A computer centre has 3expert programmers. The centre wants 3 application programmes to be developed. The head of thecomputer centre, after studying carefully the programmes to be developed, estimates the computer time in minutes required by the experts for the application programmes as follows.


Programmers 


A 
B 
C 
Programmes 
1 
6 
3 
5 
2 
5 
9 
2 
3 
5 
7 
8 
Try this problem
2. A department has five employess with five jobs to be permormed. The time (in hours) each men will take to perform ech job is given in the effectiveness matrix.


Employees 


I 
II 
III 
IV 
V 
Jobs 
A 
10 
5 
13 
15 
16 
B 
3 
9 
18 
13 
6 
C 
10 
7 
2 
2 
2 
D 
7 
11 
9 
7 
12 
E 
7 
9 
10 
4 
12 
How should the jobs be allocated, one per employee, so as to minimize the total manhours?
Try this problem
Unbalanced Assignment Problem.
3. In the modification of a plant layout of a factory four new machines M1, M2, M3 and M4 are to be installed in a machine shop. There are five vacant places A, B, C, D and E available. Because of limited space, machine M2 cannot be placed at C and M3 cannot be placed at A. The cost of locating a machine at a place (in hundred rupess) is as follows.


Location 


A 
B 
C 
D 
E 
Machine 
M1 
9 
11 
15 
10 
11 
M2 
12 
9 
 
10 
9 
M3 
 
11 
14 
11 
7 
M4 
14 
8 
12 
7 
8 
Find the optimal assignment schedule.
Try this problem
4. An airline company has drawn up a new flight schedule involving five flights. To assist in allocating five pilots to the flights, it has asked them to state their preference scores by giving each flight a number out of 10. The higher the number, the greater is the preference. Certain of these flights are unsuitable to some pilots owing to domestic reasons. These have been marked with a .


Flight Number 


I 
II 
III 
IV 
V 
Pilot 
A 
8 
2 
 
5 
4 
B 
10 
9 
2 
8 
4 
C 
5 
4 
9 
6 
 
D 
3 
6 
2 
8 
7 
E 
5 
6 
10 
4 
3 
What should be the allocation of the pilots to flights in order to meet as many preferences as possible?
Try this problem

Solve Assignment Problem (Using Hungarian Method)

Find Solution of Assignment Problem
Here given problem is balanced... The number of row = 5 The number of column = 5  J_{1}  J_{2}  J_{3}  J_{4}  J_{5}   W_{1}  10  5  13  15  16   W_{2}  3  9  18  13  6   W_{3}  10  7  2  2  2   W_{4}  7  11  9  7  12   W_{5}  7  9  10  4  12          Here given problem is balanced... Find out the each row minimum element and subtract it from that row  J_{1}  J_{2}  J_{3}  J_{4}  J_{5}   W_{1}  5  0  8  10  11  (5)  W_{2}  0  6  15  10  3  (3)  W_{3}  8  5  0  0  0  (2)  W_{4}  0  4  2  0  5  (7)  W_{5}  3  5  6  0  8  (4)         Find out the each column minimum element and subtract it from that column...  J_{1}  J_{2}  J_{3}  J_{4}  J_{5}   W_{1}  5  0  8  10  11   W_{2}  0  6  15  10  3   W_{3}  8  5  0  0  0   W_{4}  0  4  2  0  5   W_{5}  3  5  6  0  8    (0)  (0)  (0)  (0)  (0)   Rowwise & columnwise assignment  final assignment... Assigned rows and columns No of assiment = 4, Rows = 5 Which are not equal Tick mark not allocated rows and allocated columns  J_{1}  J_{2}  J_{3}  J_{4}  J_{5}   W_{1}  5
 [0]  8  10
 11   W_{2}  [0]  6  15  10  3  ✓  W_{3}  8
 5  [0]     W_{4}   4  2  [0]  5  ✓  W_{5}  3  5  6   8  ✓   ✓    ✓    Minimum element :2 Now substract 2 from each uncovedred numbers and add it to numbers at the intersection of any lines  J_{1}  J_{2}  J_{3}  J_{4}  J_{5}   W_{1}  7  0  8  12  11   W_{2}  0  4  13  10  1   W_{3}  10  5  0  2  0   W_{4}  0  2  0  0  3   W_{5}  3  3  4  0  6          Rowwise & columnwise assignment  final assignment... Assigned rows and columns No of assiment = 5, Rows = 5 Optimal assignments are  J_{1}  J_{2}  J_{3}  J_{4}  J_{5}   W_{1}  7  [0]  8  12  11   W_{2}  [0]  4  13  10  1   W_{3}  10  5   2  [0]   W_{4}   2  [0]   3   W_{5}  3  3  4  [0]  6          Optimal solution is Work  Job  Cost  W_{1}  J_{2}  5  W_{2}  J_{1}  3  W_{3}  J_{5}  2  W_{4}  J_{3}  9  W_{5}  J_{4}  4   Total  23 




