Page 323 -

ASSIGNMENT PROBLEM: THE NETWORK MODEL AND A LINEAR PROGRAMMING FORMULATION 303

Phase II of the transportation Simplex method is only addition and subtraction operations are
thus the same as phase II of the Simplex method necessary. We can implement the entire
for linear programming. At each iteration, one procedure in a transportation tableau that has
variable is brought into solution and another one row for each origin and one column for each
variable is dropped from solution. The reason the destination. A simplex tableau for such a problem
method works so much better for transportation would require a row for each origin, a row for
problems is that the special mathematical each destination and a column for each arc; thus,
structure of the constraint equations means that the simplex tableau would be much larger.

Assignment Problem: The Network Model and a Linear
7.3
Programming Formulation

The assignment problem arises in a variety of decision-making situations; typical
assignment problems involve assigning jobs to machines, people to tasks, sales
personnel to sales territories, contracts to bidders and so on. A distinguishing
feature of the assignment problem is that one person is assigned to one and only
one task. Specifically, we look for the set of assignments that will optimize a stated
objective, such as minimize cost, minimize time or maximize profit.
To illustrate the assignment problem, let us consider the case of Fowle Marketing
Research, which has just received requests for market research studies from three
new clients. The company faces the task of assigning a project leader (agent) to each
client (task). Currently, three individuals are available for the project leader assign-
ments. Fowle’s management realizes, however, that the time required to complete
each study will depend on the experience and ability of the project leader assigned.
The three projects have approximately the same priority, and the company wants to
assign project leaders to minimize the total number of days required to complete all
three projects. If a project leader is to be assigned to one client only, what assign-
D. F. Votaw and Alex ments should be made?
Orden presented their To answer the assignment question, Fowle’s management must first consider all
paper ‘The personnel possible project leader–client assignments and then estimate the corresponding
assignment problem’ at a
symposium in project completion times. With three project leaders and three clients, nine assign-
Washington DC in 1957 ment alternatives are possible. The alternatives and the estimated project comple-
considered to be the first tion times in days are summarized in Table 7.22.
Mathematical
Programming Figure 7.4 shows the network representation of Fowle’s assignment problem. The
Symposium. nodes correspond to the project leaders and clients, and the arcs represent the
possible assignments of project leaders to clients. The supply at each origin node
and the demand at each destination node are 1; the cost of assigning a project leader
to a client is the time it takes that project leader to complete the client’s task. Note

Table 7.22 Estimated Project Completion Times (Days) for the Fowle Marketing
Research Assignment Problem
Client

Project Leader 1 2 3
1. Terry 10 15 9
2. Karl 9 18 5
3. Mustafa 6 14 3

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.