Page 330 -

310 CHAPTER 7 TRANSPORTATION, ASSIGNMENT AND TRANSSHIPMENT PROBLEMS

Step 3. Subtract the value of the smallest unlined element from every unlined
element, and add this same value to every element at the intersection of
two lines. All other elements remain unchanged. Return to step 2, and
continue until the minimum number of lines necessary to cover all the
zeros in the matrix is equal to the number of rows.
The minimum unlined element is 2. In the preceding matrix we circled this element.
Subtracting 2 from all unlined elements and adding 2 to the intersection element for
Terry and client 3 produces the new matrix:

1 2 3
Terry 0 0 2
Karl 1 5 0
Mustafa 0 3 0

Returning to step 2, we find that the minimum number of straight lines required to
cover all the zeros in the current matrix is 3. The following matrix illustrates the step
2 calculations.

1 2 3
Terry 0 0 2 Three lines must be drawn to cover all zeros; therefore,
Karl 1 5 0 the optimal solution has been reached (the number of
Mustafa 0 3 0 lines is the same as the number of rows)

According to step 2, then, it must be possible to find an assignment with a value of
zero. To do so we first locate any row or column that contains only one zero. If all
have more than one zero, we choose the row or column with the fewest zeros. We
draw a square around a zero in the chosen row or column, indicating an assignment,
and eliminate that row and column from further consideration. Row 2 has only one
zero in the Fowle problem, so we assign Karl to client 3 and eliminate row 2 and
column 3 from further consideration. Mustafa must then be assigned to client 1 (the
only remaining zero in row 3) and, finally, Terry to client 2. The solution to the
Fowle problem, in terms of the reduced matrix, requires a time expenditure of zero
days, as follows:

1 2 3

Terry 0 ¤ 0 2
Karl 1 5 ¤ 0
Mustafa ¤ 0 3 0

We obtain the value of the optimal assignment by referring to the original
assignment problem and summing the solution times associated with the

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.