Allocation (assignment) problems

Welcome to Allocation Problems!

Ever wondered how a delivery company decides which driver should take which route to save the most fuel? Or how a sports coach decides which player should play in which position to get the best result? This is exactly what allocation (assignment) problems are all about!

In this chapter, part of Decision Mathematics 2, you will learn how to pair up "workers" and "jobs" in the most efficient way possible. While it might look like a lot of numbers at first, it is actually a very logical, step-by-step puzzle. Don't worry if it seems a bit mechanical; once you get the rhythm of the Hungarian Algorithm, you'll be an efficiency expert in no time!

1. Understanding the Goal

An allocation problem involves a set of tasks and an equal number of people (or machines) to do them. Each person has a different "cost" associated with each task (this could be time, money, or distance).

The Objective: We want to assign exactly one person to one task so that the total cost is minimized.

We represent these costs in a cost matrix. For example, if we have 3 workers (A, B, C) and 3 jobs (1, 2, 3), the matrix shows how much it "costs" for worker A to do job 1, and so on.

Did you know? This method is called the Hungarian Algorithm because it was developed by two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry!

Key Takeaway: Allocation is about finding the "best fit" to keep total costs as low as possible.

2. The Cost Matrix Reduction

Before we can solve the problem, we need to "reduce" the matrix. This simplifies the numbers without changing which assignment is the best. Important: In the Edexcel syllabus, you must reduce rows first.

Step A: Row Reduction

1. Look at each row individually.
2. Find the smallest number in that row.
3. Subtract that smallest number from every number in that same row.
Result: Every row will now have at least one zero.

Step B: Column Reduction

1. Look at the new matrix you just made.
2. Look at each column individually.
3. Find the smallest number in that column.
4. Subtract it from every number in that column.
Result: Every row AND every column should now have at least one zero.

Quick Tip: If a column already has a zero after row reduction, the column reduction won't change it (because you are subtracting 0)!

Key Takeaway: Reduction creates "opportunity costs." The zeros represent the best possible options for each worker or job.

3. The Hungarian Algorithm

Once you have reduced the matrix, you need to see if you can make a perfect assignment using only the zeros. If you can't, you need to adjust the matrix.

The "Line Cover" Test

Draw the minimum number of horizontal and vertical lines needed to cover all the zeros in the matrix.

• If the number of lines equals the size of the matrix (\( n \)), an optimal assignment can be made.
• If the number of lines is less than \( n \), you must improve the matrix.

Improving the Matrix (The "Smallest Uncovered" Rule)

If you didn't have enough lines, follow these steps:
1. Find the smallest value that is not covered by any line. Let's call this value \( e \).
2. Subtract \( e \) from every element that is not covered by any line.
3. Add \( e \) to every element that is at an intersection of two lines.
4. Leave elements covered by only one line exactly as they are.
5. Repeat the "Line Cover" test on this new matrix.

Analogy: Imagine the lines are "full" paths. By subtracting \( e \) from uncovered spots, you are making new "free" paths (zeros). By adding \( e \) to intersections, you are "paying" for using two paths at once.

Key Takeaway: We keep adjusting until the number of lines needed to cover the zeros equals the number of rows/columns.

4. Making the Final Assignment

When the number of lines equals \( n \), you can pick your zeros!

Step-by-step matching:
1. Look for a row or column with only one zero. Circle it and cross out any other zeros in that row or column.
2. Repeat until every worker is assigned to exactly one job.
3. Use the original cost matrix to calculate the total minimum cost by adding up the costs of your chosen pairings.

Common Mistake: Students often calculate the total cost using the reduced matrix. Always go back to the original numbers from the start of the question!

5. Dealing with Special Cases

Real-life isn't always a perfect square. Here is how to handle "messy" data:

Dummy Locations (Unequal Rows and Columns)

The Hungarian Algorithm only works on square matrices (e.g., 4 workers for 4 jobs).
• If you have 4 workers but only 3 jobs, add a "Dummy Job" column.
• Give the Dummy Job a cost of 0 for every worker.
• This represents a worker remaining idle.

Incomplete Data (The "Impossible" Task)

Sometimes a worker is physically unable to do a specific job. In your matrix, replace this "impossible" link with a very high cost, often represented by the letter \( M \).
• Because \( M \) is so huge, the algorithm will never pick it as a minimum cost option.

Key Takeaway: Use dummies to make the matrix square and \( M \) to block specific assignments.

6. Maximizing Profit

What if the numbers in the matrix aren't "costs" but "profits"? We want the highest total, not the lowest.

The Trick: We must turn a maximum problem into a minimum problem.
1. Find the largest value in the entire original matrix.
2. Subtract every value in the matrix from this largest value.
3. Now, use the Hungarian Algorithm as normal on this new matrix.

Encouraging Phrase: It feels backwards, doesn't it? But by subtracting everything from the max value, the "best" profit becomes the "0" cost! Trust the process.

Key Takeaway: To maximize, "flip" the matrix by subtracting all values from the maximum value first.

Quick Review Checklist

1. Reduce Rows first: Subtract the smallest in each row.
2. Reduce Columns: Subtract the smallest in each column.
3. Cover Zeros: Use the minimum lines possible.
4. Lines < \( n \)? Subtract smallest uncovered value from all uncovered; add to intersections.
5. Lines = \( n \)? Assign workers to zeros.
6. Final Cost: Always use the Original Matrix values for the final sum.

Don't worry if this seems tricky at first—practice two or three full problems, and the pattern will become second nature!