A-level Mathematics/Edexcel/Decision 2/Assignment Problems

Assignment Problems (AP) (also known as Allocation Problems, although they will be known as the former throughout this article) are a common form of problem. A distinguishing feature of AP is that one agent is assigned to one and only one task. Examples in real-life situations could be:

• Assigning contracts
• Assigning tasks to machinery
• Assigning agents to tasks
• Assigning Sales Personnel to Territories

An example of such a problem would be three lorries, A, B and C, and three loads that need to be transported, 1, 2 and 3. An example arrangement would be A → 1, B → 2 and C → 3. This means that Lorry A transports Load 1, Lorry B transports Load 2 and Lorry C transports Load 3.

Balanced Problems

A balanced AP is one in which:

(number of agents) = (number of tasks)

Table 1

	1	2	3
A	15	10	12
B	10	7	11
C	15	6	9

Consider again our lorry and load example. In this example, the number of agents (lorries) was 3 and the number of tasks (loads to be transported) is also equal to 3. Thus, it is a balanced problem. Initially, one will consider only balanced problems and how they are to be solved.

Upon expansion of the earlier problem, it was revealed that the cost for each lorry to transport each load is different. These are represented in Table 1.

The manager of the fleet of lorries wishes to minimise to total cost to complete all three jobs. How would one allocate the lorries to the loads? The table of numbers given is called the cost matrix of the problem.

Formulation as a Linear Programming Problem

A Linear Programming Problem can easily be developed for AP. One would define $x$_ij (where agent i is assigned task j) where:

$x$_ij=1, when agent i is completing task j

$x$_ij=0, when agent i does not complete task j

Thus, one can obtain the contraints for the Linear Programming Problem by considering each agent/task in turn:

As each agent is assigned to exactly one job, we can deduce:

for agent A: $x$_A1 + $x$_A2 + $x$_A3 = 1

for agent B: $x$_B1 + $x$_B2 + $x$_B3 = 1

for agent C: $x$_C1 + $x$_C2 + $x$_C3 = 1

Similarly, since each job is assigned to exactly one agent, one can deduce:

for job 1: $x$_A1 + $x$_B1 + $x$_C1 = 1

for job 2: $x$_A2 + $x$_B2 + $x$_C2 = 1

for job 3: $x$_A3 + $x$_B3 + $x$_C3 = 1

If we apply this to the aforementioned example, one can see that for lorry A, it can only carry one of loads 1, 2 or 3. So, $x$_A1 could = 1, with $x$_A2 and $x$_A3 being zero, or $x$_A2 = 1, with $x$_A1 and $x$_A3 being zero, etc.

The obtain the objective function for this example, we must consider the total costs.

For lorry A, costs will be: 15$x$_A1 $+$ 10$x$_A2 $+$ 12$x$_A3

For lorry B, costs will be: 10$x$_B1 $+$ 7$x$_B2 $+$ 11$x$_B3

For lorry C, costs will be: 15$x$_C1 $+$ 6$x$_C2 $+$ 9$x$_C3

The means, therefore, that the objection function, Z, for this example is to minimise Z where:

Z = 15$x$_A1 $+$ 10$x$_A2 $+$ 12$x$_A3 $+$ 10$x$_B1 $+$ 7$x$_B2 $+$ 11$x$_B3 $+$ 15$x$_C1 $+$ 6$x$_C2 $+$ 9$x$_C3

Finally, this means that one can conclude the LPP to be:

Minimise Z, where Z = 15$x$_A1 $+$ 10$x$_A2 $+$ 12$x$_A3 $+$ 10$x$_B1 $+$ 7$x$_B2 $+$ 11$x$_B3 $+$ 15$x$_C1 $+$ 6$x$_C2 $+$ 9$x$_C3, subject to:

$x$_A1 + $x$_A2 + $x$_A3 = 1

$x$_B1 + $x$_B2 + $x$_B3 = 1

$x$_C1 + $x$_C2 + $x$_C3 = 1

$x$_A1 + $x$_B1 + $x$_C1 = 1

$x$_A2 + $x$_B2 + $x$_C2 = 1

$x$_A3 + $x$_B3 + $x$_C3 = 1

Solution of the Balanced Assignment Problem

An algorithm was developed by Harold Kuhn in the 1950s, and was named the Hungarian Algorithm. Its name is a reference to Dénes Kőnig and Jenő Egerváry, a pair of prominent Hungarian Mathematicians whose techniques are applied in this algorithm.

The Hungarian Algorithm

For the Hungarian Algorithm to work, the assignment problem must meet the following criteria:

• Each worker must be assigned, as we previously saw, to exactly one job.
• Each job must be assigned to exactly one worker.
• In the cost matrix, a constant can be added or subtracted from all cost values in any row or column without having any effect on the optimal assignments.

There are three stages in the implementation of the Hungarian Algorithm:

• Find the opportunity cost matrix
• Test for an optimal assignment. If one can be made, use it and stop.
• If an optimal assignment cannot be made, revise the opportunity cost matrix and return to the previous step.

