Assignment Problem:
Hungarian Solution Method
Learning Outcomes
[Link] special linear programming problems
using the assignment model.
2. Solve assignment problems with the Hungarian
method.
Introduction
The assignment problem refers to the class of linear
programming problems that involve determining the most
efficient assignment of
• people to projects
• salespeople to territories
• contracts to bidders
• jobs to machines, etc.
The objective is most often to minimize total costs or total
time of performing the tasks at hand.
Assignment Problems
One important characteristic of assignment problems is
that only one job or worker is assigned to one machine or
project.
An example is the problem of a taxi company with 4 taxis
and 4 passengers. Which taxi should collect which
passenger in order to minimize costs? Each assignment
problem has associated with it a table, or matrix.
Generally, the rows contain the objects or people we wish
to assign, and the columns comprise the tasks or things we
want them assigned to. The numbers in the table are the
costs associated with each particular assignment.
Assignment Problems
As an illustration of the assignment problem, let us
consider the case of a Fix-It-Shop, which has just
received three new rush projects to repair:
(1) a radio, (2) a toaster oven, and (3) a broken coffee
table.
Three repair persons, each with different talents and
abilities, are available to do the jobs.
The owner of the shop estimates what it will cost in
wages to assign each of the workers to each of the three
projects.
Assignment Problems
The costs which are shown in Table 1 differ because the
owner believes that each worker will differ in speed and
skill on these quite varied jobs.
Table 1: Repair costs of the Fix-It-Shop assignment problem
Assignment Problems
Table 2 summarizes all six assignment options. The table also shows
that the least-cost solution would be to assign Cooper to project 1,
Brown to project 2, and Adams to project 3, at a total cost of $25.
Table 2: Assignment alternatives and Costs of Fix-It-Shop assignment problem
Assignment Problems
The owner’s objective is to assign the three projects
to the workers in a way that will result in the lowest
cost to the shop.
Note that the assignment of people to projects must
be on a one-to-one basis; each project will be
assigned exclusively to one worker only.
Hungarian Solution Method
Special algorithms exist to solve assignment
problems. The most common is probably the
Hungarian solution method.
The Hungarian method of assignment provides us
with an efficient means of finding the optimal
solution without having to make a direct
comparison of every assignment option.
Hungarian Solution Method
It operates on a principle of matrix reduction, which
means that by subtracting and adding appropriate
numbers in the cost table or matrix, we can reduce
the problem to a matrix of opportunity costs.
Opportunity costs show the relative penalties
associated with assigning any person to a project as
opposed to making the best or least-cost assignment.
We would like to make assignments such that the
opportunity cost for each assignment is zero.
Hungarian Solution Method
The steps involved in the Hungarian method are outlined
below.
1. Find the opportunity cost table by (a) Subtracting
the smallest number in each row of the original cost
table or matrix from every number in that row. (b)
Then subtracting the smallest number in each column
of the table obtained in part (a) from every number in
that column.
Hungarian Solution Method
The steps involved in the Hungarian method are outlined
below.
2. Test the table resulting from step 1 to see whether an
optimal assignment can be made. The procedure is to
draw the minimum number of vertical and horizontal
straight lines necessary to cover all zeros in the table. If
the number of lines equals either the number of rows or
columns, an optimal assignment can be made. If the
number of lines is less than the number of rows or
columns, we proceed to step 3.
Hungarian Solution Method
The steps involved in the Hungarian method are outlined
below.
3. Revise the present opportunity cost table. This is done
by subtracting the smallest number not covered by a line
from every other uncovered number. This same smallest
number is also added to any number(s) lying at the
intersection of the horizontal and vertical lines. We then
return to step 2 and continue the cycle until an optimal
assignment is possible.
Fix-It-Shop: Minimization assignment example
Let us now apply the three steps to the Fix-It-Shop assignment
example.
The original cost table for the problem is given in Table 3.
Table 3: Initial Table Table 4: Row reduction (part a)
After the row reduction (Step 1 part a), we get the cost Table 4.
Fix-It-Shop: Minimization assignment example
Taking the costs in Table 4 and subtracting the smallest number in each column
from each number in that column results in the total opportunity costs given in
Table 5. This step is the column reduction of Step 1 part (b)
If we draw vertical and horizontal straight lines (Step 2) to cover all the zeros in
Table 5 we get Table 6. Since the number of lines is less than the number of rows
or columns an optimal assignment cannot be made.
Table 5: Column Reduction (Step 1 part b) Table 6: Testing for an optimal solution
Fix-It-Shop: Minimization assignment example
Since Table 6 doesn’t give an optimal solution we revise the table. This is
accomplished by subtracting the smallest number not covered by a line from all
numbers not covered by a straight line.
This same smallest number is then added to every number (including zeros) lying
in the intersection on any two lines. The smallest uncovered number in Table 6 is
2, so this value is subtracted from each of the four uncovered numbers.
A 2 is also added to the number that is covered by the intersecting horizontal and
vertical lines. The results of this step are shown in Table 7.
Table 7: Revised opportunity cost table
Fix-It-Shop: Minimization assignment example
To test now for an optimal assignment, we return to Step 2 and find the
minimum number of lines necessary to cover all zeros in the revised
opportunity cost table. Because it requires three lines to cover the zeros
(see Table 8), an optimal assignment can be made.
Table 8: Optimality test on the revised table
Fix-It-Shop: Minimization assignment example
Finally, we make the allocation. Note that only one
assignment will be made from each row or column. We use
this fact to proceed to making the final allocation as
follows:
a. Find a row or column with only one zero cell.
b. Make the assignment corresponding to that zero cell.
c. Eliminate that row and column from the table.
d. Continue until all the assignments have been made.
Fix-It-Shop: Minimization assignment example
For our Fix-It-Shop problem these steps are summarized in Table 9.
Table 9: Making the final assignment
Fix-It-Shop: Minimization assignment example
To interpret the table we recall that our objective was to
minimize costs, there is only one assignment that Adams can go to
where the opportunity costs are $0. That is to assign Adams
Project 3.
If Adams gets assigned to Project 3, then there is only one project
left where the opportunity cost is $0 for Cooper.
Therefore Cooper gets assigned to Project 1.
This leaves Brown being assigned to Project 2, where the
opportunity costs are $0.
Fix-It-Shop: Minimization assignment example
The optimal allocation is to assign Adams to Project 3, Brown to
Project 2, and Cooper to Project 1. The total labor cost of this
assignment are computed from the original cost table (see Table 1).
They are as follows:
Maximization Assignment Problems
Some assignment problems are phrased in terms of
maximizing the payoff, profit, or effectiveness of an
assignment instead of minimization costs. It is easy to
obtain an equivalent minimization problem by converting
all numbers in the table to opportunity costs; efficiencies
to inefficiencies, etc.
This is achieved through subtracting every number in the
original payoff table from the largest single number in
the number.
Maximization Assignment Problems
The transformed entries represent opportunity costs; it
turns out that minimizing the opportunity costs
produces the same assignment as the original
maximization problem.
Once the optimal assignment for this transformed
problem has been computed, the total payoff or profit
is found by adding the original payoffs of those cells
that are in the original assignment.
British Navy: Maximization assignment example
The British Navy wishes to assign four ships to patrol four
sectors of the North Sea. In some areas ships are to be on
the outlook for illegal fishing boats, and in other sectors to
watch for enemy submarines, so the commander rates each
ship in terms of its profitable efficiency in each sector.
These relative efficiencies are illustrated in Tables 10.
On the basis of the ratings shown, the commander wants to
determine the patrol assignments producing the greatest
overall efficiencies.
British Navy: Maximization assignment example
We start by converting the maximizing efficiency table into a
minimization opportunity cost table. This is done by subtracting
each rating from 100, the largest rating in the whole table. The
resulting opportunity costs are given in Table 11.
Table 10: Efficiencies of British Ships Table 11: Opportunity Costs of British
in Patrol sectors Ships
British Navy: Maximization assignment example
Next, we follow steps 1 and 2 of the assignment algorithm. The
smallest number is subtracted from every number in that row to
give Table 12; and then the smallest number in each column is
subtracted from every number in that column as shown in Table 13.
Table 12: Row opportunity costs Table 13: Total opportunity costs for
for the British Navy Problem the British Navy Problem
British Navy: Maximization assignment example
The minimum number of straight lines needed to cover all zeros in
this total opportunity cost table is four. Hence an optimal
assignment can be made. The optimal assignment is ship 1 to sector
D, ship 2 to sector C, ship 3 to sector B, and ship 4 to sector A.
The overall efficiency, computed from the original efficiency data
Table 10, can now be shown:
Summary
In this session, we discussed the Hungarian method
for solving both:
(1) maximization and
(1) minimization assignment problems.
