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
1. Introduction
(Previous example)		3. Example-2
(Next example)

2. Algorithm & Example-1


Algorithm
Hungarian Method Steps (Rule)
Step-1: If number of rows is not equal to number of columns, then add dummy rows or columns with cost 0, to make it a square matrix.
Step-2: a. Identify the minimum element in each row and subtract it from each element of that row.

b. Identify the minimum element in each column and subtract it from every element of that 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-4: (a) If the number of assigned cells = the number of rows, then an optimal assignment is found and In case you have chosen a 0 cell arbitrarily, then there may be an alternate optimal solution exists.

(b) If optimal solution is not optimal, then goto Step-5.
Step-5: Draw a set of horizontal and vertical lines to cover all the 0

a. Tick(✓) mark all the rows in which no assigned 0.

b. Examine Tick(✓) marked rows, If any 0 cell occurs in that row, then tick(✓) mark that column.

c. Examine Tick(✓) marked columns, If any assigned 0 exists in that columns, then tick(✓) mark that row.

d. Repeat this process until no more rows or columns can be marked.

e. Draw a straight line for each unmarked rows and marked columns.

f. If the number of lines is equal to the number of rows then the current solution is the optimal, otherwise goto step-6
Step-6: Develop the new revised opportunity cost table

a. Select the minimum element, say k, from the cells not covered by any line,

b. Subtract k from each element not covered by a line.

c. Add k to each intersection element of two lines.
Step-7: Repeat steps 3 to 6 until an optimal solution is arrived.
Example-1
Find Solution of Assignment problem using Hungarian method (MIN case)
Work\JobIIIIIIIVV
A105131516
B3918136
C107222
D7119712
E7910412


Solution:
The number of rows = 5 and columns = 5
   `I`  `II`  `III`  `IV`  `V`    
 `A` 105131516
 `B` 3918136
 `C` 107222
 `D` 7119712
 `E` 7910412
   


Here given problem is balanced.

Step-1: Find out the each row minimum element and subtract it from that row
   `I`  `II`  `III`  `IV`  `V`    
 `A`  5 `5=10-5` 0 `0=5-5` 8 `8=13-5` 10 `10=15-5` 11 `11=16-5` (-5) Minimum element of `1^(st)` row
 `B`  0 `0=3-3` 6 `6=9-3` 15 `15=18-3` 10 `10=13-3` 3 `3=6-3` (-3) Minimum element of `2^(nd)` row
 `C`  8 `8=10-2` 5 `5=7-2` 0 `0=2-2` 0 `0=2-2` 0 `0=2-2` (-2) Minimum element of `3^(rd)` row
 `D`  0 `0=7-7` 4 `4=11-7` 2 `2=9-7` 0 `0=7-7` 5 `5=12-7` (-7) Minimum element of `4^(th)` row
 `E`  3 `3=7-4` 5 `5=9-4` 6 `6=10-4` 0 `0=4-4` 8 `8=12-4` (-4) Minimum element of `5^(th)` row
   