To demonstrate these three steps, let us consider again the lorry example:

Finding the Opportunity Cost Matrix

The Opportunity Cost Matrix (OCM) is essentially a modified version of our initial Cost Matrix. In order to change the Cost Matrix into the OCM, one must carry out two stages.

1. Carry out row reduction
2. Carry out column reduction

Row reduction is the operation in which the smallest number in each row is subtracted from every number in that row. With our earlier example:

Cost Matrix

	1	2	3
A	15	10	12
B	10	7	11
C	15	6	9

Cost Matrix with Row Minima

	1	2	3	Row Minimum
A	15	10	12	10
B	10	7	11	7
C	15	6	9	6

Cost Matrix after Row Reduction

	1	2	3
A	5	0	2
B	3	0	4
C	9	0	3

Next, one completes the column reduction. This is the same as row reduction, only with the smallest number in each column being subtracted from each value within that column. Thus:

Cost Matrix after Row Reduction

	1	2	3
A	5	0	2
B	3	0	4
C	9	0	3

Cost Matrix with Column Minima

	1	2	3
A	5	0	2
B	3	0	4
C	9	0	3
Column Minimum	3	0	2

Cost Matrix after Column Reduction

	1	2	3
A	2	0	0
B	0	0	2
C	6	0	1

Thus, the completed Opportunity Cost Matrix is:

Opportunity Cost Matrix

	1	2	3
A	2	0	0
B	0	0	2
C	6	0	1

Interpreting The Opportunity Cost Matrix

Since the aim of an assignment problem is to assign exactly one agent to exactly one task, one must match each agent up to the task which best minimises overall cost. After completing the row reduction and column reduction, it is logical to assume that the values that remain in the table are the minimum possible. Similarly, since the values in the table are the cost-values, the lowest values in the table are, surely, those of lowest cost. In order to find a solution, one must select one zero from each row and one zero from each column. However, one cannot select more than one value from any row or column, as it will result in one agent/task being assigned twice, which cannot occur in an Assignment Problem.

Again, let's consider the earlier example. If we were to select one zero from each column/row without any doubles occurring, the only possible solution is (with selected costs marked by asterices):

Opportunity Cost Matrix

	1	2	3
A	2	0	0*
B	0*	0	2
C	6	0*	1

If we then assign this solution to our original cost matrix, one can see the following:

Cost Matrix

	1	2	3
A	15	10	12*
B	10*	7	11
C	15	6*	9

Thus, the final assignment is:

A → 3 (cost 12)

B → 1 (cost 10)

C → 2 (cost 6)

Z = 12 + 10 + 6 = 28

It is interesting to see that, despite this being the cheapest solution, it doesn't actually utilise all of the lowest values within the table.

Optimality of a Solution

An important issue with AP is the optimality of solution - when one obtains a solution, how can one be sure it truly is the best solution available? With the Hungarian algorithm, there is a fairly straightforward test for optimality that concerns drawing lines through the zeros in the Opportunity Cost Matrix. If the number of lines (horizontal and vertical only) is equal to the number of rows/columns, the solution obtained is optimal. If, however, the number of lines needed does not equal the number of rows/columns, the solution is not optimal, and can be improved. This is a somewhat perplexing technique, but one that is straightforward to implement and clear to interpret.

Consider the following OCM:

Opportunity Cost Matrix

	1	2	3
A	1	0	2
B	5	0	0
C	6	3	1

It is fairly easy to see that it would require only two lines to draw through all of the zeros - one could use a horizontal line through row B, and a vertical line through column 2, for instance. 2≠3 (the number of rows/columns), thus an optimal solution cannot be made.

Consider, on the other hand, our lorry example. Is the solution that we obtained optimal?

Opportunity Cost Matrix

	1	2	3
A	2	0	0
B	0	0	2
C	6	0	1

One can see that, in order to strike through each zero, one would need three lines (for instance, one through column 2, one through row B and one through row A). 3 = 3, thus we have an optimal solution that cannot be improved upon.

Revision of the Opportunity Cost Matrix

In the event of achieving a non-optimal assignment, one must revise the OCM. There are several steps in this process:

1. Check the costs uncovered by the drawn lines
2. Identify the smallest uncovered value
3. Subtract this value from all of the uncovered costs
4. Add this value to any costs that are at the intersection of any two drawn lines

Take our non-optimal solution from earlier. The smallest uncovered value was one. Subtracting one from each uncovered value gives:

Opportunity Cost Matrix

	1	2	3
A	0	0	1
B	5	0	0
C	5	3	0

Adding one to the point of intersection of the two lines (in this example, one could have drawn them through row B and column 2, therefore the point of intersection is cell B2) gives:

Opportunity Cost Matrix

	1	2	3
A	0	0	1
B	5	1	0
C	5	3	0

Again, only two lines (this time, they must be through row A and column 3) are needed. They intersect at cell A3. The smallest uncovered value is, again, 1. So, subtracting one from each uncovered cell and adding one to cell A3 gives:

