Page 327 -

ASSIGNMENT PROBLEM: A SPECIAL-PURPOSE SOLUTION PROCEDURE 307

Multiple Assignments
At the beginning of this section, we indicated that a distinguishing feature of the
If some tasks require
more than one person, assignment problem is that one person is assigned to one and only one task. In
the linear programming generalizations of the assignment problem where one person can be assigned to two
formulation can also
accommodate the or more tasks, the linear programming formulation of the problem can be easily
situation. Use the modified. For example, let us assume that in the Fowle Marketing Research prob-
number of people lem Terry could be assigned up to two clients; in this case, the constraint represent-
required as the right- ing Terry’s assignment would be x 11 + x 12 + x 13 2. In general, if a i denotes the
hand side of the
appropriate task upper limit for the number of tasks to which person i can be assigned, we write the
constraint. people constraints as:
X
n
x ij a i i ¼ 1; 2; ... ; m
j¼1
Thus, we see that one advantage of formulating and solving assignment problems as
linear programmes is that special cases such as the situation involving multiple
assignments can be easily handled.

NOTES AND COMMENTS

1 As noted, the assignment model is a special case provides another means of dealing with situations
of the transportation model. We stated in the when the number of tasks exceeds the number of
notes and comments at the end of the preceding people. That is, we add one dummy person, but
section that the optimal solution to the provide the dummy person with the capability to
transportation problem will consist of integer handle multiple tasks. The number of tasks the
values for the decision variables as long as the dummy person can handle is equal to the
supplies and demands are integers. For the difference between the number of tasks and the
assignment problem, all supplies and demands number of people.
equal 1; so, the optimal solution must be integer 3 The Management Science in Action, Heery
valued and the integer values must be 0 or 1. International, describes how managers are
2 Combining the method for handling multiple assigned to construction projects. The
assignments with the notion of a dummy person application involves multiple assignments.

7.4 Assignment Problem: A Special-Purpose Solution Procedure

The Hungarian method
was invented and As mentioned previously, the assignment problem is a special case of the trans-
published by Harold portation problem. So, the transportation Simplex method can be used to solve the
Kuhn, a US assignment problem. However, the assignment problem has an even more special
mathematician, in 1955. structure: all supplies and demands equal 1. Because of this additional special
Kuhn gave the algorithm
its name to reflect the structure, special-purpose solution procedures have been specifically designed to
fact that his work was solve the assignment problem; one such procedure is called the Hungarian method.
largely based on the In this section we will show how the Hungarian method can be used to solve the
earlier works of two Fowle Marketing Research problem.
Hungarian
mathematicians: De´nes Recall that the Fowle problem (see Section 7.3) involved assigning project leaders
Ko¨nig and Jeno˜ Egerva´ry. to clients; three project leaders were available and three research projects were to be

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.