Lesson 6: The Hungarian algorithm for a minimum

A 3×33 \times 3 Hungarian algorithm with no adjustment

SkillsMinimum assignment (Hungarian)Steps of the Hungarian algorithm

Worked example

  • Simple familiar

Three couriers, AA, BB and CC, can each cover one of three suburbs. The table gives the delivery time in minutes. Use the Hungarian algorithm to find the allocation with the least total time.

123A13104B5107C91112\begin{array}{c|ccc} & 1 & 2 & 3 \\ \hline A & 13 & 10 & 4 \\ B & 5 & 10 & 7 \\ C & 9 & 11 & 12 \end{array}
1 of 5 steps
  1. Step 1: Row reduction

    Subtract each row's smallest entry (4, 5 and 9):

    123A960B052C023\begin{array}{c|ccc} & 1 & 2 & 3 \\ \hline A & 9 & 6 & 0 \\ B & 0 & 5 & 2 \\ C & 0 & 2 & 3 \end{array}

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. Row reduce, then column reduce.

  2. Cover the zeros with the fewest lines; nn lines means assign.

  3. Assign one zero per row and column, and total from the original table.

Watch out for

  • Skipping column reduction: after row reduction, column 2 has no zero, and you can't complete an assignment from the zeros.

Save your progress with a free account