Multiple optimal solutions in an assignment problem.(Apr 2002) (Apr 2005)
An Assignment problem can have more than one optimal solution, which is called multiple optimal solutions. The meaning of multiple optimal solutions is – The total cost or total profit will remain same for different sets or combinations of allocations. It means we have the flexibility of assigning different allocations while still maintaining Minimum (Optimal) cost or Maximum (Optimal) profit.
We can detect multiple optimal solutions when there are multiple zeroes in any columns or rows in the final (Optimal) table in the Assignment problem.