4th Edition
N. D. Vohra
Quantitative
Techniques in
Management
© 2010
Chapter 6
Specially Structured
Linear Programmes II:
Assignment Problem
Contents
1. Assignment Problem: A Variant of
the Transportation Problem
2. Methods of Solution
Complete Enumeration
Transportation Method
Simplex Method
Hungarian Assignment Method
3. Hungarian Assignment Method (HAM)
4. Special Topics
Unbalanced Assignment Problems
Constrained Assignment Problems
Unique vs. Multiple Optimal Solutions
Maximization Problems
5. Dual of Assignment Problem
Solution to an Assignment
Problem
Can be solved by complete enumeration
– ruled out since the number of
alternatives is very large (equal to n!)
Can be formulated and solved as a
transportation problem – not efficient
because the solution would be severely
degenerate
Can be formulated and solved an LPP (a
0-1 IPP) – also not an efficient way of
solving the problem
Can be solved by Hungarian Assignment
Method (HAM)
HAM is most efficient of all methods
Assignment Problem: A
Variant of Transportation
Problem
Job
Worker Supply
A B C D
1 45 40 51 67 1
2 57 42 63 55 1
3 49 52 48 64 1
4 41 45 60 55 1
Demand 1 1 1 1 4
Assignment Problem as LPP
Min Z = 45x11 + 40x12 + 51x13 + 67x14 + 57x21 +
42x22 + 63x23 + 55x24 + 49x31 + 52x32 + 48x33
+ 64x34 + 41x41 + 45x42 + 60x43 + 55x 44
Subject to
x11 + x12 + x13 + x14 = 1
x21 + x22 + x23 + x24 = 1
x31 + x32 + x33 + x34 = 1
x41 + x42 + x43 + x44 = 1
x11 + x21 + x31 + x41 = 1
x12 + x22 + x32 + x42 = 1
x13 + x23 + x33 + x43 = 1
x14 + x24 + x34 + x44 = 1
xij = 1 if assignment is made
xij = 0 if assignment is not made
Hungarian Assignment
Method
Step 1
Balance the problem if it is
unbalanced
Place an M as the cost element if
some assignment is prohibited
Convert into equivalent min
problem if it is a max problem
For this conversion, subtract each
value of the matrix from a
constant value, K ( generally the
largest value in the given matrix)
Step 2
Obtain zeros in every row and
column by row reductions and
column reductions
Hungarian Assignment
Method (…continued)
Step 3
Cover all zeros by least number of
horizontal/ vertical lines
If number of lines = n move to step
4 else, make adjustment: select
least uncovered value; subtract it
from every uncovered value; and
add to each one at intersection of
lines
Again cover zeros with lines to find
if you could go to 4
Step 4
Make assignments by considering
zeros
HAM: Making Assignments
Select a row/column with a single
zero
Make an assignment at zero by
placing a square around it
Cross out zero/s, if any, in the
corresponding column/row
Continue in this manner until all
assignments are made
If there are multiple zeros left in all
rows and columns, select a zero
arbitrarily, make assignment and
cancel other zeros in the row and
column involved
Multiple zeros in all rows and
columns remaining indicates
multiple optimal solutions
HAM: An Example
Solve the Problem: Time (in hours)
Job
Person
1 2 3 4 5
A 27 18 X 20 21
B 31 24 21 12 17
C 20 17 20 X 16
D 22 28 20 16 27
X indicates prohibited assignment
To solve this problem:
Balance by adding a dummy
person
Place an M for each prohibited
assignment
Solution to Assignment
Problem
Job
Person
1 2 3 4 5
A 27 18 M 20 21
B 31 24 21 12 17
C 20 17 20 M 16
D 22 28 20 16 27
E 0 0 0 0 0
Row Reductions: RCT-1
Job
Person
1 2 3 4 5
A 9 0 M 2 3
B 19 12 9 0 5
C 4 1 4 M 0
D 6 12 4 0 11
E 0 0 0 0 0
Solution (…continued)
Number of lines covering zeros (=4)
in RCT-1 is smaller than n (=5)
So, revise the table:(the least
uncovered value = 4)
RCT-2 is the resulting table
In RCT- 2, number of lines covering all
zeros = 5, which is equal to n, so
make assignments
RCT-2
Job
Person
1 2 3 4 5
A 9 0 M 6 3
B 15 18 5 0 1
C 4 1 4 M 0
D 2 8 0 0 7
E 0 0 0 4 0
Solution: Making Assignments
To make assignments in RCT-2,
Make an assignment at zero by placing a
square around it
Select column 1, assign E-1
Cross out zeros in row E
Select column 2, assign A-2
Select column 3, assign D-3
Select row 2, assign B-4
Cross out zero in column 4
Select row 5, assign C-5
Optimal Assignment Solution:
A-2; B-4; C-5; D-3 and
Job 1: unassigned
Total Time = 66 hours
Solution to Example 6.14
Layover Time Matrix – Crew at New Delhi
Flight 201 202 203 204
101 24 25 6 11
102 22 23 28 9
103 16 17 22 27
104 10 11 16 21
Layover Time Matrix – Crew at Mumbai
Flight 201 202 203 204
101 20 19 14 9
102 22 21 16 11
103 28 27 22 17
104 10 9 28 23
Solution to Example 6.14
(…continued)
Layover Time Matrix – Crew at New Delhi / Mumbai
Flight 201 202 203 204
101 20* 19* 6 9*
102 22 21* 16* 9
103 16 17 22 17*
104 10 9* 16 21
(*) indicates that crew is based at Mumbai
Other values indicate crew is based at New Delhi
The above matrix is derived by
comparing various pairs of flights and
taking the lower of the two layover
values involved; since for a given pair
of flights, crew will be based where
the layover time is smaller
Solution to Example 6.14
(…continued)
Reduced Cost Table 1
Flight 201 202 203 204
101 14 13 0 3
102 13 12 7 0
103 0 1 6 1
104 1 0 7 12
Optimal Pairing of Flights:
Layover
Flight Flight Crew-Base
Time
101 203 6 New Delhi
102 204 9 New Delhi
103 201 16 New Delhi
104 202 9 Mumbai
Multiple Choice Questions
Assignments can be made when
the minimum number of lines in a
reduced cost table with which all
zeros can be covered is
1. Exactly equal to n.
2. Equal to or greater than n.
3. Equal to or less than n.
4. Less than or greater than n.
Multiple Choice Questions
Mark the correct statement:
1. Assignment problems can be
solved using HAM only.
2. An assignment problem is a
special type of transportation
problem.
3. Unbalanced assignment problems
cannot be solved.
4. An assignment problem cannot be
of maximisation type.
Multiple Choice Questions
Mark the correct statement:
1. An assignment problem is said to be
unbalanced when all the workers
cannot perform all the jobs involved.
2. An assignment problem may require
the introduction of both: dummy
jobs and dummy workers.
3. An unbalanced assignment problem
is one where the number of workers
is more than, or less than, the
number of jobs.
4. An assignment problem with m
workers and n jobs will involve a
total of m n possible assignments.
Multiple Choice Questions
The minimum number of lines
covering all zeros in a Reduced
Cost Table can be:
1. At most n.
2. At least n.
3. at most r + c –1 (r: rows, c:
columns).
4. n – 1.
Multiple Choice Questions
When making assignment, we
begin with
1. Scanning and selecting rows with
single zeros and then proceed to
scan and select columns.
2. Scanning and selecting columns with
single zeros and then proceed to
scan and select rows.
3. Scanning and selecting rows or
columns with single zeros.
4. Selecting rows and columns with
single zeros in turn.
Multiple Choice Questions
Mark the correct statement:
1. If we begin making assignments by
selecting a row/column with
multiple zeros, then multiple
optimal solutions would result.
2. Multiple optimal solutions may have
different objective function values.
3. While making assignments, if we
face a situation where all the
rows/columns remaining have
multiple zeros, then multiple
optimal solutions are indicated.
4. Multiple optimal solutions imply
that at least one worker gets more
Multiple Choice Questions
In an assignment problem
involving 8 workers and 8 jobs,
total number of assignments
possible are:
1. 8
2. 16
3. 64
4. 8!
Multiple Choice Questions
Mark the wrong statement:
1. An assignment problem can be
solved by writing it as a linear
programming problem and using the
simplex algorithm.
2. The Hungarian method of solution
assumes that one worker can be
assigned only one job.
3. The relative cost of assigning job j to
worker i is not changed by the
subtraction of a constant from either
a row or a column of the cost matrix.
4. For converting a maximisation
problem into a minimisation
problem, a constant value, usually
the largest value, is subtracted from
all elements of the given matrix.
Multiple Choice Questions
Which of the following should be
preferred in making assignments?
1. A row with a single zero.
2. A column with multiple zeros.
3. A column with a single zero.
4. Either (a) or (c).