Finding the Reduced Cost Matrix

Given a matrix representing the costs of a having each worker performing a task, we can find the minimum total cost of having each worker perform just one of the tasks so that the total cost of performing all the tasks is minimized by first finding the reduced cost matrix.

To reduce the cost matrix:

1. Subtract the least value in each row from each element of that row.

2. Using the new matrix, subtract the least value in each column from each element in that column.

For example, suppose we have the cost matrix below.

The smallest numbers in the first, second, third and fourth rows are 13, 11, 15 and 33 respectively.

Subtract 13 from every element in the first row.

Subtract 11 from every element in the second row.

Subtract 15 from every element in the third row.

Subtract 33 from every element in the fourth row.

We then have the matrix below.

The smallest numbers in the first, second, third and fourth columns are 0, 0, 10 and 4 respectively.

Subtract 0 from every element in the first column.

Subtract 0 from every element in the second column.

Subtract 10 from every element in the third column.

Subtract4 from every element in the fourth column.

We then have the reduced cost matrix below.