Step-2: Find out the each column minimum element and subtract it from that column.
   `I`  `II`  `III`  `IV`  `V`    
 `A`  5 `5=5-0` 0 `0=0-0` 8 `8=8-0` 10 `10=10-0` 11 `11=11-0`
 `B`  0 `0=0-0` 6 `6=6-0` 15 `15=15-0` 10 `10=10-0` 3 `3=3-0`
 `C`  8 `8=8-0` 5 `5=5-0` 0 `0=0-0` 0 `0=0-0` 0 `0=0-0`
 `D`  0 `0=0-0` 4 `4=4-0` 2 `2=2-0` 0 `0=0-0` 5 `5=5-0`
 `E`  3 `3=3-0` 5 `5=5-0` 6 `6=6-0` 0 `0=0-0` 8 `8=8-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 `(A,II)` is assigned

(2) Rowwise cell `(B,I)` is assigned, so columnwise cell `(D,I)` crossed off.

(3) Rowwise cell `(D,IV)` is assigned, so columnwise cell `(C,IV)`,`(E,IV)` crossed off.

(4) Columnwise cell `(C,III)` is assigned, so rowwise cell `(C,V)` crossed off.


Rowwise & columnwise assignment shown in table
   `I`  `II`  `III`  `IV`  `V`    
 `A` 5 [0] (1) Rowwise cell `(A,II)` is assigned81011
 `B`  [0] (2) Rowwise cell `(B,I)` is assigned
so columnwise cell `(D,I)` crossed off.		615103
 `C` 85 [0] (4) Columnwise cell `(C,III)` is assigned
so rowwise cell `(C,V)` crossed off.		 0 Columnwise `(C,IV)` crossed off because
(3) Rowwise cell `(D,IV)` is assigned		 0 Rowwise `(C,V)` crossed off because
(4) Columnwise cell `(C,III)` is assigned
 `D`  0 Columnwise `(D,I)` crossed off because
(2) Rowwise cell `(B,I)` is assigned		42 [0] (3) Rowwise cell `(D,IV)` is assigned
so columnwise cell `(C,IV)`,`(E,IV)` crossed off.		5
 `E` 356 0 Columnwise `(E,IV)` crossed off because
(3) Rowwise cell `(D,IV)` is assigned		8
   


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

Step-5: Draw a set of horizontal and vertical lines to cover all the 0

a. Tick(✓) mark all the rows in which no assigned 0.

b. Examine Tick(✓) marked rows, If any 0 cell occurs in that row, then tick(✓) mark that column.

c. Examine Tick(✓) marked columns, If any assigned 0 exists in that columns, then tick(✓) mark that row.

d. Repeat this process until no more rows or columns can be marked.

e. Draw a straight line for each unmarked rows and marked columns.

f. If the number of lines is equal to the number of rows then the current solution is the optimal, otherwise goto step-6

Step-5: Cover the 0 with minimum number of lines
(1) Mark(✓) row `E` since it has no assignment

(2) Mark(✓) column `IV` since row `E` has 0 in this column

(3) Mark(✓) row `D` since column `IV` has an assignment in this row `D`.

(4) Mark(✓) column `I` since row `D` has 0 in this column

(5) Mark(✓) row `B` since column `I` has an assignment in this row `B`.

(6) Since no other rows or columns can be marked, therefore draw straight lines through the unmarked rows `A,C` and marked columns `I,IV`


Tick mark not allocated rows and allocated columns
   `I`  `II`  `III`  `IV`  `V`    
 `A` 5[0]81011
 `B` [0]615103 ✓(5) (5) Mark(✓) row `B` since column `I` has an assignment in this row `B`.
 `C` 85[0]00
 `D` 042[0]5 ✓(3) (3) Mark(✓) row `D` since column `IV` has an assignment in this row `D`.
 `E` 35608 ✓(1) (1) Mark(✓) row `E` since it has no assignment
    ✓
(4) (4) Mark(✓) column `I` since row `D` has 0 in this column		 ✓
(2) (2) Mark(✓) column `IV` since row `E` has 0 in this column


Step-6: Develop the new revised opportunity cost table

a. Select the minimum element, say k, from the cells not covered by any line,

b. Subtract k from each element not covered by a line.

c. Add k to each intersection element of two lines.

Step-6: Develop the new revised table by selecting the smallest element, among the cells not covered by any line (say k = 2)
Subtract k = 2 from every element in the cell not covered by a line.
Add k = 2 to every elment in the intersection cell of two lines.

   `I`  `II`  `III`  `IV`  `V`    
 `A`  7 `7=5+2`
intersection cell of two lines		 0 cell covered by a line 8 cell covered by a line 12 `12=10+2`
intersection cell of two lines		 11 cell covered by a line
 `B`  0 cell covered by a line 4 `4=6-2`
cell not covered by a line		 13 `13=15-2`
cell not covered by a line		 10 cell covered by a line 1 `1=3-2`
cell not covered by a line
 `C`  10 `10=8+2`
intersection cell of two lines		 5 cell covered by a line 0 cell covered by a line 2 `2=0+2`
intersection cell of two lines		 0 cell covered by a line
 `D`  0 cell covered by a line 2 `2=4-2`
cell not covered by a line		 0 `0=2-2`
cell not covered by a line		 0 cell covered by a line 3 `3=5-2`
cell not covered by a line
 `E`  3 cell covered by a line 3 `3=5-2`
cell not covered by a line		 4 `4=6-2`
cell not covered by a line		 0 cell covered by a line 6 `6=8-2`
cell not covered by a line
   


Repeat steps 3 to 6 until an optimal solution is obtained.

Step-3: Make assignment in the opporunity cost table
(1) Rowwise cell `(A,II)` is assigned

(2) Rowwise cell `(B,I)` is assigned, so columnwise cell `(D,I)` crossed off.

(3) Rowwise cell `(E,IV)` is assigned, so columnwise cell `(D,IV)` crossed off.

(4) Columnwise cell `(C,V)` is assigned, so rowwise cell `(C,III)` crossed off.

(5) Rowwise cell `(D,III)` is assigned


Rowwise & columnwise assignment shown in table
   `I`  `II`  `III`  `IV`  `V`    
 `A` 7 [0] (1) Rowwise cell `(A,II)` is assigned81211
 `B`  [0] (2) Rowwise cell `(B,I)` is assigned
so columnwise cell `(D,I)` crossed off.		413101
 `C` 105 0 Rowwise `(C,III)` crossed off because
(4) Columnwise cell `(C,V)` is assigned		2 [0] (4) Columnwise cell `(C,V)` is assigned
so rowwise cell `(C,III)` crossed off.
 `D`  0 Columnwise `(D,I)` crossed off because
(2) Rowwise cell `(B,I)` is assigned		2 [0] (5) Rowwise cell `(D,III)` is assigned 0 Columnwise `(D,IV)` crossed off because
(3) Rowwise cell `(E,IV)` is assigned		3
 `E` 334 [0] (3) Rowwise cell `(E,IV)` is assigned
so columnwise cell `(D,IV)` crossed off.		6
   


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

Optimal assignments are
   `I`  `II`  `III`  `IV`  `V`    
 `A`  7 Original cost 10 [0] Original cost 5 8 Original cost 13 12 Original cost 15 11 Original cost 16
 `B`  [0] Original cost 3 4 Original cost 9 13 Original cost 18 10 Original cost 13 1 Original cost 6
 `C`  10 Original cost 10 5 Original cost 7 0 Original cost 2 2 Original cost 2 [0] Original cost 2
 `D`  0 Original cost 7 2 Original cost 11 [0] Original cost 9 0 Original cost 7 3 Original cost 12
 `E`  3 Original cost 7 3 Original cost 9 4 Original cost 10 [0] Original cost 4 6 Original cost 12
   


Optimal solution is
WorkJobCost
`A``II`5
`B``I`3
`C``V`2
`D``III`9
`E``IV`4
Total23


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


1. Introduction
(Previous example)		3. Example-2
(Next example)


Share this solution or page with your friends.


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

.