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 assigns players to positions to get the best result? That is exactly what Allocation (or Assignment) Problems are all about! In this chapter of Decision Mathematics 2, we’ll learn how to use a clever method called the Hungarian Algorithm to make these decisions perfectly every time. Don't worry if it seems like a lot of steps at first; once you get the rhythm, it's like following a recipe!

1. What is an Allocation Problem?

An allocation problem involves matching a set of "workers" to an equal set of "tasks" in a way that minimizes the total cost (or maximizes the total profit).

The Core Rule: Each worker must be assigned to exactly one task, and each task must be completed by exactly one worker. This is known as a one-to-one matching.

We represent these problems using a cost matrix, where the numbers inside represent the cost of a specific worker doing a specific task.

Did you know? The Allocation problem is actually a special, simplified version of the Transportation problem you studied in the previous chapter. While transportation deals with many-to-many, allocation is strictly one-to-one!

Key Takeaway:

Allocation problems aim to find the most efficient 1-to-1 pairing between two groups, usually represented in a square matrix.

2. The Hungarian Algorithm (Minimising Cost)

The Hungarian Algorithm is the "gold standard" for finding the least cost allocation. It works by reducing the matrix until the best options are represented by zeros.

Step-by-Step Process:

Step 1: Row Reduction
Look at each row. Find the smallest number in that row and subtract it from every number in that same row. Your goal here is to make sure every row has at least one zero.

Step 2: Column Reduction
Now look at the columns of your new matrix. Find the smallest number in each column and subtract it from every number in that column. Now, every row and every column should have at least one zero.

Step 3: Cover the Zeros
Try to cover all the zeros in the matrix using the minimum number of horizontal and vertical lines.
Memory Aid: Think of this like a game of Minesweeper—you want to use the fewest "strips" of tape possible to hide every single zero.

Step 4: Is it Optimal?
Count your lines.
- If the number of lines = the size of the matrix (e.g., 3 lines for a 3x3 matrix), you’ve found the best solution! Jump to Step 6.
- If the number of lines is less than the size of the matrix, you need to "augment" the matrix (Step 5).

Step 5: Augmenting the Matrix
This is the part students often find tricky, so let’s take it slow:
1. Find the smallest uncovered number (let’s call it \(e\)).
2. Subtract \(e\) from every uncovered number.
3. Add \(e\) to any number where two lines intersect.
4. Numbers covered by only one line stay the same.
5. Go back to Step 3 and try covering the zeros again.

Step 6: Assigning
Look for a zero that is the only zero in its row or column. Assign that worker to that task. Cross out that row and column and repeat until everyone is matched.

Quick Review: The "3-Rule" for Augmenting

- Uncovered? Subtract.
- Intersection? Add.
- One Line? Leave alone.

3. Handling "Mismatched" Problems

Sometimes, real life isn't perfectly square. What if you have 4 workers but only 3 jobs? Or what if a certain worker is physically unable to do a specific job?

Dummy Locations

The Hungarian Algorithm only works on square matrices. If you have a 3x4 matrix, you must add a dummy row or column to make it 4x4.
- The costs for all cells in a dummy row/column are always 0.
- Analogy: Imagine a game of musical chairs where you add an invisible "ghost chair." If someone is assigned to the ghost chair, it just means they don't get a real chair in the final result!

Incomplete Data (The "Big M" Method)

If a task cannot be assigned to a specific worker (maybe they lack the license for it), we don't want the algorithm to pick that cell. We give that cell an infinitely high cost (represented by \(M\) or \(\infty\)). Because we are trying to minimise cost, the algorithm will avoid the "M" cell at all costs!

Common Mistake to Avoid:

Don't forget Step 2 (Column Reduction)! Many students do the row reduction, see a zero in every column, and think they can skip to Step 3. Always check every column; if a column doesn't have a zero, you must subtract the minimum from it.

4. Maximising Profit

What if the numbers in the matrix aren't "costs" (bad things) but "profits" (good things)? The Hungarian Algorithm is built to find the minimum, so we have to trick it into finding the maximum.

How to Modify the Algorithm:

1. Find the largest value in the entire original matrix.
2. Subtract every value in the matrix from this largest value.
3. This creates a new matrix of "opportunity costs."
4. Run the standard Hungarian Algorithm on this new matrix to find the minimum. This minimum will correspond to the original maximum profit!

Example: If your highest profit is £50 and a cell has a profit of £10, the "loss" of picking that cell is £40. By minimising the "loss," you are maximising the profit!

5. Linear Programming Formulation

You might be asked to show how an allocation problem can be written as a Linear Program (LP). This is just a formal way of writing down our "one-to-one" rules.

Let \(x_{ij}\) be a variable that is:
- \(1\) if worker \(i\) is assigned to task \(j\).
- \(0\) if worker \(i\) is not assigned to task \(j\).

The Objective Function:
Minimise \(C = \sum \sum (c_{ij} \times x_{ij})\)
(This just means: Multiply each cost by its 1 or 0 and add them all up).

The Constraints:
1. Each worker gets one task: For each row, the sum of \(x\) values must equal 1.
\(\sum_{j=1}^{n} x_{ij} = 1\) for all \(i\)
2. Each task gets one worker: For each column, the sum of \(x\) values must equal 1.
\(\sum_{i=1}^{n} x_{ij} = 1\) for all \(j\)

Key Takeaway:

Formulating as an LP makes the problem "readable" for a computer. The constraints ensure that every row and column in our final assignment has exactly one "1" and the rest are "0".

Final Summary Checklist

- Is the matrix square? If not, add a dummy row/column with zeros.
- Is it a Maximisation problem? If so, subtract everything from the largest value first.
- Are there impossible tasks? Use \(M\) for those costs.
- Step 1: Row subtract.
- Step 2: Column subtract.
- Step 3: Cover zeros with min lines.
- Step 4: Lines < size? Augment (Subtract from uncovered, add to intersections).
- Step 5: Final assignment using zeros.

Keep practicing! The more matrices you "reduce," the more natural the Hungarian Algorithm becomes. You've got this!