5.

4 Assignment model 201

TABLE 5.31 Assignment Model

Jobs
1 2 ... n

1 c11 c12 ... c1n 1

2 c21 c22 ... c2n 1
Worker
o o o o o o
N cn1 cn2 ... c 1
1 1 ... 1

The assignment model is a special case of the transportation model, where the
workers represent origins and jobs represent destinations. The offer
(demand) at each origin (destination) is equal to 1. The cost of 'transporting' the worker
workijIn fact, the assignment model can be solved directly.
as a transport model (or as a regular PL). However, the fact
that the supply and demand are equal to 1 leads to the development of an algorithm of
simple solution called Hungarian method. Although the new solution method appears
it is totally foreign to the transport model, in reality the algorithm has its origin
in the simplex method, just like the transportation model.

5.4.1 Hungarian method8

We will use two examples to present the mechanics of the new algorithm. The si-
The following section provides an explanation of the procedure based on the simplex method.

Example 5.4-1
Joe Klyne's three children, John, Karen, and Terri, want to earn some money for their expenses.
Mr. Klyne chose three tasks for his children: to mow the lawn, to paint the door of the
garage and wash the family cars. To avoid early competition among the heirs
he asks them to submit individual (secret) bids for what they consider a payment

TABLE 5.32 Mr. Klyne's assignment problem

To trim To paint Wash

John $15 $10 $9

Karen $9 $15 $10
Terri $10 $12 $8

8Like with the transportation method, the classical Hungarian method (designed mainly for calculations
Annuals) is something of the past, and is presented here for historical reasons. Currently, that type is not required.
of calculations, since the problem can be solved using highly efficient PL computer codes
clients. Perhaps the benefit of studying these classical techniques is that they are based on a complex theory.
which reduces the solution steps to simple rules suitable for manual calculations.

[Link]
202 Chapter 5 Transport model and its variants

TABLE 5.33 Application of the Hungarian method to the assignment problem from example 5.4-1

Step 1: Step 2:

Podar To paint Wash Minimum queue. Podar To paint To wash

John 15 10 9 p1ϭ 9 John 6 1 0

Karen 9 15 10 p2ϭ 9 Q Karen 0 6 1 Q
Terri 10 12 8 p3ϭ 8 Terri 2 4 0

Max column. q1ϭ 0 q2ϭ 1 q3ϭ 0

Step 3:

Podar Paint Wash

John 6 0 0
Karen 0 5 1
Terri 2 3 0

just for each of the three tasks. Table 5.32 summarizes the bids received. The children re-
they will weigh their father's decision regarding the assignment of the tasks.
The assignment problem will be solved by the Hungarian method.

Step 1. Determinei, the minimum cost element in the row of the original cost matrix, and
remove it from all the elements of the row, i51, 2, 3.
Step 2. For the matrix created in step 1, determinej, the minimum cost element of the
column, and subtract it from all the elements of the column, j51, 2, 3.
Step 3. Based on the matrix from step 2, try to determine a feasible assignment between
all resulting zero entries.
3a. If that allocation can be found, it is optimal.
3b. Otherwise, more calculations are required (as explained in example 5.4-2).

Table 5.33 demonstrates the application of the two steps to the current problem.
The cells with underlined zero entries in step 3 give the optimal (feasible) solution: John
Karen gets the job of painting, Karen gets the job of mowing the lawn, and Terri gets the job of washing the cars.
vials of the family. The total cost for Mr. Klyne is $918,185. This amount always
it will be the same (p11p21p3)1(q11q21q3)5(91918)1(01110)5$27. (A justification
this result is given in the following section.)

As indicated in step 3 of the Hungarian method, the zeros created by the steps
1 and 2 may not provide a feasible solution directly. In this case, they are needed
more steps to determine the optimal (feasible) allocation. The following example of-
show this situation.

Example 5.4-2
Suppose that the situation analyzed in example 5.4-1 is expanded to four children and four tasks.
Table 5.34 summarizes the cost elements of the problem.

[Link]
 5.4 Allocation model 203

TABLE 5.34 Allocation Model

Task
1 2 3 4

1 $1 $4 $6 $3
2 $9 $7 $10 $9
Child
3 $4 $5 $11 $7
4 $8 $7 $8 $5

TABLE 5.35 Reduced assignment matrix

Task
1 2 3 4

1 0 3 2 2
2 2 0 0 2
Child
3 0 1 4 3
4 3 2 0 0

The application of steps 1 and 2 to the matrix of table 5.34 (withp151,p257,p354,p45

5,q150,q250,q353 yq450) gives as a result the reduced matrix of table 5.35 (check it out.
beautiful!)
The zero entry locations do not allow for unique tasks to be assigned to all the children.
For example, if we assign child 1 task 1, then column 1 will be removed, and child three will not.
it will have a zero entry in the other three columns. This obstacle can be overcome by adding-
Proceed to the next step in the procedure given in example 5.4-1:
Step 3b. If feasible zero element assignments cannot be found,
(i) Trace or eliminate horizontal and vertical lines in the last reduced matrix.
to cover all entries zero.
(ii) Select the minimum uncovered entry and subtract it from each uncovered entry.
and then add it to each entry at the intersection of two lines.
(iii) If it cannot determine a feasible allocation among the zero entries result-
yes, repeat step 3a.
The application of step 3b to the last matrix produces the shaded cells in table 5.36.
The unshaded minimum input (shown underlined) is equal to 1. This input is added.
to the intersection cell and is subtracted from the remaining shaded cells to produce the matrix of
table 5.37, and the optimal solution indicated by the underlined zeros.

TABLE 5.36 Application of step 3b

Task
1 2 3 4

1 0 3 2 2
2 2 0 0 2
Child
3 0 1 4 3
4 3 2 0 0

[Link]
204 Chapter 5 Transport model and its variations

TABLE 5.37 Optimal Assignment

Task
1 2 3 4

1 0 2 1 1
2 3 0 0 2
Child
3 0 0 3 2
4 4 2 0 0

Moment of AMPL.
The file [Link] provides the AMPL model for the assignment model. The mo-
the work is similar to that of the transport model.

SET OF PROBLEMS 5.4A

1. Solve the assignment models of table 5.38.
Solve them using the Hungarian method.
(b) Experiment with TORA. Express the problem as a LP and solve it with TORA.
(c) Experiment with TORA. Use TORA to solve the problem as a model.
of transport.
(d) Experiment with Solver. Modify the file [Link] to solve the problem.
(e) Experiment with AMPL. Modify the file [Link] to solve the
problem.
2. JoShop needs to assign 4 jobs to 4 workers. The cost of carrying out a job is a
function of workers' skills. Table 5.39 summarizes the cost of the assignments.
Worker 1 cannot perform job 3, and worker 3 cannot perform
Task 4. Determine the optimal assignment using the Hungarian method.

TABLE 5.38 Data from problem 1

(i) (ii)

$3 $8 $2 $10 $3 $3 $9 $2 $2 $7
$6 $5 $2 $7 $5 $6 $1 $5 $6 $6
$6 $4 $2 $7 $5 $9 $4 $7 $10 $3
$8 $4 $2 $3 $5 $2 $5 $4 $2 $1
$7 $8 $6 $7 $7 $9 $6 $2 $4 $6

TABLE 5.39 Data from problem 2

Work
1 2 3 4

1 $50 $50 — $20

2 $70 $40 $20 $30
Worker
3 $90 $30 $50 —
4 $70 $20 $60 $70

[Link]