We use cookies to improve your experience on our site and to show you relevant advertising. By browsing this website, you agree to our use of cookies. Learn more   

AtoZmath.com
Support us
(New) All problem can be solved using search box
I want to sell my website www.AtoZmath.com with complete code
Home What's new College Algebra Games Feedback About us
Algebra Matrix & Vector Numerical Methods Statistical Methods Operation Research Word Problems Calculus Geometry Pre-Algebra


Home > Operation Research calculators > Assignment Problem example (Using Hungarian method)
1. Assignment problem using Hungarian method example ( Enter your problem )
( Enter your problem )
  1. Introduction
  2. Algorithm & Example-1
  3. Example-2
  4. Unbalanced Assignment Problem
  5. Maximization case in Assignment Problem
  6. Multiple optimal solutions in Assignment Problem
  7. Restrictions on Assignment Problem
  8. Restrictions and Unbalanced Assignment Problem
 		Other related methods
  1. Assignment problem using Hungarian method
  2. Travelling salesman problem using Hungarian method
  3. Travelling salesman branch and bound (penalty) method
  4. Travelling salesman branch and bound method
  5. Travelling salesman nearest neighbor method
  6. Travelling salesman diagonal completion method
  7. Crew assignment problem
7. Restrictions on Assignment Problem
(Previous example)		2. Travelling salesman problem using Hungarian method
(Next method)

8. Restrictions and Unbalanced Assignment Problem


Find Solution of Assignment problem using Hungarian method (MIN case)
Work\JobABCDE
M1911151011
M2129-109
M3-1114117
M41481278


Solution:
The number of rows = 4 and columns = 5
   `A`  `B`  `C`  `D`  `E`    
 `M_1` 911151011
 `M_2` 129M109
 `M_3` M1114117
 `M_4` 1481278
   


Here given problem is unbalanced and add 1 new row to convert it into a balance.
   `A`  `B`  `C`  `D`  `E`    
 `M_1` 911151011
 `M_2` 129M109
 `M_3` M1114117
 `M_4` 1481278
 `W_5` 00000
   



Step-1: Find out the each row minimum element and subtract it from that row
   `A`  `B`  `C`  `D`  `E`    
 `M_1`  0 `0=9-9` 2 `2=11-9` 6 `6=15-9` 1 `1=10-9` 2 `2=11-9` (-9) Minimum element of `1^(st)` row
 `M_2`  3 `3=12-9` 0 `0=9-9` M M 1 `1=10-9` 0 `0=9-9` (-9) Minimum element of `2^(nd)` row
 `M_3`  M M 4 `4=11-7` 7 `7=14-7` 4 `4=11-7` 0 `0=7-7` (-7) Minimum element of `3^(rd)` row
 `M_4`  7 `7=14-7` 1 `1=8-7` 5 `5=12-7` 0 `0=7-7` 1 `1=8-7` (-7) Minimum element of `4^(th)` row
 `W_5`  0 `0=0-0` 0 `0=0-0` 0 `0=0-0` 0 `0=0-0` 0 `0=0-0` (-0) Minimum element of `5^(th)` row
   


Step-2: Find out the each column minimum element and subtract it from that column.
   `A`  `B`  `C`  `D`  `E`    
 `M_1`  0 `0=0-0` 2 `2=2-0` 6 `6=6-0` 1 `1=1-0` 2 `2=2-0`
 `M_2`  3 `3=3-0` 0 `0=0-0` M M 1 `1=1-0` 0 `0=0-0`
 `M_3`  M M 4 `4=4-0` 7 `7=7-0` 4 `4=4-0` 0 `0=0-0`
 `M_4`  7 `7=7-0` 1 `1=1-0` 5 `5=5-0` 0 `0=0-0` 1 `1=1-0`
 `W_5`  0 `0=0-0` 0 `0=0-0` 0 `0=0-0` 0 `0=0-0` 0 `0=0-0`
    (-0) Minimum element of `1^(st)` column (-0) Minimum element of `2^(nd)` column (-0) Minimum element of `3^(rd)` column (-0) Minimum element of `4^(th)` column (-0) Minimum element of `5^(th)` column


