Matching and Allocation Problems (VCE SSCE General Mathematics): Revision Notes

Matching and Allocation Problems

Introduction to bipartite graphs

A bipartite graph is a special type of graph where the vertices are divided into two separate groups. The key characteristic is that each edge connects a vertex from one group to a vertex in the other group. In other words, edges never connect vertices within the same group.

Understanding bipartite graphs through an example

Imagine a music school with four teachers: Anastasios, Panayioti, Olga, and Irene. These teachers can teach four different musical instruments: trumpet, piano, violin, and clarinet. We can represent this situation using a bipartite graph.

In the graph:

• One group contains the four teachers (shown as vertices on the left)
• The other group contains the four instruments (shown as vertices on the right)
• Edges connect each teacher to the instruments they are qualified to teach

This visual representation helps us see which teachers can teach which instruments at a glance. The edges show the possible connections, making it easier to solve allocation problems.

Solving allocation problems with bipartite graphs

An allocation problem involves matching items from one group to items in another group. In the music school example, we need to assign each teacher to exactly one instrument class.

By examining the bipartite graph, we can work out the optimal allocation:

• Anastasios is the only teacher who can teach clarinet, so he must be assigned to clarinet
• Irene can only teach violin, so she must be assigned to violin
• With those two assignments made, Olga must teach piano
• Finally, Panayioti must teach trumpet

This logical process of elimination allows us to find a complete allocation where each teacher has one class and each instrument has one teacher.

Worked example: TV presenters

Complete bipartite graphs

A complete bipartite graph is a special case where every vertex in one group is connected to every vertex in the other group. This means there are edges between all possible pairs of vertices from different groups.

In the factory example shown above, there are four employees and four machines. Each employee can use every machine, so every employee vertex connects to every machine vertex. This creates a complete bipartite graph.

The Hungarian algorithm

Introduction to cost matrices

In real-world allocation problems, some matches are better than others. For example, different employees might take different amounts of time to complete tasks on different machines. We can represent this information in a cost matrix.

A cost matrix is a table where:

• Rows represent items from the first group (e.g., employees)
• Columns represent items from the second group (e.g., machines)
• Each cell contains the "cost" of that particular allocation (e.g., time in minutes)

Here's an example cost matrix for a factory with four employees (Wendy, Xenefon, Yolanda, and Zelda) and four machines (A, B, C, and D):

Employee	A	B	C	D
Wendy	30	40	50	60
Xenefon	70	30	40	70
Yolanda	60	50	60	30
Zelda	20	80	50	70

The numbers represent how many minutes each employee takes to complete their task on each machine. For instance, Wendy takes $30$ minutes on machine A but $60$ minutes on machine D.

Purpose of the Hungarian algorithm

The Hungarian algorithm is a systematic method that finds the optimal allocation to minimise the total cost. It works by transforming the cost matrix through a series of steps until we can identify the best allocation.

The algorithm ensures that we assign each employee to exactly one machine (or each item from one group to exactly one item from the other group) while minimising the total time, cost, or whatever metric we're measuring.

Steps of the Hungarian algorithm

For our example:

• Wendy's row: subtract $30$ from each value
• Xenefon's row: subtract $30$ from each value
• Yolanda's row: subtract $30$ from each value
• Zelda's row: subtract $20$ from each value

Employee	A	B	C	D
Wendy	0	10	20	30
Xenefon	40	0	10	40
Yolanda	30	20	30	0
Zelda	0	60	30	50

In our example, we need three lines to cover all zeros, but we need to make four allocations. Therefore, we continue.

Column C doesn't have a zero, so subtract $10$ from every value in column C:

Employee	A	B	C	D
Wendy	0	10	10	30
Xenefon	40	0	0	40
Yolanda	30	20	20	0
Zelda	0	60	20	50

Step 4: Check again

Count the minimum number of lines needed to cover all zeros.

If this equals the number of allocations, jump to Step 6.

Otherwise, continue to Step 5a.

We still need only three lines to cover all zeros, so we continue.

In our example, the smallest uncovered value is $10$.

Add $10$ to cells covered by two lines and subtract $10$ from uncovered cells:

Employee	A	B	C	D
Wendy	0	0	0	30
Xenefon	50	0	0	50
Yolanda	30	10	10	0
Zelda	0	50	10	50

Step 5b: Repeat from Step 4

Check again how many lines are needed to cover all zeros.

Now we need four lines, which equals our four required allocations, so we proceed to Step 6.

From our final table:

• Wendy connects to A, B, and C (has zeros in those columns)
• Xenefon connects to B and C
• Yolanda connects to D
• Zelda connects to A

Exam tips

When performing the Hungarian algorithm:

• Always work carefully through each step in order
• Keep track of which operation you're performing (row reduction, column reduction, etc.)
• When covering zeros with lines, use the minimum number possible
• Double-check your arithmetic at each stage
• Remember to use the original cost matrix when calculating the final total cost
• Show all your working clearly in the exam