Introduction to Allocation (Assignment) Problems
Welcome to Decision Mathematics 2! We’re kicking things off with a topic that is actually quite useful in real life: Allocation Problems. Imagine you are a manager at a busy restaurant. You have four chefs and four specific tasks (like prep, grilling, plating, and cleaning). Some chefs are faster at grilling, while others are better at prep. How do you assign one person to exactly one task so that the total time taken is as low as possible?
That is the heart of an allocation problem. We want to find the "least cost" way to match a group of people (or machines) to an equal number of tasks. Don't worry if this seems tricky at first—we use a very reliable "recipe" called the Hungarian Algorithm to solve it every single time!
Quick Review: Before we start, remember that in this chapter, we usually work with square matrices (like 3x3 or 4x4) because we assume the number of people equals the number of tasks.
1. The Cost Matrix
The first thing you’ll see is a cost matrix. This is just a table where the rows represent people and the columns represent jobs. Each number inside is the "cost" (which could be time, money, or distance) of that person doing that job.
Example: If the value in Row A, Column 2 is 15, it means Person A takes 15 minutes to do Job 2.
2. The Hungarian Algorithm: Step-by-Step
The Hungarian Algorithm is a systematic way to find the best assignment. Think of it as "reducing" the costs until we find the zeros—the zeros represent the best possible matches!
Step 1: Row Reduction
In every row, find the smallest number. Subtract that number from every element in that same row. Important: Always do rows first!
Step 2: Column Reduction
Look at your new matrix. In every column, find the smallest number. Subtract it from every element in that column. (If a column already has a zero, it stays the same).
Step 3: Covering Zeros
Try to cover all the zeros in the matrix using the minimum possible number of horizontal and vertical lines.
- If the number of lines equals the size of the matrix (e.g., 3 lines for a 3x3), you’ve found the optimal solution! Jump to Step 5.
- If you need fewer lines than the size of the matrix, move to Step 4.
Step 4: Augmenting the Matrix
If you didn't have enough lines, we need to "create" more zeros:
1. Find the smallest uncovered number (let's call it \(e\)).
2. Subtract \(e\) from every uncovered number.
3. Add \(e\) to any number covered by two lines (the intersections).
4. Numbers covered by only one line stay the same.
5. Now, go back to Step 3 and try covering the zeros again.
Step 5: Final Allocation
Look for the zeros. Assign people to jobs where a zero exists, making sure each person gets only one job and each job is only done once.
Memory Aid: Use the mnemonic "Really Cool Llamas Act" to remember the order: Row reduction, Column reduction, Lines, Augment!
3. Special Cases: Dummies and Impossible Tasks
Sometimes the real world isn't a perfect square. Here is how we handle it:
Dummy Rows or Columns
What if you have 3 workers but 4 jobs? You can't leave a job empty! We add a dummy worker.
- Create a new row (Row D).
- Give it a cost of 0 for every job.
- Solve the problem as usual. Whoever is assigned to the "Dummy" is actually the job that doesn't get a real person assigned to it!
Incomplete Data (Impossible Tasks)
What if Person B is allergic to fish and cannot do the "Fish Prep" job?
- We give that specific cell a massive cost (often labeled \(M\) or a very high number like 999).
- Because the algorithm looks for the lowest cost, it will avoid that "massive" cost at all costs!
Key Takeaway
Dummies are used to make the matrix square. Massive costs are used to prevent an impossible assignment.
4. Maximizing instead of Minimizing
Usually, we want to minimize cost or time. But what if the numbers in the matrix are profits and we want to maximize them?
The Trick: To turn a maximization problem into a minimization one:
1. Find the largest number in the entire original matrix.
2. Subtract every value in the matrix from this largest number.
3. Now, use the Hungarian Algorithm normally on this new matrix!
Example: If the highest profit is 50 and a certain cell is 40, the new value becomes \(50 - 40 = 10\). After solving, the "lowest cost" in the new matrix corresponds to the "highest profit" in the old one.
Common Mistakes to Avoid
- Forgetting Column Reduction: Many students do row reduction and then go straight to drawing lines. Always check those columns!
- Drawing too many lines: Always look for the absolute minimum number of lines to cover zeros. If you can cover them with 2 lines, don't use 3.
- Intersections: When augmenting (Step 4), remember to add the value to the intersections. It’s easy to accidentally subtract there too.
Quick Review Box
- Goal: Match \(n\) workers to \(n\) tasks at minimum cost.
- Algorithm: Hungarian Algorithm (Rows -> Columns -> Lines -> Augment).
- Non-square: Add a "Dummy" row/column with zeros.
- Maximization: Subtract all values from the largest value first.
Did you know? The Hungarian Algorithm is named after two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry, who laid the groundwork for it back in 1931! It’s still one of the most efficient ways to solve these problems today.