Assignment Problem
The Assignment Model
Characteristics
• Special form of linear programming model similar to the
transportation model.
• Supply at each source and demand at each destination limited to
one unit.
• In a balanced model supply equals demand.
• In an unbalanced model supply does not equal demand.
Assignment Problem
This method can solve a special form of LP problem,
including the classical assignment problem, with these
typical characteristics:
is a special case of a transportation problem
the right-hand sides of constraints are all 1
the signs of the constraints are = rather than < or >
the value of all decision variables is either 0 or 1
Assignment Problem
An assignment problem seeks to minimize the total cost
assignment of m workers to m jobs, given that the cost of
worker i performing job j is cij.
It assumes all workers are assigned and each job is
performed.
An assignment problem is a special case of a transportation
problem in which all supplies and all demands are equal to
1; hence assignment problems may be solved as linear
programs.
The network representation of an assignment problem with
three workers and three jobs is shown on the next slide.
Assignment Problem
Network Representation
c11
11 1
c12
c13
c21
c22
2 2
c23
c31 c32
3 3
c33
WORKERS JOBS
Assignment Problem –
Cost Matrix
Let the following represent the standard assignment problem
cost matrix, c:
Tasks
1 2 … n
1 c 11 c 12 … c 1n
Assignees 2 c 21 c 22 … c 2n
… …
n c n1 c n2 … c nn
Assignment Problem
Linear Programming Formulation
Min cijxij
ij
s.t. xij = 1 for each resource (row) i
j
xij = 1 for each job (column) j
i
xij = 0 or 1 for all i and j.
Note: A modification to the right-hand side of the first
constraint set can be made if a worker is permitted to work
more than 1 job.
Hungarian Method
The Hungarian method solves minimization assignment
problems with m workers and m jobs.
Special considerations can include:
number of workers does not equal the number of
jobs — add dummy workers/jobs with 0 assignment
costs as needed
worker i cannot do job j — assign cij = +M
maximization objective — create an opportunity loss
matrix subtracting all profits for each job from the
maximum profit for that job before beginning the
Hungarian method
Hungarian Method
Step 1: For each row, subtract the minimum number in
that row from all numbers in that row.
Step 2: For each column, subtract the minimum number
in that column from all numbers in that column.
Step 3: Draw the minimum number of lines to cover all
zeroes. If this number = m, STOP — an assignment can
be made.
Step 4: Determine the minimum uncovered number
(call it d).
Subtract d from uncovered numbers.
Add d to numbers covered by two lines.
Numbers covered by one line remain the same.
Then, GO TO STEP 3.
Hungarian Method
Finding the Minimum Number of Lines and Determining the
Optimal Solution
Step 1: Find a row or column with only one unlined zero
and circle it. (If all rows/columns have two or more unlined
zeroes choose an arbitrary zero.)
Step 2: If the circle is in a row with one zero, draw a line
through its column. If the circle is in a column with one
zero, draw a line through its row. One approach, when all
rows and columns have two or more zeroes, is to draw a
line through one with the most zeroes, breaking ties
arbitrarily.
Step 3: Repeat step 2 until all circles are lined. If this
minimum number of lines equals m, the circles provide the
optimal assignment.
Assignment Problem –
Hungarian Method
Consider following cost matrix.
Tasks
1 2 3 4 Row Minimum
1 14 5 8 7 5
Assignees 2 2 12 6 5 2
3 7 8 3 9 3
4 2 4 6 10 2
Reduce by Row Minimum.
Tasks
1 2 3 4
1 9 0 3 2
Assignees 2 0 10 4 3
3 4 5 0 6
4 0 2 4 8
Column Min 0 0 0 2
Assignment Problem –
Hungarian Method
Reduced by Column Minimum:
Tasks
1 2 3 4
1 9 0 3 0
Assignees 2 0 10 4 1
3 4 5 0 4
4 0 2 4 6
Reduce by Minimum of uncovered cells (1):
Tasks
1 2 3 4
1 10 0 3 0
Assignees 2 0 9 3 0
3 5 5 0 4
4 0 1 3 5
Assignment Problem –
Hungarian Method
Solution is now optimal since minimum number of lines to
cover all 0 is 4 (equal to n).
Tasks
1 2 3 4
1 10 0 3 0
Assignees 2 0 9 3 0
3 5 5 0 4
4 0 1 3 5
A3 -> T3, A1 -> T2, A2 -> T4, A4 -> T1
Z = 3 + 5 + 5 + 2 = 15
Example 1: AP
A contractor pays his subcontractors a fixed fee plus mileage for work
performed. On a given day the contractor is faced with three electrical
jobs associated with various projects. Given below are the distances
between the subcontractors and the projects.
Project
A B C
Westside 50 36 16
Subcontractors Federated 28 30 18
Goliath 35 32 20
Universal 25 25 14
How should the contractors be assigned to minimize total costs?
Note: There are four subcontractors and three projects. We create a
dummy project Dum, which will be assigned to one subcontractor (i.e.
that subcontractor will remain idle)
Example 1: AP
Network Representation (note the dummy
project) West. 50
A
36
0 16
28
30
Fed. B
18
0
35 32
20
Gol. C
0
25 25
14
Univ. Dum.
0
Example 1: AP
Initial Tableau Setup
Since the Hungarian algorithm requires that there be the
same number of rows as columns, add a Dummy column
so that the first tableau is (the smallest elements in each
row are marked red):
A B C Dummy
Westside 50 36 16 0
Federated 28 30 18 0
Goliath 35 32 20 0
Universal 25 25 14 0
Example 1: AP
Step 1: Subtract minimum number in each row from all
numbers in that row. Since each row has a zero, we
simply generate the original matrix (the smallest
elements in each column are marked red). This yields:
A B C Dummy
Westside 50 36 16 0
Federated 28 30 18 0
Goliath 35 32 20 0
Universal 25 25 14 0
Example 1: AP
Step 2: Subtract the minimum number in each column
from all numbers in the column. For A it is 25, for B it is
25, for C it is 14, for Dummy it is 0. This yields:
A B C Dummy
Westside 25 11 2 0
Federated 3 5 4 0
Goliath 10 7 6 0
Universal 0 0 0 0
Example 1: AP
Step 3: Draw the minimum number of lines to cover all zeroes
Step 3: Draw the minimum number of lines to cover all zeroes
(called minimum cover). Although one can "eyeball" this
minimum, use the following algorithm. If a "remaining" row has
only one zero, draw a line through the column. If a remaining
column has only one zero in it, draw a line through the row. Since
the number of lines that cover all zeros is 2 < 4 (# of rows), the
current solution is not optimal.
A B C Dummy
Westside 25 11 2 0
Federated 3 5 4 0
Goliath 10 7 6 0
Universal 0 0 0 0
Step 4: The minimum uncovered number is 2 (circled).
Example 1: AP
Step 5: Subtract 2 from uncovered numbers; add 2 to
all numbers at line intersections; leave all other numbers
intact. This gives:
A B C Dummy
Westside 23 9 0 0
Federated 1 3 2 0
Goliath 8 5 4 0
Universal 0 0 0 2
Example 1: AP
Step 3: Draw the minimum number of lines to cover all
zeroes. Since 3 (# of lines) < 4 (# of rows), the current
solution is not optimal.
A B C Dummy
Westside 23 9 0 0
Federated 1 3 2 0
Goliath 8 5 4 0
Universal 0 0 0 2
Step 4: The minimum uncovered number is 1 (circled).
Example 1: AP
Step 5: Subtract 1 from uncovered numbers. Add 1 to
numbers at intersections. Leave other numbers intact. This
gives:
A B C Dummy
Westside 23 9 0 1
Federated 0 2 1 0
Goliath 7 4 3 0
Universal 0 0 0 3
Example 1: AP
Find the minimum cover:
A B C Dummy
Westside 23 9 0 1
Federated 0 2 1 0
Goliath 7 4 3 0
Universal 0 0 0 3
Step 4: The minimum number of lines to cover all 0's is four.
Thus, the current solution is optimal (minimum cost)
assignment.
Example 1: AP
The optimal assignment occurs at locations of zeros such
that there is exactly one zero in each row and each
column:
A B C Dummy
Westside 23 9 0 1
Federated 0 2 1 0
Goliath 7 4 3 0
Universal 0 0 0 3
Example 1: AP
The optimal assignment is (go back to the original table for
the distances):
Subcontractor Project Distance
Westside C 16
Federated A 28
Universal B 25
Goliath (unassigned)
Total Distance = 69 miles
Example 1: AP via LP
In our example the LP formulation is:
Min z = 50x11 + 36x12 + 16x13 + 0x14 + 28x21 + 30x22 + 18x23 +
0x24 + 35x31 + 32x32 + 20x33 + 0x34 + + 25x41 + 25x42 + 14x43 +
0x44
s.t.
x11 + x12 + x13 + x14 = 1 (row 1)
x21 + x22 + x23 + x24 = 1 (row 2)
x31 + x32 + x33 + x34 = 1 (row 3)
x41 + x42 + x43 + x44 = 1 (row 4)
x11 + x21 + x31 + x41 = 1 (column 1)
x12 + x22 + x32 + x42 = 1 (column 2)
x13 + x23 + x33 + x43 = 1 (column 3)
x14 + x24 + x34 + x44 = 1 (column 4)
xij >= 0 for i = 1, 2, 3, 4 and j = 1, 2, 3, 4 (nonnegativity)
Assignment Problem –
Conversion to Standard Cost Matrix
Consider following cost matrix, how do you convert to satisfy
the standard definition of the assignment problem?
Tasks
1 2 3 4
1 10 9 8 7
Assignees 2 4 - 5 6
3 2 1 8 -
Add “big M” to avoid incompatible assignments, and add a
dummy assignee (or task) to have equal assignees and tasks.
Tasks
1 2 3 4
1 10 9 8 7
Assignees 2 4 M 5 6
3 2 1 8 M
4 0 0 0 0