KOTEBE UNIVERSITY OF EDUCATION

BUSINESS AND ECONOMICS FACULTY

ACCOUNTING AND FINANCE DEPARTMENT

CHAPTER FOUR : ASSIGNMENT MODEL

BY ; Shewayirga Assalf ( Asst. Prof.)

March. 2023
Assignment
model
• The assignment model is a special form of a linear programming model that is
similar to the transportation model.

• An assignment problem is a special form of transportation problem where

all supply and demand values equal one.

• One-to-one pairing.

• Helps in assigning work/jobs to machines or employees with to minimize or

maximize objectives i.e. distance, time, cost, profit….
The steps of the assignment solution
method
1. Row reductions: subtracting the minimum value in each row from all row values.

2. Column reductions: subtracting the minimum value in each column from all column values.

3. Checking for optimality: the solution is optimum when all zeros in the table can be covered
with minimum number of vertical/horizontal lines equal to number of row or column. If the
solution is optimum make assignment.

4. If the solution is not optimum, select the minimum value and subtract from all uncovered
values and add to values at the intersection of lines in the table.

5. If m lines are required, the tableau contains the optimal solution and m unique assignments
can be made. If fewer than m lines are required, repeat step 4.

• Where m is the number of rows or columns

Exampl
e

Employees
A B C D
1 ETB 15 20 18 24
Job 2 12 17 16 15
3 14 15 19 17
4 11 14 12 13

Required: make the assignment which minimizes

cost
Row Reduction
Employees
Opportunity cost
A B C D
Employees
1 15 20 18 24
Job A B C D
2 12 17 16 15
1 0 5 3 9
3 14 15 19 17
Job 2 0 5 4 3
4 11 14 12 13
3 0 1 5 3
4 0 3 1 2
Column Reduction
Employees
A B C D
Opportunity cost
1 0 5 3 9
Employees
Job 2 0 5 4 3
A B C D
3 0 1 5 3
1 0 4 2 7
4 0 3 1 2 Job 2 0 4 3 1
3 0 0 4 1
4 0 2 0 0
Covered zero values

Employees
A B C D
• The solution is not optimum, because
1
4 2 7
0 the number of row or column are not
Job 2
0 4 3 1
equal to the covered i.e. 3≠ 4
3
0 0 4 1
4
0 2 0 0

Optimum?
The minimum number of
Further Reduction lines used to cover zeros
are equal to number of
Employees rows/columns

A B C D
1 0 4 2 7
Job 2 0 4 3 1 Employees
1 A B C D
3 0 0 4 1
1 00 3 1 6
4 0 2 0 0
Job 2 0 3 2 00
3 1 00 3 1
4 1 2 00 0

Opti m!
mu
Make
assignment Job-employee assignment
Employees
A B C D 1 A birr 15
1 0 3 1 6 2 D 15
Job 2 0 3 2 0 3 15
4 B 12
3 1 0 3 1
C ETB57
4 1 2 0 0
Example
2
• The Ethiopian basketball association has four basketball games on a particular
night. The association office wants to assign four teams of officials to the four
games in a way that will minimize the total distance traveled by the officials. The
distances in meters for each team of officials to each game location are shown in
Table 34.
Table 34. The Travel Distances to Each Game for Each Team of Officials

Game Sites

Officials BOLE LIDETA ARADA YEKA

A 210 90 180 160

B 100 70 130 200
C 175 105 140 170
D 80 65 105 120

Required: Make assignment which can reduce the distance

• The first step in the assignment method of solution is to develop an opportunity
cost table.

• by first subtracting the minimum value in each row from every value in the row.

• In other words, the best course of action is determined for each row, and the
penalty or "lost opportunity" is developed for all other row values.

• The row reductions for this example are shown in Table 35.
Table 35. The Assignment Tableau with Row Reductions

Game Sites
Officials RALEIGH ATLANTA DURHAM CLEMSON
A 120 0 90 70
B 30 0 60 130
C 70 0 35 65
D 15 0 40 55

Next, column reductions and are shown in Table 36. It represents the completed
opportunity cost table for our example.
Assignments can be made in this table wherever a zero is present. For example, team A
can be assigned to LIDETA. An optimal solution results when each of the four teams can
be uniquely assigned to a different game.
Table 36. The Tableau with Column Reductions

Game Sites

Officials RALEIGH ATLANTA DURHAM CLEMSON

A 105 0 55 15
B 15 0 25 75
C 55 0 0 10
D 0 0 5 0
• Notice in Table 36 that the assignment of team A to Atlanta means that no other
team can be assigned to that game.

• Once this assignment is made, the zero in row B is infeasible, which indicates

that there is not a unique optimal assignment for team B. Therefore, Table 36

does not contain an optimal solution.

A test to determine if four unique assignments exist in Table 36 is to draw the

minimum number of horizontal or vertical lines necessary to cross out all zeros

through the rows and columns of the table.

For example, Table 37 shows that three lines are required to cross out all zeros.
Table 37. The Opportunity Cost Table with the Line
Test

Game Sites

Officials RALEIGH ATLANTA DURHAM CLEMSON

A 105 0 55 15
B 15 0 25 75
C 55 0 0 10
D 0 0 5 0
• The three lines indicate that there are only three unique assignments, whereas four
are required for an optimal solution.

• (NB even if the three lines could have been drawn differently, the
subsequent solution method would not be affected.)

• Next, subtract the minimum value that is not crossed out from all values
not crossed out.

• Add this minimum value to those cells where two lines intersect.

• The minimum value not crossed out in Table 37 is 15.

• The second iteration for this model with the appropriate changes is shown
in
Table 38.
Table 38. The Second
Iteration

