Page 326 -

306 CHAPTER 7 TRANSPORTATION, ASSIGNMENT AND TRANSSHIPMENT PROBLEMS

Table 7.23 Optimal Project Leader Assignments for the Fowle Marketing
Research Problem
Project Leader Assigned Client Days

Terry 2 15
Karl 3 5
Mustafa 1 6
Total 26

problem parallel those for the transportation problem. Specifically, we can handle
the following:
1 total number of people (supply) not equal to the total number of tasks (demand);
2 a maximization objective function;
3 unacceptable assignments.
The situation in which the number of people does not equal the number of tasks is analo-
gous to total supply not equalling total demand in a transportation problem. If the
number of people exceeds the number of tasks, the extra people simply remain unas-
signed in the linear programming model. If the number of tasks exceeds the number of
people, the linear programming model will not have a feasible solution. In this situation,
a simple modification is to add enough dummy people to equalize the number of people
and the number of tasks. For instance, in the Fowle problem we might have had five
clients (tasks) and only three project leaders. By adding two dummy project leaders, we
can create a new assignment problem with the number of project leaders equal to the
number of clients. The objective function coefficients for the assignment of dummy
project leaders would be zero so that the value of the optimal solution would represent
the total number of days required by the assignments actually made (no assignments will
actually be made to the clients receiving dummy project leaders).
If the assignment alternatives are evaluated in terms of revenue or profit rather
than time or cost, the linear programming formulation can be solved as a max-
imization rather than a minimization problem. In addition, if one or more assign-
ments are unacceptable, the corresponding decision variable can be removed from
the linear programming formulation. This scenario could happen, for example, if
one person did not have the experience necessary for one or more of the tasks.

A General Linear Programming Model of the Assignment Problem
The general assignment problem involves m people and n tasks. If we let x ij ¼ 1or0
according to whether person i is assigned to task j, and if c ij denotes the cost of
assigning person i to task j, we can write the general assignment model as:
X X
n
m
Min c ij x ij
i¼1 j¼1
s:t:
X
n
x ij 1 i ¼ 1; 2; .. . ; m People
j¼1
X
m
x ij ¼ 1 j ¼ 1; 2; .. . ; n Tasks
i¼1
x ij 0 for all i and j

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.