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 LL is the largest entry, each new entry is L−xL - x. Any complete assignment of an n×nn \times n table uses nn entries, so its new total is nL−(original total)nL - (\text{original total}). That is smallest exactly when the original total is largest.

Multiplying every entry by −1-1 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

  • Complex familiar

A company has four sales representatives — Alex (AA), Bella (BB), Chen (CC) and Dina (DD) — 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.

1234A15221810B21202315C17152420D1324128\begin{array}{c|cccc} & 1 & 2 & 3 & 4 \\ \hline A & 15 & 22 & 18 & 10 \\ B & 21 & 20 & 23 & 15 \\ C & 17 & 15 & 24 & 20 \\ D & 13 & 24 & 12 & 8 \end{array}
7 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Subtract every entry from the largest entry.

  2. Apply the Hungarian algorithm for a minimum.

  3. 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.

[8597106498]\begin{bmatrix} 8 & 5 & 9 \\ 7 & 10 & 6 \\ 4 & 9 & 8 \end{bmatrix}
Interactive

A maximum assignment, step by step

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 5×55 \times 5 problem with two optimal assignments

  • 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.

8 steps

Try it yourself first, then check the working one step at a time.

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.

This is the final matrix of a Hungarian algorithm (3 lines are needed to cover the zeros). How many optimal assignments are there?

123P002Q001R310\begin{array}{c|ccc} & 1 & 2 & 3 \\ \hline P & 0 & 0 & 2 \\ Q & 0 & 0 & 1 \\ R & 3 & 1 & 0 \end{array}
Choose one answer

Tip

Inspection works for maximums too

For a 3×33 \times 3 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 4×44 \times 4 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.

Lesson 7 of 70% read

Save your progress with a free account