Solution

We shall apply the Hungarain method to the following matrix, which is the cost matrix for the problem.

$\left[ \begin{array}{rrrr} 90 & 75 & 75 & 80 \\ 35 & 85 & 55 & 65 \\ 125 & 95 & 90 & 105 \\ 45 & 110 & 95 & 115 \end{array}\right]$

Step 1

Subtract 75 from the first row of the matrix, subtract 35 from its second row , subtract 90 rowm its third row , and subtract 45 from its frouth row to obtain the following matrix.

$\left[ \begin{array}{rrrr} 15 & 0 & 0 & 5 \\ 0 & 50 & 20 & 30 \\ 35 & 5 & 0 & 15 \\ 0 & 65 & 50 & 70 \end{array}\right]$

Step 2

The fist three columns of the previous matrix already contain zero entries: threfore, we need only subtract 5 from its fourth column. The result is......

$\left[ \begin{array}{rrrr} 15 & 0 & 0 & 0 \\ 0 & 50 & 20 & 25 \\ 0 & 50 & 20 & 30 \\ 35 & 5 & 0 & 10 \\ 0 & 65 & 50 & 75 \end{array}\right]$

Step 3

Cover the zero entries with a minimum number of vertical and horizontal lines. This may be done by first trying to cover the zeros with one line, then tow, and finally with three. The indicated covering is not unique.

Step 4

Because the minimum nimber of lines used un Step 3 is three, an optimal assignment of zeros is not yet possible.

Step 5

Subtract 20, the smalles uncovered entry of the matrix, from each ofits uncovered entries and add it tio the two entries covered twice with lines. The result is the following matrix *******

Step 6

Cover the zero entries of the matirx with a minimum number of vertical and horizonal lines. ******

Step 7

Because the minimum number of lines is still three, an optimal assignment of zeros is not yet possible.

Step 8

Subtract5, the smalles uncovered entry of the matrx, from each of its uncovered entries and add it to the entries covered twice with lines. The result is the following matrix..... *****

Step 9

Cover the zero entries with a minimum number of vertical and horizontal lines.

Step 10

Because the zero entries of the matrix cannot be covered with fewer than four lines, it must contain an optimal assignment of zeros.

By trial and error, we can find the following two optimal assignment of zeros.