Step-3: Make assignment in the opporunity cost table

a. Identify rows with exactly one unmarked 0. Make an assignmment to this single 0 by make a square ( [0] ) around it and cross off all other 0 in the same column.

b. Identify columns with exactly one unmarked 0. Make an assignmment to this single 0 by make a square ( [0] ) around it and cross off all other 0 in the same rows.

c. If a row and/or column has two or more unmarked 0 and one cannot be chosen by inspection, then choose the cell arbitarily.

d. Continue this process until all 0 in rows/columns are either assigned or cross off( ).

Step-3: Make assignment in the opporunity cost table
(1) Rowwise cell `(M_1,A)` is assigned, so columnwise cell `(W_5,A)` crossed off.

(2) Rowwise cell `(M_3,E)` is assigned, so columnwise cell `(M_2,E)`,`(W_5,E)` crossed off.

(3) Rowwise cell `(M_4,D)` is assigned, so columnwise cell `(W_5,D)` crossed off.

(4) Columnwise cell `(W_5,C)` is assigned, so rowwise cell `(W_5,B)` crossed off.

(5) Rowwise cell `(M_2,B)` is assigned


Rowwise & columnwise assignment shown in table
   `A`  `B`  `C`  `D`  `E`    
 `M_1`  [0] (1) Rowwise cell `(M_1,A)` is assigned
so columnwise cell `(W_5,A)` crossed off.		2612
 `M_2` 3 [0] (5) Rowwise cell `(M_2,B)` is assignedM1 0 Columnwise `(M_2,E)` crossed off because
(2) Rowwise cell `(M_3,E)` is assigned
 `M_3` M474 [0] (2) Rowwise cell `(M_3,E)` is assigned
so columnwise cell `(M_2,E)`,`(W_5,E)` crossed off.
 `M_4` 715 [0] (3) Rowwise cell `(M_4,D)` is assigned
so columnwise cell `(W_5,D)` crossed off.		1
 `W_5`  0 Columnwise `(W_5,A)` crossed off because
(1) Rowwise cell `(M_1,A)` is assigned		 0 Rowwise `(W_5,B)` crossed off because
(4) Columnwise cell `(W_5,C)` is assigned		 [0] (4) Columnwise cell `(W_5,C)` is assigned
so rowwise cell `(W_5,B)` crossed off.		 0 Columnwise `(W_5,D)` crossed off because
(3) Rowwise cell `(M_4,D)` is assigned		 0 Columnwise `(W_5,E)` crossed off because
(2) Rowwise cell `(M_3,E)` is assigned
   


Step-4: Number of assignments = 5, number of rows = 5
Which is equal, so solution is optimal

Optimal assignments are
   `A`  `B`  `C`  `D`  `E`    
 `M_1`  [0] Original cost 9 2 Original cost 11 6 Original cost 15 1 Original cost 10 2 Original cost 11
 `M_2`  3 Original cost 12 [0] Original cost 9 M Original cost M 1 Original cost 10 0 Original cost 9
 `M_3`  M Original cost M 4 Original cost 11 7 Original cost 14 4 Original cost 11 [0] Original cost 7
 `M_4`  7 Original cost 14 1 Original cost 8 5 Original cost 12 [0] Original cost 7 1 Original cost 8
 `W_5`  0 Original cost 0 0 Original cost 0 [0] Original cost 0 0 Original cost 0 0 Original cost 0
   


Optimal solution is
WorkJobCost
`M_1``A`9
`M_2``B`9
`M_3``E`7
`M_4``D`7
`W_5``C`0
Total32


This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then Submit Here


7. Restrictions on Assignment Problem
(Previous example)		2. Travelling salesman problem using Hungarian method
(Next method)


Share this solution or page with your friends.


Home What's new College Algebra Games Feedback About us
 
Copyright © 2024. All rights reserved. Terms, Privacy
 
 

.