Allocation (assignment) problems

Understanding Allocation Problems

Allocation problems are a specific type of linear programming problem where tasks have to be assigned to resources in an optimal way.
The goal is to minimise cost or maximise profit while ensuring that every task is assigned to exactly one resource and each resource is assigned exactly one task.
The Hungarian algorithm is a commonly used method to solve allocation problems. It was developed by Harold Kuhn.

The Hungarian algorithm is an efficient method for solving allocation problems.
It operates by setting up a cost matrix where the rows represent tasks and columns represent resources.
It then proceeds through stages of row and column reductions, covering zeros with the minimal number of lines, and altering the matrix, until an optimal solution is found.

Start with forming a cost matrix where tasks are on one axis and resources on the other.
All elements in the matrix need to be non-negative.
If tasks and resources are not the same number, a dummy row or column should be added with zero cost.
Perform row reduction first, subtracting the smallest element in each row from every element in that row.
Then perform column reduction, subtracting the smallest element in each column from every element in that column.
The matrix should now have at least one zero in every row and every column.
Next, cover all zeros using the minimum number of lines. If the number of lines is equal to the number of resources or tasks, an optimal allocation is found.
If not, alter the matrix: subtract smallest uncovered value from all uncovered values, and add it to all element at intersections of lines.
Repeat covering zeros and altering matrix processes until the number of lines drawn is equal to the number of resources or tasks.

In real-world scenarios, allocation problems can involve complex tasks and multiple resources.
Factors such as budget constraints, time limitations, or specific needs of tasks can all be incorporated into the cost matrix.
Furthermore, constraints like availability of resources or perquisites for tasks can be represented by infinite costs in the cost matrix.