Assignment problem using Hungarian method Restrictions and Unbalanced Assignment Problem

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

Support us

Home > Operation Research calculators > Assignment Problem example (Using Hungarian method)

1. Assignment problem using Hungarian method example ( Enter your problem )

( Enter your problem )

Introduction
Algorithm & Example-1
Example-2
Unbalanced Assignment Problem
Maximization case in Assignment Problem
Multiple optimal solutions in Assignment Problem
Restrictions on Assignment Problem
Restrictions and Unbalanced Assignment Problem

Other related methods

Assignment problem using Hungarian method
Travelling salesman problem using Hungarian method
Travelling salesman branch and bound (penalty) method
Travelling salesman branch and bound method
Travelling salesman nearest neighbor method
Travelling salesman diagonal completion method
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\^Job A B C D E
M1 9 11 15 10 11
M2 12 9 - 10 9
M3 - 11 14 11 7
M4 14 8 12 7 8

Solution:
The number of rows = 4 and columns = 5

	`A`	`B`	`C`	`D`	`E`
`M_1`	9	11	15	10	11
`M_2`	12	9	M	10	9
`M_3`	M	11	14	11	7
`M_4`	14	8	12	7	8

Here given problem is unbalanced and add 1 new row to convert it into a balance.

	`A`	`B`	`C`	`D`	`E`
`M_1`	9	11	15	10	11
`M_2`	12	9	M	10	9
`M_3`	M	11	14	11	7
`M_4`	14	8	12	7	8
`W_5`	0	0	0	0	0

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.	2	6	1	2
`M_2`	3	[0] (5) Rowwise cell `(M_2,B)` is assigned	M	1	0 Columnwise `(M_2,E)` crossed off because (2) Rowwise cell `(M_3,E)` is assigned
`M_3`	M	4	7	4	[0] (2) Rowwise cell `(M_3,E)` is assigned so columnwise cell `(M_2,E)`,`(W_5,E)` crossed off.
`M_4`	7	1	5	[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

Work	Job	Cost
`M_1`	`A`	9
`M_2`	`B`	9
`M_3`	`E`	7
`M_4`	`D`	7
`W_5`	`C`	0
	Total	32

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