Assignment problem using Hungarian method Multiple optimal solutions in 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

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 )

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

5. Maximization case in Assignment Problem
(Previous example)

7. Restrictions on Assignment Problem
(Next example)

6. Multiple optimal solutions in Assignment Problem

Multiple optimal solutions in Assignment Problem
While making an assignment in reducted matrix, it is possible to have two or more ways to assign 0's. In such case there may be an alternate optimal solution exists with same optimal value.

Example
Find Solution of Assignment problem using Hungarian method (MAX case)
_Work\^Job I II III IV
A 42 35 28 21
B 30 25 20 15
C 30 25 20 15
D 24 20 16 12

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

	`I`	`II`	`III`	`IV`
`A`	42	35	28	21
`B`	30	25	20	15
`C`	30	25	20	15
`D`	24	20	16	12

Here the problem is of Maximazition type and convert it into minimization by substracting it from maximum value 42

	`I`	`II`	`III`	`IV`
`A`	0 `0=42-42`	7 `7=42-35`	14 `14=42-28`	21 `21=42-21`
`B`	12 `12=42-30`	17 `17=42-25`	22 `22=42-20`	27 `27=42-15`
`C`	12 `12=42-30`	17 `17=42-25`	22 `22=42-20`	27 `27=42-15`
`D`	18 `18=42-24`	22 `22=42-20`	26 `26=42-16`	30 `30=42-12`

Here given problem is balanced.

Step-1: Find out the each row minimum element and subtract it from that row

	`I`	`II`	`III`	`IV`
`A`	0 `0=0-0`	7 `7=7-0`	14 `14=14-0`	21 `21=21-0`	(-0) Minimum element of `1^(st)` row
`B`	0 `0=12-12`	5 `5=17-12`	10 `10=22-12`	15 `15=27-12`	(-12) Minimum element of `2^(nd)` row
`C`	0 `0=12-12`	5 `5=17-12`	10 `10=22-12`	15 `15=27-12`	(-12) Minimum element of `3^(rd)` row
`D`	0 `0=18-18`	4 `4=22-18`	8 `8=26-18`	12 `12=30-18`	(-18) Minimum element of `4^(th)` row

Step-2: Find out the each column minimum element and subtract it from that column.

	`I`	`II`	`III`	`IV`
`A`	0 `0=0-0`	3 `3=7-4`	6 `6=14-8`	9 `9=21-12`
`B`	0 `0=0-0`	1 `1=5-4`	2 `2=10-8`	3 `3=15-12`
`C`	0 `0=0-0`	1 `1=5-4`	2 `2=10-8`	3 `3=15-12`
`D`	0 `0=0-0`	0 `0=4-4`	0 `0=8-8`	0 `0=12-12`
	(-0) Minimum element of `1^(st)` column	(-4) Minimum element of `2^(nd)` column	(-8) Minimum element of `3^(rd)` column	(-12) Minimum element of `4^(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,I)` is assigned, so columnwise cell `(B,I)`,`(C,I)`,`(D,I)` crossed off.

(2) Columnwise cell `(D,II)` is assigned, so rowwise cell `(D,III)`,`(D,IV)` crossed off.

Rowwise & columnwise assignment shown in table

	`I`	`II`	`III`	`IV`
`A`	[0] (1) Rowwise cell `(A,I)` is assigned so columnwise cell `(B,I)`,`(C,I)`,`(D,I)` crossed off.	3	6	9
`B`	0 Columnwise `(B,I)` crossed off because (1) Rowwise cell `(A,I)` is assigned	1	2	3
`C`	0 Columnwise `(C,I)` crossed off because (1) Rowwise cell `(A,I)` is assigned	1	2	3
`D`	0 Columnwise `(D,I)` crossed off because (1) Rowwise cell `(A,I)` is assigned	[0] (2) Columnwise cell `(D,II)` is assigned so rowwise cell `(D,III)`,`(D,IV)` crossed off.	0 Rowwise `(D,III)` crossed off because (2) Columnwise cell `(D,II)` is assigned	0 Rowwise `(D,IV)` crossed off because (2) Columnwise cell `(D,II)` is assigned

Step-4: Number of assignments = 2, number of rows = 4
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 `B` since it has no assignment

(2) Mark(✓) row `C` since it has no assignment

(3) Mark(✓) column `I` since row `B` has 0 in this column

(4) Mark(✓) row `A` since column `I` has an assignment in this row `A`.

(5) Since no other rows or columns can be marked, therefore draw straight lines through the unmarked rows `D` and marked columns `I`

Tick mark not allocated rows and allocated columns

	`I`	`II`	`III`	`IV`
`A`	[0]	3	6	9	✓(4) (4) Mark(✓) row `A` since column `I` has an assignment in this row `A`.
`B`	0	1	2	3	✓(1) (1) Mark(✓) row `B` since it has no assignment
`C`	0	1	2	3	✓(2) (2) Mark(✓) row `C` since it has no assignment
`D`	0	[0]	0	0
	✓ (3) (3) Mark(✓) column `I` since row `B` 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 = 1)
Subtract k = 1 from every element in the cell not covered by a line.
Add k = 1 to every elment in the intersection cell of two lines.

	`I`	`II`	`III`	`IV`