Opportunity Cost Matrix

	1	2	3
A	0	0	2
B	4	0	0
C	4	2	0

Finally, the minimum number of lines needed to draw through all of the zeros is 3, which is the number of rows/columns. This means any assignment made will be optimal.

Solutions of Unbalanced Assignment Problems

The definition of a balanced AP was one in which the number of agents was the same as the number of tasks. In reality, this is unlikely to be the case - that is, it is unlikely that one would have the same number of taxi drivers to the number of customers, for example. In the event of an unbalanced problem, one must add a dummy, which is a blank/empty row, added to the Cost Matrix, in order to 'balance' the rows, for the sake of the algorithm. If one had, for instance, three agents and four tasks, one would add a dummy row. On the other hand, if one had four agents and three tasks, one would add a dummy task. This helps as it means that one agent or task will be left without a 'real' assignment, as using them would increase the total cost of the assignment.

Consider the following example:

A taxi company has four drivers (A, B, C, D), each currently at different locations. Three customers (1, 2, 3) have called the taxi company and need to be driven to their destinations. The total distance that would be travelled, by the driver, is represented in the cost matrix below:

Cost Matrix

	1	2	3
A	11	19	17
B	21	15	13
C	15	18	21
D	18	15	17

The Taxi Company wishes to minimise the total distance travelled by its drivers. Find an optimal solution to this Assignment Problem.

Solution:

Initially, one must add a dummy column, in order to make this a 'balanced' problem. Let this column be called "Row 4". Since there isn't actually a fourth customer, all of the costs in this matrix will be zero. This will mean that the otherwise most expensive taxi in the matrix will result in being assigned the dummy - in other words, it won't be used in the problem.

First, let's carry out row and column reduction:

Cost Matrix with Row Minima

	1	2	3	4	Row Minimum
A	11	19	17	0	0
C	15	18	21	0	0
D	18	15	17	0	0

... with Column Minima

	1	2	3	4
A	11	19	17	0
B	21	15	13	0
C	15	18	21	0
D	18	15	17	0
Column Minimum	11	15	13	0

Opportunity Cost Matrix

	1	2	3	4
A	0	4	4	0
B	10	0	0	0
C	4	3	8	0
D	7	4	0	0

As one can see, all of the zeros in the Opportunity Cost Matrix can only be struck through using 4 lines (for instance, 1 line vertically through Column 4, 3 lines horizontally through Rows A, B & D). Thus, we've already arrived at the optimal solution because 4 lines can be used to mark through the entire matrix. The only possible solution is:

A → 1

B → 3

C → 2

D → 4*

Z = 11 + 13 + 18 = 42

• Of course, customer 4 is in fact a 'dummy' - i.e., D doesn't actually transport any customer. Thus, the only three drivers needed are drivers A, B and C. Driver A will transport Passenger 1, Driver B will transport Passenger 3 and Driver C will transport Passenger 2.

Maximisation Problems

All of the examples that have been considered so far have been Minimisation problems - in other words, they've been ones in which the aim of the problem was to minimise a cost. Assignment problems can, however, be used for the opposite reason - to maximise a gain or a profit. Consider the example of ice-cream seller. They know that, in certain towns, they will sell more icecream than others. The day, too, changes how much ice-cream s/he sells - they only drive the van on Monday, Wednesday and Saturday (M, W and S respectively). Taking into account that the ice-cream van can only visit one town at a time, which town should the ice-cream van visit on which day, in order to maximise his/her profit.

The following cost-matrix represents the earnings (in £100s) for each town (A, B, C) on each day (M, W, S):

Cost Matrix

	M	W	S
A	10	7	11
B	10	12	12
C	9	13	11

If one were to carry out row and column reduction, as per usual, and then to come to a solution, it would be a solution that gave the minimum profit that the ice-cream van could make. In order to find the maximum profit, we first identify the largest value in the matrix. In this case, it is 13. We then subtract each number from 13 and assign the new number to the cell the original number was in. In other words, cell A1 (of current value 10) becomes $13-10=3$.

After completing this process for the whole matrix, we achieve the following:

Cost Matrix

	M	W	S
A	3	6	2
B	3	1	1
C	4	0	2

We can now carry out row and column reduction, as we usually would. This, eventually, results in the following Opportunity Cost Matrix:

Opportunity Cost Matrix

	M	W	S
A	0	6	1
B	0	1	0
C	1	0	1

Since the smallest number of lines that can be used to strike-through each of the zeros in this matrix is 3 (which is equal to the number of rows/columns), an optimal assignment can be made. The only possible assignment is:

A → M

B → S

C → W

On the cost matrix, this gives us:

Cost Matrix

	M	W	S
A	10*	7	11
B	10	12	12*
C	9	13*	11

This means that:

On Monday, the van will visit town A.

On Wednesday, the van will visit town B.

On Saturday, the van will visit town C.

The total profit gives:

$Z=10+12+13=35$

Thus the maximum total profit of the ice-cream van is £3500.