Game Sites
Officials RALEIGH ATLANTA DURHAM CLEMSON
A 90 0 40 0
B 0 0 10 60
C 55 15 0 10
D 0 15 5 0

If the number of unique assignments is less than the number of rows

(or columns), a line test must be used.
• No matter how the lines are drawn in Table 38, at least four are required to cross

out all the zeros. This indicates that four unique assignments can be made and

that an optimal solution has been reached. Now let us make the assignments

from Table 38.

• In a line test, all zeros are crossed out by horizontal and vertical lines; the

minimum uncrossed value is subtracted from all uncrossed values and added to

cell values where two lines cross.

•
• First, team A can be assigned to either the LIDETA game or the YEKA game.

• We will assign team A to LIDETA first.

• This means that team A cannot be assigned to any other game, and no other team
can be assigned to LIDETA.

• Therefore, row A and the LIDETA column can be eliminated.

• Next, team B is assigned to BOLE. (Team B cannot be assigned to

LIDETA, which has already been eliminated.)

• The third assignment is of team C to the ARADA game. This leaves team D for
the YEKA game.
Table 38
Assignment Distance
Team A Lideta 90
Team B Bole 100
Team C Arada 140
Team D Yeka 120

450 meters

Now let us go back and make the initial assignment of team A to YEKA
(the alternative assignment we did not initially make).
This will result in the following set of assignments.
Table 39
Assignment Distance
Team A Yeka 160
Team B Lideta 70
Team C Arada 140
Team D Bole 80

450 Meters

These two assignments represent multiple optimal solutions for

our example
problem.
Both assignments will result in the officials traveling a minimum total distance of
450 meters.
Special cases in assignment model
1. Unbalanced assignment model

• When the number of rows and columns are not equal

• Assignment problem algorithm is to be true iff number of rows and columns are equal.

• But sometimes number of rows ≠ 𝑛𝑢𝑚𝑏𝑒𝑟𝑠 𝑜𝑓 𝑐𝑜𝑙𝑢𝑚𝑛𝑠

• Developing dummy row or column

Example
Jobs
1 2 3 4
Machines Find the optimum
A 15 19 12 16 assignment
B 23 21 18 17
C 20 16 11 19
1. Develop the tableau with dummy
row
Jobs
Machines 1 2 3 4
A 15 19 12 16
B 23 21 18 17
C 20 16 11 19
Dummy row 0 0 0 0
Row reduction

Jobs
Machines 1 2 3 4 Column reduction
A 3 7 0 4 • We don’t do column reduction because
B 6 4 1 0
the least number in all columns is
C 9 5 0 8
zero, means number minus zero = no
DR 0 0 0 0
change
• Check optimality: the above table is not optimal because the minimum lines
used to cover zeros are less than the number of rows/ columns

• Further reduction

Jobs Make assignment

Machines 1 2 3 4
A 0 4 0 4 Optimum! A-------1 15
B-------4 17
B 3 1 1 0
C-------3 11
C 6 2 0 8
DR 0 0 3 3
43
NB there is no actual assignmen
for job 2!
2. Ma x im iz a tio n o b j e c t i v e

• What if the object of assignment problem is maximization

• There will be one additional step at the initial stage

• i.e. conversion of the table to opportunity cost table

• By identifying the largest value in each column then subtract each value from the
largest number in that column.
Exampl
e
jobs
Machine 1 2 3 Find the optimum
assignment
A 14 22 30
B 20 18 40
C 11 12 50

Develop opportunity cost

table
Assignment jobs
A====2-------22 Machine 1 2 3
B====1-------20 A 6 0 20
B 0 4 10
C====3-------50
Optimal! C 9 10 0
profit
3. U n a c c e p t a b l e p a i r i n g

• Sometime some machines or employees are/can not allowed/do some jobs due to
handicap, capacity, skills etc.

• In such case we ignore assignment in the prohibited machine or employee

by assigning “m” then nothing is to be done on the “m” throughout the
computation.
Exampl
e
• Machine B cannot do job Row reduction
3
jobs jobs
Machine 1 2 3 Machine 1 2 3
A 8 7 2 A 6 5 0
B 1 4 3 B 0 3 M
C 7 9 3 C 4 6 0
Column
reduction

jobs
Machine 1 2 3
A 4 2 0
B 0 0 M
C 6 3 0
Check
optimality

jobs
Machine 1 2 3
A 2 0 0
B 0 0 M Optimum!
C 4 1 0
Assignment
B=====1 1
C=====3 3
A=====2 7
11
Solve the following linear programming
problem.
• Minimize

18X11+30X12+20X13+18X14+25X21+18X14+25X21+27X22+22X23+16X24+30X31+26X32++19X33
+32X34+40X41+36X42+27X43+29X44+30X51+26X52+18X53+24X54

subject to
X11+X12+X13+X14=1

Supply constraint
X21+X22+X23+X24=1

X31+X32+X33+X34=1
X11+X21+X31+X41=1
X41+X42+X43+X44=1
X12+X22+X32+X42=1 Demand constraint

X13+X23+X33+X43=1

X14+X24+X34+X44=1
Solve the following linear programming
problem.
Minimize 18X +30X +20X +18X +25X +18X +25X +27X +22X +16X +30X
11 12 13 14 21 14 21 22 23 24 31 +26X32+
+19X33+32X34+40X41+3
6X42+27X43+29X44+30X51+26X52+18X53+24X54
subject to
X11+X12+X13+X14≤ 1
X21+X22+X23+X24≤ 1
X31+X32+X33+X34 ≤1
X41+X42+X43+X44 ≤1
X51+X52+X53+X54 ≤1
X11+X21+X31+X41+X51=1
X12+X22+X32+X42+X52=1
X13+X23+X33+X43+X53=1
X14+X24+X34+X44+X54=1
• Xij ≥0