Question 15.SP.1: King Finance Corporation, headquartered in New York, wants t...

a) The cost table has a fourth column to represent New York. To “balance” the problem, we add a “dummy” row (person) with a zero relocation cost to each city.

b) Subtract the smallest number in each row and cover all zeros (column subtraction of each column’s zero will give the same numbers and therefore is not necessary). See Figure 15.SP.1a.

c) Only 2 lines cover, so subtract the smallest uncovered number (200) from all uncovered numbers, and add it to each square where two lines intersect. Then cover all zeros. See Figure 15.SP.1b.

d) Only 3 lines cover, so subtract the smallest uncovered number (100) from all uncovered numbers, and add it to each square where two lines intersect. Then cover all zeros. See Figure 15.SP.1c.

e) Still only 3 lines cover, so subtract the smallest uncovered number (100) from all uncovered numbers, add it to squares where two lines intersect, and cover all zeros. See Figure 15.SP.1d.

f) Because it takes four lines to cover all zeros, an optimal assignment can be made at zero squares. We assign:
Wilson to Omaha
Jones to Miami
Dummy (no one) to Dallas
Smith to New York
Cost = $500 + $1,100 + $0 + $800
= $2,400