Lesson 7: Maximum assignments and more than one optimum

A 5×55 \times 5 problem with two optimal assignments

SkillsMinimum assignment (Hungarian)Steps of the Hungarian algorithm

Worked example

  • Complex unfamiliar

A florist has five drivers — Amir (AA), Bree (BB), Cole (CC), Dee (DD) and Eli (EE) — and five delivery routes. The table shows the time in minutes each driver takes on each route.

12345A81611918B16791218C1818111112D66798E4961018\begin{array}{c|ccccc} & 1 & 2 & 3 & 4 & 5 \\ \hline A & 8 & 16 & 11 & 9 & 18 \\ B & 16 & 7 & 9 & 12 & 18 \\ C & 18 & 18 & 11 & 11 & 12 \\ D & 6 & 6 & 7 & 9 & 8 \\ E & 4 & 9 & 6 & 10 & 18 \end{array}

The florist says, "Eli lives near route 1 and Bree near route 2, so they should take those; the rest doesn't matter much." Find every optimal allocation and the minimum total time, and comment on the florist's statement.

1 of 8 steps
  1. Step 1: Row reduction

    Subtract 8, 7, 11, 6 and 4:

    12345A083110B902511C77001D00132E052614\begin{array}{c|ccccc} & 1 & 2 & 3 & 4 & 5 \\ \hline A & 0 & 8 & 3 & 1 & 10 \\ B & 9 & 0 & 2 & 5 & 11 \\ C & 7 & 7 & 0 & 0 & 1 \\ D & 0 & 0 & 1 & 3 & 2 \\ E & 0 & 5 & 2 & 6 & 14 \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. Run the algorithm until nn lines are needed.

  2. Make the forced choices (rows or columns with one available zero).

  3. Try each remaining choice; every complete assignment of zeros is optimal.

Watch out for

  • Reporting only one of the two allocations when the question asks for all of them.

  • Assuming a forced-looking choice is unique without checking the other zeros.

Save your progress with a free account