Lesson 7 of 7 · 18 min
Maximum assignments and more than one optimum
Find the allocation with the largest total by converting a maximum problem into a minimum one, and find every optimal assignment when there is more than one.
What you will be able to do
- Convert a maximum assignment problem into a minimum one by subtracting every entry from the largest entry.
- Apply the Hungarian algorithm to find a maximum assignment and its total.
- Find all the optimal assignments when the final matrix allows more than one.
Not every allocation problem is about saving time or money. A sales manager assigning four reps to four regions wants the largest total sales; a coach choosing who swims which leg might be maximising points. The Hungarian algorithm only knows how to find a minimum — so turn the maximum problem into a minimum problem first.
Key idea
Maximum problems
Subtract every entry from the largest entry in the table. Each new entry measures how far that pairing falls short of the best possible, so making the total shortfall as small as possible makes the original total as large as possible.
Then apply the Hungarian algorithm for a minimum, and total the assignment from the original table.
Why subtracting from the largest works — and why not just make the numbers negative?
If is the largest entry, each new entry is . Any complete assignment of an table uses entries, so its new total is . That is smallest exactly when the original total is largest.
Multiplying every entry by also turns a maximum into a minimum, and after row reduction it gives exactly the same matrix. Queensland textbooks and most worked solutions subtract from the largest entry, because every number stays a whole number of 0 or more and the working is easier to follow. That is the method used here.
Worked example
A maximum assignment for sales regions
A company has four sales representatives — Alex (), Bella (), Chen () and Dina () — for four regions. The table shows each rep's expected weekly sales in a region, in thousands of dollars. Use the Hungarian algorithm to allocate one region to each rep so that total expected sales are as large as possible.
Step 1: Convert to a minimum problem
The largest entry is 24. Subtract every entry from 24:
Each new entry is how far that pairing falls short of 24, so the smallest total shortfall gives the largest total sales.
Step 2: Row reduction
Subtract 2, 1, 0 and 0:
Step 3: Column reduction
Subtract 2 from column 1 and 4 from column 4:
Step 4: Cover the zeros
Rows and and column 2 cover every zero: 3 lines, fewer than 4, so adjust.
Step 5: Adjust
The smallest uncovered entry is 4 (at ). Subtract 4 from the uncovered entries (rows and , columns 1, 3 and 4) and add 4 at the crossings and :
Step 6: Assign
4 lines are now needed. has one zero: – 2. then takes 3 (its other zero). 's zeros are in columns 1 and 3, so – 1, and – 4.
Step 7: Total from the original table
, that is $83 000 per week.
Try it yourself first, then check the working one step at a time.
Answer
Alex – Region 3, Bella – Region 1, Chen – Region 4, Dina – Region 2, for maximum expected sales of $83 000 per week.
Method
Subtract every entry from the largest entry.
Apply the Hungarian algorithm for a minimum.
Total the assignment from the original table.
Watch out for
Totalling the converted table (which gives the total shortfall, not the sales).
Forgetting to convert: minimising the sales table itself finds the smallest total, $57 000.
A coach wants the largest total score. Write the matrix you would give to the Hungarian algorithm for a minimum.
Expected weekly sales (thousands of dollars) for four reps in four regions. The first step converts the table; the rest is the usual algorithm. Switch to "minimise" to compare the answers.
Common mistake
Minimising a maximum problem
Running the algorithm on the original sales table finds the allocation with the smallest sales — here $57 000 instead of $83 000. Read the question for words like profit, sales, score or points, and convert first.
Sometimes the zeros of the final matrix allow more than one complete assignment. Every one of them has the same total — the optimal total — so each is an optimal assignment. That is why the syllabus says "assignment/s". When a question asks for the optimal assignment, find them all.
Worked example
A problem with two optimal assignments
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.
Try it yourself first, then check the working one step at a time.
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.
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.
This is the final matrix of a Hungarian algorithm (3 lines are needed to cover the zeros). How many optimal assignments are there?
Tip
Inspection works for maximums too
For a maximum problem, listing all 6 allocations and choosing the largest total is often quickest, and no conversion is needed. Use the Hungarian algorithm when the table is or larger, or when the question asks for it.
Exam tip
For a maximum problem, write one line saying what you did and why: "Subtract each entry from the largest entry, 24, so that minimising the new table maximises sales." Then give the allocation and the total from the original table, with units.
Summary
For a maximum, subtract every entry from the largest entry, then minimise with the Hungarian algorithm.
Total the final assignment from the original table, not the converted one.
If the final zeros allow several complete assignments, they are all optimal and have the same total.
Find every optimal assignment by starting from rows or columns with only one zero, then trying each remaining choice.
Small maximum problems can be done by inspection: list every allocation and choose the largest.
Finished the lesson?
Try the 2 quick checks above and the lesson completes itself, or mark it complete now.