Page 325 -

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

The constraints for the assignment problem reflect the conditions that each project
leader can be assigned to at most one client and that each client must have one
assigned project leader. These constraints are written as follows:

Because the number of x 11 þ x 12 þ x 13 1 Terry’s assignment
project leaders equals the x 21 þ x 22 þ x 23 1 Karl’s assignment
number of clients, all the
constraints could be x 31 þ x 32 þ x 33 1 Mustafa’s assignment
written as equalities. But x 11 þ x 21 þ x 31 ¼ 1 Client 1
when the number of
project leaders exceeds x 12 þ x 22 þ x 32 ¼ 1 Client 2
the number of clients, x 13 þ x 23 þ x 33 ¼ 1 Client 3
less-than-or-equal-to
constraints must be used Note that one constraint matches up with each node in Figure 7.4.
for the project leader
constraints. Combining the objective function and constraints into one model provides the
following nine-variable, six-constraint linear programming model of the Fowle Mar-
keting Research assignment problem.

Min 10x 11 þ 15x 12 þ 9x 13 þ 9x 21 þ 18x 22 þ 5x 23 þ 6x 31 þ 14x 32 þ 3x 33
s:t:
x 11 þ x 12 þ x 13 1
x 21 þ x 22 þ x 23 1
x 31 þ x 32 þ x 33 1
¼ 1
x 11 þ x 21 þ x 31
x 12 þ x 22 þ x 32 ¼ 1
x 13 þ x 23 þ x 33 ¼ 1
x ij 0 for i ¼ 1; 2; 3; j ¼ 1; 2; 3

Can you formulate and Figure 7.5 shows the computer solution for this model. Terry is assigned to client
solve a linear
programming model for 2(x 12 ¼ 1), Karl is assigned to client 3 (x 23 ¼ 1) and Mustafa is assigned to client 1
an assignment problem? (x 31 ¼ 1). The total completion time required is 26 days. This solution is summar-
Try part (b) of Problem 9. ized in Table 7.23.

Problem Variations

Because the assignment problem can be viewed as a special case of the trans-
portation problem, the problem variations that may arise in an assignment

Figure 7.5 The Excel Solution for the Fowle Marketing Research Assignment Problem
Objective Function Value = 26.000

Variable Value Reduced Costs
-------------- --------------- -----------------
EXCEL file X11 0.000 0.000
X12 1.000 0.000
FOWLE X13 0.000 3.000
X21 0.000 0.000
X22 0.000 4.000
X23 1.000 0.000
X31 1.000 0.000
X32 0.000 3.000
X33 0.000 1.000

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.