`A`	0 cell covered by a line	2 `2=3-1` cell not covered by a line	5 `5=6-1` cell not covered by a line	8 `8=9-1` cell not covered by a line
`B`	0 cell covered by a line	0 `0=1-1` cell not covered by a line	1 `1=2-1` cell not covered by a line	2 `2=3-1` cell not covered by a line
`C`	0 cell covered by a line	0 `0=1-1` cell not covered by a line	1 `1=2-1` cell not covered by a line	2 `2=3-1` cell not covered by a line
`D`	1 `1=0+1` intersection cell of two lines	0 cell covered by a line	0 cell covered by a line	0 cell 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,I)` is assigned, so columnwise cell `(B,I)`,`(C,I)` crossed off.

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

(3) Columnwise cell `(D,III)` is assigned, so rowwise cell `(D,IV)` crossed off.

Rowwise & columnwise assignment shown in table

	`I`	`II`	`III`	`IV`
`A`	[0] (1) Rowwise cell `(A,I)` is assigned so columnwise cell `(B,I)`,`(C,I)` crossed off.	2	5	8
`B`	0 Columnwise `(B,I)` crossed off because (1) Rowwise cell `(A,I)` is assigned	[0] (2) Rowwise cell `(B,II)` is assigned so columnwise cell `(C,II)`,`(D,II)` crossed off.	1	2
`C`	0 Columnwise `(C,I)` crossed off because (1) Rowwise cell `(A,I)` is assigned	0 Columnwise `(C,II)` crossed off because (2) Rowwise cell `(B,II)` is assigned	1	2
`D`	1	0 Columnwise `(D,II)` crossed off because (2) Rowwise cell `(B,II)` is assigned	[0] (3) Columnwise cell `(D,III)` is assigned so rowwise cell `(D,IV)` crossed off.	0 Rowwise `(D,IV)` crossed off because (3) Columnwise cell `(D,III)` is assigned

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

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

(2) Mark(✓) column `I` since row `C` has 0 in this column

(3) Mark(✓) column `II` since row `C` has 0 in this column

(4) Mark(✓) row `A` since column `I` has an assignment in this row `A`.

(5) Mark(✓) row `B` since column `II` 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 `D` and marked columns `I,II`

Tick mark not allocated rows and allocated columns

	`I`	`II`	`III`	`IV`
`A`	[0]	2	5	8	✓(4) (4) Mark(✓) row `A` since column `I` has an assignment in this row `A`.
`B`	0	[0]	1	2	✓(5) (5) Mark(✓) row `B` since column `II` has an assignment in this row `B`.
`C`	0	0	1	2	✓(1) (1) Mark(✓) row `C` since it has no assignment
`D`	1	0	[0]	0
	✓ (2) (2) Mark(✓) column `I` since row `C` has 0 in this column	✓ (3) (3) Mark(✓) column `II` since row `C` has 0 in this column

	`I`	`II`	`III`	`IV`
`A`	0 cell covered by a line	2 cell covered by a line	4 `4=5-1` cell not covered by a line	7 `7=8-1` cell not covered by a line
`B`	0 cell covered by a line	0 cell covered by a line	0 `0=1-1` cell not covered by a line	1 `1=2-1` cell not covered by a line
`C`	0 cell covered by a line	0 cell covered by a line	0 `0=1-1` cell not covered by a line	1 `1=2-1` cell not covered by a line
`D`	2 `2=1+1` intersection cell of two lines	1 `1=0+1` intersection cell of two lines	0 cell covered by a line	0 cell 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,I)` is assigned, so columnwise cell `(B,I)`,`(C,I)` crossed off.

(2) Columnwise cell `(D,IV)` is assigned, so rowwise cell `(D,III)` crossed off.

(3) Rowwise cell `(B,II)` is assigned, so columnwise cell `(C,II)` crossed off., so rowwise cell `(B,III)` crossed off.

(4) Rowwise cell `(C,III)` is assigned

Rowwise & columnwise assignment shown in table

	`I`	`II`	`III`	`IV`
`A`	[0] (1) Rowwise cell `(A,I)` is assigned so columnwise cell `(B,I)`,`(C,I)` crossed off.	2	4	7
`B`	0 Columnwise `(B,I)` crossed off because (1) Rowwise cell `(A,I)` is assigned	[0] (3) Rowwise cell `(B,II)` is assigned so columnwise cell `(C,II)` crossed off. so rowwise cell `(B,III)` crossed off.	0 Rowwise `(B,III)` crossed off because (3) Rowwise cell `(B,II)` is assigned, so columnwise cell `(C,II)` crossed off.	1
`C`	0 Columnwise `(C,I)` crossed off because (1) Rowwise cell `(A,I)` is assigned	0 Columnwise `(C,II)` crossed off because (3) Rowwise cell `(B,II)` is assigned	[0] (4) Rowwise cell `(C,III)` is assigned	1
`D`	2	1	0 Rowwise `(D,III)` crossed off because (2) Columnwise cell `(D,IV)` is assigned	[0] (2) Columnwise cell `(D,IV)` is assigned so rowwise cell `(D,III)` crossed off.

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

Optimal assignments are

	`I`	`II`	`III`	`IV`
`A`	[0] Original cost 42	2 Original cost 35	4 Original cost 28	7 Original cost 21
`B`	0 Original cost 30	[0] Original cost 25	0 Original cost 20	1 Original cost 15
`C`	0 Original cost 30	0 Original cost 25	[0] Original cost 20	1 Original cost 15
`D`	2 Original cost 24	1 Original cost 20	0 Original cost 16	[0] Original cost 12

Optimal solution is

Work	Job	Cost
`A`	`I`	42
`B`	`II`	25
`C`	`III`	20
`D`	`IV`	12
	Total	99

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