Lesson 7: Maximum assignments and more than one optimum

A maximum assignment for sales regions

SkillMaximum assignment

Worked example

  • 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}
1 of 7 steps
  1. Step 1: Convert to a minimum problem

    The largest entry is 24. Subtract every entry from 24:

    1234A92614B3419C7904D1101216\begin{array}{c|cccc} & 1 & 2 & 3 & 4 \\ \hline A & 9 & 2 & 6 & 14 \\ B & 3 & 4 & 1 & 9 \\ C & 7 & 9 & 0 & 4 \\ D & 11 & 0 & 12 & 16 \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. 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.

Save your progress with a free account