Multiple Optimal Solutions: Assignment Problem

Sometimes, it is possible to cross out all the zeros in the reduced matrix in two or more ways.

If you can choose a zero cell arbitrarily, then there will be multiple optimal solutions with the same total pay-off for assignments made. In such a case, the management may select that set of optimal assignments, which is more suited to their requirement.

Example: Multiple Optimal Solutions

Consider the following assignment problem: The Spicy Spoon restaurant has four payment counters. There are four persons available for service. The cost of assigning each person to each counter is given in the following table.

Assign one person to one counter to minimize the total cost.

Solution.

After applying steps 1 to 3 of the Hungarian Method, we obtain the following matrix.

Table

Use Horizontal Scrollbar to View Full Table Calculation.

Job
Person	1	2	3	4
A		3	6	9
B		1	2	3
C		1	2	3
D

Now by applying the usual procedure, we get the following matrix.

Table

Job
Person	1	2	3	4
A		2	5	8
B			1	2
C			1	2
D	1

The resulting matrix suggest the alternative optimal solutions as shown in the following tables.

Table

Job
Person	1	2	3	4
A		2	4	7
B				1
C				1
D	2	1

Job
Person	1	2	3	4
A		2	4	7
B				1
C				1
D	2	1

The persons B & C may be assigned either to job 2 or 3.
The two alternative assignments are: