Lesson 7: Maximum assignments and more than one optimum
A problem with two optimal assignments
SkillsMinimum assignment (Hungarian)Steps of the Hungarian algorithm
Worked example
A florist has five drivers — Amir (), Bree (), Cole (), Dee () and Eli () — and five delivery routes. The table shows the time in minutes each driver takes on each route.
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.
Step 1: Row reduction
Subtract 8, 7, 11, 6 and 4:
Step 2: Column reduction
Only column 5 lacks a zero; subtract its smallest entry, 1:
Step 3: Cover the zeros
Columns 1 and 2 and row cover every zero: 3 lines, fewer than 5.
Step 4: Adjust
The smallest uncovered entry is 1 ( and and ). Subtract 1 from the uncovered entries and add 1 at the crossings and :
Step 5: Cover again
5 lines are now needed, so an optimal assignment exists.
Step 6: Make the forced choices
has only one zero: – 1. has only one zero: – 2. 's zeros are in columns 1 and 4; column 1 is taken, so – 4.
Step 7: Try every remaining choice
and are left with routes 3 and 5, and both have zeros in both. So either – 3, – 5 or – 5, – 3.
Both choices use only zeros, so both are optimal.
Step 8: Total from the original table
First: . Second: . Both give 39 minutes.
Answer
There are two optimal allocations, each totalling 39 minutes: – 4, – 2, – 3, – 5, – 1, or – 4, – 2, – 5, – 3, – 1. The florist is right that Eli should take route 1 and Bree route 2 — both are in every optimal allocation — but wrong that the rest doesn't matter: Amir must take route 4, and Cole and Dee must share routes 3 and 5.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Run the algorithm until lines are needed.
Make the forced choices (rows or columns with one available zero).
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.